Generating and Populating Caves

Before this point, the vast majority of Cogmind maps have fallen under the room-and-corridor style generation. The wide range of adjustable parameters, when combined with a variety of themed content (and prefabs!), give that one style plenty of potential to create a unique feel and gameplay for different areas of the world.

That said, roguelikes which combine multiple disparate map generators can do an even better job of presenting the player with new challenges. Check out this compilation featuring some of the map types found in Dungeon Crawl: Stone Soup:

DCSS map generation variety--click for full size, and see here for some descriptions.

Impressive!

With Cogmind, setting, lore, and atmosphere are important to consider alongside pure gameplay variety, so maps are designed to meet multiple goals in those respects, somewhat reducing the possibility for radical deviations. Aside from the 100% machine-built parts of the world, however, there is room for the more natural areas found in the planet’s interior: caves.

Of course, caves bring with them a set of problems different from the original map generator and its associated algorithms. Fortunately the caves also have a very different meaning in terms of lore and gameplay, and lack the “living ecosystem” found in the core areas of the world, so there’s no need to migrate many of those existing systems to fit a new architecture. (Besides, doing so would also lessen the impact of using a completely different map generator in the first place!) Instead, caves are all found in branches, a concept described in the Layout section of this article, and these branches have a different composition and purpose you can read about over there if not already familiar.

For this article I won’t be going into descriptions of content (so it’s mostly spoiler free); we’ll instead be looking at some of the design and technical considerations accounted for with cave generation.

Generating Caves

Regarding the method used to generate caves, I’ve already given an introduction to the randomized cellular automata algorithm. There’s plenty of background information that I won’t repeat here, though at the time parameters were not yet set for inclusion in the world (those were demos created in the mapgen test program), so it’s worth taking a peek at what the cave layouts really look like in game now.

Firstly, know that since release last year there has been one variation of the cave generator at work, in the form of mines:

A fully-revealed mine.

These are basically small square-shaped areas containing sparser caves interspersed by what appear to be dug out rooms linked by tunnels.

The real cave systems are significantly larger, and because individual caves have more room to expand, they’re more likely to generate a few extra nooks and crannies.

A fully-revealed cave map, without content. Overlay insets show major loops and flow paths.

For reference, I drew overlays demonstrating the relatively linear overarching flow structure (despite being caves) here, and the primary loops here. There are definitely loops available for tactical purposes, but generally fewer than you’ll find in other areas of the world--this could have a strong impact on strategy for some players. Overall the linearity-with-loops design should work together to keep the map from being too linear, while still doing away with boring backtracking. (And of course the player is free to create their own loops by destroying walls where convenient :P)

Again, if you want to read more about the principles of connectivity, looping, and guided generation as they apply to the algorithm, check out the introductory article. Here I just wanted to show an example of what a real cave layout looks like now that they’re in the game. It’s still possible the parameters will be further tweaked depending on how content generation goes, which is a work in progress. You’ll also see below that the layout itself may in some cases be altered by content.

Populating Caves

While the system behind procedural cave layouts themselves was worked out back in 2014, the first stage of content generation wasn’t added until last year.

This was in the form of “encounters,” wherein caves (analogous to rooms in room-and-corridor maps) each have their own content pulled from a pool of available encounters that themselves generally fall into one of four categories: fluff, rewards, risk vs. reward, and danger. The encounter system was described in more detail towards the end of the map composition post.

As a reminder, here’s what a potential encounter distribution scenario might look like in a mine:

A mine with distributed encounter types marked with their associated category color.

So this is a feature which has been in use to populate other branches, and also even cave maps in the form of mines. But mines are relatively small and contain a fairly narrow selection of simple encounters, thus they didn’t really need support for prefabs which allow for a wider range of unique (but still dynamic) content to be added fairly easily. Truthfully, there wasn’t enough time to implement cave prefabs before launch in 2015, either, so that also played a role--mines use a bit of hardcoding instead.

Full-size caves, of which there are also many more than mines, will need better encounters. And certainly more encounters. These are areas that prefabs can really help since hardcoding content is a slow error-prone process, and scripting support for encounters has expanded greatly since first described, while adding multiple features for prefab content in other branches.

So the last thing really needed here is prefab support in caves. Well, caves have had prefab support, just not encounter prefab support--the more important and versatile kind.

There are actually two methods of adding prefabs to Cogmind maps. One is integrating them into the cave generator itself, which isn’t even a part of the game engine (i.e. it can be run without Cogmind at all), and by nature this one will be somewhat limited in what it can do because it places prefabs before the caves are even generated. Thus these prefabs would be meant to serve a central role on the map, e.g. a huge and defining static area, or special entrances/exits. Relying too heavily on this type of prefab will result in maps becoming too repetitive and familiar over time, as it’s not a very flexible system (at least not without a ton of extra work for each new map). It’s more efficient to add a majority of cave prefabs through method #2, the encounter system.

The problem: How do you integrate static prefabs with a cave map that’s already been generated?

Prefabs themselves have a defined shape, one that we obviously can’t change to fit the surroundings, so the only option is to terraform the caves as necessary to accept a prefab. This must be done without having a negative impact on cave connectivity, and also in a way that looks good, and doesn’t cause some other manner of chaos :P.

I’ve currently added two methods for prefab-cave integration. And hopefully two will be enough (hardcoded encounters pick up the slack in terms of highly unique content, or those that are more free-form and able to fit into any cave without disturbing its natural structure).

Centered Prefabs

The most easily implemented cave prefab is very intrusive, simply dropped onto the geometric center of its parent cave. (Remember that here I’m referring to “cave” as a single cave-room, just one of many caves that make up a single cave system map.) Here’s an example of a prefab outpost plopped right into a rather large cave:

