Testing Mazing algorithms

[sokol815]

Hey everyone! I have 2 different mazing algorithms that I am trying out.

Both of the below links take you to a page showing the maze being generated. The second has a restart maze option.

The first basically makes a random path until it hits a dead-end, then it will restart at the most recent terminus.
exilania.com/tests/maze1.html

The second starts a path then randomly switches to another path that branches from a random node on the currently generated paths.
exilania.com/tests/maze2.html

I think they both have their merits. What are your thoughts? I am leaning towards the 2nd algorithm because of all the false paths it will create.

Both mazes use a digger that has a rule where he can only move into a spot X from spot @ if a pattern is matched:

Code: [Select]

? = doesn't matter
# = wall
X = spot of interest (and is a wall)
@ = current spot
###
#X#
?@?


[Trystan]

I think they both have their merits. What are your thoughts?

Why not use both? Use one 50% of the time and the other 50% of the time. Or one on even levels and the other on odd levels.

[requerent]

It's difficult to comprehend what experience each maze-type provides without testing them first. You need to apply LOS and explore them yourself to get an idea of what is reasonable and not.

[mushroom patch]

It's hard to tell what's going on with your first test thing because you're not using a monospace font (or something). <tt> tags might help with that?

About maze algorithms, ones reasonable way to go is spanning trees: You take a grid, you enumerate its spanning trees, each spanning tree is a maze. I believe there are reasonably efficient algorithms for doing this kind of thing, although I admit I don't know any computationally efficient ways to do it off the top of my head. Another related way to go is to take a grid and assign random weights to its edges, then find the minimal or maximal spanning tree -- this can definitely be done by standard, efficient algorithms. This approach has some interesting possibilities using natural random models for assigning edge weights. It's a pretty controllable kind of thing. You may want to add some extra edges and prune dead ends from a raw spanning tree to get reasonable maps, so there'd be some experimentation to do...

[Mats1]

I would go with the first one. The second one looks like a maze from a (literal) maze game, whereas the second looks a little more 'roguelike maze'.
How easily are these algorithms modified to create rooms in the mazes?

[Kimchi]

I like the first one a lot, actually. I think there's a certain distance you can take false paths, such that it still feels like you're just exploring. If you make them too long, however, then running into those dead ends starts to get annoying, I think.

If you want to make rooms quickly and easily, you could use one of these algorithms first, and then just blank out rectangular regions of the screen to make large spaces. Every room would be accessible this way, too.

[Cruiser1]

Hey everyone! I have 2 different mazing algorithms that I am trying out.
The first basically makes a random path until it hits a dead-end, then it will restart at the most recent terminus.
exilania.com/tests/maze1.html
The second starts a path then randomly switches to another path that branches from a random node on the currently generated paths.
exilania.com/tests/maze2.html
I think they both have their merits. What are your thoughts? I am leaning towards the 2nd algorithm because of all the false paths it will create.

The first algorithm is commonly called "recursive backtracking", because it's stack based and always carves forward until it can't anymore, and has to back up the visited location stack to check previous locations. Recursive backtracking produces long passages with fewer dead ends. The second algorithm which periodically switches to another location to carve from, is a version of the "growing tree" algorithm. Both algorithms produce "perfect" Mazes with no loops or inaccessible locations, that are minimum spanning trees. These Maze generation algorithms and others that might be of interest are described on this page.

The "best" algorithm of course depends on what you want to use the resulting Maze for, and what experience you want the player to have. For example, in a Roguelike dungeon, it's okay to have Mazes with passage loops (which may be obvious doors, secret doors, and such), or "sparseness" in which not every solid area has passages in it.