Biomes and map generation

[Cervator]

I think I got myself confused about regional features and regional generation - thinking again the cities would get placed during world gen, but they wouldn't "hatch" until the player gets within regional distance, at which point (for infinite worlds) you then might place more cities further out on additional world map generating.

The cities may hatch into building and NPC "eggs" at this point too (via city grammar!), and I could see a return of the "city biome" concept if we add biome to Chunk (or match it to the world map?) and make it so it can change over time - as it would be the perfect way to pre-flatten appropriate terrain for the buildings (change from world-gen-time biome to city biome to affect eventual block spawning).

When the player is nearly within visible range the individual buildings might then hatch (via building grammar!) along with NPCs. Likely some of this stuff would span multiple chunks (big buildings) but if you store the buildings as entities with a filled blueprint/blockcollection attached and rely on city biomes being flat at a set height you should be able to prep it almost entirely without spawning actual terrain blocks (caveat: rivers and such)

I put together a bit of a diagram in a Google Doc - feel free to tweak it (but be wary of merged cells in GDocs!): https://docs.google.com/spreadsheet/ccc?key=0AnbZuNt7s9nVdGhBcE5PSm5jY202UGhORktjOW5INmc

Green is what we've already got, Yellow is what I think we're mainly talking about these days. Which can be split out quite a bit:

• World - we need an abstract world scope that can fit generators at different levels and store a map. Maybe one pixel = one chunk and holds one calculated biome value + humidity + temp + height (+ anything else?)
• Terrain - this is the map we'd generate out of one of our techniques like Tectonic, Plasma, Polygonesia (heh), and what we can currently get from TerrainPreviewGenerator for the random Perlin noise edition
• City (world scope) - just a dot on the map that means "city goes here" (a city egg with high-level info)
• City (region scope) - hatches the city egg into a series of building & NPC eggs (the details written in a city PAG), and sets city biome - as long as the biome can revert to match the surroundings should the city itself disappear this might work
• City (local scope) - hatches the buildings and NPCs (each with their own PAG?) into actual entities/blocks, ready for local terrain chunk gen to spawn the area around it

By cutting out the pieces like in the spreadsheet I figure we could split out incubator threads and also make it clearer what who is working on (like Nym on world scope, Skaldarnar on grammar, Tenson on city PAGS, Perdemot on NPCs/AI)

 

[begla]

Here are just some quick notes on terrain generation in Terasology from my perspective (and how I approached it all the time):

Everything Cervator said sounds about right - while infinite worlds are very nice, it's very hard to implement local features. There are a lot of erosion based algorithms out there which can (and which I have) transfered into R^3. Interesting stuff like thermal erosion and hydraulic erosion. But applying them to an infinite map is almost impossible. That's because every voxel needs to know every other voxel in the neighborhood at any time (imagine soil eroding from a higher point in the landscape - what if the valley has not been generated yet?). And there is the other very important point... While those effects are very noticeable in a high-resolution voxel-based or height-map-based visualizations, they are almost invisible in our current visualization form.

I've created that terrain in the screenshot using a lot of different noise function and applied some iterations of the well-known thermal erosion algorithm (if I recall correctly). The terrain itself is generated by a mixture of a hybrid fractal based noise function by Kenton Musgrave which outputs more details in high altitude regions and less details in valleys. In addition some of the mountain features are created using a Voronoi based noise function - which almost works as simple as a Perlin noise function. You can even combine multiple octaves of that function (which results in very interesting results).

While the terrain looked nice in this form, I had more of a struggle making terrain look good in Terasology. Mostly because the blocky style is very sensitive to high frequencies. We almost want to keep the frequencies of the noise functions a low as possible at all times while still filling the landscapes with details. That's why there is trilinear interpolation hidden within the terrain generator somewhere.

The library I've written a while ago for this example is composed of many modules which can be combined in any way imaginable. So it might be of interest one day to port this library over from C# to Terasology to support the generation of finite maps. And there is some implementation of the old fashioned Plasma-Fractal algorithm and the more advanced version of the Diamond-Square-Algoirithm hidden in there. But the results of both can be easily reproduced when combining multiple layers of Perlin noise in a certain way. So it might be more efficient to stick to a fast implementation of Perlin/Simplex noise (which we're using already).

EDIT: Thinking of - it would be interesting to use the renderer (which supports voxels and height-maps) to output a preview of chunks in a less blocky manner. Hum. Might become a separate project one day. Porting that to Java is too much hassle for now.

As far as physically terrain generation goes - I have no clue. And as alway... I need to experiment with something to get a better understanding how it actually works and if it is any use. But we should keep in mind that we are far off from the limit what finite and infinite fractal based terrain generation have to offer. And creating local features will be a lot of hard work and will require a lot of trial and error sessions. But a finite map will make it much easier to get going.

 

