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