Best Approach To 3D Maze Generation

Hi Everyone,

I found this thread on 3D maze generation and wanted to know if this would be the best way of going about making a procedurally generated 3D maze.

http://forum.unity3d.com/threads/110153-Random-3D-maze-generation-script-not-working-properly

Specifically I would like the implementation to be as efficient as possible as far as memory usage goes during runtime while actually walking through the maze. So my question is this. Should my generation algorithm piece together terrain prefabs or should my generation algorithm create the vertices of the maze model and then make the model that way? I am leaning towards the first way as demonstrated in the example I posted. I just wanted to be sure I was beginning this in the right direction. Any other helpful resources would really be appreciated.

Well less items = less drawcalls. So if you could piece it together by code i would do that.

For the most effective maze generation, it really depends on what type of maze/dungeon you are looking for. There are many different ways to create one.

Also do it need to expand at run-time or do you just need to generate it at start?

If you re-use a set of polished prefabs (put together like Legos), you can get some nice-looking results (e.g., Diablo 3). And if they all share the same material (texture atlas), are set to Static, and use under 900 vertex attributes for dynamic batching, you can batch them and use an efficient shader to very significantly reduce draw calls. You could also consider combining them into a single mesh. It might take more memory, though, and if you’re going to use occlusion culling, don’t combine them.

The thread you referenced already includes a link to the Wikipedia entry on maze generation, which is a good start.

This blog has some very readable descriptions of a variety of maze generation algorithms:

http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorithm-recap

(Especially see the Growing Tree algorithm.)

But I think this article does the best job of describing and analyzing your options:

http://www.astrolog.org/labyrnth/algrithm.htm

I’ve been working on my 3d maze game for a bit now, and have at some point tried both of those methods.
Currently, I’m dynamically generating meshes to represent my 7 different maze tiles / models.
(But I could have easily used existing model prefabs, I just wanted dynamic features such as maze tile width, height, etc so all maze levels aren’t the same looking).

Then I clone those to piece together the entire maze.
Check out my web player in my sig to see the type of maze I’m generating (you are ‘on’ the maze’, not ‘in’ it, and can see a limited view of the surrounding maze tiles).
My maze style may look different, but really, instead of using my flat style tiles/meshes, I could have easily generated taller tiles, inverted the faces, and placed the player inside, instead of on top.

I’m using fog to reduce the view distance (plus to create an atmosphere). Powerups will be used to increase your view distance, but this may be tricky as this may cause more vertices to be displayed at once, and hard to determine the max to use to not cause FPS drops.

I want this on mobile but have not tried it yet. If I experience any FPS issues, I plan on implementing a chunking system and simply generate custom meshes for each 5x5x5 (for example) world section.

So which method is better or recommended? Not sure. As long as you use one material to share between all meshes, you should be good either way. It also may depend on your level size. I have not pushed my levels to the limits yet, as I’m still working on the menus and gameplay . . . level editing will be near the end.

Here’s a level preview screen showing you the entire maze for a certain level shape (Cube Squared in this case):

Here’s a shot while playing (the green box is the player placeholder, I suck at graphics!):

I went ahead and used the technique mentioned in the thread I posted. However, I was going for a hypermaze, namely a 3D maze where paths are separated not by single walls, but by an empty cell. I also modified the algorithm to generate from six independent points. The result is below.

When I set the dimensions to anything above about 25x25x25 I begin to experience lag. This brings me to TonyLi’s post. I am very interested in the techniques you’ve mentioned. Any suggested posts or references would really help me out. Essentially I have 6 difference prefabs representing walls (a unique prefab for each unique path in the maze). The end result is just thousands of cloned prefabs which make up the walls. What would be the best way to make this run more smoothly? And thanks for everyone’s kindness and support :slight_smile: I hope all of your projects are going smoothly.

Yeah, 25x25x25 is over 15,000 nodes. Sounds like you could use chunking (like Doug.McFarlane writes) to only instantiate the minimum required nodes around the player. That alone might eliminate lag.

Then again, in design there’s “perfect” and then there’s “fun.” Simplifications might make the maze less “perfect” but could drastically improve the experience. Maybe generate some 6x6x1 or 3x3x3 prefabs and put those together instead of working with individual nodes.

The guy who runs astrolog.org wrote an article on hypermazes: http://www.astrolog.org/labyrnth/hypermaz.htm which also has a link to his maze generator, Daedalus, which does hypermazes. Maybe some of the ideas in the article would apply to your maze, too.