[begla]

And here is my favorite book on that topic which contains whole chapters by the grandmasters of procedural generation themselves:

http://www.amazon.com/Texturing-Modeling-Third-Procedural-Approach/dp/1558608486/

 

[Nym Traveel]

Wow, so much response

I think I have to split up this reply a bit...

World - we need an abstract world scope that can fit generators at different levels and store a map. Maybe one pixel = one chunk and holds one calculated biome value + humidity + temp + height (+ anything else?)

The problem I see with this is the following: the edges of the biomes would be very harsh... Atm I rather think of soften these edges a bit and let the biomes flow into each other.
Whether one pixel shall be one chunk or not is depending on the size and generation of the map.

If we really go with the tectonics approach I'd suggest one picel of the map to determine the basic elevation of several dozens chunks (interpolated with the neigbour pixels). We would need to calculate the whole world based on one 512x512 or 1024x1024 image...

Concerning the city biome:
If we want such, we first need to define what will be our abstract thing biome:
Currently it's per-block value based on x,z. The current "regions of one biome" are just caused by the resolution of the responsible noise. As a matter of fact, I wouldn't change that too much because of the lack of alternatives.
The problem with the city-biome would be: what criterias would set such a biome? This would need yet another noise (temperature and humidity would be inappropriate) which would seperate between normal and city. Besides that: what should a city biome achieve? Just flattening the land? I think we could get better results when the actual City-generation process takes care of terraforming for the city to spawn. With this we could seperate: walkways can be very steep, maybe supported by stairs whereas houses need a flat basis.

But applying them to an infinite map is almost impossible. That's because every voxel needs to know every other voxel in the neighborhood at any time

Thats one of my sources of pain and thinking, too.
I recently thought of calculating the first row of the adjasent chuncs to guarantee a neighbor in the current chunk. Not only this would lead to a 26% increased calculation time, but also lead to basically the same artifacts with just locally eroding, because of the layered way those algorithms work (calculate all blocks then change all blocks at once).

While the terrain looked nice in this form, I had more of a struggle making terrain look good in Terasology. Mostly because the blocky style is very sensitive to high frequencies. We almost want to keep the frequencies of the noise functions a low as possible at all times while still filling the landscapes with details. That's why there is trilinear interpolation hidden within the terrain generator somewhere.

Thats the reason I started the heighlimit thread - if you think abour the current mountains in terasology - those are little hills . Imagine rasterizing your image on a 1m³ raster, the result still would be very nice.
This, however would need some serious optimisation in the chunk/memory organisation and shall not be the topic discussed here.
btw: nice render!

The problem I see in using Voronoi noise and polygonial approch are basically the same: They have borders which can't be extended easily and thus are not feasable for a infinite world (at least I couldn't imagine an easy way, correct me pls )
I think this noise you described below the image is described in the book?
This would be a nice fractal to start with


Doesn't really fit into any section of the post, so I seperated it:
As of now, we have 2 main cultures, which are opposing frontes. We certainly will have a complete plot/lore in which the player starts. I suspect we will sometimes be placed in the dilemma of naming some cities and maybe make some sort of autonaming thing for smaller villages. Possible quests could be to make sth in a specific village - but what if this village isn't created yet? Maybe just set quests so they just take generated villages (or villages whose egg is spawned) into account? But what about capitals? And the territories of the culture? I think this will be very hard to accomplish by using a truly infinite terrain which doesn't look generic.

With one world map (maybe wrapped around the corner) we easily could set Points of Interest, which would drive the territory and city placement.
This also would make encouraging quests possible like:
"go to the abandonned mine just a few kilometers south-west from here - my son was on the trace of treasure rumors. The [insert Culture-name here, I forgot ] have a camp there, I fear the worst..."
This would encourage/force the player to follow routes he would never have thought of. Maybe because on this way first are some big rivers with dangerous currents and some harsh and big mountains. (just some random thoughts )

Maybe we should cut this topic apart? Actual world map generation and generation of regional features?

So long,
Nym

 

[Immortius]

The problem I see in using Voronoi noise and polygonial approch are basically the same: They have borders which can't be extended easily and thus are not feasable for a infinite world (at least I couldn't imagine an easy way, correct me pls )

Ignore for a moment the polygonal shapes generally produced using Voronoi. Underneath that Voronoi noise is about the random placement of points in a world. These points could be used to drive feature placement.

Voronoi noise (or at least the algorithm I use) is similar to perlin noise in that it is infinite - given a single seed you can sample the closest points to a given position.

public struct VoronoiResult
{
    public float distance;
    public Vector2 delta;
    public uint id;
}

