💾 Archived View for epi.benthic.zone › posts › 2021-08-18_GeneratingRandomMazes.gmi captured on 2022-03-01 at 15:25:10. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2021-11-30)
-=-=-=-=-=-=-
2021-08-18
I was reading up about graph algorithms for a project that I'm working on when I realized that it would be neat to generate some random mazes and display them here on my Gemini capsule. You can now do that by visiting
Read on for more about how I did this.
One way to make a maze is to take a graph consisting of vertices connected by edges, and create a /spanning tree/ for that graph. The spanning tree connects every pair of vertices in the graph with exactly one path. The path through the maze is the single path from the starting vertex to the finishing vertex.
To make lots of different mazes, we need to generate a spanning tree for a given graph randomly. To start with, let's think about how we might generate a single random path from one vertex to another on a graph. We could imagine a /random walk/ that starts at our first vertex (call it u) and randomly jumps from one vertex to one of its neighbors. A single step of a random walk looks like
function rw_step(u)
ns = neighbors(u)
rand(ns)
end
which first finds the neighboring vertices of u and then randomly picks a vertex to visit. The `neighbors
` function depends on the structure of our graph. We'll work with a uniform N x N grid, in which case each vertex has four neighbors -- north, east, south and west -- unless it is on one or more of the boundaries of the grid. We start our random walk at u and then walk until it hits v:
function rw(u,v)
γ = [u]
while γ[end] != v
push!(γ,rw_step(γ[end]))
end
γ
end
We have a problem, though. The random walk might visit any vertex in our graph more than once (except for v). But the spanning tree only has a single path from one vertex to another. We need to get rid of the loops in the random walk, creating a /loop-erased random walk/.
Wikipedia on loop-erased random walks
function erase_loops(γ)
N = length(γ)
ts = [1]
while ts[end] < N
t = findlast(x->x == γ[t[end]],γ)
push!(ts,t+1)
end
γ[ts]
end
This is a little complicated, but it follows the algorithm described in the Wikipedia article directly. We start with the first element in our path γ, which is just a list of vertices that we visited on our random walk, starting at u and ending at v. We look at the path and find the last time, t, that we visited the first vertex, and then we add t + 1 to our list of indices. Our path is now just like we started at v and jumped to the vertex at γ[t+1], instead of going around the big loop from v and back to v. We repeat this process of getting rid of loops until we hit the end of the path, and then we return the elements of the path with all of the loops erased: a loop-erased random walk.
Now a single loop-erased random walk is just a path from one vertex to another. The spanning tree of our graph has a path from every vertex to another. To generate loop-erased paths between all of the vertices, we use /Wilson's algorithm/. This is pretty simple. We start with the starting vertex of the maze, u = (1,1) in the lower left corner of the grid. Then we pick any vertex other than u and construct the loop-erased random walk from there to u. That path forms the first branch of a tree that we are going to build, and this tree data structure will be the spanning tree of the graph when we are finished.
On the next time around, we choose another vertex that is not already in the tree, and then we perform a loop-erased random walk until we hit any one of the vertices already in the tree. Once we do, we add the new path to the tree, branching off of the vertex that we just hit. We repeat that until all of the vertices are in the tree. The algorithm looks something like
function spanning_tree(u,g)
# Collect all the vertices in the graph
vs = vertices(g)
# Create a Tree with just the starting vertex
T = Tree(u)
# Pick a vertex that is not in the tree already
v = pick_vertex(vs,T)
while not_all_vertices_in(T)
# Do a loop-erased random walk from v until
# you hit the tree
γ = lera(v,T)
# Add the path to the tree
add_path!(T,γ)
# Pick a new vertex not in the tree
v = pick_vertex(vs,T)
end
T
end
This skips a lot of details, including how we represent the tree data structure. I first started with a typical tree implementation like
struct Tree
u # Vertex
children::Vector{Tree}
end
But it turned out that checking to see whether a vertex was in this kind of tree took too long. You basically have to search through the whole tree every time, and that adds up, because you have to do it at every step of the loop-erased random walk to see whether you've hit the tree yet.
The way I chose to do this is to store the tree as a sparse adjacency matrix. Since we have a fixed grid of vertices, we never need to add or remove vertices, so we can just set up a sparse matrix of size N² x N². Checking to see if a vertex is in the tree is O(1): we just index into the matrix at the correct row and check to see whether any of the entries are 1. To add a path, we just walk down the path, adding an entry from γ[i] -> γ[i+1] and γ[i+1]->γ[i]. This works much better. I'm no expert on data structures, though, so maybe there is an even better way to do this.
Once all the vertices are in our tree, we have a spanning tree, and it turns out that this is a /uniform spanning tree/: each spanning tree has an equal probability of being selected, which is good, because it makes it unlikely that you'll draw the same maze twice.
The next step is to draw our maze in ASCII so we can display in via Gemini. I first tried to figure out how to do this with Unicode box drawing characters, but that got complicated quickly. So I stuck with underscores "_" and vertical bars "|". The trick here is to build up the maze from bottom left to top right. This way, you only need to look at the south and east neighbors of each vertex, and there are really only four options: " _", "__", " |", and "_|" depending on whether the south and east neighbors are connected. You also have to draw the edges on the left, top and right and make holes for the entrance and exit, and you are good to go.
Other than figuring out which data structure to use for the tree, this was the most complicated part of making a maze generator. My gemini server, molly-brown supports SCGI, so I can launch a Julia process that listens for requests to a Unix domain socket. Once it connects, it outputs a Gemini header, and then generates and prints a maze to the socket. This part was fairly easy, using Julia's Sockets module.
function start_mazeserver(domain_socket)
server = listen(domain_socket)
begin
while isopen(server)
sock = accept(server)
# Gemini Response Header
print(sock,"21 text/gemini;charset=utf-8\r\n")
#
print(sock,"# A randomly generated maze\r\n")
print(sock,"Make your way from the bottom left to the top right\r\n")
# Maze
print(sock,"```A randomly generated maze\r\n",ust((1,1),16),"```\r\n")
close(sock)
end
end
end
Since I don't care about the request parameters, I just want to show a new maze every time the CGI path is visited, I thought I might be able to just ignore the request headers that molly-brown sends to the SCGI server. It turns out that closing the socket before you have read all of the sent bytes will cause molly-brown to issue a 42 error, even if the server successfully sent everything it wants. So I had to add a line to read the SCGI header from the socket. The key here is to parse the first couple of bytes of the header up to a ":" as the length of the header, then you can read that many bytes from the socket. Otherwise, you don't know exactly how many bytes to read, and you might not get them all depending on when you do the read.
Once I had the server working, I set up a systemd service on my Linode and launched it, and now you, too, can generate mazes.
If you want to see the source code, you can find it here under an MIT License.