Rarely will an algorithm produce a perfect procedurally generated map, and even if it does, some degree of post-processing will still be necessary to analyze the layout. When we look at a map produced by a generator, we can determine pretty quickly whether or not the layout is sufficient for our purposes; we can also see likely bottlenecks where enemies might gather to stop the player, or areas considered “out of the way” that might hold more treasure. In the program, however, a map is nothing but coordinates telling us what each space represents, giving us no hint as to its overall composition and layout. How do we teach a game to understand and use the map as we do? We need “dungeon metrics.”
Requirements
First and foremost we have to check if we even want a given map. Without any constraints on the results, the same algorithm can produce a wide variety of layouts, some of which are either not what we expect or downright unplayable. In those cases we’ll want to throw out the map and try again.
Composition
The most basic requirement is the final amount of playable, or “open,” space. A lower bound ensures the map isn’t too sparse, while an upper bound keeps it from being too open.
These two caves were generated using the exact same algorithm, differing by only one parameter: the amount of open space required (15~30% on top, 40~60% on bottom).
Another important requirement to consider controlling for is the number of individual rooms/caves of varying sizes.
These two maps were generated using the exact same algorithm, differing only by the number of rooms required (20 or more small rooms on top, at least 20 medium and 5 large on bottom).
Pathfinding
Some games use precalculated map data to optimize pathfinding, but that’s not what I’m referring to here (it’s also not too useful in Cogmind due to the completely destructible environment).
Pathfinding is an important part of map analysis since you have to ensure it’s possible to reach one or more exits from the entrance of a map. This won’t be an issue for cellular automata assuming the final tunneling phase is doing its job, but tunneling algorithms constructing maps with more than one tunneler must confirm that the tunnelers did eventually meet and join their respective creations.
Another possible requirement pathfinding can enforce is a minimum distance between entrances and exits. If too close together much of the map area remains unexplored, an especially relevant issue in Cogmind because there is no XP system--the best reward (“evolving”/leveling up) comes when you find the exit. Having an exit too near the entrance would be poor design in this case since there’s little incentive to stick around.
Etc.
An alternative to automating the selection process is to use procedural generation but hand-pick the set of maps that are actually used in game. This works, but ultimately limits the pool of possibilities to the number of maps selected by the developer. (Nonetheless some games out there do use this method.)
Whether selecting maps for final use or simply to trying to improve an algorithm, it can help to have multiple ways to look at the same map. For example a monochrome view is useful for checking available play space and overall layout without being distracted by a map’s individual parts.
The normal view on the left is nice for clearly identifying size and positioning of caves, but the monochrome view is the purest representation of playable vs. non-playable space, and is closer to what the player will see and experience.
See the previous two posts for images showing individual highlighting of tunnels, caves, rooms, junctions, “halls,” etc. Those are not processed images--the debugging features of the map generator itself include many such views to aid development.
Another tip for more efficiently addressing issues during development: Always have the generator output the random seed used to generate each map (I have mine added to an ongoing list). That way you can always feed the seed back into the generator to repeatedly generate the same map and find out what went wrong or how the algorithm could be improved.
Records
Once you’ve decided to keep a generated map, there’s still plenty to be done. It’s time to analyze the content and layout to record what useful info we can.
The simplest component we’ll want to remember is where all the rooms/caves are located. Rooms (and corridors) dug by tunnelers are easy since we built them in the first place--just record as you go. Caves are a different story since they were grown randomly. To find them we just scan the map with a standard floodfill.
Locating caves in a map via floodfill before connecting them.
Herein lies another advantage of allowing cellular automata to create many disconnected caves then reconnecting them during post-processing: The caves are naturally separated into discrete “rooms” for you by the algorithm! This means we’ll later be able to take advantage of any of the methods of analysis that work on normal room-and-corridor dungeons. More on that later.
Location and size are not the only important information that could come in handy when deciding how to use different parts of the map. We can record doors and which direction they face (used for optimizing some types of pathfinding, or setting up ambushes), which rooms and corridors are attached to each junction, which tunnels are linked to which cave(s), and which caves are directly accessible from another cave. My favorite piece of data that I’ll be discussing further below is relative seclusion/connectedness.
General statistics collected from the final map may also affect what you decide to do with it as a whole, data like the percent composition by cell type, maximum and average seclusion of areas, the largest individual hall/cave, etc. These could of course be used as additional requirements to filter out unwanted maps.
Analysis & Application
So what do we do with all this collected data besides decide whether to throw away a map? The obvious application is object placement.
Robots and parts in the 7DRL were spawned without regard for whether an area belonged to a room or corridor; you could find a stockpile of parts sitting anywhere out in the open. It would make more sense to store most of those in rooms, both for realism and from a gameplay point of view (“do I open that door to search for parts even though my scanners show robots on the other side that may or may not be hostile?”).
As mentioned before, corridor junctions are likely to contain terminals, and large halls will contain bigger machines. Guards are more likely to patrol intersections. Choosing the best locations would be difficult without first recording details about the map layout.
Connectedness
My favorite analytical tool for cave systems is the relative connectedness of each cave.
Visualization of cave connectedness, where brighter caves are better connected to the system.
Because the number of direct cave connections alone is less meaningful in many scenarios, I define “connectedness” as the number of immediately connected caves plus the number of caves those are connected to as well. Notice in the above visualization that outlying caves are shaded darker, representing a lower connectedness value.
Less connected caves in different parts of the map are likely positions for entrances/exits, and others are good candidates for placing loot, secrets, or perhaps nastier surprises for nosy explorers.
At the other end of the spectrum, well-connected caves are where most enemy activity will probably be concentrated.
Seclusion
For maps created by the tunneling algorithm, all rooms are rated by their “seclusion” value. Seclusion uses different calculation criteria than cave connectedness since map connectivity is much higher. Instead it’s based on the distance from the fastest path the player can take between an entrance and the exit(s).
Visualization of room seclusion, where darker red rooms are further from the quickest routes across the map.
The four entrances/exits (pink dots) are connected by the most direct paths between them (green lines), then the entrance to each room pathfinds to the closest point on any of those lines. Notice that the further a room is from a path the darker its shade of red. (For purposes of the visualization any room with below average relative seclusion, where “average” is based on the map values, is not shaded.) The more secluded a room, the more likely it will hold something of value or interest to the player. Of course this idea of “seclusion” assumes the player knows where they’re going when they may very well not! But that’s okay, because the player deserves a little something for having traveled so far out of their way, and having overcome whatever obstacles they had to in order to arrive there.
This is the fourth in a five-part series on procedural maps:
- Part 1: Procedural Map Generation
- Part 2: Tunneling Algorithm
- Part 3: Cellular Automata
- Part 5: Dungeon Prefabs
RSS (posts)
Mastodon
Patreon
Discord
/r/Cogmind
Indie DB
11 Comments
Ohhh. I can’t wait to play. This is all turning out amazing. I still can’t believe this started as a 7drl.
Thanks! Heh, every game starts with a prototype (or should, anyway!). 7DRLs are a great way to prototype since they force you to finish in a short time. Of course, I spent a good month or two planning the 7DRL before even starting, so it all came together a more nicely than most ;)
No problem! That’s a very good point, I’ve just become used to the idea that most 7DRLs stay as exactly that.. a 7DRL (usually no updates after, and if so only a minor bugfix one)
I’m still really happy to see this getting the full treatment because it is an amazing (and unique) idea. I’m admittedly spoiled by free roguelikes but I’ll gladly pay once it’s out. :)
It turned out to be a pretty fun game, and an idea worthy of further development. A few other well-regarded roguelikes started out as 7DRLs, too: Brogue, Hoplite, and I’m sure more.
Many of the best roguelikes are free. I envy people who have all that extra time to devote to fun hobbies like that (my former self included =p). I totally wish I could just release Cogmind for free, but without any revenue I couldn’t justify the amount of time it’s taking to develop it. Assuming I worked on Cogmind only in my spare time and couldn’t consider it “work”, it would probably be done some time in 2020. Fortunately we won’t have to wait that long! Glad to hear that many people are willing to support it, and I promise it will bring a huge amount of value to the table compared to your average roguelike, so it should be worth it.
That’s true.. and Brogue is another one of my favorites.
I’ve been following the project for awhile and I definitely have no doubts that it’ll live up to my expectations if not pass them entirely. So no worries there, paying isn’t an issue.. even if it was free I’d want to donate anyway. :P
This looks fantastic.
Do you worry about the paid-for model reducing the odds of this going hugely popular? About the only ones I can think of which charged for the game have been heavily on the accessibile end of the market -- dungeons of dredmor, ToME (Which is donation-able rather than priced, but also relatively straightforward dungeon murder)
(Hi! The RPS devlog sucked me in. Love the analysis you give of the work here…)
Thanks, and that’s a good question.
I think any game good enough will naturally be popular regardless of the model, though I somewhat doubt the possibility of “huge” popularity in this case anyway simply because it’s a fairly niche game with a small target audience. (Smaller than ToME, definitely smaller than Dredmor, while also a bit different from both.)
I would certainly be more worried if I was making yet another fantasy roguelike or pixel art RPG-ish game. There are so many samey games out there that don’t do enough to innovate, while Cogmind as a whole is offering an experience that doesn’t exist yet. Once complete there will be nothing comparable on the market, making it a bit easier to justify the pay model.
I would also be more worried if I was making a significant monetary investment, which I’m not. (Aside from the investment of time, of course, which is technically money but I’m willing to work for much less if I can make my dream games, you know? ;)
Honestly, I started out preferring to try a donation model for developing roguelikes, but then discovered that as of a few years ago my country no longer allows donations to individuals (only registered non-profits), so the only way I can financially support development of the game is to actually sell it as a product. The alternative would be to work on it only as a hobby and release it for free, but that would be a pretty long wait. I’m getting a lot done now, but only because I can work on it full time, and only because that work will supposedly pay off in the end.
I guess that’s how life works in general--you make the best of whatever situation you’ve got! And in the case of game development, personal factors can lead different devs to take different routes.
Glad to have you aboard Reiver!
Hmm, reading back through these entries after the game’s at alpha 4, now I’m wondering: can you generally assume that if you’re finding awesome stuff that you’re pretty far from the exit? Or is this mechanic not used that directly in the current game? :3
Nope, not used that directly. You can just as easily find cool stuff right around the corner from your starting point :D.
I discussed it here as an optional feature for map design, and I do take advantage of so-called “seclusion” ratings in certain parts of the algorithm, but not for item distribution. Of course, if you find a big old locked door, or an obviously well-guarded area, you can be fairly confident there’s some kind of reward there.
(I moved your comment to this post on metrics, because I’m pretty sure this is what you were referring to rather than prefabs.)
Very interesting stuff. How did you actually implement the calculation of the seclusion value for each room? Off the top of my head, I can think of either floodfilling from each room and keeping count of the steps taken until the path is hit, or doing A* from the rooms into each path tile. It smells like there could be a good solution by using dynamic programming…
Ah, we could definitely use a few more details there :D
The room entrances are of course stored during generation, so we have that info, and the lines between each entrance/exit are all mapped out via A*. During that process, every 20th point on the inter-stair lines is saved. Then, as you’re thinking, it does a floodfill from each room until it hits any of the extracted line points, recording the distance it took.
The reason it only uses every 20 is that’s a close enough approximation for this purpose, plus literally doing it for every point on the lines would be both a waste of time, and is actually way too slow on large maps anyway! I found 20 to be a good number for this style of map. Plenty fast.