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.

	def connect_labyrinth(L):
	while not nx.is_connected(L):
	connect_components(L)
	def connect_components(L):
	for c in nx.connected_components(L):
	for n in random.sample(c, len(c)):
	neighbours = list(get_grid_neighbours(L, n))
	random.shuffle(neighbours)
	for neigh in neighbours:
	if neigh not in c:
	L.add_edge(n, neigh)
	return
	def get_grid_neighbours(L, n):
	i, j = n
	for di, dj in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
	neigh = (i + di, j + dj)
	if neigh in L:
	yield neigh

view raw .py hosted with ❤ by GitHub

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