Geometric centering of an outpost in parent cave.

Notice that the outpost’s territory completely overwrites both the closed and open areas that were under it, and includes an open buffer zone around it as well. Intrusive, but it gets the job done here.

I chose to center a prefab over the geometric center of its cave (meaning a position that gravitates towards that largest open areas of that cave) in case the parent cave has a big open fat area to one end and a long protrusion headed off in the opposite direction, in which case its geometric center could be some distance from its simple coordinate center. In such a situation, using the latter would be more likely to break one of the few rules governing this type of prefab placement: Prefabs are allowed to overlap any earth and the parent cave itself, but not other caves.

One of the current limitations on centered prefab design is that they must be rectangular, though I might remove that restriction later if it becomes annoying at some point. Organic/rounded centered prefabs have their thematic uses, especially in caves, though technically this can be faked under the current system by rounding corners in the prefab and simply leaving a little more open space at the corners where it integrates with the map.

Here I should remind readers that prefabs are not static (unless I want them to be :P)--most come in variable layouts, and also have randomized content, so there’s plenty of variety even for a single encounter type. This leads to unexpected roguelike fun for new players (“hey I remember this place from last time, there’s a helpful friendly robot inside--OMG WHAT’S SHOOTING ME”) while also being designed to provide strategic challenges for experience players (“there is definitely useful loot here and I can take the usual guards, but is it worth the small chance of possibly being ambushed by a larger force?”).

As mentioned a few times before with regard to world structure, branches are meant to be the less predictable areas of the world, compared to the main complex where there are plenty of procedural-driven systems at work, but they’re relatively consistent and predictable for the experienced player. This offers two different types of major areas you can bounce back and forth between as necessary (or desired). In terms of design, prefabs are the key to “custom” content available in branches, so it’s important to get them right :)

Embedded Prefabs

This one was more complicated.

There needed to be a way to add prefab areas that are not nearly as intrusive, for the more common cave-like situation where you have interesting encounters off the main path in some side area, or at least not right smack in the middle of a cave. This meant there needed to be a way to excavate areas for prefabs off the edges of existing caves. And that meant there needed to be space to do that excavating, and a way to efficiently locate that space…

As you can see in the full-size cave image further above, caves are fairly tightly packed in. So my first thought, in order to vastly increase the amount of earth (diggable area) between caves, was to do cave generation in two phases: a first phase uses a cellular automata-like process to define cave-shaped blobs which are marked off limits to digging during the regular mapgen process, then do the normal process, which would automatically avoid the natural “pockets of earth” formed from phase one. These pockets would then be available for latter digging out by encounters for their prefabs. As promising as it sounds, the more useful this approach (i.e. more pockets), the more it would have a broad impact on the caves as a whole, lengthening corridors and increasing the amount of space between individual caves, regardless of whether there were any prefabs inserted. This solution felt a bit too extreme.

There’s a much easier alternative that doesn’t compromise the integrity of the existing cave designs: Simply expand the diggable area around all the outer edges of the map so at least those are generally valid directions. Now there’s plenty of area to dig! Then comes the next step: Where exactly do we start digging? This is really easy to do by eye--we can immediately see ideal places to dig out little areas, but in the code caves are just numbered areas with a list of their internal coordinates. So at this point it was a matter of figuring out the smallest set of rules that could search for applicable locations and satisfy all conditions and potential layouts when trying to excavate areas for prefabs.

I spent two hours figuring out a workable set of rules.

The final rules are very brute force, but they work so let’s go with them :D

Steps to embed a prefab in a cave wall.

1. Select a random prefab for a given encounter, and rotate it to face a random cardinal direction.
2. Pick a random open cell in the cave, intended to be one front corner of the prefab’s location. Then based on the length of the front face of the prefab, locate where its opposite corner will be. If the second corner is not inside the cave, keep trying with different points.
3. Measure the distance along the imaginary sides of the prefab until it hits a wall.
4. Every prefab has a manually set “maxProtrusion” value, a restriction on the amount its depth is allowed to protrude into its parent cave. If the distance measured on either side exceeds the maxProtrusion value, push the corners back towards the wall until both distances are within that value. (If there is no distance at which the protrusion value can be obeyed on both sides, which might happen with a combination of small protrusion threshold and highly uneven/diagonal cave edges, go back to #2.)
5. Check the validity of the prefab’s target area: The “outer rectangle” cannot contain any stairs (since it would overwrite them) and the “inner rectangle” can only be earth--not even open cells from the same cave are allowed, since it would allow unexpected/unpredictable alternative entrances to the prefab area.
6. Also ensure there is at least a 1-cell-thick wall of earth around the sides and back of the inner rectangle (i.e. not immediately touching some other open cave or prefab area), for the same reason indicated in #5.
7. Place the prefab on the map! Then convert to wall any earth cells around the outer edge that are adjacent to open prefab space.
8. Add objects as per the prefab’s definition, like… a terminal that allows you to access a door and collect a cache of nice launchers someone so considerately left here :D

If no valid area was found in the current cave within a certain threshold of tries, try with other random prefabs for that encounter, and if that still doesn’t work, start over with another cave. (Encounters are chosen first, so the goal is to find a valid place for that encounter.)

Unlike centered prefabs, embedded prefabs can be non-rectangular since their sides and back edge are guaranteed to be against earth, meaning they can have a built-in cave-like appearance as in the example above.

The above diagrams were drawn in REXPaint. Here’s a shot of a real prefab generated in game:

Sample embedded prefab in game.

Time to make some more prefabs!

Update 1/11/2017: Regarding prefab integration into room-and-corridor style maps, see the newer article Map Prefabs, in Depth, which also explains the elements that go into constructing an individual prefab itself.