Maze¶
quest.maze.Maze is a helper class which generates mazes. It’s included
in the Quest framework, but you could easily use it in other projects.
quest.maze.Maze is used in the quest.examples.maze.MazeGame
demo project.
-
class
quest.maze.Maze(columns, rows)[source]¶ Generates a maze stored in a 2-dimensional array.
This class generates a maze. The mathematical definition of a maze is a set of paths that are connected so that there is exactly one way to go between any two points. Here’s an example:
>>> from quest.maze import Maze >>> m = Maze(55, 15) >>> m.generate() >>> print(m) ╔═══════════════╦═════╦═════════╦═════════╦═══════╦═══╗ ║ ║ ║ ║ ║ ║ ║ ║ ╔═════════╦══ ║ ══╗ ║ ║ ══╦══ ╚═══╦══ ║ ║ ╔═══╗ ╠══ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ╔═════╗ ║ ║ ╚═╗ ╚═╦═╩═╗ ╚═╦═══╗ ║ ╔═╩═══╝ ║ ║ ║ ══╣ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ╔═╗ ║ ║ ╠═══╝ ╔═╝ ║ ║ ║ ║ ║ ╚═══╣ ══╗ ╔═╩═╝ ╠══ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ══╦═╝ ╔═╝ ╠═╝ ║ ╚═══╗ ╠══ ║ ║ ╔═══╣ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ╠═╩═════╝ ║ ╠═══╦═╝ ╔═╣ ╔═╝ ╔═╩═╦══ ║ ║ ╔═╩═══╝ ║ ║ ╚═╣ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ╔═══════╝ ║ ║ ║ ╔═╝ ║ ╚══ ║ ══╝ ══╩═══╩════ ╔═╝ ╚══ ║ ║ ║ ║ ║ ║ ║ ║ ╚═╩═══════════╩═══╩═════════╩═════════════════╩═══════╝
There are many different algorithms for generating mazes, and they tend to produce mazes with different characteristics. This class implements a depth-first search maze generation algorithm, which tends to produce long corridors without much branching. See
generate()for a description of how this works.- Parameters
columns – the number of columns in the maze (including edge walls).
rows – the number of rows in the maze (including edge walls).
-
generate(seed=None)[source]¶ Generates (or re-generates) a random maze.
We are always going to keep track of a current point and we’re going to keep a list of points that have been visited. Every time a point becomes the current point, we will add it to visited. Also, every time we move to a new current point, we add the old current point to a stack. This becomes a history of where we have been.
Now we see if the current point has any neighbors that have not yet been visited. If so, choose one randomly, make it the current point, and repeat. Now the maze is growing like a worm, one point at a time. At some point, though, the growing worm will get stuck in a dead end, where the current point has no unvisited neighbors. It can’t grow anymore.
This is where the history stack comes in. Since the maze can’t grow from the current point, let’s pop the most recent point off the history stack and make that the current point instead. If that point has unvisited neighbors, great: we can continue. Otherwise, keep popping points off the history stack until we find one that has unvisited neighbors.
When does this end? Once the history stack is empty. That means we have worked our way all the way back to the starting point, and no points have any unvisited neighbors remaining. This means the maze has filled up its whole world so it’s finished!
If you want to see this in action, here is a website with several different maze-generation algorithms. Choose “Flood fill/Depth-first.”
- Parameters
seed – If provided, sets the random seed. (Random numbers on computers are not really random, they’re just hard to predict. If you set the random seed to the same value, you’ll get the same set of random numbers every time. This is helpful when you want to get the same random maze.)
-
generate_fully_connected_maze()[source]¶ Generates a maze where every node is connected to all its neighbors.
-
connect(p0, p1)[source]¶ Connects two points by storing each in the other’s list of links.
- Parameters
p0 – A point, which is represented as a tuple of (x, y) coordinates.
p1 – Another point, also a tuple.
-
connected(p0, p1)[source]¶ Checks whether two points are connected as neighbors.
- Parameters
p0 – A point, which is represented as a tuple of (x, y) coordinates.
p1 – Another point, also a tuple.
- Returns
True if the points are connected, otherwise False.
-
neighbors(point)[source]¶ Gets a list of the point’s neighbors.
The points we care about are those with odd coordinates, like (1, 1) and (5, 7). Let’s call these points nodes. They are represented with stars in the diagrams below.
The reason nodes are on the odd coordinates is because we need to leave room for walls between points in the maze, and surrounding the maze.
╔═══════╗ ╔═══════╗ ╔═══════╗ ║* * * *║ ║* * * *║ ║ ║ ║ ┼ ┼ ┼ ║ ╠═════╗ ║ ╠═════╗ ║ ║* * * *║ ║* * *║*║ ║ ║ ║ ║ ┼ ┼ ┼ ║ ║ ╔══ ║ ║ ║ ╔══ ║ ║ ║* * * *║ ║*║* *║*║ ║ ║ ║ ║ ║ ┼ ┼ ┼ ║ ║ ║ ══╝ ║ ║ ║ ══╝ ║ ║* * * *║ ║*║* * *║ ║ ║ ║ ╚═══════╝ ╚═╩═════╝ ╚═╩═════╝
- Parameters
point – A tuple of (x, y) coordinates.
- Returns
A list of nodes two spaces to the left, right, down, and up from the given point, as long as they are in bounds.
-
is_in_bounds(point)[source]¶ Checks whether a point is in bounds.
- Returns
True if the point is in bounds, otherwise False.
-
get_walls()[source]¶ Returns a list of points containing walls in the current maze.
To find all the walls, we just loop through every (x, y) point in the maze and check if it’s a wall. First off, all the points around the edges must be walls. Then, If both a point’s x and y coordinates are odd, the point is definitely not a wall (See
neighbors()). If both a point’s coordinates are even, it is definitely a wall. For points with one even and one odd coordinate, we need to check the links to see whether the point has been chosen as a link. Otherwise, it’s a wall.- Returns
A list of (x, y) tuples for wall spaces in the maze.
-
str_char(point, walls, nodes=False)[source]¶ Determines which character should represent a point in the maze.
- Parameters
point – A (x, y) tuple.
walls – A list of (x, y) tuples.
nodes – If True, points that are nodes (see
neighbors()) will be shown as stars.