Labyrinth generation

[volos314]

Do you now any ways to generate "original" levels?
I've implemented a kind of different maze in my game, but I need some more algorithms. I think it's important to create levels with various design, that's why I strongly need more maze-gen algorithms.

[Grue]

You can try cellular automata algorithm (never seen this one put to good use). If you take the Game of Life and change the parameters (when cells die and appear) you'll get stable maze-like structures. I don't remember the right parameters off the top of my head, but you can play with various freely available Game of Life simulators to find them.

[Slash]

You can try cellular automata algorithm (never seen this one put to good use).

What??? CvRL and Drash use cellular automata

Maybe their maps arent that good

[Grue]

I wasn't aware of it. Pretty cool!

[Slash]

I also forgot to add ZeldaRL, which uses the most complex cellular automata of all them; it isn't used for labyrinths or caves but rather for the overworld... ending up in something like this: (although this one is a bit outdated)

[stu]

I use CA in Cracks and Crevices and also in Fishguts.

[Slash]

Fishguts??

[stu]

Fishguts??

the name of my normal CRPG well it was just a codename but I havnt been able to think up a nice 1 or 2 word name

[Gamer_2k4]

Does it have to be a maze?  I have a pretty decent generator that makes good caves using a raycasting technique.

[Rabiat]

Sorry if I'm stating the obvious, but maybe this could serve as a starting point for those who are unfamiliar with maze generation. Here are some widely used, basic techniques to create mazes:

• Rogue style: horizontally and vertically divide a map in sections to guarantee there's no overlap, build a room in each section, then dig tunnels between the rooms. (This is the technique used in e.g. Rogue and Biskup's QHack)
• Recursive subdivision: start by dividing a clear map in two halves, or four quarters, using walls. Then subdivide each room in the same manner, and continue until all rooms are small enough. (This is the technique used in e.g. Alphaman and DoomRL)
• Overlapping shapes: fill a map with rock tiles, then dig out shapes (circles, crosses, or L-shapes) at random locations, making sure that at least a single tile overlaps with a previously dug out tile. (This technique produces results similar to e.g. Dungeon Crawl's Lair branch)
• Prim's/Kruskal's algorithms: fill a map with rock tiles, then dig out 1x3 sections, making sure each section overlaps with a single previously dug out tile. This creates a perfect maze, i.e. one that has a single path from one point to another. (Doesn't occur in any RLs that I know of)

These are just basic approaches, and each requires some postprocessing to create a playable Roguelike map. By themselves, none of them will produce nice NetHack or Angband style maps. Recursive subdivision doesn't create twisty tunnels, Prim and Kruskal don't make rooms at all, and the 'overlapping shapes' technique doesn't create very nice rooms or tunnels, just a roughly hewn cave. The advantage of all techniques is that they can be used to guarantee connected mazes (i.e. with no unreachable segments).

I've always liked perfect mazes as a starting point, but they involve lots of postprocessing. Creating loops in tunnels, filling up dead ends to free up space for rooms, inserting doors at appropriate places, etc.

Here's a couple of references I'd recommend:

• Maze generation algorithm article on Wikipedia, covers Prim/Kruskal and recursive subdivision.
• Think Labyrinth extensive list of generation algorithms, hoewever not geared toward RLs.
• Random Dungeon Design article for Jamis Buck's D&D level generator covers the gap between standard maze generation algorithms and playable maps.
• Edit: and of course Map articles from Roguelike Development covering many aspects of RL map design and implementation.

I'd be very interested if anyone knows more techniques or references.

[Gamer_2k4]

Prim's/Kruskal's algorithms: fill a map with rock tiles, then dig out 1x3 sections, making sure each section overlaps with a single previously dug out tile. This creates a perfect maze, i.e. one that has a single path from one point to another. (Doesn't occur in any RLs that I know of)

The minotaur mazes in ADOM use this approach, I believe.

I'd be very interested if anyone knows more techniques or references.

Dungeondweller has several articles about this sort of thing, as well as many other aspects of roguelike development.  Most of the articles have probably also been transferred to RogueBasin.

[Rabiat]

You can try cellular automata algorithm (never seen this one put to good use).

There's an article on RogueBasin with some nice examples: Cellular Automata Method for Generating Random Cave-Like Levels.

[Lummox JR]

Whoa, I hadn't seen RogueBasin before. I've been to roguelikedevelopment.org--it's one of my favorites--but this is so much neater and more readable. Quite cool.

That cave article is a good one. Too bad the math symbols are lost to character formatting hell instead of using HTML entities, though. I never had much luck with the cave tests I tried before using the cellular automata technique, but this one looks very promising!

I like the idea of starting with an almost-connected cave and then completing connections as corridors that were dug into the main cave by past denizens. Some would lead to special rooms (like a monster's lair, treasure vault, etc.) as seen in those results, others to another wide cavern system, perhaps some ancient bazaar now an abode of monsters.

[Slash]

Well, nice you found roguebasin... lots of info there!

About the Cellular Automata Algorithm, it sure is good for caves, but hey! there are lots of other uses for it, including post processing of fractal generated overworlds... basically. anything you need to make look organic following an example pattern

[Lummox JR]

I kind of wonder if cellular automata would be good for forests as well, if it was modified to use some random rules. They follow a similar pattern after all. For instance, this might do nicely:

If no tree here
  If trees in radius 3 < 4
    If random(25%)
      Create tree
Else
  If other trees in radius 2 > 1
    If random(25%)
      Delete tree

A pattern of radius 3 is roughly 37 tiles, so 4 in 37 gives roughly 11% coverage, while the second rule is used to remove neighbors that are too close. There should still be plenty of cases of trees growing right next to each other, which is common, but not too many dense clumps.