Dev Blog 5: Level Generation Algorithm

I'm a bit late on the April update because I spent last weekend at the Halifax Game Jam, where my team produced the endless flyer Flight Club.  However, April was a pretty eventful month in terms of development.  I've continued to update the UI in the combat sections of the game, so it keeps getting a little bit better and more usable with each passing month.  There's also now a complete (albeit fairly bare-bones) game loop, where you can select a bounty/quest, go into a combat section to complete the bounty, and then return with your reward to the hub section.  May is the month when I'm implementing a lot of the hub functionality, but I'll get to that in the next dev blog.

The main thing that I spent April working on was the level generation algorithm and the level editing tool that makes that easier.  Up until now there's been a single hard-coded combat area in the game, but now I've put in place most of the code that will be necessary for generating unique areas for each combat.  I'll spend the rest of this blog post explaining how the level generation actually works.


My approach to the way the level generation would work was inspired by Spelunky, as described in Derek Yu's book about his process for making the game.  In Spelunky, each level is made up of a grid of sections.  The sections are pre-designed, and there are variations on each of them.  At run-time, the game chooses a selection of the available sections, then randomly applies available permutations to them for a bit of variation.  That approach helps ensure that Spelunky's levels have the feeling of being designed, while still presenting an enormous variety of potential configurations.

My game is taking a similar approach, which works like this:

  • Combat areas are made up of a hierarchy of pieces.  Those pieces, from smallest to largest, are tiles, quadrants, and tilesets.
  • Each combat area is comprised of four quadrants. The quadrants are pre-designed with specific terrain and object placements.
  • There are several "themes" for combat areas, which are divided into tilesets.  For example, you can have a fight in a bar, on a spaceship, in a spaceport, and so forth.  Quadrants are unique to a specific theme.
  • Each of the four quarters of the map (top left, top right, etc.) has its own list of quadrants that can be spawned.  Some quadrants can be spawned on any section of the map, while others are restricted to only one quarter of the map.  This is to ensure that, for example, a bar-themed map will only ever have one actual bar, so that the map that's generated feels plausible.  On the other hand, a quadrant that's just composed of an arrangement of tables can spawn in any of the quarters, since seeing multiple sections of tables in a bar is perfectly normal.
  • Tiles can be of three types: floor, mid-height (ie. objects in the environment such as tables), and walls (or other comparably tall structures, like statues, that a character can't see or attack across).
  • Mid-height object tiles typically have a list of items that can spawn on them when the map is generated.  As discussed in the first dev log, players don't have any weapons equipped when they begin combat; they can only use whatever items are available on the map, and those are semi-randomly generated and placed.
  • This all comes together to produce a combat area that is 12 tiles wide and 10 tiles tall, although the level generation code is written in such a way that it would be easy to vary the map size for different themes if that seems like a good idea in the future.

The Map Hierarchy

As discussed above, combat maps are made up of tilesets, which are made up of quadrants, which are made up of tiles, which can have items generated on them.  These parts are all Scriptable Objects in Unity, which allows me to create a lot of individual pieces with a relatively small amount of effort.

As a tactical RPG, everything runs through a tile-based grid.  Individual tiles are constructed as follows (this will likely change as the game gets closer to completion):


Next are quadrants, which are the actual pieces that the map algorithm uses when a level loads.  A quadrant is just a grid of tiles, and they're what I use to compose the pieces of the level.  I wrote a quadrant editor to allow me to quickly create them visually by dragging tiles onto the grid, but unfortunately it's glitching out at the moment so I can't include a screenshot of how it works.

The final component is the tilesets.  Each bounty has a tileset associated with it.  When the player accepts a bounty, the tileset is the piece that's passed into the map generator.  The map generator chooses one of the available tiles in each quadrant, pieces together the final map grid, and then decides which items to spawn and where to spawn them. 


You can see that there's one additional feature on each tileset, which is the generic enemies that go with it.  In addition to the character that the player must capture to collect their bounty, most maps will also feature "generic" enemies that match the theme of the map.  For example, if you're in a bar fight, you might also wind up fighting some angry patrons who don't like the fact that you've disrupted their drinking.  Tilesets will contain multiple types of generic enemies, but at the moment I've only created one for testing.

So that about sums up how level generation works.  Next month I'll be back to explain the hub that the player returns to between bounties.