##########################################################################################
########################################## INFO ##########################################
##########################################################################################
# This file is part of the PyRat library.
# It is meant to be used as a library, and not to be executed directly.
# Please import necessary elements using the following syntax:
# from pyrat import <element_name>
"""
This module provides a random maze with no holes, i.e., in which all cells of the grid are accessible.
Walls and mud are placed randomly.
It is also the base class of random mazes with holes, which only redefine how cells are added.
"""
##########################################################################################
######################################### IMPORTS ########################################
##########################################################################################
# External imports
import sys
import random
# PyRat imports
from pyrat.src.mazes.maze import Maze
from pyrat.src.game.exceptions import PyRatException
##########################################################################################
######################################### CLASSES ########################################
##########################################################################################
[docs]
class RandomMaze (Maze):
"""
*(This class inherits from* ``Maze`` *).*
A random maze is a maze that is created randomly.
All cells of the grid are accessible (there are no holes), and walls and mud are placed randomly.
You can specify the size of the maze, the density of walls and mud, and the range of the mud values.
You can also specify a random seed to reproduce the same maze later.
This class is also the base class of random mazes with holes (``BigHolesRandomMaze``, ``UniformHolesRandomMaze`` and ``HolesOnSideRandomMaze``).
They redefine the ``_add_cells(...)`` method, and receive an additional ``cell_percentage`` argument.
Since the maze is generated by the constructor of this class, the attributes they need to add cells must be set before calling it.
"""
##################################################################################
# CONSTRUCTOR #
##################################################################################
[docs]
def __init__ ( self,
wall_percentage: float,
mud_percentage: float,
mud_range: tuple[int, int] | None = None,
random_seed: int | None = None,
*args: object,
**kwargs: object
) -> None:
"""
Initializes a new instance of the class, and generates the maze.
Args:
wall_percentage: Percentage of walls to be present.
mud_percentage: Percentage of mud to be present.
mud_range: Range of the mud values (optional if mud_percentage = 0.0).
random_seed: Random seed for the maze generation, set to None for a random value.
args: Arguments to pass to the parent constructor (in particular, the width and height of the maze).
kwargs: Keyword arguments to pass to the parent constructor (in particular, the width and height of the maze).
"""
# Inherit from parent class
super().__init__(*args, **kwargs)
# Check validity
if not isinstance(wall_percentage, float):
raise PyRatException(f"Argument 'wall_percentage' must be a real number of type float (e.g., 50.0 rather than 50), got {wall_percentage!r} of type {type(wall_percentage).__name__}")
if not isinstance(mud_percentage, float):
raise PyRatException(f"Argument 'mud_percentage' must be a real number of type float (e.g., 50.0 rather than 50), got {mud_percentage!r} of type {type(mud_percentage).__name__}")
if not (0.0 <= wall_percentage <= 100.0):
raise PyRatException(f"Argument 'wall_percentage' must be a percentage between 0.0 and 100.0, got {wall_percentage!r}")
if not (0.0 <= mud_percentage <= 100.0):
raise PyRatException(f"Argument 'mud_percentage' must be a percentage between 0.0 and 100.0, got {mud_percentage!r}")
if not isinstance(mud_range, (type(None), tuple, list)):
raise PyRatException(f"Argument 'mud_range' must be a tuple, a list, or None, got {mud_range!r} of type {type(mud_range).__name__}")
if not (mud_range is None or len(mud_range) == 2):
raise PyRatException(f"Argument 'mud_range' must be a pair (min, max), got {mud_range!r} with {len(mud_range)} element(s)")
if not (random_seed is None or (isinstance(random_seed, int) and not isinstance(random_seed, bool))):
raise PyRatException(f"Argument 'random_seed' must be an integer or None, got {random_seed!r} of type {type(random_seed).__name__}")
if not (random_seed is None or 0 <= random_seed < sys.maxsize):
raise PyRatException(f"Argument 'random_seed' must be a non-negative integer lower than sys.maxsize, or None, got {random_seed!r}")
if not ((mud_percentage > 0.0 and mud_range is not None and len(mud_range) == 2) or mud_percentage == 0.0):
raise PyRatException(f"Argument 'mud_range' must be a pair (min, max) if 'mud_percentage' is not 0.0, got mud_range={mud_range!r} with mud_percentage={mud_percentage!r}")
if not (mud_range is None or isinstance(mud_range[0], int)):
raise PyRatException(f"Argument 'mud_range' must be a pair of integers, got {mud_range!r} (first element of type {type(mud_range[0]).__name__})")
if not (mud_range is None or isinstance(mud_range[1], int)):
raise PyRatException(f"Argument 'mud_range' must be a pair of integers, got {mud_range!r} (second element of type {type(mud_range[1]).__name__})")
if not (mud_range is None or 1 < mud_range[0] <= mud_range[1]):
raise PyRatException(f"Argument 'mud_range' must be a valid interval (min, max) with 2 <= min <= max, got {mud_range!r}")
# Protected attributes
self._wall_percentage = wall_percentage
self._mud_percentage = mud_percentage
self._mud_range = mud_range
self._random_seed = random_seed
self._rng = random.Random(self._random_seed)
# Generate the maze
self._create_maze()
##################################################################################
# PROTECTED METHODS #
##################################################################################
def _add_cells (self) -> None:
"""
This method adds cells to the maze.
Here, all cells of the grid are added, and connected to their neighbors (walls are added later).
Child classes can redefine it to create mazes with holes.
"""
# Add all cells
for row in range(self.get_height()):
for col in range(self.get_width()):
self.add_vertex(self.rc_to_i(row, col))
# Connect them
for row in range(self.get_height()):
for col in range(self.get_width()):
if row > 0:
self.add_edge(self.rc_to_i(row, col), self.rc_to_i(row - 1, col))
if col > 0:
self.add_edge(self.rc_to_i(row, col), self.rc_to_i(row, col - 1))
##################################################################################
def _add_mud (self) -> None:
"""
This method adds mud to the maze.
It replaces some edges with weighted ones.
"""
# Determine the number of mud edges
target_nb_mud = int(self.nb_edges() * self._mud_percentage / 100)
# Add mud to some edges
edges = self.get_edges()
self._rng.shuffle(edges)
for vertex, neighbor in edges[:target_nb_mud]:
self.remove_edge(vertex, neighbor, True)
weight = self._rng.randint(self._mud_range[0], self._mud_range[1])
self.add_edge(vertex, neighbor, weight)
##################################################################################
def _add_walls (self) -> None:
"""
This method adds walls to the maze.
It uses a random spanning tree to determine the maximum number of walls.
All edges have the same weight at this point, so this tree is also a minimum spanning tree.
"""
# Determine the maximum number of walls by computing a random spanning tree
mst = self.random_spanning_tree(self._rng.randint(0, sys.maxsize))
target_nb_walls = int((self.nb_edges() - mst.nb_edges()) * self._wall_percentage / 100)
walls = []
for vertex, neighbor in self.get_edges():
if not mst.has_edge(vertex, neighbor):
self.remove_edge(vertex, neighbor, True)
walls.append((vertex, neighbor))
# Remove some walls until the desired density is reached
self._rng.shuffle(walls)
for vertex, neighbor in walls[target_nb_walls:]:
self.add_edge(vertex, neighbor)
##################################################################################
def _create_maze (self) -> None:
"""
*(This method redefines the abstract method of the parent class with the same name).*
It creates a random maze using the parameters given at initialization.
It is called by the constructor.
"""
# Add cells, walls, and mud
self._add_cells()
self._add_walls()
self._add_mud()
##########################################################################################
##########################################################################################