{"id":798,"date":"2014-07-04T15:37:01","date_gmt":"2014-07-04T07:37:01","guid":{"rendered":"http:\/\/www.gridsagegames.com\/blog\/?p=798"},"modified":"2014-09-09T21:52:56","modified_gmt":"2014-09-09T13:52:56","slug":"dungeon-metrics","status":"publish","type":"post","link":"https:\/\/www.gridsagegames.com\/blog\/2014\/07\/dungeon-metrics\/","title":{"rendered":"Dungeon Metrics"},"content":{"rendered":"

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.”<\/p>\n

Requirements<\/h1>\n

First and foremost we have to check if we even want<\/em> 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.<\/p>\n

Composition<\/h2>\n

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.<\/p>\n

\"map_metric_openness\"<\/a>

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).<\/p><\/div>\n

Another important requirement to consider controlling for is the number of individual rooms\/caves of varying sizes.<\/p>\n

\"map_metric_roomcount\"<\/a>

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).<\/p><\/div>\n

Pathfinding<\/h2>\n

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).<\/p>\n

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.<\/p>\n

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.<\/p>\n

Etc.<\/h2>\n

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.)<\/p>\n

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.<\/p>\n

\"map_metric_monochrome\"<\/a>

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.<\/p><\/div>\n

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.<\/p>\n

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.<\/p>\n

Records<\/h1>\n

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.<\/p>\n

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.<\/p>\n

\"map_metric_floodfill\"<\/a>

Locating caves in a map via floodfill before connecting them.<\/p><\/div>\n

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.<\/p>\n

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.<\/p>\n

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.<\/p>\n

Analysis & Application<\/h1>\n

So what do we do with all this collected data besides decide whether to throw away a map? The obvious application is object placement.<\/p>\n

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?”).<\/p>\n

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.<\/p>\n

Connectedness<\/h2>\n

My favorite analytical tool for cave systems is the relative connectedness of each cave.<\/p>\n

\"map_metric_connectedness\"<\/a>

Visualization of cave connectedness, where brighter caves are better connected to the system.<\/p><\/div>\n

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<\/em> 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.<\/p>\n

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.<\/p>\n

At the other end of the spectrum, well-connected caves are where most enemy activity will probably be concentrated.<\/p>\n

Seclusion<\/h2>\n

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).<\/p>\n

\"map_metric_seclusion\"<\/a>

Visualization of room seclusion, where darker red rooms are further from the quickest routes across the map.<\/p><\/div>\n

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.<\/p>\n

This is the fourth in a five-part series on procedural maps:<\/em><\/p>\n