public class VoronoiDiagram2D
{
    private Vector2 offset;

    public static float StandardDistanceFunction(Vector2 delta)
    {
        return delta.x * delta.x + delta.y * delta.y;
    }

    /// <summary>
    /// Lookup table for cube feature counts.
    /// </summary>
    private int[] poissonCount = new int[256]
    {
        4,3,1,1,1,2,4,2,2,2,5,1,0,2,1,2,2,0,4,3,2,1,2,1,3,2,2,4,2,2,5,1,2,3,
        2,2,2,2,2,3,2,4,2,5,3,2,2,2,5,3,3,5,2,1,3,3,4,4,2,3,0,4,2,2,2,1,3,2,
        2,2,3,3,3,1,2,0,2,1,1,2,2,2,2,5,3,2,3,2,3,2,2,1,0,2,1,1,2,1,2,2,1,3,
        4,2,2,2,5,4,2,4,2,2,5,4,3,2,2,5,4,3,3,3,5,2,2,2,2,2,3,1,1,4,2,1,3,3,
        4,3,2,4,3,3,3,4,5,1,4,2,4,3,1,2,3,5,3,2,1,3,1,3,3,3,2,3,1,5,5,4,2,2,
        4,1,3,4,1,5,3,3,5,3,4,3,2,2,1,1,1,1,1,2,4,5,4,5,4,2,1,5,1,1,2,3,3,3,
        2,5,2,3,3,2,0,2,1,1,4,2,1,3,2,1,2,2,3,2,5,5,3,4,5,5,2,4,4,5,3,2,2,2,
        1,4,2,3,3,4,2,5,4,2,4,2,2,2,4,5,3,2
    };

    /// <summary>
    /// Used to adjust the density of cellular features.
    /// </summary>
    private static readonly float densityAdjustment = 0.39815f;
    private static readonly float inverseDensityAdjustment = 1.0f / densityAdjustment;

    public delegate float SizeFunction(Vector2 dist);

    private SizeFunction sizeFunc;

    public VoronoiDiagram2D(SizeFunction sizeFunc, RandomSource random)
    {
        offset = 99999 * new Vector2(random.Next(), random.Next());
        this.sizeFunc = sizeFunc;
    }

    /// <summary>
    /// </summary>
    /// <param name="at"></param>
    /// <param name="numPoints">Should be less than 5</param>
    /// <returns></returns>
    public VoronoiResult[] ClosestPoints(Vector2 at, int numPoints)
    {
        VoronoiResult[] results = new VoronoiResult[numPoints];
        for (int i = 0; i < results.Length; i++)
        {
            results[i].distance = float.MaxValue;
        }

        at *= densityAdjustment;
        at += offset;

        IntVector2 cell = new IntVector2(Mathf.FloorToInt(at.x), Mathf.FloorToInt(at.y));
        
        ProcessCell(cell, at, results);
        
        Vector2 cellPos = at - cell.ToVector2();
        Vector2 distMax = new Vector2(sizeFunc(new Vector2(1 - cellPos.x,0)), sizeFunc(new Vector2(0, 1 - cellPos.y)));
        Vector2 distMin = new Vector2(sizeFunc(new Vector2(cellPos.x, 0))   , sizeFunc(new Vector2(0, cellPos.y)));

        // Test near cells
        if (distMin.x < results[results.Length - 1].distance) ProcessCell(cell - IntVector2.XAxis, at, results);
        if (distMin.y < results[results.Length - 1].distance) ProcessCell(cell - IntVector2.YAxis, at, results);
        if (distMax.x < results[results.Length - 1].distance) ProcessCell(cell + IntVector2.XAxis, at, results);
        if (distMax.y < results[results.Length - 1].distance) ProcessCell(cell + IntVector2.YAxis, at, results);
        
        // Test further cells
        if (distMin.x + distMin.y < results[results.Length - 1].distance) ProcessCell(cell - IntVector2.One, at, results);
        if (distMax.x + distMax.y < results[results.Length - 1].distance) ProcessCell(cell + IntVector2.One, at, results);
        if (distMin.x + distMax.y < results[results.Length - 1].distance) ProcessCell(cell - IntVector2.XAxis + IntVector2.YAxis, at, results);
        if (distMax.x + distMin.y < results[results.Length - 1].distance) ProcessCell(cell + IntVector2.XAxis - IntVector2.YAxis, at, results);

        for (int i = 0; i < results.Length; i++)
        {
            results[i].delta *= inverseDensityAdjustment;
            results[i].distance *= inverseDensityAdjustment * inverseDensityAdjustment;
        }

        return results;
    }

    private uint incrementSeed(uint last)
    {
        uint newSeed = 1402024253 * last + 586950981;
        return newSeed;
    }

