Clippy-suggested edits
[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 Player {
13     pub energy: u16,
14     pub health: u8
15 }
16
17 #[derive(Debug, Clone, PartialEq, Eq)]
18 pub struct BitwiseGameState {
19     pub status: GameStatus,
20     pub player: Player,
21     pub opponent: Player,
22     pub player_buildings: PlayerBuildings,
23     pub opponent_buildings: PlayerBuildings,
24 }
25
26 #[derive(Debug, Clone, PartialEq, Eq)]
27 pub struct PlayerBuildings {
28     pub unconstructed: ArrayVec<[UnconstructedBuilding; MAX_CONCURRENT_CONSTRUCTION]>,
29     pub buildings: [u64; DEFENCE_HEALTH],
30     pub occupied: u64,
31     
32     pub energy_towers: u64,
33
34     pub missile_towers: [u64; MISSILE_COOLDOWN_STATES],
35     pub firing_tower: usize,
36     
37     pub missiles: [(u64, u64); MISSILE_MAX_SINGLE_CELL],
38     pub tesla_cooldowns: ArrayVec<[TeslaCooldown; TESLA_MAX]>
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, &mut self.player_buildings, player_command);
59         BitwiseGameState::perform_command(&mut self.opponent, &mut self.opponent_buildings, opponent_command);
60
61         BitwiseGameState::update_construction(&mut self.player_buildings);
62         BitwiseGameState::update_construction(&mut self.opponent_buildings);
63         
64         BitwiseGameState::fire_teslas(&mut self.player, &mut self.player_buildings, &mut self.opponent, &mut self.opponent_buildings);
65
66         BitwiseGameState::add_missiles(&mut self.player_buildings);
67         BitwiseGameState::add_missiles(&mut self.opponent_buildings);
68
69         BitwiseGameState::move_and_collide_missiles(&mut self.player, &mut self.player_buildings, &mut self.opponent_buildings.missiles);
70         BitwiseGameState::move_and_collide_missiles(&mut self.opponent, &mut self.opponent_buildings, &mut self.player_buildings.missiles);
71
72         BitwiseGameState::add_energy(&mut self.player, &mut self.player_buildings);
73         BitwiseGameState::add_energy(&mut self.opponent, &mut self.opponent_buildings);
74
75         self.update_status();
76         self.status
77     }
78
79     pub fn player(&self) -> &Player { &self.player }
80     pub fn opponent(&self) -> &Player { &self.opponent }
81     pub fn player_has_max_teslas(&self) -> bool { self.player_buildings.count_teslas() >= TESLA_MAX }
82     pub fn opponent_has_max_teslas(&self) -> bool { self.opponent_buildings.count_teslas() >= TESLA_MAX }
83
84     pub fn unoccupied_player_cell_count(&self) -> usize { self.player_buildings.occupied.count_zeros() as usize }
85     pub fn unoccupied_opponent_cell_count(&self) -> usize { self.opponent_buildings.occupied.count_zeros() as usize }
86     pub fn location_of_unoccupied_player_cell(&self, i: usize) -> Point  {
87         let bit = find_bit_index_from_rank(self.player_buildings.occupied, i as u64);
88         let point = Point { index: bit };
89         debug_assert!(point.to_either_bitfield() & self.player_buildings.occupied == 0);
90         point
91     }
92     pub fn location_of_unoccupied_opponent_cell(&self, i: usize) -> Point {
93         let bit = find_bit_index_from_rank(self.opponent_buildings.occupied, i as u64);
94         let point = Point { index: bit };
95         debug_assert!(point.to_either_bitfield() & self.opponent_buildings.occupied == 0);
96         point
97     }
98 }
99
100 fn find_bit_index_from_rank(occupied: u64, i: u64) -> u8 {
101     // Adapted from https://graphics.stanford.edu/~seander/bithacks.html#SelectPosFromMSBRank
102     let v = !occupied;
103     
104     let mut r = u64::from(v.count_ones()) - i;
105
106     let a: u64 =  v - ((v >> 1) & (!0u64/3));
107     let b: u64 = (a & (!0u64/5)) + ((a >> 2) & (!0u64/5));
108     let c: u64 = (b + (b >> 4)) & (!0u64/0x11);
109     let d: u64 = (c + (c >> 8)) & (!0u64/0x101);
110     let mut t: u64 = (d >> 32) + (d >> 48);
111
112     let mut s: u64 = 64;
113     s -= (t.wrapping_sub(r) & 256) >> 3; r -= t & (t.wrapping_sub(r) >> 8);
114     t  = (d >> (s - 16)) & 0xff;
115     s -= (t.wrapping_sub(r) & 256) >> 4; r -= t & (t.wrapping_sub(r) >> 8);
116     t  = (c >> (s - 8)) & 0xf;
117     s -= (t.wrapping_sub(r) & 256) >> 5; r -= t & (t.wrapping_sub(r) >> 8);
118     t  = (b >> (s - 4)) & 0x7;
119     s -= (t.wrapping_sub(r) & 256) >> 6; r -= t & (t.wrapping_sub(r) >> 8);
120     t  = (a >> (s - 2)) & 0x3;
121     s -= (t.wrapping_sub(r) & 256) >> 7; r -= t & (t.wrapping_sub(r) >> 8);
122     t  = (v >> (s - 1)) & 0x1;
123     s -= (t.wrapping_sub(r) & 256) >> 8;
124     s = 65 - s;
125
126     64 - s as u8
127 }
128
129 impl BitwiseGameState {
130     pub fn new(
131         player: Player, opponent: Player,
132         player_buildings: PlayerBuildings, opponent_buildings: PlayerBuildings
133     ) -> BitwiseGameState {
134         BitwiseGameState {
135             status: GameStatus::Continue,
136             player, opponent,
137             player_buildings, opponent_buildings
138         }
139     }
140
141     /**
142      * Like with the expressive, this is to make things more
143      * comparable when writing tests, not for actual use in the
144      * engine.
145      */
146     #[cfg(debug_assertions)]
147     pub fn sort(&mut self) {
148         for i in 0..MISSILE_MAX_SINGLE_CELL {
149             for j in i+1..MISSILE_MAX_SINGLE_CELL {
150                 let move_down1 = !self.player_buildings.missiles[i].0 & self.player_buildings.missiles[j].0;
151                 self.player_buildings.missiles[i].0 |= move_down1;
152                 self.player_buildings.missiles[j].0 &= !move_down1;
153
154                 let move_down2 = !self.player_buildings.missiles[i].1 & self.player_buildings.missiles[j].1;
155                 self.player_buildings.missiles[i].1 |= move_down2;
156                 self.player_buildings.missiles[j].1 &= !move_down2;
157
158                 let move_down3 = !self.opponent_buildings.missiles[i].0 & self.opponent_buildings.missiles[j].0;
159                 self.opponent_buildings.missiles[i].0 |= move_down3;
160                 self.opponent_buildings.missiles[j].0 &= !move_down3;
161
162                 let move_down4 = !self.opponent_buildings.missiles[i].1 & self.opponent_buildings.missiles[j].1;
163                 self.opponent_buildings.missiles[i].1 |= move_down4;
164                 self.opponent_buildings.missiles[j].1 &= !move_down4;
165             }
166         }
167
168         self.player_buildings.unconstructed.sort_by_key(|b| b.pos);
169         self.opponent_buildings.unconstructed.sort_by_key(|b| b.pos);
170
171         self.player_buildings.tesla_cooldowns.sort_by_key(|b| b.pos);
172         self.opponent_buildings.tesla_cooldowns.sort_by_key(|b| b.pos);
173
174
175         while self.player_buildings.firing_tower > 0 {
176             self.player_buildings.firing_tower -= 1;
177             let zero = self.player_buildings.missile_towers[0];
178             for i in 1..self.player_buildings.missile_towers.len() {
179                 self.player_buildings.missile_towers[i-1] = self.player_buildings.missile_towers[i];
180             }
181             let end = self.player_buildings.missile_towers.len()-1;
182             self.player_buildings.missile_towers[end] = zero;
183         }
184         while self.opponent_buildings.firing_tower > 0 {
185             self.opponent_buildings.firing_tower -= 1;
186             let zero = self.opponent_buildings.missile_towers[0];
187             for i in 1..self.opponent_buildings.missile_towers.len() {
188                 self.opponent_buildings.missile_towers[i-1] = self.opponent_buildings.missile_towers[i];
189             }
190             let end = self.opponent_buildings.missile_towers.len()-1;
191             self.opponent_buildings.missile_towers[end] = zero;
192         }
193     }
194
195     #[cfg(debug_assertions)]
196     pub fn sorted(&self) -> BitwiseGameState {
197         let mut res = self.clone();
198         res.sort();
199         res
200     }
201
202     fn perform_command(player: &mut Player, player_buildings: &mut PlayerBuildings, command: Command) {
203         match command {
204             Command::Nothing => {},
205             Command::Build(p, b) => {
206                 let bitfield = p.to_either_bitfield();
207
208                 let price = match b {
209                     BuildingType::Attack => MISSILE_PRICE,
210                     BuildingType::Defence => DEFENCE_PRICE,
211                     BuildingType::Energy => ENERGY_PRICE,
212                     BuildingType::Tesla => TESLA_PRICE,
213                 };
214                 let construction_time = match b {
215                     BuildingType::Attack => MISSILE_CONSTRUCTION_TIME,
216                     BuildingType::Defence => DEFENCE_CONSTRUCTION_TIME,
217                     BuildingType::Energy => ENERGY_CONSTRUCTION_TIME,
218                     BuildingType::Tesla => TESLA_CONSTRUCTION_TIME,
219                 };
220
221                 // This is used internally. I should not be making
222                 // invalid moves!
223                 debug_assert!(player_buildings.buildings[0] & bitfield == 0);
224                 debug_assert!(p.x() < FULL_MAP_WIDTH && p.y() < MAP_HEIGHT);
225                 debug_assert!(player.energy >= price);
226                 debug_assert!(b != BuildingType::Tesla ||
227                               player_buildings.count_teslas() < TESLA_MAX);
228
229                 player.energy -= price;
230                 player_buildings.unconstructed.push(UnconstructedBuilding {
231                     pos: p,
232                     construction_time_left: construction_time,
233                     building_type: b
234                 });
235                 player_buildings.occupied |= bitfield;
236             },
237             Command::Deconstruct(p) => {
238                 let unconstructed_to_remove_index = player_buildings.unconstructed.iter().position(|ref b| b.pos == p);
239                 let deconstruct_mask = !(p.to_either_bitfield() & player_buildings.buildings[0]);
240                 
241                 debug_assert!(deconstruct_mask != 0 || unconstructed_to_remove_index.is_some());
242                 
243                 if let Some(i) = unconstructed_to_remove_index {
244                     player_buildings.unconstructed.swap_remove(i);
245                 }
246                 
247                 player.energy += DECONSTRUCT_ENERGY;
248                 
249                 for tier in 0..player_buildings.buildings.len() {
250                     player_buildings.buildings[tier] &= deconstruct_mask;
251                 }
252                 player_buildings.energy_towers &= deconstruct_mask;
253                 for tier in 0..player_buildings.missile_towers.len() {
254                     player_buildings.missile_towers[tier] &= deconstruct_mask;
255                 }
256                 player_buildings.tesla_cooldowns.retain(|t| t.pos != p);
257                 player_buildings.occupied &= deconstruct_mask;
258             }
259         }
260     }
261
262     fn update_construction(player_buildings: &mut PlayerBuildings) {
263         let mut buildings_len = player_buildings.unconstructed.len();
264         for i in (0..buildings_len).rev() {
265             if player_buildings.unconstructed[i].construction_time_left == 0 {
266                 let building_type = player_buildings.unconstructed[i].building_type;
267                 let health = if building_type == BuildingType::Defence { DEFENCE_HEALTH } else { 1 };
268                 
269                 let pos = player_buildings.unconstructed[i].pos;
270                 let bitfield = pos.to_either_bitfield();
271                 
272                 for health_tier in 0..health {
273                     player_buildings.buildings[health_tier] |= bitfield;
274                 }
275                 if building_type == BuildingType::Energy {
276                     player_buildings.energy_towers |= bitfield;
277                 }
278                 if building_type == BuildingType::Attack {
279                     player_buildings.missile_towers[player_buildings.firing_tower] |= bitfield;
280                 }
281                 if building_type == BuildingType::Tesla {
282                     player_buildings.tesla_cooldowns.push(TeslaCooldown { 
283                         pos,
284                         cooldown: 0,
285                         age: 0
286                     });
287                 }
288                 
289                 buildings_len -= 1;
290                 player_buildings.unconstructed.swap(i, buildings_len);
291             } else {
292                 player_buildings.unconstructed[i].construction_time_left -= 1
293             }
294         }
295         player_buildings.unconstructed.truncate(buildings_len);
296     }
297
298     fn fire_teslas(player: &mut Player, player_buildings: &mut PlayerBuildings, opponent: &mut Player, opponent_buildings: &mut PlayerBuildings) {
299         BitwiseGameState::fire_single_players_teslas_without_cleanup(player, player_buildings, opponent, opponent_buildings);
300         BitwiseGameState::fire_single_players_teslas_without_cleanup(opponent, opponent_buildings, player, player_buildings);
301
302         BitwiseGameState::update_tesla_activity(player_buildings);
303         BitwiseGameState::update_tesla_activity(opponent_buildings);
304     }
305
306     fn fire_single_players_teslas_without_cleanup(player: &mut Player, player_buildings: &mut PlayerBuildings, opponent: &mut Player, opponent_buildings: &mut PlayerBuildings) {
307         player_buildings.tesla_cooldowns.sort_unstable_by(|a, b| b.age.cmp(&a.age));
308         for tesla in player_buildings.tesla_cooldowns.iter_mut() {
309             tesla.age += 1;
310             if tesla.cooldown > 0 {
311                 tesla.cooldown -= 1;
312             } else if player.energy >= TESLA_FIRING_ENERGY {
313                 player.energy -= TESLA_FIRING_ENERGY;
314                 tesla.cooldown = TESLA_COOLDOWN;
315
316                 if tesla.pos.to_either_bitfield() & RIGHT_COL_MASK != 0 {
317                     opponent.health = opponent.health.saturating_sub(TESLA_DAMAGE);
318                 }
319
320                 let x = tesla.pos.x();
321                 let y = tesla.pos.y();
322                 let missed_cells = (u32::from(SINGLE_MAP_WIDTH - x)).saturating_sub(2);
323                 
324                 let top_row = y.saturating_sub(1);
325                 let top_row_mask = 255u64 << (top_row * SINGLE_MAP_WIDTH);
326                 let mut destroy_mask = top_row_mask.wrapping_shl(missed_cells) & top_row_mask;
327
328                 let mut hits = 0;
329                 for _ in 0..(if y == 0 || y == MAP_HEIGHT-1 { 2 } else { 3 }) {
330                     hits |= destroy_mask & opponent_buildings.buildings[0];
331                     destroy_mask &= !hits;
332                     destroy_mask <<= SINGLE_MAP_WIDTH;
333                 }
334                 BitwiseGameState::destroy_buildings(opponent_buildings, hits);
335             }
336         }
337     }
338
339     fn add_missiles(player_buildings: &mut PlayerBuildings) {
340         let mut missiles = player_buildings.missile_towers[player_buildings.firing_tower];
341         for mut tier in &mut player_buildings.missiles {
342             let setting = !tier.0 & missiles;
343             tier.0 |= setting;
344             missiles &= !setting;
345         }
346         player_buildings.firing_tower = (player_buildings.firing_tower + 1) % MISSILE_COOLDOWN_STATES;
347     }
348
349     fn move_and_collide_missiles(opponent: &mut Player, opponent_buildings: &mut PlayerBuildings, player_missiles: &mut [(u64, u64); MISSILE_MAX_SINGLE_CELL]) {
350         let mut destroyed = 0;
351         let mut damaging = 0;
352         for _ in 0..MISSILE_SPEED {
353             for missile in player_missiles.iter_mut() {
354                 let swapping_sides = missile.0 & RIGHT_COL_MASK;
355                 let about_to_hit_opponent = missile.1 & LEFT_COL_MASK;
356
357                 missile.0 = (missile.0 & !RIGHT_COL_MASK) << 1;
358                 missile.1 = ((missile.1 & !LEFT_COL_MASK) >> 1) | swapping_sides;
359
360                 damaging = (damaging << 1) | about_to_hit_opponent;
361
362                 let mut hits = 0;
363                 for health_tier in (0..DEFENCE_HEALTH).rev() {
364                     hits = opponent_buildings.buildings[health_tier] & missile.1;
365                     missile.1 &= !hits;
366                     opponent_buildings.buildings[health_tier] &= !hits;
367                 }
368                 destroyed |= hits;
369             }
370         }
371         let damage = damaging.count_ones() as u8 * MISSILE_DAMAGE;
372         opponent.health = opponent.health.saturating_sub(damage);
373
374         BitwiseGameState::destroy_buildings(opponent_buildings, destroyed);
375         BitwiseGameState::update_tesla_activity(opponent_buildings);
376     }
377
378     fn destroy_buildings(buildings: &mut PlayerBuildings, hit_mask: u64) {
379         let deconstruct_mask = !hit_mask;
380         
381         buildings.energy_towers &= deconstruct_mask;
382         for tier in &mut buildings.missile_towers {
383             *tier &= deconstruct_mask;
384         }
385         for tier in &mut buildings.buildings {
386             *tier &= deconstruct_mask;
387         }
388         buildings.occupied &= deconstruct_mask;
389     }
390
391     fn update_tesla_activity(buildings: &mut PlayerBuildings) {
392         let occupied = buildings.occupied;
393         buildings.tesla_cooldowns.retain(|t| (t.pos.to_either_bitfield() & occupied) != 0);
394     }
395     
396     
397     fn add_energy(player: &mut Player, player_buildings: &mut PlayerBuildings) {
398         player.energy += player_buildings.energy_generated();
399     }
400
401     fn update_status(&mut self) {
402         let player_dead = self.player.health == 0;
403         let opponent_dead = self.opponent.health == 0;
404         self.status = match (player_dead, opponent_dead) {
405             (true, true) => GameStatus::Draw,
406             (false, true) => GameStatus::PlayerWon,
407             (true, false) => GameStatus::OpponentWon,
408             (false, false) => GameStatus::Continue,
409         };
410     }
411
412 }
413
414 impl PlayerBuildings {
415     pub fn count_teslas(&self) -> usize {
416         self.tesla_cooldowns.len()
417             + self.unconstructed.iter().filter(|t| t.building_type == BuildingType::Tesla).count()
418     }
419
420     pub fn empty() -> PlayerBuildings {
421         PlayerBuildings {
422             unconstructed: ArrayVec::new(),
423             buildings: [0; DEFENCE_HEALTH],
424             occupied: 0,
425             energy_towers: 0,
426             missile_towers: [0; MISSILE_COOLDOWN_STATES],
427             firing_tower: 0,
428             missiles: [(0,0); MISSILE_MAX_SINGLE_CELL],
429             tesla_cooldowns: ArrayVec::new()
430         }
431     }
432
433     pub fn energy_generated(&self) -> u16 {
434         ENERGY_GENERATED_BASE + self.energy_towers.count_ones() as u16 * ENERGY_GENERATED_TOWER
435     }
436 }