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