{"id":742,"date":"2014-06-13T06:21:55","date_gmt":"2014-06-12T22:21:55","guid":{"rendered":"http:\/\/www.gridsagegames.com\/blog\/?p=742"},"modified":"2014-09-09T21:52:24","modified_gmt":"2014-09-09T13:52:24","slug":"procedural-map-generation","status":"publish","type":"post","link":"https:\/\/www.gridsagegames.com\/blog\/2014\/06\/procedural-map-generation\/","title":{"rendered":"Procedural Map Generation"},"content":{"rendered":"

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

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

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

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

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

Methods<\/h1>\n

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

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

BSP Trees<\/h2>\n

BSP trees<\/a> can be used to create some of the simplest and most immediately recognizable roguelike maps--rectangular rooms attached to one another by corridors.<\/p>\n

\"mapgen_bsp1\"<\/a>

BSP Tree, Example 1 (source<\/a>)<\/p><\/div>\n

\"mapgen_bsp2\"<\/a>

BSP Tree, Example 2 (source<\/a>)<\/p><\/div>\n

Tunneling Algorithms<\/h2>\n

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

\"mapgen_tunneler\"<\/a>

Tunneler Example (source<\/a>)<\/p><\/div>\n

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

\"mapgen_drunkard1\"<\/a>

Drunkard’s Walk, Example 1 (source<\/a>)<\/p><\/div>\n

\"mapgen_drunkard2\"<\/a>

Drunkard’s Walk, Example 2 (source<\/a>)<\/p><\/div>\n

Cellular Automata<\/h2>\n

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

\"mapgen_automata1\"<\/a>

Cellular Automata, Example 1 (source<\/a>)<\/p><\/div>\n

\"mapgen_automata2\"<\/a>

Cellular Automata, Example 2 (source<\/a>)<\/p><\/div>\n

As you can see from the types listed above, what I’m really talking about here is procedural dungeon<\/em> 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!<\/p>\n

Design<\/h1>\n

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

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

Exploration & Fun<\/h2>\n

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

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

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

\"mapgen_deadends\"<\/a>

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

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

\"mapgen_complex\"<\/a>

A graph-based map generation technique that ensures a general number of loops (source<\/a>).<\/p><\/div>\n

Content<\/h1>\n

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

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<\/a> in combination with text files.<\/p>\n

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<\/em> time on content creation, but I’ll probably want more control over the look and feel of significant plot-related locations.<\/p>\n

Cogmind<\/h1>\n

Cogmind maps will be using a combination of tunnelers and cellular automata, which I’ll be introducing in subsequent posts.<\/p>\n

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