11 March 2016

sense of place (ii. out of the dungeon)

Welcome to the second installment of this article series about map generation in LoSt. Part I covered the basic anatomy of a place. The topic of this post will be climates, and some things to consider when creating an overworld-based Roguelike, such as my game is set out to be. The rant that follows may please some in part or in its entirety; there's no "tl, dr", in any case.


├że olde labyrinthe
Let's start with a digression, namely the topic of labyrinths, in a meandering attempt to reach the actual topic at hand, as it were.

Early European culture distinguished two main types of labyrinths: "unicursal" (with a single path leading circuitously to the center) and "multicursal" (having branching paths, only one of which leads to the designated goal)1. In modern times we typically include a third category of "network labyrinths"2.

We might attempt to establish a fourth kind of labyrinth here. Let's call it a "deterministic maze": It has several paths, all of which lead to the same endpoint. A curious specimen in academic labyrinthology, deterministic mazes are quite frequent in video games3. Consider how the exemplary level designs of Zelda are structured as deterministic mazes: In addition to a (meandering) main path, there are shortcuts and detours available. These, however, are carefully constructed to ensure the player's passage through certain waypoints (culminating with the boss). Likewise, story-driven games tend to gravitate towards one fixed ending (or a few), like a stream might bifurcate around a great rock, only to converge on the other side.

The traditional Roguelike dungeon falls under this category of deterministic mazes. All roads lead to Yendor. And yet, procedural generation shines at its brightest when behaving more like a network labyrinth, which is to say, when the completely unexpected occurs. After all, what could be more like a network-maze of thematic associations than Dwarf Fortress?

I'll make one last point concerning historical labyrinths: The maze King Minos had Daedalus construct for the Minotaur, served as a prison, to keep the monster trapped within. Conversely, the labyrinth is also a fortification, built to keep trespassers out. Most Roguelikes emphasize this last aspect of the labyrinth, as an impenetrable stronghold to safe-keep the universally coveted MacGuffin. The motif of descending and ascending with the amulet, as featured in games like Rogue and Nethack, is actually a quite striking image. However, it was clear from the outset that I wasn't going to take LoSt in that direction.

