While checking out other people’s tech demos for inspiration, I came across one featuring a randomly generated maze. It had a big ol’ space in the middle with all the other paths branching off it, all of which lead to dead ends, or if you were lucky, one more branch off some of them, also leading to a dead end. But how does one stop that from happening, and make a nice satisfying maze that isn’t solved by a systematic and very boring approach of returning to one spot and testing all the paths branching off it? How do you make sure you get a good maze every time?
I had this algorithm figured out for a while but when I saw the Procedural Generation Jam was on I thought this would be the perfect thing to develop in code and submit. I ended up making my first ever 3D game with it, mostly to show off the maze and show how challenging (but possible) it is to solve when you’re not looking at the entire thing from the top.
The algorithm is based on having a “critical path”, which is a specified minimum number of steps you can take to get to the centre of the maze. This will have a number of paths branch off it, none of which are allowed to create a shortcut across any other path. The number of steps from the centre (hereafter SFC for brevity) are stored in each square, and creating a shortcut across a path does not necessarily create a shortcut across the critical path- but continuously updating the SFC for squares not on the current path as long as this doesn’t affect the critical path is a lengthy process.
I tested it out manually first using excel, but the first maze was lacking somewhat in walls due to its annoying tendency to create little 2×2 square rooms. (The critical path is in blue)
After I changed my rules to count paths of equal length to the paths they cut across as prohibited shortcuts, and made it equally likely for a path to continue in the same direction than go left or right (previously a 1/3 chance for each direction), a much more “mazelike” maze was produced.
I implemented this in Unity, using prefab horizontal and vertical walls with posts to connect them and a 40×40 area size. This led to a couple more improvements. First of all I implemented it still finding the critical path by trial and error. This found some great squiggly paths and I can make it try enough iterations that it has an incredibly low chance of not finding a viable path, but I didn’t want my program to fail/crash every 1 in a million times. Instead I stored the distance away from the centre in each square and stopped the path from moving into a square that was further away than the centre than there were steps left in the path. The only problem then was the path dead-ending itself- easily solved by going back on itself until it could then get back to the centre. I experimented with weighting the path so that it was more likely to go in a more interesting route, and stop it squiggling about at the start of the maze and suddenly going straight to the centre when its “distance from the centre” condition was met.
Creating branches off the critical path was then much easier. The only condition is that they are not allowed to create shortcuts off any other path. After creating the game version, I realised that a lot of the mazes had huge sections blocked off with only one point of entry, which was exactly what I was trying to avoid in the first place. I fixed this by setting a maximum branch length, to encourage paths to connect back onto each other- making the diagram of possible routes to the centre more like the first one in this diagram and less like the second.
Here’s the full algorithm:
- Find a critical path of a specified length (in the examples, 40 steps). Starting on the first step, select a square forward (50% chance), left (25% chance), or right (25% chance). If this square is fewer steps from the centre than there are steps left in the path, step into it. If there are no viable step options, back up one square and mark the previous square as non-viable. Repeat this for the specified number of steps.
- Randomly select a path-occupied square in the grid. If it has at least one empty square next to it, randomly choose one to start a new path branching off. Otherwise, choose a different square.
- When making a new path, follow the “stepping” procedure the same as for the critical path until the next step is onto a path occupied square. If the SFC of that square – the SFC of the square this path branched off from < the steps in this path, connect the path onto the square. Otherwise, or if the square is part of the same path, generate a new direction to go in. If all the directions are blocked or the path has reached a specified maximum length, end the path.
- Once the path is complete, update the SFC of each square by starting from the SFC of the square that the path branches off from, adding one each time. Then repeat this process from the other end, stopping when the next square’s SFC is less than or equal to the current square’s SFC.
- Repeat steps 2-4 until all the squares have a path across them.
Edit: I also discovered this episode of the excellent game design webseries Extra Credits about procedural generation that really cemented my ideas about how the generator should work and how I can use it going forward.
With a “lab mouse” scenario in mind I downloaded a cute little mouse asset from the asset store and made the generator into a game. It was my first ever 3D game and the first one with animations- which Unity has of course made quite easy to work with. Programming the camera was quite fun, because I wanted the player to be given some idea of the layout of the maze before they start. For demonstration purposes I added a “cheat” button that shows the critical path, since the feature was already in there for debugging.
It’s something I could add a lot of features to- sound effects, enemies and hints could all make it more engaging. For now, on to more technical things.