Modding:Zone Procedural Generation

This page is about modding. See the modding overview for an abstract on modding.

This page is about modding. See the modding overview for an abstract on modding.

For best results, it's recommended to have read the following topics before this one:

• Modding:C Sharp Scripting
• Modding:Intro - Zones and Worlds

As a roguelike, Caves of Qud uses procedural generation (procgen) for many parts of the game. For zone building in particular it is important to know about some of the algorithms that the game uses for procgen so that you can build coherent dynamic zones. This section covers some of the most important algorithms in the game's toolbox.

All code examples on this page assume that you are starting from the starter code from the zones and worlds intro.

FastNoise

An important component of procedural generation is creating noise: a randomized signal with special properties, depending on the application that you're targeting. Some examples of noise that are commonly used in procedural generation are Perlin noise, simplex noise, and fractal noise.

Caves of Qud provides two interfaces for generating noise. The first is the FastNoise class, which can be used to generically sample from many different noise distributions. FastNoise is used heavily throughout the Qud codebase, including:

• by the Strata zone builder (used by generic underground zones) to define wall layout based on the wall material.
• by the Moon Stair zone builder to define the layout of crystals.
• by the RiverBuilder zone builder in the pathfinding algorithm used to generate rivers, by assigning random weights to cells.
• by the CrystalGrassy and CrystalDirty widgets to paint floor tiles in the Moon Stair.

In general, usage of FastNoise entails instantiating a FastNoise instance, setting noise generation parameters on it, and then sampling using GetNoise(x,y,z). For example, here's how the CrystalGrassy part samples simplex noise:

namespace XRL.World.Parts;

[Serializable]
public class CrystalGrassy : IPart
{
    [NonSerialized]
    private static FastNoise fastNoise = new FastNoise();

    // ...

    public static double sampleSimplexNoise(string type, int x, int y, int z, int amplitude, float frequencyMultiplier = 1f)
    {
        fastNoise.SetSeed(getSeed(type));
        fastNoise.SetNoiseType(FastNoise.NoiseType.SimplexFractal);
        fastNoise.SetFrequency(0.25f * frequencyMultiplier);
        fastNoise.SetFractalType(FastNoise.FractalType.FBM);
        fastNoise.SetFractalOctaves(3);
        fastNoise.SetFractalLacunarity(0.7f);
        fastNoise.SetFractalGain(1f);
        return Math.Ceiling((double)fastNoise.GetNoise(x, y, z) * (double)amplitude);
    }

    // ...
}

Explanations of all of the different noise types and parameters are outside the scope of this tutorial. To familiarize yourself with the practical implications of these parameter choices, we strongly recommend trying out the noise exploration tool from the Auburn/FastNoiseLite repository, either by installing it and running it locally or by running it in the browser.

As a practical example, here's a zone builder that simply creates a wall distributed using sampled noise:

namespace XRL.World.ZoneBuilders {
    public class RandomWalls : ZoneBuilderSandbox {
        public bool BuildZone(Zone Z) {
            var noise = new FastNoise();
            noise.SetSeed(0);
            noise.SetNoiseType(FastNoise.NoiseType.SimplexFractal);
            noise.SetFrequency(0.05f);
            noise.SetFractalType(FastNoise.FractalType.FBM);
            noise.SetFractalOctaves(3);
            noise.SetFractalLacunarity(0.7f);
            noise.SetFractalGain(1f);

            // Z.wX/Z.wY are the X/Y coords of the parasang; X and Y are the
            // coordinates within the parasang.
            int dX = (3 * Z.wX + Z.X) * 80;
            int dY = (3 * Z.wY + Z.Y) * 25;
            foreach (var C in Z.GetCells()) {
                if (noise.GetNoise(C.X + dX, C.Y + dY, Z.Z) >= 0)
                    C.AddObject("Shale");
            }

            return true;
        }
    }
}

Try adding it to the Worlds.xml provided to you in the introduction by adding the following:

