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