Random Labyrinths

I like Borges. And Borges likes Labyrinths. So, I want to make some good labyrinths.

Let's define a labyrinth as a graph with a path from a start node to an end node. We will be making classic 2d-grid labyrinths. We want to get from start (green) to end (red). We can start with a grid with random connections (selected by 50/50 coin flip).

A randomly connected grid graph - not a labyrinth

Unfortunately, most of these randomly connected graphs do not have a path from start to end (including above), and so do not qualify as labyrinths. 

So, we want to add connections to make a path from start to end. I will go even further and make the graph connected (= there is a path between all pairs of nodes). The strategy for this is:

• Start with a grid graph with no connections
• While there are still unconnected components, repeat:
• Find a node that has a grid neighbor that is not in the same component. Add an edge between them.

This implementation is admittedly naive. It is very wasteful about computing the connected components over and over again. Still, it can quickly produce decent labyrinths:

10 x 10 Labyrinth

30 x 30 Labyrinth