Unreachable Rooms

It’s been a while… if you’ve been expecting content, I do apologize.  I’ve had quite a few other pressing matters to attend to and well, updating this site didn’t make the top 10.  But now… now… it’s at least top 10.  So hopefully I’ll have lots of stuff to post in the near future.

As I’ve mentioned… once or twice (there’s an entire category on this site!), I love thinking about and producing procedural content.  Not only does it reduce the amount of content development I need to do (which is time consuming, especially for programmer-art types), every application brings about new and interesting problems to solve.

I’ve tried to design algorithms from time to time.  But have never really been happy with any of the algorithms.  Designs either weren’t aesthetically pleasing enough, or didn’t flow well enough to be used for any sort of engaging gameplay… and after all, my end goal is to be able to use this content in video games.  Even if the target game hasn’t been nailed down, it’s nice to have all of the tools ready anyway.

I came back to this problem recently, and after one sleepless night and a little more research, I think I’m finally happy with this algorithm (except that currently, my wall placing and door placing system can cause rooms that were reachable to suddenly become unreachable again).

If you’re interested in a similar approach to the one I’m going to outline here, I recommend you take a look at: TinyKeep’s Generation Algorithm.

For those that like TL;DR versions, I’ll post the screen shots first and go into the details below.

ScreenShot 1

ScreenShot 2

Here are the three basic steps for the algorithm in glorious wordy detail:

 

Build a list of rooms

This is a step that’s probably going to be in everyone’s algorithm.  You need some way to build a list of rooms.  The strategy I’m using here is basically the same as the one listed above from TinyKeep (you really should check it out).  It’s actually quite brilliant.  Not only does it produce a nice assortment of random sizes, but it also keeps the room density fairly uniform across the entire map.  This is the feature I was looking for.

My other solutions always had an issue with uniform distribution, which had to be reigned in using a second pass over the room list.  This always ended producing very mechanical room orientations, which produced playable results, but started looking the same after a few different builds.

In this algorithm, we place a large number of randomly sized tiles within a certain section of the map.  The smaller this “placement” area, the more uniform the final map will be in shape.  This, and most other settings, are configurable through the builder interface, so it’s pretty easy to create profile types for different types of maps if you want to.

Once all the tiles are placed, we move all pieces around until no two tiles are overlapping, but all tiles are fairly tightly packed together.  The article above labels this as using an AI construct known as a “Steering” or “Flocking” Behavior.  My algorithm allows you to select a few different policies to affect the tile movements.  The default is to select pieces randomly and “repel” all other pieces away, along the vector constructed by drawing a line between their respective center points.  We repeat this selection until there are no overlapping pieces, or we’ve iterated a maximum number of times (to avoid looping infinitely, just in case).  We can then either throw out a piece that overlaps until there are no overlapping pieces left, or fall back to one of the other policies.

The other policies are: move largest first and move smallest first.  Both of these have different effects on the map as you can imagine.  Move largest first will push large rooms farther to the outside of the map, and move smallest will… do the opposite.  Random produces the best results if you want a more uniform room density.

Next we label each piece based on certain criteria.  Currently only size is supported, but locality and other aspects might be implemented in the future.  Large pieces become rooms (above a certain area threshold or dimension threshold), small tiles become “construction pieces” that I’ll get to later.  Once all the pieces have been labeled we move onto the next step.

 

Connecting Rooms

How do we connect rooms, so that the map is conducive to engaging gameplay?  What makes the gameplay engaging in the first place?  Game levels tend to fall into two categories:  Linear and Non-linear.  Linear maps are good for games that are mission driven (go from point A to B) and provide some choice, but ultimately steer the player in a certain direction.  Non-linear maps are good for games that center around other gameplay elements.  Multiplayer shooters for example, want more non-linear maps.  There should be at least 2 entrances to every room (except for some secret rooms, that you certainly don’t want to be caught in against an opponent with a rocket launcher…), you don’t want to allow players to lock everyone out of a large section of the map.

Of course, it’s not that simple is it? Games affectionately known as “Rogue-likes” tend to have a mix of these two types of gameplay.  There’s usually 1 exit (or an optional secret exit) in the level, you ultimately want to steer the player in that direction.  But at the same time these games are about looting and exploration, which would be boring in an entirely linear level.  These types of games need, something in the middle.

This algorithm uses a simple approach to build linear paths through the level between rooms, by choosing rooms that are closest to them, and then using a probability function to generate extra “branches” to more paths as configured.  Once a room has been connected to the root through some path, it is removed from the list of candidates.  Once the list is empty, we know that we have a graph of room connections connecting all of the rooms together.

This produces a linear level with branches.  If you want a linear level, you simply make the longest path the path to the end, and make the branches optional / secret areas (with items or whatever you’d like to place there).

Finally, we have a “connectedness pass”.  The higher you set the connectedness (% setting which determines how many leaf nodes to operate on), the more the algorithm tries to connect leaf nodes together.  At maximum connectedness, there are no leaf nodes, and every map has at least 1 cycle that goes around the outside, and then randomly some paths that might pass through the middle.  This produces neat looking FPS shooter maps, much nicer than the ones I posted here a year ago.

 

Bake to a Tile Grid

This part takes the structure we created above and bakes everything down to a tile grid.  At this point the build is immutable, you can no longer add rooms or make any changes to the data structure.  I made this restriction for the moment because a lot of the data from the room graph is used when building items and other things on top of the tile grid.  The restriction might be removed later in the future if I can design a better tile system (but it’s currently not needed for any of my current designs).

When baking the rooms, we first lay out hallways between all connected rooms.  Currently this just measures Manhattan distance, and moves along the shortest coordinate first and then across the longest, placing hallway tiles.  These are cells that are marked in light blue in the screen shots.

Any hallway that passes through a “construction tile” (the ones that were too small to be rooms) then combine with those.  This makes some of the longer hallways into interestingly shaped rooms, with guaranteed exits to main rooms.  These are dark blue in the screenshots.  I’ve kept the data organized and in groups so it’s easier to place items appropriately (quest items and key characters in the main “rooms”, collectibles and bonuses in the little side areas of the secondary rooms).

We then go and bake all of the rooms to the map, and surround everything with walls.  Rooms are the grey areas, and the walls are the cells outlined in white.

Doors are placed at hallway / room intersections, and we have our final map.  Doors are present in the screenshot, they are just really smart at that resolution (the tiny white filled in cells).  There are doors with other security levels built in as well, and there are currently 5 door types can be placed: normal, red / blue / green “key required” doors, and switch activated doors.  Only the regular doors are used in this version because I haven’t finished the key placing algorithm yet, which makes sure that the keys can all be obtained in order without causing any deadlock.

Feel free to comment or suggest any features you’d love to see added, or other tweakable parameters.  I’ll probably include this generator in a release of RPM at some point if I can make it generic enough.

Leave a Reply

Your email address will not be published. Required fields are marked *


*

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>