<!-- ... -->
<zone Level="10" x="1" y="1" Name="test zone">
  <builder Class="RandomWalls" />
  <widget Blueprint="Dirty" />
</zone>
<!-- ... -->

Here's an example of some walls generated by this noise:

Compared this with the type of walls that we generate when we use cellular noise:

noise.SetSeed(0);
noise.SetNoiseType(FastNoise.NoiseType.Cellular);
noise.SetFrequency(0.05f);
noise.SetCellularDistanceFunction(FastNoise.CellularDistanceFunction.Natural);
noise.SetCellularReturnType(FastNoise.CellularReturnType.CellValue);
noise.SetCellularJitter(0.1f);

The walls generated by this kind of noise are blocky relative to the smoothness of simplex noise.

NoiseMap

The other utility class that is frequently used for noise generation is NoiseMap (in XRL.World.ZoneBuilders.Utility). This is also used extensively throughout the game, for example:

• it is used to distribute water in Lake Hinnom and in River.
• it is used to distribute clumps of trees in the outskirts of Bey Lah.
• it is used to make some random regions of walls holographic in the chuppah of Girsh Qas and Girsh Qon.

NoiseMap provides a few less customizability options than FastNoise, and doesn't support as many different types of noise. On the other hand, it allows modders to explicitly define regions of high or low noise.

Algorithm

Unlike FastNoise, NoiseMap only supports one algorithm for noise generation. At a high level, NoiseMap creates a two-dimensional grid of random values and then iteratively convolves it with a custom filter, blurring the noise in a manner similar to how box linear filtering and Gaussian blurring work. The algorithm creates a few locations of high noise (randomly, and through noise map nodes that are passed in to the algorithm), which are then smoothed out through iterated convolutions.

More specifically, the algorithm used by NoiseMap works as follows:

• Create a 2D Noise array, called Noise, and fill it with uniformly random values via Stat.Random(0, BaseNoise).
• Divide the zone into SectorsWide x SectorsHigh non-overlapping rectangles ("sectors"), then shuffle the list of sectors.
• Iterate over each sector and place Stat.Random(SeedsPerSector) "seeds" in random (not necessarily exclusive) locations in the sector. Sample noise as Stat.Random(MinSeedDepth, MaxSeedDepth) at each seed location.
  • These seed locations serve as areas of high noise.
