Official development blog

Procedural Map Generation

17 Flares Filament.io Made with Flare More Info'> 17 Flares ×

Procedurally generated maps are a core feature of roguelikes. For a genre that is almost synonymous with “randomness” (within reason), randomized maps are the easiest way to broadly manifest that key element since maps affect many aspects of gameplay from exploration strategy and tactical positioning to item and enemy locations.

Notice how walkthroughs for strategy games need only mark key locations on an overview map and indicate what to do where--you can win every time by following that series of steps. While players can enjoy having multiple attempts to solve what is essentially a glorified puzzle, no matter how fun the game is it will come to an end once all the solutions are found.

So randomized maps give us infinite replayability by providing different challenges every time, not to mention the extra satisfaction from overcoming less spoilable challenges where player progress is measured by personal skill rather than trial-and-error. That the layout of every new map is 100% unknown also lends a good amount of suspense to exploration.

Of course the benefits of procedural maps are pointless without sufficient variety in mechanics and content to make multiple playthroughs worthwhile--the same old hack-and-slash affair won’t do. Hence any roguelikes that survive the test of time will have deep gameplay, too.

Lately I’ve turned my attention to Cogmind’s map generation, so here begins a series of posts on the topic.

Methods

There is a wide variety of methods for generating maps. Naturally no single method is suitable for all purposes, thus most developers will end up tweaking whatever method(s) they choose to fit the needs of their game more closely. Of course designing a method from scratch is also possible, though conceptually a few of the common ones are a good place to start exploring the topic.

There’s no need to go into implementation details here since that’s already been done all over the web; instead I’ll just link to the source of each image where you can find an explanation.

BSP Trees

BSP trees can be used to create some of the simplest and most immediately recognizable roguelike maps--rectangular rooms attached to one another by corridors.

mapgen_bsp1

BSP Tree, Example 1 (source)

mapgen_bsp2

BSP Tree, Example 2 (source)

Tunneling Algorithms

Tunneling algorithms dig corridors and rooms out of solid terrain, much as a real dungeon architect might. Except for the often useless or redundant pathways…

mapgen_tunneler

Tunneler Example (source)

Drunkard’s Walk, a highly-randomized tunneling algorithm, is useful for creating cave-like environments with a mix of open and narrow areas.

mapgen_drunkard1

Drunkard’s Walk, Example 1 (source)

mapgen_drunkard2

Drunkard’s Walk, Example 2 (source)

Cellular Automata

Cellular automata are great for digging natural-looking cave systems. Unlike other methods you have to find a way to ensure connectivity in a post-generation phase, since certain algorithms are likely to produce disconnected areas.

mapgen_automata1

Cellular Automata, Example 1 (source)

mapgen_automata2

Cellular Automata, Example 2 (source)

As you can see from the types listed above, what I’m really talking about here is procedural dungeon generation. Most roguelikes take place beneath the ground, which makes sense from a design standpoint. The highly random nature of roguelikes means it’s likely that at some point (many points…) the player will face an encounter for which they are woefully unprepared and must escape. Underground environments offer a greater amount of negative space that can be used to control what can and cannot be seen or reached from a certain vantage point, and all of it shown in an easy-to-digest manner, e.g. rectangular rooms, corridors, and cavern walls. Compartmentalizing encounters into rooms enables dungeons to provide a tighter experience, fitting more content within a smaller overall area. Sure one encounter may very well spill over into the next when you start running for your life, but that’s why every experienced rogueliker will tell you to never flee into the unknown!

Design

Beyond choosing a method of generation (or mixing multiple methods), any number of parameters must be established and tweaked to produce layouts that work for the gameplay. Many small rooms or fewer large rooms? Lots of long corridors, or no corridors at all, just rooms separated by doors? An expansive winding cave system that draws the player to explore and lose themselves in it, or a mostly linear cavern contoured as it is for the atmosphere?

Map layout isn’t just about theme, it reflects how the game (or sub-area) plays. Many roguelikes have fairly small rooms and narrow corridors due to a high percentage of close-range combat. Cogmind is mostly ranged combat, so wider corridors and large rooms are much more common to give combatants room to find a shot.

Exploration & Fun

Aside from designing maps that complement game mechanics, it’s also important to consider available travel routes from one encounter to the next. Unpopulated rooms and corridors actually do serve a purpose, as there doesn’t need to be a fight around every corner. Real players do need some rest, or more importantly some extra space to work with when things aren’t going according to plan. In Cogmind in particular that extra space is also useful for taking the stealth approach--with the right components and know-how many confrontations can be avoided entirely.

But the primary factor I pay attention to when tweaking map parameters is the number and density of loops. By loops I mean places where multiple pathways reach the same destination. A map with few or no loops in its layout will require lots of backtracking, and backtracking is not fun! Players may still choose to travel along previous paths be it to gather items or escape an enemy, but taking the same route multiple times shouldn’t be forced on them. Long paths that lead to dead ends had better at least contain treasure or access to a new area. Cogmind has some fairly large maps by roguelike standards, so I have to be especially cognizant of pointless pathways.

