Python Maze Generator Part II: Voronoi Diagrams

voronoimazecover.png

In a previous post, I generated random mazes in Python from a 2-D grid of points.

Today I am doing a similar thing, only the mazes are a little more interesting by starting with a Voronoi diagram.

The code for this post can be found here.

This animation shows the maze being solved with a backtracking algorithm, with the path in green and the backtracking steps in purple.

What is a Voronoi diagram?

A Voronoi diagram, also called a Voronoi tesselation, is computed by partitioning a space into regions called cells based on a set of objects or seed points.

It's a nearest-neighbors map of these points.

Any point within a Voronoi cell is closer to the seed point in that region than any other seed point.

NYC Subway Voronoi

If you've never heard of Voronoi diagrams before, a practical example to illustrate them is finding the closest subway station to any other location in NYC.

NYC subway voronoi map

The subway stations (their latitude, longitude coordinates) are the seed points to compute the Voronoi diagram, where each subway station point is enclosed by a Voronoi cell.

To find the closest subway station to a location, you simply find the Voronoi cell that contains that location, and the subway station corresponding to that cell is the closest one.


We can also use random points to generate a Voronoi diagram and then break down some of the cell walls to create a maze.

Voronoi cells are convex polygons, so instead of starting with a grid of squares for this maze, we have bunch of polygons with a variable number of sides in the space.

Generating a Voronoi Diagram

Of course we could implement an algorithm to generate a Voronoi diagram ourselves.

Fortune's sweep line algorithm is a common algorithm for this.

But there are also some great libraries that will do it for us.

I'm using SciPy - the docs can be found here.

SciPy uses the QHull library.

Generating a Voronoi diagram from a set of points with SciPy is straightforward.

import random
from scipy.spatial import Voronoi

#list of random points for this example
points = [(random.randint(0,100),random.randint(0,100)) for i in range(100)]
vor = Voronoi(points)

How to create a maze from a Voronoi diagram

First we need a set of seed points.

Any old random points like I generated above can lead to a very uneven distribution of points, where you would have clumps of Voronoi cells.

random_point_distribution.png

That may or may not bother you, but in this case I wanted the maze to be a bit more even and somewhat uniform.

Poisson-Disk sampling

So instead we will generate a set of random points where the points are packed together as tightly as possible into the boundaries we want for the maze, but all points are also separated by at least a minimum distance.

poisson_distribution_points.png

Much better.

So we will use Poisson-disk sampling to generate a set of seed points to feed to SciPy to generate the Voronoi diagram.

initial voronoi diagram

Here is the resulting Voronoi diagram, and now it's time to turn it into a maze.

Carving out the maze

A maze can be viewed as a graph.

A graph has nodes and edges, where the edges connect pairs of nodes.

The points that we just generated and used to construct the Voronoi diagram are the nodes of this graph.

Each point is a neighbor of other points that it shares a Voronoi cell edge with, so there is an edge between a point and each of its neighbors.

The orange edges show these neighbor relationships, and are the edges we will traverse over for both creating and solving the mazes.

Voronoi diagram neighbors graph - delaunay triangulation

These edges also correspond to the Delaunay triangulation, which is the dual graph of the Voronoi diagram.

In the 2-D grid maze, the neighbors were simply the cells to the top, right, left and bottom - and you could allow for diagonals as well.

Breaking down walls

Now it's time to break down the walls between some of these neighbors.

In my other maze post, I used Kruskal's algorithm to find a minimum spanning tree, which results in a graph where all vertices are connected by a subset of the edges, with no cycles.

This time I am going to use a randomized depth-first search algorithm to generate the maze.

This algorithm will traverse the neighbor graph above, and randomly pick walls of the Voronoi cell polygons to remove.

Randomized depth-first search

This is a backtracking algorithm that starts with a random seed point and proceeds in a depth-first search, picking random neighbors and breaking down the walls between them.

  1. Look at its neighbors and pick a random neighbor that hasn't yet been visited.
  2. Remove the Voronoi cell wall between the current cell and the random neighbor.
  3. If there are no unvisited neighbors, backtrack to the last point that has unvisited neighbors and continue.

Voronoi diagram maze initial image with entrance and exit marked

Now the maze is complete, with an entrance marked by the blue polygon, and the exit is marked by the red polygon.

After carving out the maze paths, we also have a list of legal edges that can be traversed when solving the maze.

A Voronoi cell wall bisects two nodes, and so whenever a wall is removed, the edge between those two nodes is added to the list as a legal step when solving the maze.

In this maze at least, we don't allow walking through walls, so when solving the maze, if an edge we want to traverse is not in the list of legal edges, it means there is a wall blocking that path, so we can't move there.

Solving the maze

Use any of your favorite path-finding algorithms to solve the maze.

Breadth-first search

Breadth-first search is a fundamental path-finding algorithm where the algorithm explores paths in layers, which is why it fans out the way it does.

It starts with a node and explores all of its neighbors at each level or layer before moving to the next.

Breadth-first search can be used to find the shortest path from one point to another in a graph.

Backtracking depth-first search

This is the same visualization you saw at the top of the post.

This backtracking depth-first search algorithm to solve the maze is similar to the randomized backtracking algorithm used to generate it.

Depth-first search is different than breadth-first search because it explores a path from one neighbor as far as it can before coming back and moving to the next neighbor.

With backtracking, the path is built incrementally, and when a path is found to be non-viable, the algorithm tries to correct by taking a step back and then seeing if it can keep going in a different direction.

Dijkstra's algorithm

Dijkstra's algorithm is basically breadth-first search for weighted graphs.

This graph has weights assigned to the edges that are based on the distance from the exit.

When it picks the next neighbor cell to move to in the path, it will pick the one that is closer to the exit.


Path planning with Voronoi diagrams

Another use for Voronoi diagrams is in path planning.

If the seed points used to generate the Voronoi diagram represent obstacles that you want to avoid, then a safe path to follow would be along the edges of the Voronoi diagram.

Thanks for reading!

If you have any questions or comments, leave them below or reach out to me on Twitter @LVNGD.

blog comments powered by Disqus

Recent Posts

picto_sm_sharp.png
Building Pictogram Grids in D3.js
Nov. 22, 2020

Pictograms have been around for a long time, and with good reason. They are interesting and engaging, and might even help your audience to remember the information better. In this post we will build a pictogram grid in D3.js.

Read More
Playing Minesweeper graphic
Solving Minesweeper in Python as a Constraint Satisfaction Problem
Nov. 15, 2020

Let's play Minesweeper in Python. In this post we will treat Minesweeper as a constraint satisfaction problem and use common algorithms like constraint propagation and backtracking search to mimic logic we would use to play the game as humans.

Read More
minesweeper_header.png
Generating Minesweeper boards in Python
Nov. 6, 2020

In the next couple of posts we're playing Minesweeper in Python. You may be familiar with it since it probably can be found on your nearest computer. First we need to generate a board - that's this post - and then in the next, we will play the game.

Read More
Get the latest posts as soon as they come out!