Maze Generation (Kruskal’s Algorithm)
Contents
Maze Generation (Kruskal’s Algorithm)¶
Fig. 15 Generated Maze¶
ßKruskal’s Algorithm find the minimum spanning forest of an undirected edge-weighted graph. if the graph is connected, it find the minimum spanning tree.
Fig. 16 Krukal Demo Source: Wikipedia¶
Terminology¶
Cost of graph: This is the sum of the weights of all the edges in the tree of the graph. This can be used to represent the cost estimated to implement the link between the two vertices.
Minimum Spanning tree: It is a subgraph or a tree that connects all the graph vertices with the minimum cost possible.
Solution¶
First, we generate an undirected graph represented by 2-dimensional matrix.
white square is a cell — and represents graph node
green square is a wall
black square can be either one — and represents graph link
Fig. 17 Maze Matrix¶
Kruskal’s algorithm splits the graph nodes into separate components and repeatedly unifies them using graph links. However, there is a condition that after the link has been added, number of components must have decreased.
All we need is to pick an edge on random, check if the neighboring cells belong to a different components and unify them by turning black position into white cell. Otherwise make there wall.
Imports¶
import numpy as np
from bokeh.plotting import figure, show, output_notebook
Algorithm¶
def generateMaze(x: int, y: int):
"""generate a random maze with kruskal's algorithm of a given size
* 0 = green dot e.g. wall
* 1 = white dot e.g. cell (graph node)
* 2 = black cell, will be transformed to green or white (graph link)
Args:
x (int): x-size of the maze
y (int): y-size of the maze
Returns:
list: 2 dimensional array with 0 (wall) and 1 (cell) representing the maze
"""
# maze skeleton
maze = np.tile([[1, 2], [2, 0]], (y // 2 + 1, x // 2 + 1))
# Strip last element of x and y to make it flipable
maze = maze[:-1, :-1]
# get disct of coodinates of all cells and all walls
cells = {(i, j): (i, j) for i, j in np.argwhere(maze == 1)}
walls = np.argwhere(maze == 2)
# subroutine union-find
def find(p: int , q: int):
"""find parent x-y cell of given cell p-q
Args:
p (int): location x of cell to locate
q (int): location y of cell to locate
Returns:
list: x-y location of parent cell
"""
# if x,y not parent cell
if p != cells[p] or q != cells[q]:
# get parent cell
cells[p], cells[q] = find(cells[p], cells[q])
return cells[p], cells[q]
# randomly shuffle the walls to so the maze will be different each time
np.random.shuffle(walls)
# find spanning tree
for wi, wj in walls:
if wi % 2: # black dots on even rows union-find left right neighbors
p, q = find((wi - 1, wj), (wi + 1, wj))
else: # black dots on uneven rows union-find up down neighbors
p, q = find((wi, wj - 1), (wi, wj + 1))
# update cell value
maze[wi, wj] = p != q
if p != q:
cells[p] = q
return maze
def createBorder(maze: list):
"""Create boarder around the maze
"""
## make border of the maze walls
maze[0] = 0
maze[-1] = 0
maze[:, 0] = 0
maze[:, -1] = 0
return maze
Test¶
size = {'x': 80, 'y': 40}
maze = generateMaze(size['x'], size['y'])
maze = createBorder(maze)
print("Generated array maze=")
print(maze)
Generated array maze=
[[0 0 0 ... 0 0 0]
[0 0 0 ... 1 0 0]
[0 0 1 ... 1 1 0]
...
[0 1 1 ... 1 0 0]
[0 0 0 ... 0 0 0]
[0 0 0 ... 0 0 0]]