    private void ProcessCell(IntVector2 cell, Vector2 at, VoronoiResult[] results)
    {
        uint seed = (uint)(702395077 * cell.x + 915488749 * cell.y);
        // Number of features
        int count = poissonCount[seed >> 24];
        seed = incrementSeed(seed);

        for (int point = 0; point < count; point++)
        {
            uint id = seed;
            seed = incrementSeed(seed);

            float x, y;
            x = (seed + 0.5f) / 4294967296.0f;
            seed = incrementSeed(seed);
            y = (seed + 0.5f) / 4294967296.0f;
            seed = incrementSeed(seed);
            Vector2 innerPos = new Vector2(x, y);
            Vector2 delta = cell.ToVector2() + innerPos - at;

            float dist = sizeFunc(delta);

            if (dist < results[results.Length - 1].distance)
            {
                int index = results.Length - 1;
                while (index > 0 && dist < results[index - 1].distance) index--;

                for (int i = results.Length - 1; i > index; i--)
                {
                    results[i] = results[i - 1];
                }
                results[index].distance = dist;
                results[index].delta = delta;
                results[index].id = id;
            }
        }
    }

}

 

[eleazzaar]

The problem with this currently is:
When we want a full 3d grid with dimensions humidity, temperature, elevation to drive the biometype we would need to fill this thing up completely ->way too much possible combinations. What shoud hot, humid, high be in contrast to hot, arid, high?
Possible solution: make just the regular humidity/temperature grid and have the heigh subtracted from the humidity and temperature map. Thus, high mountainous regions would be colder and more arid.

That sounds good, but i'd modify that a little:
Increasing hight just subtracts from temperature, not humidity. That is the primary effect of elevation IRL anyway.
Thus at high humidity mountains can have huge glaciers and deep snowfields, and at low humidity mountains you have bare rock. Creating more varied mountain tops wins IMHO.

 

[Cervator]

Concerning the city biome:
If we want such, we first need to define what will be our abstract thing biome:
Currently it's per-block value based on x,z. The current "regions of one biome" are just caused by the resolution of the responsible noise. As a matter of fact, I wouldn't change that too much because of the lack of alternatives.
The problem with the city-biome would be: what criterias would set such a biome? This would need yet another noise (temperature and humidity would be inappropriate) which would seperate between normal and city. Besides that: what should a city biome achieve? Just flattening the land? I think we could get better results when the actual City-generation process takes care of terraforming for the city to spawn. With this we could seperate: walkways can be very steep, maybe supported by stairs whereas houses need a flat basis.

My thought was for city to be an unusual biome only painted on landscape after a player get close enough. The area would have a normal biome till that point. So world scope just places a city egg on normal biome, then regional scope triggers on proximity and doesn't actually flatten the land so much as paint it with a city biome that later (at local/chunk gen time) knows it is supposed to generate flat at an average height fitting of the surrounding terrain. I'm not sure if that actually accomplishes better than flattening the land at local/chunk gen time...

Doesn't really fit into any section of the post, so I seperated it:
As of now, we have 2 main cultures, which are opposing frontes. We certainly will have a complete plot/lore in which the player starts. I suspect we will sometimes be placed in the dilemma of naming some cities and maybe make some sort of autonaming thing for smaller villages. Possible quests could be to make sth in a specific village - but what if this village isn't created yet? Maybe just set quests so they just take generated villages (or villages whose egg is spawned) into account? But what about capitals? And the territories of the culture? I think this will be very hard to accomplish by using a truly infinite terrain which doesn't look generic.

With one world map (maybe wrapped around the corner) we easily could set Points of Interest, which would drive the territory and city placement.
This also would make encouraging quests possible like:
"go to the abandonned mine just a few kilometers south-west from here - my son was on the trace of treasure rumors. The [insert Culture-name here, I forgot ] have a camp there, I fear the worst..."
This would encourage/force the player to follow routes he would never have thought of. Maybe because on this way first are some big rivers with dangerous currents and some harsh and big mountains. (just some random thoughts )

IMHO a few kilometers is peanuts. Say you have a infinite world that generates an initial world map that's 128x128 km - tons of space in there for points of interest, capitals if empires are present, etc

If the player does decide to go west and travels 100km then another segment of 128kmx128km might generate on the world map at that point to prepare new points of interest. We might effectively be thinking the same way here already, just by different names, and it seems likely anything beyond 100x100km is going to matter exceedingly rarely anyway

Maybe we should cut this topic apart? Actual world map generation and generation of regional features?

Definitely. I think we should take the opportunity to build the design for all the different layers to generate, then do one incubator thread for each, with the potential to assign individual feature curators at that point. Each layer would support multiple models via mods anyway, so you could fit a huge amount of effort into just that