Out of the dungeon! (screenshot: LoSt #7)

In part, I wanted a less clearcut world than provided by the genre classics. Instead of the player vertically piercing a main dungeon, I wanted plots with broad horizons, unfolding around different locations on the map: inside houses, atop steep ravines, deep within thorn forests, on the makeshift streets of desert settlements … Rather than the concentric circles of some "Caverns of Chaos", I envisioned a network maze, like the myriad connections of a root system, or perhaps even that megalithic mythic maze, but splintered, turned microlithic by erosion or earthquake.

So, I bid you farewell, unending fields of nadir … for now … Fun fact: Versions 5-7 of LoSt did play out in a dungeon (the goal was to break out of confinement), and I am planning to reintroduce caverns and mine shafts at some point. But when that day comes, the underground biotope will only serve as one of several climate types, not the center of the world (as is literally the case in most RLs).

Drawing the line(s)

Turning away from the dungeon level as the measuring stick of map generation entails leaving behind a kind of thinking one finds in for instance Andrew Doull's Unangband Dungeon Generation. And yet, rereading Doull's articles after all these years, they still inspire with their zen-like attention to fundamental design principles. Much like the pilgrim who must traverse the maze before reaching that vantage point where he finally achieves overview of its many winding paths, I find myself prompted to reexamine the inner workings of deterministic mazes, as I try to extricate myself from their manifold confines.

Games use deterministic mazes for a number of gameplay-related reasons. Globally and locally, the structure can grant the player a sense of agency whilst keeping the designer in charge of the game's progression. Some important aspects that a typical RL might contain in deterministic mazes, include:

  • Scaling difficulty: The player descends ever deeper into the game world, and is faced with ever more challenging obstacles. Most RLs simply assign a numerical danger level to different monster types. The danger level of a generated level typically depends on the current depth, the player's level, or a function of both.
  • Pacing progression and loot distribution: Just as the dungeon gets more dangerous, so the hero grows in strength, acquiring experience and better equipment. Some games design early levels to teach the player certain skills, or supply the character with certain props/abilities, which will be needed later on. In RLs, where each challenge might have several solutions, it is often a question of keeping the character appropriately powerful at any given time. Features like side-quests can also be used to ensure that the player has access to particular artifacts and resistances. This not only serves to balance difficulty, but even provides the player with an incentive to move on. After all, unearthing shiny loot is a core experience in most Roguelikes.
  • Keeping the story in line: The world is organized so as to preserve narrative coherency. Granted, most Roguelikes skimp on the story, but let's take ADoM as an example. Before reaching the elemental temples, you are guaranteed to speak with the dying sage (who blocks your passage at an earlier level). This dialogue provides your character with an incentive to raid the temples and retrieve the orbs. In Rogue, and many successors, the vertical dungeon is presented as a goal in itself, with a storyline consisting of nothing more than a text snippet ordering you to head for the center of the labyrinth.
  • (Surely, I'm forgetting something here …?) 

early experiment with "deep" climates
Some of all this must be emulated in an open world. In particular, the difficulty curve must be scaled by making sure that the top-tier baddies (and assorted goodies) won't show up too early.

When it comes to "keeping the story in line", the construction of an open world must strike the balance between narrative linearity on the one hand, and a more, if you pardon my French, "rhizomatic" narrative structure on the other4.

Keeping that in mind for later, I was presently more concerned with making an open map that also provides meaningful thresholds in the game space.

Currently, the world generator in LoSt starts out by dividing the map into roughly hexagonal zones and designating a climate type to each zone. The method is really quite blunt – I am very little interested in huge topological maps that make sense from a geological viewpoint5 – world generation begins by setting a climate for the centre zone, and basically flood fills from there, calculating a climate for each new zone on the basis of its preexisting neighbors. During this phase, zones can also be prepatched to contain specified "places of interest"; a feature which will be used to situate settlements, special locations, boss fights, etc. The world generator is stored as a data kit, so it can easily be expanded and judiciously randomized. It will be able to choose between many small templates (for climate map generation, water distribution, locations …) and combine them into unique composite themes for each world. As the game progresses, each new zone is generated on the fly, and put to sleep once the player reaches a certain distance.

what was the thread, again?
Regarding the looming question of how to put thresholds in an open gameworld, the examples of games having already done this in various ways are too numerous to start listing.

In LoSt, I'm experimenting with what I call "deep climate" types. A deep climate is a derivative of a basic climate, spawned in pockets within the bigger region. In their basic layout, deep climates provide a threshold by hindering the player's movement somehow: "Deep deserts" might be an area overgrown by thorns, or just a deadland with a looming ziggurat in the middle. "Deep plains" might be wild groves, oases ruled by ferocious animals and plants, understood in part by native people, but where no life-lovin' settler treads. The idea is to use these deep climates to set up barriers between the opening and the mid-game. Overgrown areas can be constructed as half-way mazes, with uneven "corridors and rooms" dug through an otherwise dense carpet of vegetation. Different kinds of deep climates will offer different kinds/degrees of impenetrableness. You can always wade through thorns at decreased speed, but it's harder to trick your way around a narrow mountain pass.

Deep climates zones will also spawn more dangerous encounters than the basic climates. They will feature fiercer cousins of the critters you find in the basic climate, or larger packs with more and tougher alpha individuals, in addition to particularly nasty critter types exclusive to the deep climates. I hope to use these deep climates  as antechambers/buffers/passages to "vaults" and other special locations. Should I succeed in that venture, I may actually have done little more than replace the concentric RL dungeon with a slightly more loose network of glorified "deterministic mazes". And yet, that's still a place to build from, I guess.

Did I go a full circuit with this whole labyrinthine post, and end up about where I started? I should probably be content with that tiny advancement, a whiff of something slightly ellipsoid.

As always,

1 As Penelope Reed Doob points out in her study The Idea of the Labyrinth: From Classical Antiquity Through the Middle Ages, unicursal designs were curiously used to illustrate texts describing the multicursal labyrinth of myth. The earliest labyrinths were unicursal, and seem to have been something like fertility rituals, where the devout would pass through a spiraling maze – much like we organize airport waiting lines today. In any case, the kind of multicursal designs we know from children's comics and coloring books, is a modern phenomenon.

2 The very idea of the "network labyrinth" implies a winding maze in itself. The term was coined by Umberto Eco, who described it as "a tree plus an infinite number of corridors that connect its nodes." (From the Tree to the Labyrinth) This kind of maze connects with a multitude of modern concepts, from data clouds to deconstruction, whilst retaining an aspect of a particular medieval idea of the labyrinth as a metaphor for laborious/hard-gotten knowledge (even if substituting medieval "circuitousness" with modern "rupture" as the source of epiphany).

3 Streching the definition of a deterministic maze, we could hold Pacman as an early example: A maze with no center has as its endpoint the state of depletion after Pacman has covered all its corridors, gobbling up all the pellets. Pacman's concept of "covering the entire area" is really borrowed from the ancient unicursal mazes, but set instead in a maze of branching paths.

4 I'm not implementing bounties (quests) yet, but keeping some of this in mind: hoping to opt out of fixed quest lines, perhaps by implementing bounties as part of the factions found within the game world. Let's say you're assigned a mission to capture a criminal. The task should be solvable in different ways, but it should also be possible to ignore the mission, or join the baddies instead, or fail, yet live to see another day. I expect finalized versions of LoSt to have no win condition (but several possible plot hooks to get you started). This will ideally make it possible to recover, at least story-wise, from committing a blunder such as making your intended ally your lethal enemy.

5 A tiny bit of topology is high on my todo-list, but it will pay more attention to the rules of drama than the rules of science. I am thinking of adding an intermediate step in map generation, after the climate zones have been defined, but before quest locations are placed, where the game will put natural borders in the form of water and cliffs. Rivers and lakes will be straightforward enough, simply continuous bodies of water patterned across the land. Cliffs will be implemented as a map feature, so the game won't keep actual track of relative elevation etc. A cliff hex will be defined with a slope in one direction. It has the property of sliding everything that lands on it in this direction. Barring any special skills or equipment, if you try to scale a cliff from below, you'll just be thrown back where you started, but it'll be possible to jump down the cliff from above. Cliffs will also provide special cover, giving advantage to shooters on the high side. Once the functionality of cliffs is sorted out, they can be distributed around the map, both in "encounter-sized" chunks, and in great walls that form an initially impenetrable barrier: to reach that summit, you have to take the winding mountain road, crawling with baddies.

7 March 2016

sense of place (part i)

One of the features I'm working on right now, is map building. There is a lot to be done here. I need locations, starting with a small frontier settlement. I need the different biotopes to stay more distinct, as well as blending more seamlessly together. I need a map that makes sense, which can be used to tell a story.

So to clear my mind, perhaps, throw out some ideas, I'm going to write a bit about map generation in LoSt. I'll be covering some of the game's principal design decisions as I go along. In this series started in the midst of the 2016 7drl frenzy, let's hope for a modest first article, just to lay out some basics and get the ball rolling.

Kitting up

The data is stored in homebrew module files of what I call kits. Each defined kit can spit out an instance of a certain class (eg. a critter or a place template). An important feature of kits is that they can look up and invoke other kits semi-randomly.

On the implementation part of things, most classes share certain functions and features, by inheriting a basic class that I call FlagThing. I suck at OOP, so bear with me. FlagThings are used to keep track of everything, store things like variables (a house may store a $dweller1 and $dweller2, its inhabitants, who in turn know that house as their $home). "Everything" is a FlagThing, from place templates to skills to critters, and even kits in themselves. They make up a kind of network of parents and children, emanating from a "world" FlagThing at the root of it all.

What's in a place?

Regarding the grid, suffice to say that it's hexagonal, and that, in addition to single coordinates, I keep track of "superhexes" (clusters of ~16 hexes; and then of course you get your hyperhexes and ultrahexes).

Speaking to world generation more specifically, the world consists of layers of places: The map as a whole is treated as a single place, containing several smaller places, called landscapes. Each landscape is a continuous field of hexes which share one climate and one name. They in turn contain smaller places: a house, a cluster of plants, a circle of totem stones, an animal or human encounter … Some of these places even contain within themselves subplaces or encounters (a wandering desert animal, a family seated to dinner in a house). Basically anything that spawns a being on the map when it is generated, is understood to be a place.

When a new place is generated, the first thing it does is to find and occupy some open space within the confines of its mother place. While some places use blueprints, most places are circular at the moment. Upon generation, they can fill parts of their interior to percentage values, like a basic house or a lake, put instances of inhabitants and subplaces, and do other interesting stuff.

   place bungalow template
shape "circle"
size (4,6)
get $wall ['dirt wall']
get $gate ['closed door']
room_fill {'wood tile':100}
edge_fill {'$wall':100}
edge_put {'window'(0,2)}
edge_put {'$gate':(1,1)}

   place salt pond
shape "circle"
size (2,5)
edge_fill {'water tile':50}
core_fill {'water tile':99}
brim_fill {'water tile':75}

   place hermit house
inherit "bungalow template"
get $hermit (['cri'],['persons'])
get $thing (['prop'],['loot','tools'])
core_put {'$hermit':(1,1)}
core_put {'$thing':(0,2)}

The routines for place generation are sound enough. Next steps include establishing more meaningful relations between places. That's a topic I hope to cover in my next post.

As always,

Some experiments are
just pure failures