Tuesday, September 16, 2014

Procedural Death Labyrinth Generation, Part 2

This post follows up on the previous post about Procedural Death Labyrinth Generation in the context of the game Spelunker.

Today, I want to talk a bit about how Spelunker actually manages to achieve the cave system complexity.  Here's an example of what sorts of terrain you can expect to find in the game:

Here, we can see several interesting cave features: tight crawlspaces, large vaults festooned with flowstone, drop-offs into pools, sunken pits set into the floors of larger caverns, passages that leave from the convenient bases of caverns or from the very apex of caverns, switchbacks, and secret troves of special speleothems.  It all looks very organic and natural.

Even more importantly, the cave generation is free to wander off in any direction it likes as far as it likes.  It is not constrained to a regular grid.

And yet, it's little different than your typical roguelike game's levels.  As proof, here's another view of that same section of cave system:

Look familiar?  Now, you're just seeing connected rooms, with just some fancy generation of the walls inside them.  Now, you can see the "rooms" and how they connect.

Once you see this, you can probably guess how the game generates its cave systems, but here's a description anyway.

*  The game starts with an Entrance room.  This room has several sockets defined on the edges of the room's bounding box.  At this point, all we have is a rectangle, some points on its boundary, and a link to the Entrance room type.

*  We then select a new room type, say the Sloping Crawl, and create a room of its type.  This room is also a rectangle, and also has one or more sockets on its perimeter.

*  We place the sockets of the Sloping Crawl on top of the sockets of the Entrance.  If this doesn't cause the new room to overlap any existing rooms, then that room, and its position, is kept.  If it does overlap an existing room, then we move on to the next socket pair, or (after we have more than one other room to attach to) move on to another room to try attaching to.

*  We continue randomizing rooms and trying to match their sockets with existing rooms' sockets until we reach a predefined number of rooms.

*  This gives us the room outlines.  Now, all that needs to be done is "render" the rooms into those rectangles.

Each Room Has A Story To Tell

The different room types are what evoke the dramatic cave systems in this game.  There are several different cave types, and they all are designed to evoke a different feeling procedurally:

*  Tight crawls are designed to connect the player between the larger rooms, and feel like "secret" tunnels that other people would not notice.

*  Big rooms are intended to inspire awe and wonder.

*  Switchbacks and drop-offs are intended to give a sense of danger and challenge (and to provide a convenient way for players to get themselves killed while playing).

...and so on.  Each room is given a particular shape type, but is randomly created using noise functions, random walks, etc., so that they don't become too predictable.  For instance, here are some sample renders of the Dead End Large Room room type:

You can see that the variation, even within this one room type, is pretty large.  Exits can be short or long, lead off in many different directions, can feature water or be dry, can feature different types of flowstone, different room shapes, etc.

Each room type only has to know how to draw itself and connect itself to its activated sockets.  By introducing variation in the individual rooms, mixing the room types throughout the game map, and being a little clever about how rooms attach, you get the feeling that the whole map is one large system, rather than being individual rooms.  That's how you end up with cave systems that look like this:

Of course, even at this level, you can start to ascertain some repeated patterns, even if they are realized in different ways.  But that stems from having the benefit of the fully-zoomed-out view of the caves.  The human mind can't make the above map very easily mentally.  When you're looking at it at this level:

...those patterns are very difficult to recognize.  (And even if you do start to recognize them, if the "tropes" are built upon things that would naturally recur in a natural environment, then it's not a problem, as long as there's enough variety to provide interest.)

So that's how Spelunker generates its caves.  There's of course a lot of detail that's been left out - particularly about how to render those rooms - but these are the basics for putting together a free-form room map which can be populated with any type of room genre.

No comments:

Post a Comment