Return to site

Procedural Maze Generation

Computers do my work for me

My thoughts on Proc Gen

So I think it's time I start talking about a project I've been playing with for a little while. I'm really interested in procedural content and always have a good time when I see a game with something generated. I find it creates content for the players without as much work spent on designing individual areas.

Take a maze for example. They take absolutely forever to create manually and having multiple means that you're spending hours creating mazes that could be better spent on a feature that the player will notice.

Depth-First... First

So my first iteration on this maze generator created a simple depth-first maze (DFMaze) and passed it into a simple procedurally generated mesh script (PGMS) to give some visualisation back to me. I start in one corner, add the adjacent nodes into a list and shuffle the list. I do this until there isn't a tile left untouched. It creates a branching, winding maze that's unique every time. However, there aren't any landmarks or anything really interesting inside the maze.

Big mazes

So Unity is very versatile and can be modified quite extensively. However, sometimes the engine has some limits. In this case: Meshes have a hard limit of 65,000 vertices. That's a lot, right?

Well, a 64x64 maze requires 9 tiles per node which can either be raised or lowered. A lowered tile adjacent to a raised one will need a wall drawn between them. Most nodes are connected to 2 or 3 other nodes. So, there are an average of 6.5 walls per node. Unity uses vertex normals for smoothing, so a hard corner has to be created with individual vertices for each of the quads or things look weird.15.5 quads drawn per node and 4,096 nodes drawn. 63,488 quads in the mesh totalling around 253,952 vertices. We're totally out of range of what Unity will accept, which means we have to split the mesh into smaller pieces.

My PGMS uses lists of vertex buffers that I then plug into their own individual meshes. I found that my walls required more logic than my tiles, so I kept the meshes separate there, too. Below is a sample of how the meshes are organised in the editor.

Now, this means I can create a maze as large as I want, so I immediately stress tested my old laptop with a 256x256 maze. It took about 30 seconds of building and spat this out.

Rooms and Walkback

Now a while back I saw Evan Hahn talk at OIGC about how he generated the dungeons in Windforge. I took a little inspiration from that and decided to create some rooms via subdividing the map a few times and stamping out some holes in the maze.

I also decided to clean up the dead ends a little by creating a case where the nodes would walk back a certain while after hitting a dead end. Any intersection wouldn't be walked back as long as there were nodes that depended on it to be reached.

More subdivisions means smaller and more frequently occurring rooms.

Room First

I decided I didn't really like the odd shapes of the rooms created in my original generator, so I made some changes. I generated the rooms before I created the maze. I closed off the nodes so the maze wouldn't attach to the rooms at all, then picked some nodes to create doorways into the rooms. The nodes I picked were never closed, so the maze would naturally attach to them.


I didn't quite like just how random my generation was. It felt like every area was a maze and it was difficult to find your way between different rooms. To combat this I decided to use an A* algorithm to draw hallways between doors. The path would lower the value of the tiles it touched to create paths that would merge and split as needed. I then created a DFMaze off of the path to fill the rest of the area.

Cohesion... Redux

As cool as it was to see the paths navigate all around different rooms, I found the A* based path drawing to be slow and more than a little buggy given certain situations. I decided to change things with a simple path draw. It selected 2 doors and drew a line between them at a 90 degree angle. Any room it intersected with would be flagged, and the path would detour to the nearest door to the first contact point, resuming at the nearest door to the exit point. This repeats until the program navigates to the end of the path.

Once all doors have gone through this process, the path nodes are sent through the same DFMazeGen from above.

Going Forward

Themed tilesets are in progress, and creating the logic to set them is the next step on the programming side.

All Posts

Almost done…

We just sent you an email. Please click the link in the email to confirm your subscription!

OKSubscriptions powered by Strikingly