Mazes that change on the fly

Mazes in general are hard enough, even on a summer’s day with the promise of ice cream. Mazes that shift and twist while you’re trying to solve them are another entirely, and are a fairly common trope in fiction (like the Triwizard Maze in Harry Potter, or the dynamic mazes in The Maze Runner). How would you do it algorithmically?

There are a few ways into the problem, some quite simple: you can arbitrarily break or make links, for example. You could create a PUBG-style forced finale for a tag-style game by gradually making arbitrary links between unlinked cells. Creating walls - breaking links - is a little different however, as you might well partition the maze into independent regions, with no way of travelling between them.

You might see that as not a problem, and a maze that occasionally isolates players probably gives you scope for some interesting gameplay. In this maze I wanted every cell to main reachable from every other cell, however; assuming that you don’t want to form these independent regions when creating a new wall, how can a maze adjust so that every cell is still reachable from every other cell?

This is the same problem as handling link outages in networks. One solution is to rebuild the minimum spanning tree: however, in this context that’d be confusing. It’s entirely possible that the entire maze would change around you, which feels like it breaks an unspoken rule about mazes; although it might transform over time, anyone running the maze would expect it to happen by some rule (see Cube for example.

So while recreating the minimum spanning tree is an option, I thought it’d be better to do determine the smallest change needed to open up the maze again so that any cell could be reached from any other cell, leaving most of the maze intact. The simplest answer is to remake the broken link, but where’d be the fun in that?

One trick is to understand what’s happening when you break a link. At worst, by breaking one link you split the maze into two independent regions (yes, arguably this needs a proof). For example:

If every cell should be reachable from every other cell then we need to make a link that bridges the two regions, collapsing them into one. We can do that by

• identify the region to which each cell belongs
• identify the pairs of cells that make up the boundary between the regions
• make a new link between an arbitrarily chosen boundary pair

Breaking a link and spotting regions

Breaking a link is easy: just choose a random cell, choose a random linked neighbour and break that link in both directions.

Identifying regions is a little harder, but we can use a flood fill or something quite like Prim’s algorithm for it. Loosely speaking we can start with an arbitrary cell and tag it as belonging to a specific region. Then we can tag each of its reachable neighbours as belonging to the same region – then each of their reachable neighbours and so on until there are no more reachable neighbours. Then we can start again with a cell we haven’t considered yet, and a new region tag – and carry on until we’ve considered all cells.

Adjusting the maze

To fix the maze I just need to identify those cells at the boundary: I look at the neighbour of each cell and determining whether it’s in a different region. If it is, I add the pair to a list of boundary cell pairs.

After that, I just need to create a link between an arbitrarily chosen pair to fix the maze.

The final effect

This works, but it’s surprisingly dull to watch. It needs a certain amount of surface effect to make it interesting – walls should disappear with a particle effect flourish or melt away, and should appear to grow from the ground, or drop into place from the sky perhaps.

Akka and managing stateful things in Minecraft

In the background I’m using a simple akka actor that nudges itself some seconds after adjusting the maze to do it again. akka’s quite a nice way of doing this as it’s easy to schedule a future event, and it takes away most of the boilerplate associated with ensuring that only one thing is modifying each maze at a time. It also means I can provide some nice functions to help debug what’s going on: for example, rather than have the actor nudge itself after some duration you can put it into a stepping mode and use the summonmaze command to step through, giving you time to analyse what’s happening in each step.

Finally

In itself a maze doesn’t seem like a big thing. What’s interesting is that the simple scope of it frees you up – or if open ended enough frees the players up (see Minecraft hide and seek, for example) to create interesting games out of it. If you look at, for example, Brawl’s Minecraft minigames there’s clearly a demand for simple, highly time-limited multiplayer games that are high-enough energy to hold attention for a few minutes before switching to the next. In this kind of context – the dynamics of the environment are just enough to trigger creative behaviour – players quite happily default to simple modes of play and exploration.