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