• Iterate over the list of NoiseMapNodes in the ExtraNodes list. At each node, increment the seed count and set the noise to MaxSeedDepth (or the node's depth, if specified).
  • These node locations also serve as locations of high noise.
• Now iterate over the zone FilterPasses times, convolving the noise grid with the 3 x 3 filter {{1,3,1},{3,6,3},{1,3,1}} during each pass.

Example

As an example, let's use NoiseMap to create a zone with four pre-defined pockets of empty space, one in each corner of the zone. We'll also configure our NoiseMap to create some extra seeds so that our zone has some additional random pockets of space.

using System.Collections.Generic;
using XRL.World.ZoneBuilders.Utility;

namespace XRL.World.ZoneBuilders {
    public class TestNoiseMap : ZoneBuilderSandbox {

        public bool BuildZone(Zone Z) {
            var nodes = new List<NoiseMapNode>();
            nodes.Add(new NoiseMapNode(10, 5));
            nodes.Add(new NoiseMapNode(10, 20));
            nodes.Add(new NoiseMapNode(70, 5));
            nodes.Add(new NoiseMapNode(70, 20));

            int MaxDepth = 10; // This parameter doesn't actually do anything
            int SectorsWide = 3;
            int SectorsHigh = 3;
            int SeedsPerSector = 2;
            int MinSeedDepth = 80;
            int MaxSeedDepth = 80;
            int BaseNoise = 4;
            int FilterPasses = 5;
            int BorderWidth = -3;
            int CutoffDepth = 1;

            var noiseMap = new NoiseMap(
                Z.Width, Z.Height, MaxDepth, SectorsWide, SectorsHigh,
                SeedsPerSector, MinSeedDepth, MaxSeedDepth, BaseNoise,
                FilterPasses, BorderWidth, CutoffDepth, nodes
            );

            foreach (var cell in Z.GetCells()) {
                if (noiseMap.Noise[cell.X, cell.Y] <= 2)
                    continue;
                cell.ClearWalls();
            }

            EnsureAllVoidsConnected(Z, pathWithNoise: true);
            return true;
        }
    }
}

Use the following builders for your Worlds.xml:

<builder Class="SolidEarth" />
<builder Class="TestNoiseMap" />
<widget Blueprint="Dirty" />

Here's an example of a zone generated using this builder. We can see that the zone contains pockets of empty space at the (10, 5), (10, 20), (70, 5), and (70, 20) cells in the corners, but it's also generated some additional pockets via the seeds added by NoiseMap.

Wave function collapse

Caves of Qud makes extensive use of the wave function collapse (WFC) for certain kinds of procedural generation. In particular, it is commonly used to procedurally generate different kinds of buildings, such as huts, crypts, lairs, and so on. Examples of where WFC is used include:

• generating several areas in the Tomb of the Eaters, including the crypts and the gardens.
• generating various structures in historic sites, which in turn gets called by other zonebuilders such as Strata.
• creating initial structures when generating villages.

From a modding perspective, WFC can be thought of as an black box that takes in a colormap as input and produces a new colormap that is locally similar to the original as output. In the typical usage of WFC, the inputs it receives are formatted as .png files stored in the wavetemplates/ directory of the game's data files. If you wish to use WFC in a mod, you can either use one of the predefined templates or a template from the wavetemplates/ directory in your own mod. Each of these templates is a colormap containing pixels in a few different colors. For example, here is the compound.png wave template from the game's data files:

There are several different interfaces you can use to run WFC; the one we will show in this article is the WaveCollapseFastModel class. You can instantiate this class by passing in the wave template you want to use, the height and width of the area you want to generate, and a handful of other parameters.

using Genkit;
using XRL.Rules;

namespace XRL.World.ZoneBuilders {
    public class TestWFC : ZoneBuilderSandbox {
        public string Template = "spiral";

        public bool BuildZone(Zone Z) {
            var wfcModel = new WaveCollapseFastModel(Template, 3, 40, 20, true, false, 8, 0);

            wfcModel.Run(Stat.Random(int.MinValue, int.MaxValue), 0);
            var colorMap = new ColorOutputMap(wfcModel);

            for (int i = 0; i < colorMap.width; i++) {
                for (int j = 0; j < colorMap.height; j++) {
                    string wallType = null;
                    var color = colorMap.getPixel(i, j);
                    if (WaveCollapseTools.equals(color, ColorOutputMap.BLACK))
                        wallType = "Basalt";
                    else if (WaveCollapseTools.equals(color, ColorOutputMap.RED))
                        wallType = "Shale";
                    else if (WaveCollapseTools.equals(color, ColorOutputMap.MAGENTA))
                        wallType = "ChavvahTrunk";
                    else if (WaveCollapseTools.equals(color, ColorOutputMap.GREEN))
                        wallType = "Serpentinite";
                    else if (WaveCollapseTools.equals(color, ColorOutputMap.BLUE))
                        wallType = "Coral Rag";
                    else if (WaveCollapseTools.equals(color, ColorOutputMap.YELLOW))
                        wallType = "Gypsum";

                    if (!wallType.IsNullOrEmpty())
                        Z.GetCell(i, j).AddObject(wallType);
                }
            }

            return true;
        }
    }
}

Add this to your Worlds.xml with

<zone Level="10" x="1" y="1" Name="test zone">
  <builder Class="TestWFC" Template="huts11" />
  <widget Blueprint="Dirty" />
</zone>

Try playing around with the Template parameter and feed a few different WFC templates into the builder. You should see various structurally similar zones appear in the zones that you generate. For example, here are two zones generated with the pillars1 and huts11 templates, respectively.