Generating a Voronoi diagram from a set of points with SciPy is straightforward.
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.
That may or may not bother you, but in this case I wanted the maze to be a bit more even and somewhat uniform.
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.
So we will use Poisson-disk sampling to generate a set of seed points to feed to SciPy to generate the 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.
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.
Look at its neighbors and pick a random neighbor that hasn't yet been visited.
Remove the Voronoi cell wall between the current cell and the random neighbor.
If there are no unvisited neighbors, backtrack to the last point that has unvisited neighbors and continue.
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 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 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.
In a recent project, we had a large number of points on a canvas, where a user could draw a region of interest to see only the points within that area. Here is a demo of how to do that using MongoDB with a geospatial 2D-index. Visualized using D3.
This is Part II of my post on image similarity in Python with perceptual hashing. In this post, we will use Spotify's Annoy library to perform nearest neighbors search on a collection of images to find similar images to a query image.