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