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