notes on procedural worlds


#1

recently as a way to take breaks from perpetually impending and terrifying deadlines i’ve been doing research (reading white papers, summaries of other games’ source code, etc) to understand procedural world generation in a 2d roguelike-ish context in anticipation of a possible future project (but mostly as a learning exercise). i don’t have a blog or anything but i want a place to organize my thoughts outside of my design journals where i can easily drop links to stuff and also get feedback from other game dev ppl if anyone finds this interesting.

i want to see to what extent i can take a (very impure) functional rather than imperative approach to generating worlds. to understand how feasible this is i’m trying to break down processes that show up across different games into rough categories and work towards generic, atomic functions. here is what i have as my schema right now:

World Map: The 2D matrix of cells at the highest level. Each cell is a World Tile. (A useful analogy for World Tiles is typical tiles in old rpg world maps, which could be described as “forest tile” or “mountain tile” or “sand tile” etc)

The World Map is generated from Landmasses, which are themselves made up of Biomes (which set the rules for the kinds of World Tiles that are generated) and Features like dungeons and towns (more on this later).

For our purposes, we will say that each World Tile that does not contain a Feature contains a Field. These Fields are 2D matrices of their own, all of the same size, and the parameters for their creation are set primarily (possibly only) by which World Tile they come from. (Each cell in a Field could be thought of as a “pixel” on the World Map; in a sense, a World Tile IS a Field.)

At a high level, most of the processes for generating the World and generating Fields are the same. Because we want to design around higher-order functions, the line between things and processes begins to blur. My current methodology is loosely inspired by this roguebasin article. I’m not completely satisfied with the terminology here and would like a more cohesive set of analogies to work with but I haven’t found anything that fits quite right.

  • A Creator is a function that iterates through and modifies cells in a given Canvas (a collection of cells) based on Rules.
  • A Rule takes a cell (origin) and optionally a type of Neighborhood (a set of neighboring cells) as input and returns a boolean value.
  • A Painter is a Creator that iterates through space from some origin on the Canvas, “painting” cells (think random walk, flood fill). I think all their behavior can be elegantly captured with recursion but I need to research this further.
  • An Organism is a Creator that iterates through space and time according to its Species (a set of cellular automota rules built up from Predicates). (this is useful for some “natural” features like Landmasses and cave systems but also in-game for stuff like fire spreading)
  • A Transformer is a function that manipulates a Canvas in a non-iterative manner, for stuff like duplicating some cells somewhere else or applying geometric transformations (useful for symmetry)

Top-level imperative Designer functions that call on the Creators are probably necessary for program flow and incorporating pre-determined design elements but in a perfect world their program logic would amount to composing the I/O between Creators, basically turning them up and watching them go.

I’m not sure how flexible this design pattern actually is. It works well for geography, I think, but I’m not sure how useful it is for, say, room-and-corridor dungeons, or placing features after the world is built (all the roguelikes I’ve looked at so far brute-force their dungeon feature placement and evaluate the predicate for a given dungeon feature at random locations X times before giving up; I know stuff like this is “simple” but it feels like a hack and kind of defeats the purpose of this learning exercise). I’m still thinking about a way I can restructure this so that I can drop down some predetermined content and basically use that as the “input” for generating everything else. I have more to say about this but I’m going to save it for another post.


#2

A small piece of advice: always keep in mind what meaning you need to express through spatial borders, and how your mechanics interact with them. Traditional dungeon roguelikes need to think in terms of encounter space so specific room shapes matter less than a node-like grouping of them. Games with deeper spatial interactions like platformers needed tight bounds on the random generation before we could create interesting randomized spaces.

I believe world geography generators should prioritize believability above variation and balance considerations, so less flexible bounds are likely acceptable.


#3

Wouldn’t main dungeon generation be what an Organism is tasked towards too? It’s not any more complex than building a cave system, just using different rules (ie. would be more inclined towards straight corridors intersecting at 90 degrees, rectangular rooms with doors, etc.) and by the same fashion would not spring fully formed. So dungeon features like specially designed vaults could show up on that dungeon building timeline by random chance or set in stone for that Organism to be included, depending on its set of rules.


#4

Cellular automata rules are hell if you want to use them to create playable game spaces, in my experience.


#5

Yeah, most of my thoughts so far have been about generating interesting nature—though I’ve also been considering how procedural algorithms can work given both specific and broad directives. One of those problems, like you said, is creating spaces that are mechanically interesting; another is creating spaces “around” some markers that need to exist (of course, these issues aren’t really discrete but that’s not something i’m worried about yet). I will have more to write about this later hopefully. My approach to stuff like dungeons will likely be very different.


#6