This is good opportunity to point out that while developing and tweaking a map generator is often done outside the game itself so you can see the entire thing and examine it from a higher level, the fact that a map “looks good” can be misleading and is rarely something that players notice once inside the thing, anyway. Inside it may not be fun at all!

mapgen_deadends

Here’s a map that doesn’t look too bad as a cave system but wouldn’t be very fun to play without the right mechanics--waaay too many long dead ends.

Testing a map for connectivity post generation is an important step in determining whether to use that map (more on that in a future post). Some more complex procedural methods can build that requirement into the generation process itself:

mapgen_complex

A graph-based map generation technique that ensures a general number of loops (source).

Content

How we decide what to put where in these maps is another big issue, obviously a very game-specific one. Randomly spawning objects everywhere could be fun (heck, that’s what I did for the 7DRL!), but the most enjoyable experience can only come by considering the terrain and choosing locations with a purpose. This step is often dependent on dungeon metrics, which I’ll be dedicating a post to later on.

In a general sense, I should mention here that Cogmind will make use of some manually designed dungeon sections. These “prefab” areas will have to be integrated into the existing dungeon generation algorithms. Before that there’s also the issue of having a way to create and edit them, a process I’ll likely handle via REXPaint in combination with text files.

Prefab map pieces have many advantages, essentially all those things that are good about hand-crafted levels: Increased control over a specific part of the experience, their uniqueness draws attention to them and makes them more memorable/meaningful, and they provide a reference point common across games that players can talk about. I won’t go overboard in the prefab department, the second point of procedural maps being that you save time on content creation, but I’ll probably want more control over the look and feel of significant plot-related locations.

Cogmind

Cogmind maps will be using a combination of tunnelers and cellular automata, which I’ll be introducing in subsequent posts.

This is the first in a five-part series on procedural maps:

17 Flares Twitter 0 Facebook 0 Google+ 1 Reddit 16 StumbleUpon 0 Filament.io Made with Flare More Info'> 17 Flares ×
This entry was posted in Design, Dev Series: Procedural Maps and tagged , , , , , . Bookmark the permalink. Trackbacks are closed, but you can post a comment.

4 Comments

  1. Tamarin
    Posted June 13, 2014 at 7:32 pm | Permalink

    All of these look rather amazing. I can imagine having fun in any given number of your examples.
    I can’t wait!

    • Kyzrati
      Posted June 13, 2014 at 7:43 pm | Permalink

      Heh, well, thanks but none of these are mine!* This was more or less an overview of procedural map generation for those readers who aren’t as familiar with it. There are quite a few articles on the web about specific methods, but I haven’t really come across any that take a broader look at the topic. I thought a little background info would be a good place to start before diving into showing off my own maps.

      The next post will cover Cogmind’s main dungeon maps, followed by another on branch maps. Those will show the styles I’m actually using, and explore each in more detail. I have posted a few in-development images on Twitter, but nothing definitive yet.

      *I say none of them are mine, but the second to last was generated using one of my algorithms to make a point (though I won’t be using that style).

  2. Hawkeye
    Posted June 14, 2014 at 6:47 pm | Permalink

    Hi,

    I’m currently also in the early development phase of a space station rl. I had also a look at BSP trees and other techniques….one drawback maybe that for some sections(crew living rooms etc.) you would like to have a more classical floor layout. I’ve found this paper here http://www.hindawi.com/journals/ijcgt/2010/624817/ , which adds another possiblity. As you mentioned, I think you get the best results if you combine different approaches.

    • Kyzrati
      Posted June 14, 2014 at 8:49 pm | Permalink

      Cool paper! I’d have to say that realistic structure interiors are probably the most difficult type of procedural map generation out there, so good luck taking on such a difficult task. We have such a clear idea of what realistic human structure interiors should be like and therefore tend to be much more strict in our requirements. I guess some games get by simply doing whatever they want, but proper generation does add a lot of character as long as it’s still compatible with the game mechanics.

      Interiors are so difficult that the best solution in many cases may be the X-COM approach, which I use in X@COM and will continue to take further in the future. That is prefab map pieces which are randomly connected, though you can add rules to keep the connections logical, and rotate/flip them for greater variety (easier to do in a roguelike with fewer graphical limitations). This might be a route to seriously consider for your game.

      Mixing methods and tailoring them to your specific needs is a lot of work, but maps are pretty central to the entire experience so it’s definitely worth it. In total I’ve probably spent about 3-4 weeks getting Cogmind’s map generation to its current state, and it’s still only the beginning!

Post a Comment

Your email is never published nor shared.

You may use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>