Breadcrumbs

Level Generation in Yaga

Slavic folktales are often about a character traveling far away through unknown lands to try to fulfill an impossible quest. Yaga is no different, and Ivan will find himself entering dangerous forests or enchanting swamps (or is it the other way around?). Being an oral tradition, folktales are often improvised and changed by the narrator, so what the hero meets in each place might be different from tale to tale. Which is why the levels in Yaga are procedurally generated, and this post will go into some technical details about how we achieve that.

Our level generation process is a mix between what we’ve seen in Binding of Isaac and Moon Hunters. We freely stole borrowed techniques used in those games, but adapted them to our needs and narrative structure.

Goals & Quests

When writing the level generation, we wanted to achieve several goals:

  • Most combat encounters should have a purpose besides just fighting
  • Encourage exploration of each level
  • Have a natural, organic layout
  • Allow us to implement lock & key mechanics in some of the encounters

We decided to structure encounters and levels around small chains of rooms grouped in a single quest. Helping a woodcutter find his lost dog would thus contain three “rooms”: a place to meet the woodcutter, a place where his dog’s bones can be found, and a place in between where the culprits (a pack of psoglavs) are encountered. There are no restrictions about other encounters that may appear between these three “rooms”. Only that the bones room must only be reached through the psoglav room, and the woodcutter should be meet-able before fighting the psoglavs.

There are three types of quests in Yaga.

Main quests are the quests tied to the storyline. Each level has exactly one main quest, and this is usually attached to a function of the folktale, like “the hero find a magic donor”, or “the hero is tricked by the nemesis”, or “the hero falls in the underground and must find a way out”. These are mandatory, and have direct narrative relevance to the plot of the current tale. These often have a Lock room, and one or several Key rooms that need to be visited before progress can be made in the Lock room. This may mean an old witch who wants you to collect flowers for her before she tells you where the villain is hiding, a bear which can only be defeated by spiking his drinking water, a broken bridge which needs wood to be repaired, and others. It should be easy to figure out which are the locks, and which are the keys in the above examples.

Secondary Quests are smaller optional quests and encounters that are not mandatory to finish the level, but give the players opportunity to grow in skills, roleplay encounters and make a name for themselves. We use these as an opportunity to enrich the world and bring in elements from smaller tales and rural beliefs.

Isolated Rooms are encounters without a narrative attached, like a traveling merchant, secret rooms, random combat encounters (we didn’t say all combat will have a narrative purpose, some are there just for fun and skill-testing), mythical gardens, resting places.

Building the level

When the level is generated, the game chooses from a large library one main quest of a type appropriate for the current narrative, several secondary quests to give the players a chance to roleplay and grow their skills, and a few isolated rooms to make sure some elements are always in a level (merchants) and to add some spiciness (secrets).

The steps taken to build the level are:

  • Select a set of rooms from the main quest (Locks) and Secondary Quests that need to form the critical path
  • Lay them out in the world
  • Shuffle other secondary quest rooms and isolated rooms
  • Attach them, branching out from the rooms already set on the critical path, and keeping track of any ordering restrictions (like seen in the above woodcutter example)
  • Attach the Key rooms of the main quests at the leaf nodes of the level. This ensures the player need to do at least some exploration while pursuing the main quests, while having the opportunity to encounter secondary quests.

The illustrated level is one of the smaller ones, with just a few rooms.
Note: Speedrunners will have the opportunity of “forcing the lock” of the main quest and avoid exploring all the level to find the “keys”. However it will not always be clear how this is done, and the narrative consequences might not always be what they want.

Decorations

While we build the level, we keep track of a bounding box that encapsulates all the rooms and roads we might need. As soon as we’re finished with that, we use the box extents to fill the world with a tiling ground texture.

Adding limits to the world is a bit more trickier. Some of the quests and rooms are more generic, and should be able to be placed in more than one environment. Some rooms will sometimes be entered from the south, sometimes east, sometimes west. Both of these are reasons why the room boundaries are not known at build time and have to be added when generating the level to prevent the player from exiting the region and going into noclip-land.

Here’s how we do that:

  • Inside the level’s bounding box, we create a virtual grid of cells
  • We mark the cells of each “room” as walk-able (red in the gif above) (Note: right now, this causes the room space to remain somewhat circular. The next step is to allow us to “paint” some regions of the room that should be considered as boundaries, to enable more interesting shapes inside the rooms. This is not illustrated in this post)
  • Mark the cells on the roads connecting the rooms as walk-able
  • Grow out to define an area that we need to “border” off, to prevent player from exiting the level, marked in white in the gif above. We can define a “fill-rate” for this region, to allow for more dense or sparse scenery
  • Keep a list of cells that we must absolutely occupy with impassable stuff that the player has no way of passing. These are marked yellow in the images
  • Run a box fitting algorithm in this region, to fill it with impassable blocks.
  • Instantiate all the blocks. We have a list of various impassable blocks for each region, of different sizes, and we randomly pick from them to increase variety

The End

We then place the rooms themselves in the world, and the level is ready to be played. Here’s a video of the full process.

4 Comments

  1. Charles Geringer

    September 16, 2016 - 5:13 pm
    Reply

    This isi something that is helping me in my own project, might be useful for you guys

  2. CatalinZZ

    September 17, 2016 - 1:58 pm
    Reply

    Thanks! Will look into it.

  3. Pixel_Girl_

    October 17, 2016 - 6:46 pm
    Reply

    Wow this looks incredible I really want to play this!

Leave a Reply