asterion_core/
maze.rs

1use crate::{
2    direction::Direction, game::POWER_UPS_PER_ROOM, minotaur::Minotaur, utils::convert_rgb_to_rgba,
3    Entity, IntoDirection, Position, View, MAX_MAZE_ID,
4};
5use anyhow::Result as AppResult;
6use image::{Rgb, Rgba, RgbaImage};
7use itertools::Itertools;
8use knossos::maze::{self, GrowingTree, Method};
9use rand::{
10    seq::{IndexedRandom, IteratorRandom},
11    RngExt, SeedableRng,
12};
13use rand_chacha::ChaCha8Rng;
14use std::collections::{HashMap, HashSet};
15
16#[derive(Debug, Clone, PartialEq)]
17pub struct Maze {
18    id: usize,
19    random_seed: u64,
20    rng: ChaCha8Rng,
21    width: usize,
22    height: usize,
23    wall_size: usize,
24    passage_size: usize,
25    image: RgbaImage,
26    valid_positions: HashSet<Position>,
27    entrance: Vec<Position>,
28    exit: Vec<Position>,
29    pub power_up_positions: Vec<Position>,
30    visible_positions_cache: HashMap<(Position, Direction, View), HashSet<Position>>, // (x, y, direction, type) -> visible positions
31    success_rate: (usize, usize), //pass/attempted
32}
33
34impl Maze {
35    const DEFAULT_WALL_SIZE: usize = 2;
36    const DEFAULT_PASSAGE_SIZE: usize = 2;
37    const MARGIN_SIZE: usize = 0;
38
39    fn insert_valid_position(&mut self, position: Position) {
40        self.valid_positions.insert(position);
41
42        let (x, y) = position;
43        self.image
44            .put_pixel(x as u32, y as u32, Self::background_color());
45    }
46
47    fn build_entrance(&mut self) {
48        let rng = &mut self.rng;
49
50        let entrance_y = rng.random_range(
51            Self::MARGIN_SIZE + self.wall_size
52                ..self.image.height() as usize - Self::MARGIN_SIZE - self.wall_size - 1,
53        ) / 2
54            * 2;
55        self.entrance = {
56            let starting_x = if self.id == 0 {
57                Self::MARGIN_SIZE + self.wall_size
58            } else {
59                0
60            };
61            let mut x = starting_x;
62            loop {
63                if self.is_valid_position((x, entrance_y))
64                    && self.is_valid_position((x, entrance_y + 1))
65                {
66                    break;
67                }
68
69                self.insert_valid_position((x, entrance_y));
70                self.insert_valid_position((x, entrance_y + 1));
71
72                x += 1;
73            }
74
75            vec![(starting_x, entrance_y), (starting_x, entrance_y + 1)]
76        };
77    }
78
79    fn build_exit(&mut self) {
80        let rng = &mut self.rng;
81
82        let exit_y = rng.random_range(
83            Self::MARGIN_SIZE + self.wall_size
84                ..self.image.height() as usize - Self::MARGIN_SIZE - self.wall_size - 1,
85        ) / 2
86            * 2;
87        self.exit = {
88            let max_x = self.image.width() as usize - Self::MARGIN_SIZE - 1;
89            let mut x = max_x;
90
91            loop {
92                if self.is_valid_position((x, exit_y)) && self.is_valid_position((x, exit_y + 1)) {
93                    break;
94                }
95
96                self.insert_valid_position((x, exit_y));
97                self.insert_valid_position((x, exit_y + 1));
98                x -= 1;
99            }
100
101            vec![(max_x, exit_y), (max_x, exit_y + 1)]
102        };
103    }
104
105    fn build_extra_rooms(&mut self) {
106        let rng = &mut self.rng;
107        // Add random rooms. The number of rooms deoends on the maze size.
108        let number_of_rooms = rng.random_range(4..=((self.width + self.height) / 2).max(5));
109        let mut new_valid_positions = Vec::new();
110        for _ in 0..number_of_rooms {
111            let room_width = rng.random_range(4..=((self.width + self.height) / 6).max(5));
112            let room_height = rng.random_range(4..=((self.width + self.height) / 6).max(5));
113
114            let room_x = rng.random_range(
115                Self::MARGIN_SIZE + self.wall_size
116                    ..self.image.width() as usize - room_width - Self::MARGIN_SIZE - self.wall_size,
117            );
118            let room_y = rng.random_range(
119                Self::MARGIN_SIZE + self.wall_size
120                    ..self.image.height() as usize
121                        - room_height
122                        - Self::MARGIN_SIZE
123                        - self.wall_size,
124            );
125
126            for y in room_y..room_y + room_height {
127                for x in room_x..room_x + room_width {
128                    new_valid_positions.push((x, y));
129                }
130            }
131        }
132
133        for &position in new_valid_positions.iter() {
134            self.insert_valid_position(position);
135        }
136    }
137
138    fn random_valid_position(&self) -> Position {
139        self.valid_positions
140            .iter()
141            .choose(&mut rand::rng())
142            .copied()
143            .unwrap()
144    }
145
146    fn set_power_ups_position(&mut self, amount: usize) {
147        self.power_up_positions = self
148            .valid_positions
149            .iter()
150            .filter(|&&position| {
151                self.entrance
152                    .iter()
153                    .all(|entrance| entrance.distance(position) > 6.0)
154                    && self.exit.iter().all(|exit| exit.distance(position) > 6.0)
155            })
156            .sample(&mut rand::rng(), amount)
157            .into_iter()
158            .copied()
159            .collect_vec();
160    }
161
162    fn color(id: usize) -> Rgba<u8> {
163        let a = (id.min(MAX_MAZE_ID) as f64) / MAX_MAZE_ID as f64;
164        // red = Rgba([208, 28, 28, 125]);
165        // whiteblueish = Rgba([210, 240, 255, 125]);
166
167        Rgba([
168            (a * 208.0 + (1.0 - a) * 210.0) as u8,
169            (a * 28.0 + (1.0 - a) * 240.0) as u8,
170            (a * 28.0 + (1.0 - a) * 255.0) as u8,
171            125,
172        ])
173    }
174
175    pub fn id(&self) -> usize {
176        self.id
177    }
178
179    pub fn background_color() -> Rgba<u8> {
180        Rgba([0; 4])
181    }
182
183    /// Sets a maze width and returns itself
184    pub const fn width(mut self, width: usize) -> Self {
185        self.width = width;
186        self
187    }
188
189    /// Sets a maze height and returns itself
190    pub const fn height(mut self, height: usize) -> Self {
191        self.height = height;
192        self
193    }
194
195    /// Sets a maze rng and returns itself
196    pub fn random_seed(mut self, random_seed: u64) -> Self {
197        self.rng = ChaCha8Rng::seed_from_u64(random_seed);
198        self
199    }
200
201    /// Sets a maze wall_size and returns itself
202    pub const fn wall_size(mut self, wall_size: usize) -> Self {
203        self.wall_size = wall_size;
204        self
205    }
206
207    /// Sets a maze passage_size and returns itself
208    pub const fn passage_size(mut self, passage_size: usize) -> Self {
209        self.passage_size = passage_size;
210        self
211    }
212
213    pub fn new(id: usize) -> Self {
214        // SeedableRng::from_os_rng was removed in rand 0.10; seed the maze RNG
215        // from the thread RNG instead, which itself seeds from the OS.
216        let mut rng = ChaCha8Rng::from_rng(&mut rand::rng());
217        let random_seed = rng.random();
218
219        log::debug!("new maze seed {random_seed}");
220        Self {
221            id,
222            random_seed,
223            rng,
224            width: 0,
225            height: 0,
226            wall_size: Self::DEFAULT_WALL_SIZE,
227            passage_size: Self::DEFAULT_PASSAGE_SIZE,
228            image: RgbaImage::new(0, 0),
229            valid_positions: HashSet::new(),
230            entrance: Vec::new(),
231            exit: Vec::new(),
232            power_up_positions: Vec::new(),
233            visible_positions_cache: HashMap::new(),
234            success_rate: (0, 0),
235        }
236    }
237
238    pub fn build(mut self) -> AppResult<Self> {
239        if self.width == 0 {
240            self.width = self
241                .rng
242                .random_range(16 + 2 * (self.id / 4)..=(20 + 2 * (self.id / 2)).min(32));
243        }
244
245        if self.height == 0 {
246            self.height = self
247                .rng
248                .random_range(4 + 2 * (self.id / 4)..=(6 + 2 * (self.id / 2)).min(20));
249        }
250
251        let Rgba([r, g, b, _]) = Self::color(self.id);
252        let Rgba([br, bg, bb, _]) = Self::background_color();
253
254        let knossos_maze = maze::OrthogonalMazeBuilder::new()
255            .width(self.width)
256            .height(self.height)
257            .algorithm(Box::new(GrowingTree::new(Method::Newest75Random25)))
258            .seed(Some(self.random_seed))
259            .build();
260
261        let maze_image_wrapper = knossos_maze.format(
262            maze::Image::new()
263                .wall(self.wall_size)
264                .passage(self.passage_size)
265                .margin(Self::MARGIN_SIZE)
266                .background(knossos::Color::RGB(br, bg, bb))
267                .foreground(knossos::Color::RGB(r, g, b)),
268        );
269
270        self.image = convert_rgb_to_rgba(&maze_image_wrapper.into_inner(), Rgb([0; 3]));
271
272        self.valid_positions = self
273            .image
274            .enumerate_pixels()
275            .filter(|(_, _, pixel)| pixel[3] == 0)
276            .map(|(x, y, _)| (x as usize, y as usize))
277            .collect();
278
279        self.build_entrance();
280        self.build_exit();
281        self.build_extra_rooms();
282        self.set_power_ups_position(POWER_UPS_PER_ROOM);
283
284        Ok(self)
285    }
286
287    pub fn spawn_minotaur(&mut self, name: String) -> Minotaur {
288        let mut position = self.random_valid_position();
289        while !self.is_valid_minotaur_position(position) {
290            position = self.random_valid_position()
291        }
292
293        let speed = (self.id as u64 / 3).min(6);
294        let aggression = (0.5 + 0.1 * (self.id / 2) as f64).min(1.0);
295        let vision = (4 + self.id / 3).min(7);
296        let minotaur = Minotaur::new(name, self.id, position, speed, vision, aggression);
297        self.get_and_cache_visible_positions(position, minotaur.direction(), minotaur.view());
298
299        minotaur
300    }
301
302    pub fn get_and_cache_visible_positions(
303        &mut self,
304        position: Position,
305        direction: Direction,
306        view: View,
307    ) -> HashSet<Position> {
308        let cache_key = (position, direction, view);
309        if let Some(visible_positions) = self.visible_positions_cache.get(&cache_key) {
310            return visible_positions.clone();
311        }
312
313        if view == View::Full {
314            let mut visible_positions = HashSet::new();
315            for &(x, y) in self.valid_positions.iter() {
316                visible_positions.insert((x, y));
317            }
318
319            self.visible_positions_cache
320                .insert(cache_key, visible_positions.clone());
321            return visible_positions;
322        }
323
324        let (x, y) = position;
325        let view_radius = view.radius();
326
327        let mut visible_positions = HashSet::new();
328        for dy in
329            y.saturating_sub(view_radius)..=(y + view_radius).min(self.image().height() as usize)
330        {
331            for dx in
332                x.saturating_sub(view_radius)..=(x + view_radius).min(self.image().width() as usize)
333            {
334                // Origin is always visible
335                if x == dx && y == dy {
336                    visible_positions.insert((dx, dy));
337                    continue;
338                }
339
340                if visible_positions.contains(&(dx, dy)) {
341                    continue;
342                }
343
344                // Position must be unobstructed by walls.
345                // We check this by drawing a line from the position to (x, y) and check that the positions on the line are valid positions.
346
347                // vertical line
348                if x == dx {
349                    let iter = if y < dy {
350                        (y..=dy).collect_vec()
351                    } else {
352                        (dy..=y).rev().collect_vec()
353                    };
354
355                    'inner: for ly in iter {
356                        // The wall visible as well.
357                        visible_positions.insert((x, ly));
358                        if !self.is_valid_position((x, ly)) {
359                            break 'inner;
360                        }
361                    }
362                }
363                //horizontal line
364                else if y == dy {
365                    let iter = if x < dx {
366                        (x..=dx).collect_vec()
367                    } else {
368                        (dx..=x).rev().collect_vec()
369                    };
370
371                    'inner: for lx in iter {
372                        // The wall visible as well.
373                        visible_positions.insert((lx, y));
374                        if !self.is_valid_position((lx, y)) {
375                            break 'inner;
376                        }
377                    }
378                }
379                // generic line
380                else {
381                    let mut line = bresenham_line((x as i32, y as i32), (dx as i32, dy as i32));
382
383                    if line[0] != (x, y) {
384                        line.reverse();
385                    };
386
387                    'inner: for index in 0..line.len() {
388                        let (lx, ly) = line[index];
389                        // The wall visible as well.
390                        visible_positions.insert((lx, ly));
391                        if !self.is_valid_position((lx, ly)) {
392                            break 'inner;
393                        }
394
395                        if index < line.len() - 1 {
396                            // Check if we are moving through a wall in a diagonal
397                            let (next_x, next_y) = line[index + 1];
398
399                            // 4 cases
400                            if next_x == lx + 1
401                                && next_y + 1 == ly
402                                && self.is_valid_position((next_x, next_y))
403                                && !self.is_valid_position((lx + 1, ly))
404                                && !self.is_valid_position((lx, ly - 1))
405                            {
406                                break 'inner;
407                            }
408
409                            if next_x == lx + 1
410                                && next_y == ly + 1
411                                && self.is_valid_position((next_x, next_y))
412                                && !self.is_valid_position((lx + 1, ly))
413                                && !self.is_valid_position((lx, ly + 1))
414                            {
415                                break 'inner;
416                            }
417
418                            if next_x + 1 == lx
419                                && next_y + 1 == ly
420                                && self.is_valid_position((next_x, next_y))
421                                && !self.is_valid_position((lx - 1, ly))
422                                && !self.is_valid_position((lx, ly - 1))
423                            {
424                                break 'inner;
425                            }
426
427                            if next_x + 1 == lx
428                                && next_y == ly + 1
429                                && self.is_valid_position((next_x, next_y))
430                                && !self.is_valid_position((lx - 1, ly))
431                                && !self.is_valid_position((lx, ly + 1))
432                            {
433                                break 'inner;
434                            }
435                        }
436                    }
437                }
438            }
439        }
440
441        // Filter out-of-bounds positions.
442        visible_positions = visible_positions
443            .iter()
444            .filter(|(x, y)| {
445                *x < self.image().width() as usize && *y < self.image().height() as usize
446            })
447            .map(|(x, y)| (*x, *y))
448            .collect();
449
450        // Limit view to relevant cone depending on the direction.
451        visible_positions = visible_positions
452            .iter()
453            .filter(|(x, y)| {
454                let dx = *x as i32 - position.0 as i32;
455                let dy = *y as i32 - position.1 as i32;
456                match view {
457                    View::Cone { .. } => match direction {
458                        Direction::North => dx >= dy && dx <= -dy,
459                        Direction::East => dy <= dx && dy >= -dx,
460                        Direction::South => dx <= dy && dx >= -dy,
461                        Direction::West => dy >= dx && dy <= -dx,
462                        Direction::NorthEast => dx >= 0 && dy <= 0,
463                        Direction::SouthEast => dx >= 0 && dy >= 0,
464                        Direction::SouthWest => dx <= 0 && dy >= 0,
465                        Direction::NorthWest => dx <= 0 && dy <= 0,
466                    },
467                    View::Plane { .. } => match direction {
468                        Direction::North => dy < 0,
469                        Direction::East => dx > 0,
470                        Direction::South => dy > 0,
471                        Direction::West => dx < 0,
472                        Direction::NorthEast => dx > dy,
473                        Direction::SouthEast => dx > -dy,
474                        Direction::SouthWest => dx < dy,
475                        Direction::NorthWest => dx < -dy,
476                    },
477                    View::Circle { .. } => true,
478                    _ => unreachable!(),
479                }
480            })
481            .map(|(x, y)| (*x, *y))
482            .collect();
483
484        self.visible_positions_cache
485            .insert(cache_key, visible_positions.clone());
486
487        visible_positions
488    }
489
490    pub fn get_cached_visible_positions(
491        &self,
492        position: Position,
493        direction: Direction,
494        view: View,
495    ) -> HashSet<Position> {
496        let cache_key = (position, direction, view);
497        self.visible_positions_cache
498            .get(&cache_key)
499            .expect("Visible positions should have been cached")
500            .clone()
501    }
502
503    pub fn image(&self) -> &RgbaImage {
504        &self.image
505    }
506
507    pub fn save_image(&self, name: &str) -> AppResult<()> {
508        self.image.save(name)?;
509        Ok(())
510    }
511
512    pub fn is_valid_position(&self, position: Position) -> bool {
513        self.valid_positions.contains(&position)
514    }
515
516    pub fn is_valid_minotaur_position(&self, position: Position) -> bool {
517        let entrances = self.entrance_positions();
518        self.valid_positions.contains(&position)
519            && entrances.iter().all(|p| p.distance(position) > 6.0)
520    }
521
522    pub fn is_entrance_position(&self, position: Position) -> bool {
523        self.entrance.contains(&position)
524    }
525
526    pub fn is_exit_position(&self, position: Position) -> bool {
527        self.exit.contains(&position)
528    }
529
530    pub fn entrance_positions(&self) -> &Vec<Position> {
531        &self.entrance
532    }
533
534    pub fn exit_positions(&self) -> &Vec<Position> {
535        &self.exit
536    }
537
538    pub fn hero_starting_position(&self) -> Position {
539        let rng = &mut rand::rng();
540        *self.entrance.choose(rng).unwrap()
541    }
542
543    pub fn increase_attempted(&mut self) {
544        self.success_rate.1 += 1;
545    }
546
547    pub fn decrease_attempted(&mut self) {
548        self.success_rate.1 -= 1;
549    }
550
551    pub fn increase_passed(&mut self) {
552        self.success_rate.0 += 1;
553    }
554
555    pub fn decrease_passed(&mut self) {
556        self.success_rate.0 -= 1;
557    }
558
559    pub fn success_rate(&self) -> f64 {
560        self.success_rate.0 as f64 / self.success_rate.1 as f64
561    }
562}
563
564// Returns the list of points from (x0, y0) to (x1, y1)
565fn bresenham_line(from: (i32, i32), to: (i32, i32)) -> Vec<Position> {
566    let mut result = Vec::new();
567
568    let (mut x0, mut y0) = from;
569    let (mut x1, mut y1) = to;
570
571    let steep = (y1 - y0).abs() > (x1 - x0).abs();
572    if steep {
573        (x0, y0) = (y0, x0);
574        (x1, y1) = (y1, x1);
575    }
576    if x0 > x1 {
577        (x0, x1) = (x1, x0);
578        (y0, y1) = (y1, y0);
579    }
580
581    let delta_x = x1 - x0;
582    let delta_y = (y1 - y0).abs();
583    let mut error = 0;
584    let ystep = if y0 < y1 { 1 } else { -1 };
585    let mut y = y0;
586
587    for x in x0..=x1 {
588        if steep {
589            result.push((y as usize, x as usize))
590        } else {
591            result.push((x as usize, y as usize))
592        }
593        error += delta_y;
594        if 2 * error >= delta_x {
595            y += ystep;
596            error -= delta_x;
597        }
598    }
599
600    result
601}
602
603#[cfg(test)]
604mod tests {
605    use super::Maze;
606    use crate::{game::MAX_MAZE_ID, AppResult};
607
608    #[test]
609    fn test_random_mazes_image() -> AppResult<()> {
610        for id in 0..MAX_MAZE_ID {
611            let maze = Maze::new(id);
612            let name = format!("images/random_{}.png", id);
613            maze.save_image(&name)?;
614        }
615
616        Ok(())
617    }
618}
asterion_core/maze.rs

asterion_core/
maze.rs
