db4ad9a2cd5f1c8fd24597c51eb2b8818a7681bd
[entelect-challenge-tower-defence.git] / src / engine / bitwise_engine.rs
1 use engine::command::{Command, BuildingType};
2 use engine::geometry::Point;
3 use engine::settings::{GameSettings};
4 use engine::constants::*;
5 use engine::{GameStatus, Player, GameState};
6
7 const LEFT_COL_MASK: u64 = 0x0101010101010101;
8 const RIGHT_COL_MASK: u64 = 0x8080808080808080;
9
10 #[derive(Debug, Clone, PartialEq, Eq)]
11 pub struct BitwiseGameState {
12     pub status: GameStatus,
13     pub player: Player,
14     pub opponent: Player,
15     pub player_buildings: PlayerBuildings,
16     pub opponent_buildings: PlayerBuildings,
17 }
18
19 #[derive(Debug, Clone, PartialEq, Eq)]
20 pub struct PlayerBuildings {
21     pub unconstructed: Vec<UnconstructedBuilding>,
22     pub buildings: [u64; DEFENCE_HEALTH],
23     pub occupied: u64,
24     
25     pub energy_towers: u64,
26     pub missile_towers: [u64; MISSILE_COOLDOWN+1],
27     
28     pub missiles: [(u64, u64); MISSILE_MAX_SINGLE_CELL],
29     pub tesla_cooldowns: [TeslaCooldown; TESLA_MAX]
30 }
31
32 #[derive(Debug, Clone, PartialEq, Eq)]
33 pub struct UnconstructedBuilding {
34     pub pos: Point,
35     pub construction_time_left: u8,
36     pub building_type: BuildingType
37 }
38
39 #[derive(Debug, Clone, Copy, PartialEq, Eq)]
40 pub struct TeslaCooldown {
41     pub active: bool,
42     pub pos: Point,
43     pub cooldown: u8
44 }
45
46
47 impl GameState for BitwiseGameState {
48     fn simulate(&mut self, settings: &GameSettings, player_command: Command, opponent_command: Command) -> GameStatus {
49         BitwiseGameState::perform_command(settings, &mut self.player, &mut self.player_buildings, player_command);      BitwiseGameState::perform_command(settings, &mut self.opponent, &mut self.opponent_buildings, opponent_command);
50
51         BitwiseGameState::update_construction(settings, &mut self.player_buildings);
52         BitwiseGameState::update_construction(settings, &mut self.opponent_buildings);
53         
54         BitwiseGameState::fire_teslas(&mut self.player, &mut self.player_buildings, &mut self.opponent, &mut self.opponent_buildings);
55
56         BitwiseGameState::add_left_missiles(&mut self.player_buildings);
57         BitwiseGameState::add_right_missiles(&mut self.opponent_buildings);
58
59         BitwiseGameState::move_left_and_collide_missiles(&mut self.player, &mut self.player_buildings, &mut self.opponent_buildings.missiles);
60         BitwiseGameState::move_right_and_collide_missiles(&mut self.opponent, &mut self.opponent_buildings, &mut self.player_buildings.missiles);
61
62         BitwiseGameState::add_energy(&mut self.player, &mut self.player_buildings);
63         BitwiseGameState::add_energy(&mut self.opponent, &mut self.opponent_buildings);
64
65         self.update_status();
66         self.status
67     }
68
69
70     fn player(&self) -> &Player { &self.player }
71     fn opponent(&self) -> &Player { &self.opponent }
72     fn player_has_max_teslas(&self) -> bool { self.player_buildings.count_teslas() >= TESLA_MAX }
73     fn opponent_has_max_teslas(&self) -> bool { self.opponent_buildings.count_teslas() >= TESLA_MAX }
74
75     fn unoccupied_player_cell_count(&self) -> usize { self.player_buildings.occupied.count_zeros() as usize }
76     fn unoccupied_opponent_cell_count(&self) -> usize { self.opponent_buildings.occupied.count_zeros() as usize }
77     fn location_of_unoccupied_player_cell(&self, i: usize) -> Point  {
78         let bit = find_bit_index_from_rank(self.player_buildings.occupied, i as u64);
79         let point = Point::new(bit%SINGLE_MAP_WIDTH, bit/SINGLE_MAP_WIDTH);
80         debug_assert!(point.to_either_bitfield() & self.player_buildings.occupied == 0);
81         point
82     }
83     fn location_of_unoccupied_opponent_cell(&self, i: usize) -> Point {
84         let bit = find_bit_index_from_rank(self.opponent_buildings.occupied, i as u64);
85         let point = Point::new(bit%SINGLE_MAP_WIDTH+SINGLE_MAP_WIDTH, bit/SINGLE_MAP_WIDTH);
86         debug_assert!(point.to_either_bitfield() & self.opponent_buildings.occupied == 0);
87         point
88     }
89 }
90
91 fn find_bit_index_from_rank(occupied: u64, i: u64) -> u8 {
92     // Adapted from https://graphics.stanford.edu/~seander/bithacks.html#SelectPosFromMSBRank
93     let v = !occupied;
94     
95     let mut r = v.count_ones() as u64 - i as u64;
96
97     let a: u64 =  v - ((v >> 1) & !0u64/3);
98     let b: u64 = (a & (!0u64/5)) + ((a >> 2) & (!0u64/5));
99     let c: u64 = (b + (b >> 4)) & (!0u64/0x11);
100     let d: u64 = (c + (c >> 8)) & (!0u64/0x101);
101     let mut t: u64 = (d >> 32) + (d >> 48);
102
103     let mut s: u64 = 64;
104     s -= (t.wrapping_sub(r) & 256) >> 3; r -= t & (t.wrapping_sub(r) >> 8);
105     t  = (d >> (s - 16)) & 0xff;
106     s -= (t.wrapping_sub(r) & 256) >> 4; r -= t & (t.wrapping_sub(r) >> 8);
107     t  = (c >> (s - 8)) & 0xf;
108     s -= (t.wrapping_sub(r) & 256) >> 5; r -= t & (t.wrapping_sub(r) >> 8);
109     t  = (b >> (s - 4)) & 0x7;
110     s -= (t.wrapping_sub(r) & 256) >> 6; r -= t & (t.wrapping_sub(r) >> 8);
111     t  = (a >> (s - 2)) & 0x3;
112     s -= (t.wrapping_sub(r) & 256) >> 7; r -= t & (t.wrapping_sub(r) >> 8);
113     t  = (v >> (s - 1)) & 0x1;
114     s -= (t.wrapping_sub(r) & 256) >> 8;
115     s = 65 - s;
116
117     let bit = 64 - s as u8;
118     bit
119 }
120
121 impl BitwiseGameState {
122     pub fn new(
123         player: Player, opponent: Player,
124         player_buildings: PlayerBuildings, opponent_buildings: PlayerBuildings
125     ) -> BitwiseGameState {
126         BitwiseGameState {
127             status: GameStatus::Continue,
128             player, opponent,
129             player_buildings, opponent_buildings
130         }
131     }
132
133     /**
134      * Like with the expressive, this is to make things more
135      * comparable when writing tests, not for actual use in the
136      * engine.
137      */
138     #[cfg(debug_assertions)]
139     pub fn sort(&mut self) {
140         for i in 0..MISSILE_MAX_SINGLE_CELL {
141             for j in i+1..MISSILE_MAX_SINGLE_CELL {
142                 let move_down1 = !self.player_buildings.missiles[i].0 & self.player_buildings.missiles[j].0;
143                 self.player_buildings.missiles[i].0 |= move_down1;
144                 self.player_buildings.missiles[j].0 &= !move_down1;
145
146                 let move_down2 = !self.player_buildings.missiles[i].1 & self.player_buildings.missiles[j].1;
147                 self.player_buildings.missiles[i].1 |= move_down2;
148                 self.player_buildings.missiles[j].1 &= !move_down2;
149
150                 let move_down3 = !self.opponent_buildings.missiles[i].0 & self.opponent_buildings.missiles[j].0;
151                 self.opponent_buildings.missiles[i].0 |= move_down3;
152                 self.opponent_buildings.missiles[j].0 &= !move_down3;
153
154                 let move_down4 = !self.opponent_buildings.missiles[i].1 & self.opponent_buildings.missiles[j].1;
155                 self.opponent_buildings.missiles[i].1 |= move_down4;
156                 self.opponent_buildings.missiles[j].1 &= !move_down4;
157             }
158         }
159
160         self.player_buildings.unconstructed.sort_by_key(|b| b.pos);
161         self.opponent_buildings.unconstructed.sort_by_key(|b| b.pos);
162
163         for tesla in self.player_buildings.tesla_cooldowns.iter_mut() {
164             if !tesla.active {
165                 tesla.pos = Point::new(0,0);
166                 tesla.cooldown = 0;
167             }
168         }
169         for tesla in self.opponent_buildings.tesla_cooldowns.iter_mut() {
170             if !tesla.active {
171                 tesla.pos = Point::new(0,0);
172                 tesla.cooldown = 0;
173             }
174         }
175
176         self.player_buildings.tesla_cooldowns.sort_by_key(|b| (!b.active, b.pos));
177         self.opponent_buildings.tesla_cooldowns.sort_by_key(|b| (!b.active, b.pos));
178     }
179
180     #[cfg(debug_assertions)]
181     pub fn sorted(&self) -> BitwiseGameState {
182         let mut res = self.clone();
183         res.sort();
184         res
185     }
186
187     fn perform_command(settings: &GameSettings, player: &mut Player, player_buildings: &mut PlayerBuildings, command: Command) {
188         match command {
189             Command::Nothing => {},
190             Command::Build(p, b) => {
191                 let blueprint = settings.building_settings(b);
192                 let bitfield = p.to_either_bitfield();
193
194                 // This is used internally. I should not be making
195                 // invalid moves!
196                 debug_assert!(player_buildings.buildings[0] & bitfield == 0);
197                 debug_assert!(p.x < settings.size.x && p.y < settings.size.y);
198                 debug_assert!(player.energy >= blueprint.price);
199                 debug_assert!(b != BuildingType::Tesla ||
200                               player_buildings.count_teslas() < TESLA_MAX);
201
202                 player.energy -= blueprint.price;
203                 player_buildings.unconstructed.push(UnconstructedBuilding {
204                     pos: p,
205                     construction_time_left: blueprint.construction_time,
206                     building_type: b
207                 });
208                 player_buildings.occupied |= bitfield;
209             },
210             Command::Deconstruct(p) => {
211                 let unconstructed_to_remove_index = player_buildings.unconstructed.iter().position(|ref b| b.pos == p);
212                 let deconstruct_mask = !(p.to_either_bitfield() & player_buildings.buildings[0]);
213                 
214                 debug_assert!(deconstruct_mask != 0 || unconstructed_to_remove_index.is_some());
215                 
216                 if let Some(i) = unconstructed_to_remove_index {
217                     player_buildings.unconstructed.swap_remove(i);
218                 }
219                 
220                 player.energy += DECONSTRUCT_ENERGY;
221                 
222                 for tier in 0..player_buildings.buildings.len() {
223                     player_buildings.buildings[tier] &= deconstruct_mask;
224                 }
225                 player_buildings.energy_towers &= deconstruct_mask;
226                 for tier in 0..player_buildings.missile_towers.len() {
227                     player_buildings.missile_towers[tier] &= deconstruct_mask;
228                 }
229                 for tesla in 0..player_buildings.tesla_cooldowns.len() {
230                     if player_buildings.tesla_cooldowns[tesla].pos == p {
231                         player_buildings.tesla_cooldowns[tesla].active = false;
232                     }
233                 }
234                 player_buildings.occupied &= deconstruct_mask;
235             }
236         }
237     }
238
239     fn update_construction(settings: &GameSettings, player_buildings: &mut PlayerBuildings) {
240         let mut buildings_len = player_buildings.unconstructed.len();
241         for i in (0..buildings_len).rev() {
242             if player_buildings.unconstructed[i].construction_time_left == 0 {
243                 //TODO: Avoid blueprint here?
244                 let building_type = player_buildings.unconstructed[i].building_type;
245                 let blueprint = settings.building_settings(building_type);
246                 
247                 let pos = player_buildings.unconstructed[i].pos;
248                 let bitfield = pos.to_either_bitfield();
249                 
250                 for health_tier in 0..DEFENCE_HEALTH as u8 {
251                     if blueprint.health > health_tier*MISSILE_DAMAGE {
252                         player_buildings.buildings[health_tier as usize] |= bitfield;
253                     }
254                 }
255                 if building_type == BuildingType::Energy {
256                     player_buildings.energy_towers |= bitfield;
257                 }
258                 if building_type == BuildingType::Attack {
259                     player_buildings.missile_towers[0] |= bitfield;
260                 }
261                 if building_type == BuildingType::Tesla {
262                     let ref mut tesla_cooldown = if player_buildings.tesla_cooldowns[0].active {
263                         &mut player_buildings.tesla_cooldowns[1]
264                     } else {
265                         &mut player_buildings.tesla_cooldowns[0]
266                     };
267                     tesla_cooldown.active = true;
268                     tesla_cooldown.pos = pos;
269                     tesla_cooldown.cooldown = 0;
270                 }
271                 
272                 buildings_len -= 1;
273                 player_buildings.unconstructed.swap(i, buildings_len);
274             } else {
275                 player_buildings.unconstructed[i].construction_time_left -= 1
276             }
277         }
278         player_buildings.unconstructed.truncate(buildings_len);
279     }
280
281     fn fire_teslas(player: &mut Player, player_buildings: &mut PlayerBuildings, opponent: &mut Player, opponent_buildings: &mut PlayerBuildings) {
282
283         #[cfg(debug_assertions)]
284         {
285             player_buildings.tesla_cooldowns.sort_by_key(|b| (!b.active, b.pos));
286             opponent_buildings.tesla_cooldowns.sort_by_key(|b| (!b.active, b.pos));
287         }
288
289         for tesla in player_buildings.tesla_cooldowns.iter_mut().filter(|t| t.active) {
290             if tesla.cooldown > 0 {
291                 tesla.cooldown -= 1;
292             } else if player.energy >= TESLA_FIRING_ENERGY {
293                 player.energy -= TESLA_FIRING_ENERGY;
294                 tesla.cooldown = TESLA_COOLDOWN;
295
296                 if tesla.pos.x + 1 >= SINGLE_MAP_WIDTH {
297                     opponent.health = opponent.health.saturating_sub(TESLA_DAMAGE);
298                 }
299
300                 let missed_cells = ((SINGLE_MAP_WIDTH - tesla.pos.x) as u32).saturating_sub(2);
301                 
302                 let top_row = if tesla.pos.y == 0 { 0 } else { tesla.pos.y - 1 };
303                 let top_row_mask = 255u64 << (top_row * SINGLE_MAP_WIDTH);
304                 let mut destroy_mask = top_row_mask.wrapping_shr(missed_cells) & top_row_mask;
305
306                 for _ in 0..(if tesla.pos.y == 0 || tesla.pos.y == MAP_HEIGHT-1 { 2 } else { 3 }) {
307                     let hits = destroy_mask & opponent_buildings.buildings[0];
308                     destroy_mask &= !hits;
309                     BitwiseGameState::destroy_buildings(opponent_buildings, hits);
310                     destroy_mask = destroy_mask << SINGLE_MAP_WIDTH;
311                 }
312             }
313         }
314
315         for tesla in opponent_buildings.tesla_cooldowns.iter_mut().filter(|t| t.active) {
316             if tesla.cooldown > 0 {
317                 tesla.cooldown -= 1;
318             } else if opponent.energy >= TESLA_FIRING_ENERGY {
319                 opponent.energy -= TESLA_FIRING_ENERGY;
320                 tesla.cooldown = TESLA_COOLDOWN;
321
322                 if tesla.pos.x <= SINGLE_MAP_WIDTH {
323                     player.health = player.health.saturating_sub(TESLA_DAMAGE);
324                 }
325
326                 let missed_cells = ((tesla.pos.x - SINGLE_MAP_WIDTH) as u32).saturating_sub(1);
327                 
328                 let top_row = if tesla.pos.y == 0 { 0 } else { tesla.pos.y - 1 };
329                 let top_row_mask = 255u64 << (top_row * SINGLE_MAP_WIDTH);
330                 let mut destroy_mask = top_row_mask.wrapping_shl(missed_cells) & top_row_mask;
331
332                 for _ in 0..(if tesla.pos.y == 0 || tesla.pos.y == MAP_HEIGHT-1 { 2 } else { 3 }) {
333                     let hits = destroy_mask & player_buildings.buildings[0];
334                     destroy_mask &= !hits;
335                     BitwiseGameState::destroy_buildings(player_buildings, hits);
336                     destroy_mask = destroy_mask << SINGLE_MAP_WIDTH;
337                 }                
338             }
339         }
340
341         BitwiseGameState::update_tesla_activity(player_buildings);
342         BitwiseGameState::update_tesla_activity(opponent_buildings);
343     }
344
345     fn add_left_missiles(player_buildings: &mut PlayerBuildings) {
346         let mut missiles = player_buildings.missile_towers[0];
347         for mut tier in player_buildings.missiles.iter_mut() {
348             let setting = !tier.0 & missiles;
349             tier.0 |= setting;
350             missiles &= !setting;
351         }
352
353         BitwiseGameState::rotate_missile_towers(player_buildings);
354     }
355
356     fn add_right_missiles(player_buildings: &mut PlayerBuildings) {
357         let mut missiles = player_buildings.missile_towers[0];
358         for mut tier in player_buildings.missiles.iter_mut() {
359             let setting = !tier.1 & missiles;
360             tier.1 |= setting;
361             missiles &= !setting;
362         }
363
364         BitwiseGameState::rotate_missile_towers(player_buildings);
365     }
366
367     //TODO: Add a pointer and stop rotating here
368     fn rotate_missile_towers(player_buildings: &mut PlayerBuildings) {
369         let zero = player_buildings.missile_towers[0];
370         for i in 1..player_buildings.missile_towers.len() {
371             player_buildings.missile_towers[i-1] = player_buildings.missile_towers[i];
372         }
373         let end = player_buildings.missile_towers.len()-1;
374         player_buildings.missile_towers[end] = zero;
375     }
376
377
378     //TODO: Can I rearrange my bitfields to make these two functions one thing?
379     fn move_left_and_collide_missiles(opponent: &mut Player, opponent_buildings: &mut PlayerBuildings, player_missiles: &mut [(u64, u64); MISSILE_MAX_SINGLE_CELL]) {
380         for _ in 0..MISSILE_SPEED {
381             for i in 0..MISSILE_MAX_SINGLE_CELL {
382                 let about_to_hit_opponent = player_missiles[i].0 & LEFT_COL_MASK;
383                 let damage = about_to_hit_opponent.count_ones() as u8 * MISSILE_DAMAGE;
384                 opponent.health = opponent.health.saturating_sub(damage);
385                 player_missiles[i].0 = (player_missiles[i].0 & !LEFT_COL_MASK) >> 1;
386
387                 let swapping_sides = player_missiles[i].1 & LEFT_COL_MASK;
388                 player_missiles[i].0 |= swapping_sides << (SINGLE_MAP_WIDTH-1);
389                 player_missiles[i].1 = (player_missiles[i].1 & !LEFT_COL_MASK) >> 1;
390
391
392                 let mut hits = 0;
393                 for health_tier in (0..DEFENCE_HEALTH).rev() {
394                     hits = opponent_buildings.buildings[health_tier] & player_missiles[i].0;
395                     player_missiles[i].0 &= !hits;
396                     opponent_buildings.buildings[health_tier] &= !hits;
397                 }
398
399                 BitwiseGameState::destroy_buildings(opponent_buildings, hits);
400                 BitwiseGameState::update_tesla_activity(opponent_buildings);
401             }
402         }
403     }
404
405     fn move_right_and_collide_missiles(opponent: &mut Player, opponent_buildings: &mut PlayerBuildings, player_missiles: &mut [(u64, u64); MISSILE_MAX_SINGLE_CELL]) {
406         for _ in 0..MISSILE_SPEED {
407             for i in 0..MISSILE_MAX_SINGLE_CELL {
408                 let about_to_hit_opponent = player_missiles[i].1 & RIGHT_COL_MASK;
409                 let damage = about_to_hit_opponent.count_ones() as u8 * MISSILE_DAMAGE;
410                 opponent.health = opponent.health.saturating_sub(damage);
411                 player_missiles[i].1 = (player_missiles[i].1 & !RIGHT_COL_MASK) << 1;
412
413                 let swapping_sides = player_missiles[i].0 & RIGHT_COL_MASK;
414                 player_missiles[i].1 |= swapping_sides >> (SINGLE_MAP_WIDTH-1);
415                 player_missiles[i].0 = (player_missiles[i].0 & !RIGHT_COL_MASK) << 1;
416
417                 
418                 let mut hits = 0;
419                 for health_tier in (0..DEFENCE_HEALTH).rev() {
420                     hits = opponent_buildings.buildings[health_tier] & player_missiles[i].1;
421                     player_missiles[i].1 &= !hits;
422                     opponent_buildings.buildings[health_tier] &= !hits;
423                 }
424
425                 BitwiseGameState::destroy_buildings(opponent_buildings, hits);
426                 BitwiseGameState::update_tesla_activity(opponent_buildings);
427             }
428         }
429     }
430
431     fn destroy_buildings(buildings: &mut PlayerBuildings, hit_mask: u64) {
432         let deconstruct_mask = !hit_mask;
433         
434         buildings.energy_towers &= deconstruct_mask;
435         for tier in buildings.missile_towers.iter_mut() {
436             *tier &= deconstruct_mask;
437         }
438         for tier in buildings.buildings.iter_mut() {
439             *tier &= deconstruct_mask;
440         }
441         buildings.occupied &= deconstruct_mask;
442     }
443
444     fn update_tesla_activity(buildings: &mut PlayerBuildings) {
445         for tesla in buildings.tesla_cooldowns.iter_mut().filter(|t| t.active) {
446             tesla.active = (tesla.pos.to_either_bitfield() & buildings.occupied) != 0;
447         }
448     }
449     
450     
451     fn add_energy(player: &mut Player, player_buildings: &mut PlayerBuildings) {
452         player.energy_generated = ENERGY_GENERATED_BASE + player_buildings.energy_towers.count_ones() as u16 * ENERGY_GENERATED_TOWER;
453         player.energy += player.energy_generated;
454     }
455
456     fn update_status(&mut self) {
457         let player_dead = self.player.health == 0;
458         let opponent_dead = self.opponent.health == 0;
459         self.status = match (player_dead, opponent_dead) {
460             (true, true) => GameStatus::Draw,
461             (false, true) => GameStatus::PlayerWon,
462             (true, false) => GameStatus::OpponentWon,
463             (false, false) => GameStatus::Continue,
464         };
465     }
466
467 }
468
469 impl PlayerBuildings {
470     pub fn count_teslas(&self) -> usize {
471         self.tesla_cooldowns.iter().filter(|t| t.active).count()
472             + self.unconstructed.iter().filter(|t| t.building_type == BuildingType::Tesla).count()
473     }
474
475     pub fn empty() -> PlayerBuildings {
476         PlayerBuildings {
477             unconstructed: Vec::with_capacity(4),
478             buildings: [0; DEFENCE_HEALTH],
479             occupied: 0,
480             energy_towers: 0,
481             missile_towers: [0; MISSILE_COOLDOWN+1],
482             missiles: [(0,0); MISSILE_MAX_SINGLE_CELL],
483             tesla_cooldowns: [TeslaCooldown::empty(); TESLA_MAX]
484         }
485     }
486 }
487
488 impl TeslaCooldown {
489     pub fn empty() -> TeslaCooldown {
490         TeslaCooldown {
491             active: false,
492             pos: Point::new(0,0),
493             cooldown: 0
494         }
495     }
496 }