Maze Generation (Kruskal's Algorithm)¶

Figure 1: 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.

Figure 2: 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

Figure 3: 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¶

In [51]:

import numpy as np
from bokeh.plotting import figure, show, output_notebook

import numpy as np from bokeh.plotting import figure, show, output_notebook

Algorithm¶

In [72]:

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

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¶

In [75]:

size = {'x': 80, 'y': 40}
maze = generateMaze(size['x'], size['y'])
maze = createBorder(maze)
print("Generated array maze=")
print(maze)

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]]

In [76]:

output_notebook()

plot = figure(x_range=(0, 1), y_range=(0, 1),
              plot_height=size['y']*10, plot_width=size['x']*10)
plot.axis.visible = False
plot.outline_line_color = '#ffffff'

plot.image([maze], x=0, y=0, dw=1, dh=1, palette=['#228b22', '#ffffff'])

show(plot)

output_notebook() plot = figure(x_range=(0, 1), y_range=(0, 1), plot_height=size['y']*10, plot_width=size['x']*10) plot.axis.visible = False plot.outline_line_color = '#ffffff' plot.image([maze], x=0, y=0, dw=1, dh=1, palette=['#228b22', '#ffffff']) show(plot)

Loading BokehJS ...

In [ ]: