pyrat.src.RandomMaze
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
1##################################################################################################################################################### 2######################################################################## INFO ####################################################################### 3##################################################################################################################################################### 4 5""" 6 This file is part of the PyRat library. 7 It is meant to be used as a library, and not to be executed directly. 8 Please import necessary elements using the following syntax: 9 from pyrat import <element_name> 10""" 11 12##################################################################################################################################################### 13###################################################################### IMPORTS ###################################################################### 14##################################################################################################################################################### 15 16# External imports 17from typing import * 18from typing_extensions import * 19from numbers import * 20import sys 21import random 22import abc 23 24# PyRat imports 25from pyrat.src.Maze import Maze 26 27##################################################################################################################################################### 28###################################################################### CLASSES ###################################################################### 29##################################################################################################################################################### 30 31class RandomMaze (Maze, abc.ABC): 32 33 """ 34 This class inherits from the Maze class. 35 Therefore, it has the attributes and methods defined in the Maze class in addition to the ones defined below. 36 37 This class is abstract and cannot be instantiated. 38 You should use one of the subclasses to create a maze, or create your own subclass. 39 40 A random maze is a maze that is created randomly. 41 You can specify the size of the maze, the density of cells, walls, and mud, and the range of the mud values. 42 You can also specify a random seed to reproduce the same maze later. 43 """ 44 45 ############################################################################################################################################# 46 # MAGIC METHODS # 47 ############################################################################################################################################# 48 49 def __init__ ( self: Self, 50 cell_percentage: Number, 51 wall_percentage: Number, 52 mud_percentage: Number, 53 mud_range: Optional[Tuple[Integral, Integral]] = None, 54 random_seed: Optional[Integral] = None, 55 *args: Any, 56 **kwargs: Any 57 ) -> Self: 58 59 """ 60 This function is the constructor of the class. 61 When an object is instantiated, this method is called to initialize the object. 62 This is where you should define the attributes of the object and set their initial values. 63 Arguments *args and **kwargs are used to pass arguments to the parent constructor. 64 This is useful not to declare again all the parent's attributes in the child class. 65 In: 66 * self: Reference to the current object. 67 * cell_percentage: Percentage of cells to be reachable. 68 * wall_percentage: Percentage of walls to be present. 69 * mud_percentage: Percentage of mud to be present. 70 * mud_range: Range of the mud values (optional if mud_percentage = 0.0). 71 * random_seed: Random seed for the maze generation, set to None for a random value. 72 * args: Arguments to pass to the parent constructor. 73 * kwargs: Keyword arguments to pass to the parent constructor. 74 Out: 75 * A new instance of the class. 76 """ 77 78 # Inherit from parent class 79 super().__init__(*args, **kwargs) 80 81 # Debug 82 assert isinstance(cell_percentage, Number) # Type check for cell_percentage 83 assert isinstance(wall_percentage, Number) # Type check for wall_percentage 84 assert isinstance(mud_percentage, Number) # Type check for mud_percentage 85 assert isinstance(mud_range, (type(None), tuple, list)) # Type check for mud_range 86 assert isinstance(random_seed, (Integral, type(None))) # Type check for random_seed 87 assert random_seed is None or 0 <= random_seed < sys.maxsize # random_seed is a valid seed 88 assert (mud_percentage > 0.0 and len(mud_range) == 2) or mud_percentage == 0.0 # Mud range is an interval of 2 elements 89 assert mud_range is None or isinstance(mud_range[0], Integral) # Type check for mud_range[0] 90 assert mud_range is None or isinstance(mud_range[1], Integral) # Type check for mud_range[1] 91 assert 0.0 <= cell_percentage <= 100.0 # cell_percentage is a percentage 92 assert 0.0 <= wall_percentage <= 100.0 # wall_percentage is a percentage 93 assert 0.0 <= mud_percentage <= 100.0 # mud_percentage is a percentage 94 assert mud_range is None or 1 < mud_range[0] <= mud_range[1] # mud_range is a valid interval with minimum value 1 95 assert int(self.width * self.height * cell_percentage / 100) > 1 # At least two vertices 96 97 # Protected attributes 98 self._target_nb_vertices = int(self.width * self.height * cell_percentage / 100) 99 self._wall_percentage = wall_percentage 100 self._mud_percentage = mud_percentage 101 self._mud_range = mud_range 102 self._random_seed = random_seed 103 self._rng = random.Random(self._random_seed) 104 105 ############################################################################################################################################# 106 # PROTECTED METHODS # 107 ############################################################################################################################################# 108 109 @override 110 def _create_maze ( self: Self, 111 ) -> None: 112 113 """ 114 This method redefines the abstract method of the parent class. 115 It creates a random maze using the parameters given at initialization. 116 It should be called by the constructor of the child classes. 117 In: 118 * self: Reference to the current object. 119 Out: 120 * None. 121 """ 122 123 # Add cells, walls, and mud 124 self._add_cells() 125 self._add_walls() 126 self._add_mud() 127 128 ############################################################################################################################################# 129 130 @abc.abstractmethod 131 def _add_cells ( self: Self, 132 ) -> None: 133 134 """ 135 This method is abstract and must be implemented in the subclasses. 136 It should add cells to the maze. 137 In: 138 * self: Reference to the current object. 139 Out: 140 * None. 141 """ 142 143 # This method must be implemented in the child classes 144 # By default we raise an error 145 raise NotImplementedError("This method must be implemented in the child classes.") 146 147 ############################################################################################################################################# 148 149 def _add_walls ( self: Self, 150 ) -> None: 151 152 """ 153 This method adds walls to the maze. 154 It uses the minimum spanning tree to determine the maximum number of walls. 155 In: 156 * self: Reference to the current object. 157 Out: 158 * None. 159 """ 160 161 # Determine the maximum number of walls by computing the minimum spanning tree 162 mst = self.minimum_spanning_tree(self._rng.randint(0, sys.maxsize)) 163 target_nb_walls = int((self.nb_edges - mst.nb_edges) * self._wall_percentage / 100) 164 walls = [] 165 for vertex, neighbor in self.edges: 166 if not mst.has_edge(vertex, neighbor): 167 self.remove_edge(vertex, neighbor, True) 168 walls.append((vertex, neighbor)) 169 170 # Remove some walls until the desired density is reached 171 self._rng.shuffle(walls) 172 for vertex, neighbor in walls[target_nb_walls:]: 173 self.add_edge(vertex, neighbor) 174 175 ############################################################################################################################################# 176 177 def _add_mud ( self: Self, 178 ) -> None: 179 180 """ 181 This method adds mud to the maze. 182 It replaces some edges with weighted ones. 183 In: 184 * self: Reference to the current object. 185 Out: 186 * None. 187 """ 188 189 # Determine the number of mud edges 190 target_nb_mud = int(self.nb_edges * self._mud_percentage / 100) 191 192 # Add mud to some edges 193 edges = self.edges 194 self._rng.shuffle(edges) 195 for vertex, neighbor in edges[:target_nb_mud]: 196 self.remove_edge(vertex, neighbor, True) 197 weight = self._rng.randint(self._mud_range[0], self._mud_range[1]) 198 self.add_edge(vertex, neighbor, weight) 199 200##################################################################################################################################################### 201#####################################################################################################################################################
32class RandomMaze (Maze, abc.ABC): 33 34 """ 35 This class inherits from the Maze class. 36 Therefore, it has the attributes and methods defined in the Maze class in addition to the ones defined below. 37 38 This class is abstract and cannot be instantiated. 39 You should use one of the subclasses to create a maze, or create your own subclass. 40 41 A random maze is a maze that is created randomly. 42 You can specify the size of the maze, the density of cells, walls, and mud, and the range of the mud values. 43 You can also specify a random seed to reproduce the same maze later. 44 """ 45 46 ############################################################################################################################################# 47 # MAGIC METHODS # 48 ############################################################################################################################################# 49 50 def __init__ ( self: Self, 51 cell_percentage: Number, 52 wall_percentage: Number, 53 mud_percentage: Number, 54 mud_range: Optional[Tuple[Integral, Integral]] = None, 55 random_seed: Optional[Integral] = None, 56 *args: Any, 57 **kwargs: Any 58 ) -> Self: 59 60 """ 61 This function is the constructor of the class. 62 When an object is instantiated, this method is called to initialize the object. 63 This is where you should define the attributes of the object and set their initial values. 64 Arguments *args and **kwargs are used to pass arguments to the parent constructor. 65 This is useful not to declare again all the parent's attributes in the child class. 66 In: 67 * self: Reference to the current object. 68 * cell_percentage: Percentage of cells to be reachable. 69 * wall_percentage: Percentage of walls to be present. 70 * mud_percentage: Percentage of mud to be present. 71 * mud_range: Range of the mud values (optional if mud_percentage = 0.0). 72 * random_seed: Random seed for the maze generation, set to None for a random value. 73 * args: Arguments to pass to the parent constructor. 74 * kwargs: Keyword arguments to pass to the parent constructor. 75 Out: 76 * A new instance of the class. 77 """ 78 79 # Inherit from parent class 80 super().__init__(*args, **kwargs) 81 82 # Debug 83 assert isinstance(cell_percentage, Number) # Type check for cell_percentage 84 assert isinstance(wall_percentage, Number) # Type check for wall_percentage 85 assert isinstance(mud_percentage, Number) # Type check for mud_percentage 86 assert isinstance(mud_range, (type(None), tuple, list)) # Type check for mud_range 87 assert isinstance(random_seed, (Integral, type(None))) # Type check for random_seed 88 assert random_seed is None or 0 <= random_seed < sys.maxsize # random_seed is a valid seed 89 assert (mud_percentage > 0.0 and len(mud_range) == 2) or mud_percentage == 0.0 # Mud range is an interval of 2 elements 90 assert mud_range is None or isinstance(mud_range[0], Integral) # Type check for mud_range[0] 91 assert mud_range is None or isinstance(mud_range[1], Integral) # Type check for mud_range[1] 92 assert 0.0 <= cell_percentage <= 100.0 # cell_percentage is a percentage 93 assert 0.0 <= wall_percentage <= 100.0 # wall_percentage is a percentage 94 assert 0.0 <= mud_percentage <= 100.0 # mud_percentage is a percentage 95 assert mud_range is None or 1 < mud_range[0] <= mud_range[1] # mud_range is a valid interval with minimum value 1 96 assert int(self.width * self.height * cell_percentage / 100) > 1 # At least two vertices 97 98 # Protected attributes 99 self._target_nb_vertices = int(self.width * self.height * cell_percentage / 100) 100 self._wall_percentage = wall_percentage 101 self._mud_percentage = mud_percentage 102 self._mud_range = mud_range 103 self._random_seed = random_seed 104 self._rng = random.Random(self._random_seed) 105 106 ############################################################################################################################################# 107 # PROTECTED METHODS # 108 ############################################################################################################################################# 109 110 @override 111 def _create_maze ( self: Self, 112 ) -> None: 113 114 """ 115 This method redefines the abstract method of the parent class. 116 It creates a random maze using the parameters given at initialization. 117 It should be called by the constructor of the child classes. 118 In: 119 * self: Reference to the current object. 120 Out: 121 * None. 122 """ 123 124 # Add cells, walls, and mud 125 self._add_cells() 126 self._add_walls() 127 self._add_mud() 128 129 ############################################################################################################################################# 130 131 @abc.abstractmethod 132 def _add_cells ( self: Self, 133 ) -> None: 134 135 """ 136 This method is abstract and must be implemented in the subclasses. 137 It should add cells to the maze. 138 In: 139 * self: Reference to the current object. 140 Out: 141 * None. 142 """ 143 144 # This method must be implemented in the child classes 145 # By default we raise an error 146 raise NotImplementedError("This method must be implemented in the child classes.") 147 148 ############################################################################################################################################# 149 150 def _add_walls ( self: Self, 151 ) -> None: 152 153 """ 154 This method adds walls to the maze. 155 It uses the minimum spanning tree to determine the maximum number of walls. 156 In: 157 * self: Reference to the current object. 158 Out: 159 * None. 160 """ 161 162 # Determine the maximum number of walls by computing the minimum spanning tree 163 mst = self.minimum_spanning_tree(self._rng.randint(0, sys.maxsize)) 164 target_nb_walls = int((self.nb_edges - mst.nb_edges) * self._wall_percentage / 100) 165 walls = [] 166 for vertex, neighbor in self.edges: 167 if not mst.has_edge(vertex, neighbor): 168 self.remove_edge(vertex, neighbor, True) 169 walls.append((vertex, neighbor)) 170 171 # Remove some walls until the desired density is reached 172 self._rng.shuffle(walls) 173 for vertex, neighbor in walls[target_nb_walls:]: 174 self.add_edge(vertex, neighbor) 175 176 ############################################################################################################################################# 177 178 def _add_mud ( self: Self, 179 ) -> None: 180 181 """ 182 This method adds mud to the maze. 183 It replaces some edges with weighted ones. 184 In: 185 * self: Reference to the current object. 186 Out: 187 * None. 188 """ 189 190 # Determine the number of mud edges 191 target_nb_mud = int(self.nb_edges * self._mud_percentage / 100) 192 193 # Add mud to some edges 194 edges = self.edges 195 self._rng.shuffle(edges) 196 for vertex, neighbor in edges[:target_nb_mud]: 197 self.remove_edge(vertex, neighbor, True) 198 weight = self._rng.randint(self._mud_range[0], self._mud_range[1]) 199 self.add_edge(vertex, neighbor, weight)
This class inherits from the Maze class. Therefore, it has the attributes and methods defined in the Maze class in addition to the ones defined below.
This class is abstract and cannot be instantiated. You should use one of the subclasses to create a maze, or create your own subclass.
A random maze is a maze that is created randomly. You can specify the size of the maze, the density of cells, walls, and mud, and the range of the mud values. You can also specify a random seed to reproduce the same maze later.
50 def __init__ ( self: Self, 51 cell_percentage: Number, 52 wall_percentage: Number, 53 mud_percentage: Number, 54 mud_range: Optional[Tuple[Integral, Integral]] = None, 55 random_seed: Optional[Integral] = None, 56 *args: Any, 57 **kwargs: Any 58 ) -> Self: 59 60 """ 61 This function is the constructor of the class. 62 When an object is instantiated, this method is called to initialize the object. 63 This is where you should define the attributes of the object and set their initial values. 64 Arguments *args and **kwargs are used to pass arguments to the parent constructor. 65 This is useful not to declare again all the parent's attributes in the child class. 66 In: 67 * self: Reference to the current object. 68 * cell_percentage: Percentage of cells to be reachable. 69 * wall_percentage: Percentage of walls to be present. 70 * mud_percentage: Percentage of mud to be present. 71 * mud_range: Range of the mud values (optional if mud_percentage = 0.0). 72 * random_seed: Random seed for the maze generation, set to None for a random value. 73 * args: Arguments to pass to the parent constructor. 74 * kwargs: Keyword arguments to pass to the parent constructor. 75 Out: 76 * A new instance of the class. 77 """ 78 79 # Inherit from parent class 80 super().__init__(*args, **kwargs) 81 82 # Debug 83 assert isinstance(cell_percentage, Number) # Type check for cell_percentage 84 assert isinstance(wall_percentage, Number) # Type check for wall_percentage 85 assert isinstance(mud_percentage, Number) # Type check for mud_percentage 86 assert isinstance(mud_range, (type(None), tuple, list)) # Type check for mud_range 87 assert isinstance(random_seed, (Integral, type(None))) # Type check for random_seed 88 assert random_seed is None or 0 <= random_seed < sys.maxsize # random_seed is a valid seed 89 assert (mud_percentage > 0.0 and len(mud_range) == 2) or mud_percentage == 0.0 # Mud range is an interval of 2 elements 90 assert mud_range is None or isinstance(mud_range[0], Integral) # Type check for mud_range[0] 91 assert mud_range is None or isinstance(mud_range[1], Integral) # Type check for mud_range[1] 92 assert 0.0 <= cell_percentage <= 100.0 # cell_percentage is a percentage 93 assert 0.0 <= wall_percentage <= 100.0 # wall_percentage is a percentage 94 assert 0.0 <= mud_percentage <= 100.0 # mud_percentage is a percentage 95 assert mud_range is None or 1 < mud_range[0] <= mud_range[1] # mud_range is a valid interval with minimum value 1 96 assert int(self.width * self.height * cell_percentage / 100) > 1 # At least two vertices 97 98 # Protected attributes 99 self._target_nb_vertices = int(self.width * self.height * cell_percentage / 100) 100 self._wall_percentage = wall_percentage 101 self._mud_percentage = mud_percentage 102 self._mud_range = mud_range 103 self._random_seed = random_seed 104 self._rng = random.Random(self._random_seed)
This function is the constructor of the class. When an object is instantiated, this method is called to initialize the object. This is where you should define the attributes of the object and set their initial values. Arguments args and *kwargs are used to pass arguments to the parent constructor. This is useful not to declare again all the parent's attributes in the child class.
In:
- self: Reference to the current object.
- cell_percentage: Percentage of cells to be reachable.
- 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.
- kwargs: Keyword arguments to pass to the parent constructor.
Out:
- A new instance of the class.