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#####################################################################################################################################################
class RandomMaze(pyrat.src.Maze.Maze, abc.ABC):
 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.

RandomMaze( cell_percentage: numbers.Number, wall_percentage: numbers.Number, mud_percentage: numbers.Number, mud_range: Optional[Tuple[numbers.Integral, numbers.Integral]] = None, random_seed: Optional[numbers.Integral] = None, *args: typing_extensions.Any, **kwargs: typing_extensions.Any)
 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.