Minority Opinions

Not everyone can be mainstream, after all.

Seamless Level Transitions

leave a comment »

My ideal roguelike has neither stairs nor perfectly rectangular levels.  Unfortunately, that makes level generation tricky; as Dwarf Fortress found, it’s less satisfying to depth without being able to go over and under your position.  Fortunately, I’ve found a way to walk between levels without using explicit stairs; at any given point, everything you can see looks like it could be on a single level.  This is the feature that lets Rainbow Rooms generate mazes of infinite size on a finite screen, without scrolling.

In fact, I found two ways to do so; the first made movement and field-of-view calculations simpler, but creates some annoying restrictions on level generation.  Given that level generation is a much harder problem than the first two, and will need to be created anew for any given game, I’m going to describe the second method here.

The basic idea is that certain map cells occupy multiple levels at the same time.  So does anything on that cell.  Through such a cell, you can see any open cells on any of its levels.  From such a cell, you can move to any adjacent cell on any of its levels.  I call such cells ramps, due to similarities with the Dwarf Fortress structure of the same name.

In my implementation, this means that z coordinates are always stored as tuples, while x and y are integers.  (In Python, a tuple is an immutable list-like structure.  I could have used sets or lists instead, but tuples have slightly better performance characteristics in cases like this.)  Cell lookups always go through a single function that takes x, y, and z coordinates, returning the first match it finds on any of the z-levels specified.  If all of the levels are empty there, it returns an opaque, impassable Rock tile.

Movement, then, is easy.  Whenever the player moves, get the player’s coordinates, increment or decrement x and/or y, look up the cell at the new coordinate, and (if the new cell is passable) set the player’s coordinates to those of the new cell.  In practice, my cells only need to know their z coordinate, because they don’t change the player’s position in x or y.  Multi-tile movement is resolved as a series of single-tile steps.

The field-of-view generation is a little trickier.  The visible space at any given xy coordinate can depend on the user’s position, so it’s best to use an algorithm that checks closer spaces before moving on to farther ones.  You’ll also need a mapping of xy coordinates to sets of z-levels, initially empty except for the player’s location.  Whenever you find a transparent visible space, update that mapping; each farther neighbor of the visible space might be on any of the visible space’s z-levels, in addition to any already in the set.  I found Aaron McDonald’s implementation of the Precise Permissive algorithm ideal for this; libtcod’s internal algorithm, despite being written in C, was much slower due to optimizations that assume a single potentially visible cell per xy coordinate.

The main constraints on level generation arise from these two algorithms.  The movement routine can’t move a user directly from a single-level space to one on a different level, so each contiguous group of ramps will need to have impassable tiles separating any pair of levels.  The field of view algorithm requires that such tiles be opaque, too.  In addition, cell lookup must not be ambiguous, so each pair of levels must not have different tiles on the same xy coordinate if there’s an adjacent ramp connecting those levels.  Otherwise, you might find that simply walking can suddenly change everything behind you.

Actually, that might have been an interesting take on the One Way Trip theme, if I had written the cell lookup to always return the space on the z-level farthest from the starting point.  But it would be terrible if it meant that a monster chasing you could disappear and reappear without warning.  After all, I still mean to use this idea in a roguelike someday.


Written by eswald

9 Oct 2012 at 6:31 pm

Posted in Python, Technology

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s