We’ll probably be talking about No Man’s Sky a lot around here, but since it’s not out yet details are a bit scarce. The video above is one of the lengthier interviews I’ve seen that goes into how their system works.
Here’s an article about Grant Duncan’s recent GDC presentation about the game’s procedural generation. He mentions that the testing process involves drone-captured GIFs, and talks about how they use a tagging system to get more interesting relationships between the procedural systems.
Gearhead: Arena and Gearhead 2 are mecha piloting roguelikes with procedurally generated plots, created by Joseph Hewitt.
Gearhead takes the common elements of roguelikes and builds a more conventional RPG with them while keeping the procedurally generated aspects. It features procedurally generated maps, characters, sieges, plots, quests, and conversations.
The player is randomly assigned one of several possible background stories at the start of the game, and the overarching plot is derived from the exploration of the modular plot points that result from that.
The core procedural generation system in the game uses a template-based language that lets a designer define maps, quest events, character dialog, and so on. Many plots also spawn rumors that let the NPCs refer to them during the procedurally generated conversations.
While Gearhead 1 is a finished game, Gearhead 2 is a little bit rougher, with development stalling after a switch from Pascal to Python. But it does have a bunch of new features and a solar-system spanning procedurally generated plot that’s designed to finish in a climactic battle against a recurring antagonist.
The Gearhead website appears to be down right now, but since the games are open source, they can be downloaded from SourceForge. Both games have an ASCII version and an SDL graphics version; if you download the SDL version of Gearhead 1 you’ll also need to download the images in a separate package.
Worley noise is named after its inventor, Steven Worley (there are apparently a lot of Stevens in computer graphics). It’s also called cell noise, since it divides the space into cells. It is illustrative of a number of topics of interest in procedural generation: it involves deterministic random generation, Voronoi cells, and fractals.
Here’s a tutorial about implementing cell noise: https://aftbit.com/cell-noise-2/ Note the way it uses a linear congruential generator to place the points in a deterministic, repeatable pattern. That’s a useful technique to apply to other forms of procedural generation.
Fortune’s algorithm is a method of generating a Voronoi diagram from a set of points on a plane. It’s named after the guy who invented it, Steven Fortune.
Here’s an implementation of a city generation algorithm (by @tobmansf), inspired by Introversion’s canceled Subversion project and based on the L-system method presented in the 2001 paper Procedural Modeling of Cities: http://tmwhere.com/city_generation.html
One of the authors of the paper went on to create CityEngine, which I’m sure I’ll be talking about more in the future: http://www.esri.com/software/cityengine
Elite, created by Ian Bell and David Braben and released on the Acorn BBC Micro, defined a generation of British games and started a history of procedural generation.
Elite is a game that arguably started a genre and is one of a handful of games that often come up as examples of procedural generation. Elite, for those of you who haven’t played it, is a trading game wrapped in a space sim. You fly your ship from star to star, buying and selling various commodities. Those star systems were procedurally generated from a fixed seed, which generated the description of the star system, including its economy, government, and population. There were 8 galaxies of stars in the original Elite, each with 256 generated stars.
There were originally going to be 282 trillion galaxies in the game, but Acornsoft, the publisher, convinced the developers to trim it down to a manageable eight, each with 256 stars. Running your generator too many times often results in less interesting results. This balance is important: big enough to explore for a long time, but small enough that the generator can keep everything relatively unique, and Elite found a good balance of size and density.
The original set of stars–Lave, Zaonce, Diso, Leesti, Reorte, and of course the lawless anarchy of Riedquat–became iconic the starting area, making it a rare instance of the starting level of a legendary game being curated rather than designed: their existence arises from the algorithm, rather than being hand-crafted.
thissys.x=(((*s).w1)>>8); thissys.y=(((*s).w0)>>8); if (thissys.govtype <=1) { thissys.economy = ((thissys.economy)|2); } thissys.techlev +=((thissys.govtype)>>1); if (((thissys.govtype)&1)==1) thissys.techlev+=1; /* C simulation of 6502’s LSR then ADC */ thissys.govtype =((((*s).w1)>>3)&7); /* bits 3,4 &5 of w1 */ thissys.economy =((((*s).w0)>>8)&7); /* bits 8,9 &A of w0 */ thissys.techlev =((((*s).w1)>>8)&3)+((thissys.economy)^7);
(The original source code is also available, if you can read the assembly for a BBC Micro.)
It takes the base seed for the system and generates the location, government, economy, tech level, and so on. Perhaps the most memorable part of the generation is the so-called “goat soup” strings, which used a mad-libs system to generate brief, Hitchhiker-style descriptions of each planet: Lave’s rain forests and tree grubs, Leestian Evil Juice, the civil war in Reidquat. While this didn’t have any in-game effect, the descriptions served the important purpose of making each planet memorable and added a bit of whimsical imagination to the otherwise fairly dry trading and fighting game.
IBM PC Elite (1991)
The other interesting thing about the procedural generation in Elite is the way it uses emergence to multiply the effects of the generation. The planet stats have in-game effects: the government type, for example, affects how likely a pirate attack is, which makes Reidquat good for bounty hunting. The variables also sometimes feed into each other, so that the government and economy type influence the tech level. The locations of the systems and the 7 lightyear maximum jump range mean that different combinations of systems produce very different trading networks, so trading can be very different in different parts of the galaxy. Generating things that combine their effects emergently is a powerful technique.
Though we can quibble about the definitions used, Elite does hold a procedural generation Guinness world record, for earliest procedurally generated world. It’s certain few games of its era matched its scale or scope.
Lloyd’s algorithm is a method of finding evenly spaced points. It’s useful if you need a to divide something into a bunch of smaller cells, but want the cells to be evenly spaced and about the same size.
The way it works is to start with a random placement of points and then smooth them by gradually moving them towards the centroid of its Voronoi cell.
It’s obvious how this can be useful for map generation or mesh smoothing, but its uses go far beyond that: consider an image that you want to process so that it’s stippled or dithered. You want to distribute the dots evenly, but in a way that corresponds to the light and dark regions of your source image. Using a weighted Lloyd’s algorithm, you can produce the set of points that is spread out evenly while not being in a regular grid.
Now take it one step further: the position of trees in a forest is a set of points. Given a source image converted to a set of weighted points, you can generate the forest that matches the picture while still appearing natural and irregular.
Last December, Andy Gainey posted a look at a procedural planet generation project that he had been working on. It’s got a lot of detail about the process he went through to model the polygonal surface and add landscapes and weather to it.
One of the first things to realize about procedural generation is that it is not random. Oh, it uses random generators all over the place, but not in the way we mean when we casually say that a process is random.
Take a canvas, a nice big one. Divide it into a grid. Now, take a coin and flip it for every cell in the grid. For heads, paint it white, for tails paint it black. What you’ll get is a field of white noise. (And yes, noise comes in colors, even when we’re painting in black and white.) Its random, but it’s not very useful. It’s slightly more interesting than a flat color, but we can quickly see that there there aren’t any patterns, so our brains catch on pretty quickly and lose interest. Or worse: it can be actively unpleasant to look at.
So naively generating white noise doesn’t get great results. It doesn’t have a structure, and white noise even has clumpiness to it that makes it bad for getting an even random distribution. That’s not to say that it’s useless: there are musical and audio applications for using it directly, and there are algorithms that build on white noise. But generating interesting procedural content requires careful use of randomness.
Randomness, in other words, can’t just be used randomly.
Here’s a cool little project from 2011: procedurally generated pixel-art buildings for isometric games (Specifically OpenTTD in this case). Written by Richard Wheeler, the script builds the building layer by layer and then colors them.
This approach seems extensible to similar isometric art. It’s be fun to see if you could apply other common generative algoritms to producing pixel art like this.
