The task for today’s exercise is to build a maze and keep the size of the source code as well as memory under some limits. There is an array “world” of size WW times WH and it needs to be converted into a maze, where some cells are passable and some are walls. The outer rows and columns must become walls and the maze needs to be “perfect” – no loops and all passable cells are reachable. Let’s assume that the start is always in position (1,1) and there is one special cell being the goal.
In the above example the white square in the left upper corner, (1, 1) is the starting point and (22, 44) in is the light grey goal. Dark grey squares are walls and black cells are passable. Walls surround the maze as required. Some cells that are not empty are not reachable however (very dark grey). As long as there are few such cells a maze is good enough even if not perfect.
Generating a maze is generally not a challenging task. The assumption for today is that we are running the maze generation on a device with limited memory for both the code and the variables. Namely, we can store several bits of information in each maze cell, above that we can only use several simple variables. How does it affect our approach to maze generation algorithm?
These restrictions mean that using recursion or stack based algorithms directly is out of question. One of the possible approaches would be to use a method similar to BFS (Breadth First Search) or DFW (Depth First Search) where the next square to be visited would be randomly selected from the queue or the stack, respectively. The data structure would require some additional memory for storing “active” square coordinates, which does not match our requirements.
The idea is that we can trade time for memory size and simply mark the active squares in the same memory that we are using for storing the maze itself. Randomly selecting the next active cell to be processed requires:
- keeping track of the count of all active cells, e.g. active
- select randomly the index k from 0 to active-1 (the next cell to be processed)
- search through all the possible squares, stopping the search on kth active cell
If there are N cells, this makes the algorithm complexity to be N^2. For example a 5×5 maze with 25 cells would require at worst 25×25 = 625 operations in the worst case. So this method can be used only for rather small mazes, but we are limited by the memory anyway.
This approach leads to mazes with high branching i.e. there are many shorter corridors. If longer straight corridors are desirable, we can incorporate such a feature by storing the direction of the travel in each active cell and adding a probability P that this direction will be continued next time the cell is processed.
Here is an example of the algorithm execution for the simpler version without directionality.
In the example below:
- W: wall
- ?: available unprocessed cell
- A: active cell
- : empty cell
The initial state; walls surround the available cells.
+---+---+---+---+--
|Y/X| 0 | 1 | 2 |
+---+---+---+---+--
| 0 | W | W | W | W
+---+---+---+---+--
| 1 | W | ? | ? | ?
+---+---+---+---+--
| 2 | W | ? | ? | ?
+---+---+---+---+--
| | W | ? | ? |
Cell (1, 1) is made active and the active counter is set to 1.
+---+---+---+---+--
|Y/X| 0 | 1 | 2 |
+---+---+---+---+--
| 0 | W | W | W | W
+---+---+---+---+--
| 1 | W | A | ? | ?
+---+---+---+---+--
| 2 | W | ? | ? | ?
+---+---+---+---+--
| | W | ? | ? |
The index of the active cell to be processed is randomly selected, however there is only 1 at the moment. The algorithm scans the whole table and finds the active cell. The current active cell changes state to empty and squares up, down, right and left are examined. Walls up and left are not changed. Available cells to the right and down become active. Active cell count is updated (2).
+---+---+---+---+--
|Y/X| 0 | 1 | 2 |
+---+---+---+---+--
| 0 | W | W | W | W
+---+---+---+---+--
| 1 | W | | A | ?
+---+---+---+---+--
| 2 | W | A | ? | ?
+---+---+---+---+--
| | W | ? | ? |
In the next step the index of the active cell to be processed is randomly selected; for example 2nd: (1, 2). Table is scanned to find that cell. The current active cell changes state to empty and squares up, down, right and left are examined. Wall to the left and empty square up are not changed. Available cells right and down become active. Active cell count is updated (3).
+---+---+---+---+--
|Y/X| 0 | 1 | 2 |
+---+---+---+---+--
| 0 | W | W | W | W
+---+---+---+---+--
| 1 | W | | A | ?
+---+---+---+---+--
| 2 | W | | A | ?
+---+---+---+---+--
| | W | A | ? |
Next cell is randomly selected and found by scanning, e.g. (2, 1). The current active cell changes state to empty and squares up, down, right and left are examined. Neighboring walls and empty squares are unchanged. Available cells to the right becomes active. Neighboring active cell becomes a wall, since it would otherwise link two different empty squares and we do not want loops. Active cell count is updated – it is reduced to 2.
+---+---+---+---+--
|Y/X| 0 | 1 | 2 |
+---+---+---+---+--
| 0 | W | W | W | W
+---+---+---+---+--
| 1 | W | | | A
+---+---+---+---+--
| 2 | W | | W | ?
+---+---+---+---+--
| | W | A | ? |
This short example showed how this algorithm is able to build paths and walls with minimal additional storage.
Here is the actual Python code, extended with the feature of longer straight corridors.
Values to be stored in the maze cell. Available (unprocessed) and active (on the currently processed list) cells codes can be reused. MASK and SHIFT are used for encoding the codes (lower two bits) and travel direction (higher two bits).
MASK = 0x03
SHIFT = 2
CEMPTY = 0
CAVAIL = 1
CWALL = 2
CACT = 3
CGOAL = 3
Size efficient mapping of the numerical direction code 0…3 to x and y deltas. Deltas are -1, 0 or 1, so it’s necessary to add 1 for encoding and subtract 1 for decoding. For example if the direction d is 1, XX[1] is “1”, 1 – 1 == 0; YY[1] is “2”, 2 -1 == 1; thus the direction vector is (0, 1) i.e. down.
XX = "2101"
YY = "1210"
This is the function that scans the “world” searching for the kth active cell. The variable g is the “world” object that exposes getworld(x, y) and setworld(x, y, state) member functions. This function returns the coordinates of the kth active cell.
def mazesearchactive(g, k):
for x in range(1, g.WW - 1):
for y in range(1, g.WH - 1):
if g.getworld(x, y) & MASK == CACT:
if k == 0:
return x, y,
k -= 1
return None, None
Maze update function. g is the “world” object as above, x and y are the coordinates of the cell being updated, active and avail are counts of the active and available cells respectively. Strictly speaking available cells do not need to be counted, unless we want to implement checking if any cells were left unprocessed. So this code can be still simplified if the the target architecture requires it. d is direction (0…3), the index to XX and YY strings.
def mazeupd(g, x, y, active, avail, d):
p = g.getworld(x, y)
if p & MASK == CACT:
g.setworld(x, y, CWALL)
active -= 1
elif p == CAVAIL:
g.setworld(x, y, CACT + (d << SHIFT))
active += 1
avail -= 1
return active, avail
Finally, the maze generating function. g is the “world” object, while prob_t / prob_max is the probability that the direction of the corridor will be extended. The higher this probability, the more straight corridors. Specifying this as a ratio avoids floating point numbers that might not be available on the destination platform. The last square to be emptied is marked as the goal. This tends to be distant from the origin, however if the probability of straight corridors is higher, the last square may turn out to be close and the maze will be easy to solve.
def maze(g, prob_max, prob_t):
avail = 0
active = 0
for x in range(g.WW):
for y in range(g.WH):
if x == 0 or y == 0 or x == g.WW - 1 or y == g.WH - 1:
g.setworld(x, y, CWALL)
else:
g.setworld(x, y, CAVAIL)
avail += 1
g.setworld(1, 1, CACT)
active += 1
avail -= 1
nx, ny = -1, -1
while active > 0:
if nx == -1:
x, y = mazesearchactive(g, rr(active))
else:
x, y = nx, ny
nx, ny = -1, -1
lastd = g.getworld(x, y) >> SHIFT
g.setworld(x, y, CEMPTY)
active -= 1
for d in range(4):
nactive, avail = mazeupd(g, x + int(XX[d]) - 1, y + int(YY[d]) - 1, active, avail, d)
if lastd == d and nactive > active and rr(prob_max) <span data-mce-type="bookmark" id="mce_SELREST_start" data-mce-style="overflow:hidden;line-height:0" style="overflow:hidden;line-height:0" ></span>< prob_t:
nx, ny = x + int(XX[d]) - 1, y + int(YY[d]) - 1
active = nactive
g.setworld(x, y, CGOAL)
return x, y
This code was used in a Micropython application and should be easily portable to embedded Lua or C/C++.
And here are mazes generated with various likelihoods of direction reusing. Low values have higher branching, higher tend to have straight long corridors.
0%
10%
20%
30%
40%
50%
60%
70%
80%
90%
The script is provided in a single line form, so you can paste it into your terminal without installing anything.
From C/C++ to Python 
