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.
Evil Science
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:
Connectivity
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.
Tunnels connecting individual caves.
Guided Generation
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):
Flow path of a square cave map.
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.
Caves made fun with guided cellular automata.
This way we can continue to use the sharp spiky style with longer offshoots but keep everything moving in the same general direction.
Mines
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.
Mines have a higher number of connections and loops.
Composite Maps
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.
A hidden base?
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.
RSS (posts)
Mastodon
Patreon
Discord
/r/Cogmind
Indie DB
6 Comments
I just want to say that your work and design are amazing. My friends and I love reading your blog posts just for the delicious thought process and I have been steadily building up excitement for Cogmind’s release. Thanks for being so open with your development process!
Thanks for reading! Small-time indies need to rely on building up that interest over the long term in place of a normal marketing campaign, so… sorry for baiting you ;)
Good that there’s some useful stuff to be said in the meantime. I’m trying to avoid writing too directly about the content itself in order to avoid spoiling the game for all the people following along, so I’m having to write a bit tangentially as development progresses further into the stages where everything’s coming together to create the final, whole product. (And this last one is the longest stage by far :/)
I’ve got a lot of other ideas brewing for after this series, probably starting with another more specific map and machine-related post or two since that’s what I’m working on right now. Among the others are general posts about gameplay, robots, roguelike time systems, a preview of the world, story, an overview of fonts, some more art…
This is an interesting modification of the standard algorithm. I would be interested in further extending the idea in the following way. Rather than pick vertices at random to apply the automaton rule to, with the random probability uniform across time and the whole canvas, one could pick a particular probability distribution over the canvas and sample cells to apply the rule to according by drawing from the distribution. The distribution could further change over time, perhaps adaptively preferring dense regions on line segments between sparse regions so that tunnels connecting caverns would naturally emerge.
The idea is that since automaton rule generally reduce the number of living cells (by smoothing), a biased distribution would produce something more like open regions that are smoother in the middle, and rougher as they move outward. It’s the “clearing in the forest” idea, or for caves a clearly central cavern with cracks and rough crevices branching out.
Anyway, it’s an idea :) Neat post!
That sounds like a pretty cool approach, and a way to achieve the “growing” of connections I was talking about, thanks for adding that. Doing so would be somewhat more processing intensive, but it’s definitely suitable for creating even more realistic caves. In the case of Cogmind I prefer the “unnatural” tunnel-like connections because areas that use this generator are not unadulterated caves--they’ve been modified by inhabitants, a change which the existence of tunnels can reflect.
If the goal is to make the connections more “cave-like”, a faster option would be to instead perform a post-processing pass that slightly expands only the tunnel sections via automata. All speculation since I’m not actually testing these methods--must stay on track to actually finish this thing one day ;)
How does the “guided cellular automata” work?
Ah sorry that could’ve been a lot more clear xD.
In the image you see in the post above, notice the empty rectangular spaces in the bottom-left and top-right corners. The generator is forbidden to do anything with those predefined areas, hence the resulting overall shape. You can make these blocking rectangles (or other shapes!) static, or even have their dimensions and locations somewhat randomized for greater variety. In any case it reduces the number of open cells and essentially “guides” the automata system by keeping it within a desired area, rather than occupying most of a rectangular map, as you see with most CA-based map systems in roguelikes.