Unlike the 7DRL, which only spanned a 10-level “main dungeon,” Cogmind will cover a much greater area. Naturally a larger world needs a greater diversity of regions to explore. Taking place underground, many of the outlying areas tend to be caves, and for that cellular automata are usually the best choice for generation.
I say that but I’m actually not going to use the standard application of cellular automata. (Read about the standard process here, here, or here; I won’t be explaining it in detail.) Instead I kinda fell in love with a related idea described by Andy “Evil Scientist” Stobirski over on his blog earlier this year.
His method still relies on cellular automata in that you apply adjacency rules to open and close cells organically, but instead of repeatedly applying the rules across the entire map at once you pick cells at random. (Hey, we make roguelikes and we like random, so random it is!)
Performance-wise I believe that once fully optimized Andy’s method is faster than the standard method for achieving comparable results, and it’s a lot more versatile in terms of what it can do. I don’t have a lot of experience fiddling with cellular automata, but the few times I tried it was somewhat difficult to tweak for good results. This method produces good results with ease. “Good” is of course relative, but what I was looking for wasn’t quite available with vanilla cellular automata. I need more variety, and the flexibility of this method makes producing a variety of nice maps a simple matter. I’m sure variety can be coaxed out of cellular automata (via switching rules partway through generation), but it won’t come as easily as these did:
I like how in many maps the random distribution of rule application creates variety even within the same map, in the form of a mix of sharp and round, large and small areas.
One of the variables you can tweak using this method that is not normally adjustable when using cellular automata is the number of cells randomly visited, which is where some of the additional variety comes in. Lowering the number of applications will result in some rougher maps, but a final smoothing phase can still operate on that and get some interesting results:
As with any cellular automata-based procedural map generation, connectivity is an important issue to consider. If there’s no way to travel between multiple disconnected areas on the map, then the extra ones may as well not be there. In that vein one solution is to remove unconnected areas entirely, but that doesn’t work with certain cave styles because there will naturally be many disconnects resulting from algorithms used to achieve thinner “sprawling” styles (as opposed to big blobs).
The better solution creates new connections to reattach those areas. One possibility is to “grow” some areas so that they reconnect with others. Another is to dig tunnels between them. I prefer tunnel connections because they 1) fit the style and theme I’m going for, and 2) allow a cave system to consist of many smaller caves that can be individually identified as “rooms” for purposes of object placement (this advantage will become apparent in the next post on dungeon metrics).
My solution here varies a bit from Mr. Evil Scientist (mostly since I’m delving into the specifics of applying it to a game while he was building a more generic generator). Mine removes most pointless U-bends, goes through multiple corridor-digging phases that may not apply to all caves, has an adjustable ratio of cave-spawned corridors vs. branching corridors. and sometimes chooses to dig wider tunnels based on both set parameters and the relative size of caves being connected.
Cave maps in Cogmind won’t be as large as the main dungeon maps introduced in the previous post, but even then smaller square cave maps tend to simply not be very fun to explore, at least in the disconnected style I’ve chosen to go with. Taking the above map as an example (that’s one of the styles I’m currently planning to use):
Assuming we’re not putting a meaningful destination at the end of every dead end, the above map will require a lot of backtracking, and even if more tunnels are dug to turn it into a more intricate web of connections (enabling more loops), the map really won’t be too fun to explore due to a fundamental difference between caves and normal dungeon maps: The rough edges are filled with nooks and crannies that you have to fully explore to make sure you didn’t miss an important pathway.
In a normal dungeon with flat walls and rectangular rooms you can quickly scan the entire visible area and be relatively sure of where there is and is not a valid path. In caves you can’t be sure you haven’t overlooked something until checking everything out up close. That gets tedious, more so when you weren’t headed in a certain direction in the first place.
The solution is “guided” cellular automata. Let the generation play out as normal, but enforce a general shape that the cave must fit into, such as the narrower corridor seen below.
This way we can continue to use the sharp spiky style with longer offshoots but keep everything moving in the same general direction.
Another variation on this algorithm will be used for mines. These are generally smaller maps where you have rectangular areas dug out for processing machinery and storage purposes, as well as the actual mined areas connected to them via corridors.
Who said a single algorithm has to control an entire map? Some special areas could very well combine cellular automata and the tunneling algorithm for special cases.
This is the third in a five-part series on procedural maps:
- Part 1: Procedural Map Generation
- Part 2: Tunneling Algorithm
- Part 4: Dungeon Metrics
- Part 5: Dungeon Prefabs
Update 3/16/2016: I’ve since written Generating and Populating Caves, giving a more comprehensive overview of how caves are actually created and used in Cogmind.