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