Last year Unexplored implemented a concept they call ‘cyclic generation’ which, briefly, generates around a core concept of story/event nodes that have to happen, and generate space in between. It seems to generate narratively cohesive high-level flows in dungeons (go to door, find it’s locked, search for key, etc). The game itself has the consistency of mushy peas but it’s a solid proof-of-concept.

Here’s a quick writeup.


#7

Yeah. Most of the reason I don’t have much to say about dungeons yet is that I want actual play-spaces designed around the player’s verbs and I don’t really have that kind of thing worked out yet. I’m tackling stuff like wilderness and towns first because they are easier problems to solve in isolation.


#8

sorry to gush, my world is closed off right now


#9

Nah no worries, I always enjoy reading your replies to my game dev posts.

Here are my high-concept notes for mechanics stuff:

  • You play a fantasy archaeologist and you are an asshole. The core game loop is hiring adventurers in town and leading them to their deaths while you escape with all the treasure.

  • Dungeons are scoped like encounters. I want to capture the feeling of the old-school RPG “push your luck with how deep you delve into the dungeon” thing by way of invisible inc by way of fire emblem. Dungeons don’t end with you heroically beating a boss, they end with you grabbing the amulet of yendor and running screaming while looting your allies’ corpses.

  • Party members don’t gain experience and they are a constant drain on funds. There is a strict class system with a fixed pool of abilities for each class. The adventurers in town are generated with random classes and random abilities from their class pool. Stats are as minimal as I can make them. Abilities are very generic. There is no RNG for things like damage or hit rates.

  • There is as much emphasis on weird traps and set-pieces as on wandering monsters. Enemies kill you very fast but are easy to manipulate into wandering into traps to set them off for you and things like that.


#10

Sounds neat! I bet a fast & breezy complexity limit for combat will help; kind of an old-school Ultima feel.

Along similar themes, (self-aggrandizement warning), one of my first games I’d stand behind is a dungeon inversion: play as boss monster, feed on other monsters while being mindful of the ecology, defend yourself from the hero that comes in to slay everyone, satirizing the RPG’s destructive influence on functioning ecosystems. Most heavily-drawn from: Cubivore/Dōbutsu Banchō


#11

been reading through andrew doull’s posts on procedural generation. they are ancient but very good. been saving a lot of snippets of them

i’m going to lump in AI notes in this thread because i think it is a related concern. procedural denizens of procedural worlds, emergent behavior tied to emergent level design, etc etc. i really like this series i’ve been reading through this morning

it’s really refreshing to step away from AI as decision-trees or bayesian nets or weighted dijkstra maps (although those things are good and i will still be using them) and focusing on things that don’t actually make enemies “smarter” but more dynamic/reactive. i want to throw in a hundred hooks for battle banter. it has incredible mileage for charm and it’s more interesting to me at this point than necrodancer- or Ending-like pattern-exploitation (though obviously they are pretty orthogonal goals).


#12

If you haven’t seen it, I recommend Elan Ruskin’s talk on dialogue selection through fuzzy pattern matching. It’s an extremely elegant method for picking the most contextually relevant line (or decision, or anything) based on a collection of disparate gamestate info. It elegantly falls back to progressively less-specific lines until it finds a match.

I’ve implemented it about three times now, for dialogue, random loot generation based on a boss fight, and branching narrative selection:

http://www.gdcvault.com/play/1015528/AI-driven-Dynamic-Dialog-through


#13

[multi-axis random generation]

This is very good. I had a lot of trouble modeling interesting storytelling when I was trying to fit it to a pacing curve – how to remain cohesive enough to map to the general ramping of excitement but also introduce spikes of danger was never resolved to my satisfaction.


#14

hey, remember when valve made games (laughter, applause)

anyway this is perfect because not only is it a simple/elegant/understandable solution to a complex problem, but monadic lookup tables and human-readable predicate function composition are exactly the sort of tools i’m hoping to pick up with this project and this seems like a really good place to start


#15

yes… ::sob::


#16

using C# to slowly pick up functional program flow but i’m not really sure if i’m going about this the right way…

image


#17

I know almost nothing about functional programming but that makes me wish I was coding in C# in Visual Studio again…


#18

vscode is the new hotness imo, everything else has felt clunky/archaic to me


#19

Last time I used it it still felt laggy next to SublimeText and not as capable with project tools as full-fat VS, but I’m probably due to try it again.

I’ve take to doing all my notetaking and longform writing in SublimeText; fullscreen & no-distraction (smallish middle column). Nice piece of dark grey paper to scribble in.


#20

When I’m using a new language w/ features I’m not used to I just try to force them in and experiment with them until I understand what situations I should or shouldn’t use them in. I’ve been doing Kotlin recently, which is making it very hard for me to parse your code above due to the differing syntax, but it’s probably fine!