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