Terrain erosion

[Lion.Kanzen]

Yeah, very different and all new gameplay, new wall concept, corral and farmstead system, citizen soldiers, outpost can attack, technology pairs system. And much more innovations, mobile civic center.

But i cant figured how will work this feature, in gameplay.

Edited May 27, 2013 by Lion.Kanzen

[historic_bruno]

I see that this has so much potential and would make the game a Different RTS, from all the others produced in, like, history. Kind of a new level. Realistic terrain could really push up the quality, be what makes 0AD stand out and amaze newcomers, when they see screenshots.

I think it's much harder than it sounds. Even if we had very realistic terrain simulation, and even if it could be scaled properly to the game world, would it necessarily make a more fun, more challenging 0 A.D.? In an RTS, the terrain is part of the strategy, so if it's random without any thought to strategy and balance, then I would say it's not going to be very fun in that context. However, it's not easy to formulate constraints on the terrain generation that preserve strategic elements. This is probably why many or most(?) RTS games don't have random maps. Any experienced map designer is going to be able to create a better map than the best random map generator, because they are not doing it only for aesthetics or realism, but for gameplay too.

Needless to say I'm very skeptical about any map generation modeled on real world processes and their applicability to 0 A.D. (otherwise it's a very fascinating concept). I think it's well suited to eye candy demos and academic research, but has anyone ever seen it done successfully in a 3D game let alone an RTS?

[eduh]

Yes, in Railroad Tycoon 3, though it is not an RTS.

In that game, there are two steps to making a new map:

1: In the little screen that appears when you put the disk on the computer which normally says: Play, Uninstall, Readme, FAQ, etc. There is a button called something like World Editor. If you click there, there is a little program with a map of the world, blank, and super accurate in therms of landform. You click and drag the zone which you want to make the scenario, and it is saved.

2: After, in the inside of the game, you go to the proper world editor and start putting rivers, cities, etc.

Some screenshots of the Amazing and Wonderful game here:

http://www.gamespot..../images/281652/

You could use this system to implement scenarios in the game...

Edited May 28, 2013 by eduh

[FeXoR]

@historic_bruno: Your scepticism is justified. However, after having sane base terrain generation I intend to write some functions to make the flat parts more flat and the rough parts more rough. That way cliffs will form that are unpassable and a greater part of the map will be more suited to place buildings. Additionally woods and rock formations can be set to change passability. How well all that will turn out in the end is to be seen.

IMO the reason for most modern RTS games not having random maps is that they likely don't have eyecandy areas. Note that most 3D RTS games don't allow to zoom out far (with few exceptions) so that those areas have to be small to be noticed.

However, I don't think that should be our concern here why or if other RTS games do something or not. If something in another RTS game worked well we should think of adding it. If something went very wrong we should try to avoid it. But just because it does or does not appear often is not a criterion of quality at all.

[FeXoR]

Whoo, this looks interesting:

http://codeflow.org/...-erosion/#video

And this, hui:

http://proland.inrialpes.fr/

And all open source...

Edited June 14, 2013 by FeXoR

[eduh]

Here is another link of interest:

http://www.world-machine.com

[FeXoR]

I have made some progress. Here's a short report:

With another approach (I think it's about the 20th) I managed to get stable, riverbed-digging water erosion. It now calculates the acceleration (so driven by gravity) which seams to make the difference.

Some screen-shots of the same terrain with a different amount of water erosion cycles applied.

On tiles with water texture the water hight is more than 1/16th (~6%) of the maximum water height on the map.

(So where no water texture is there is really not much water)

Lighter water tiles mean the water runs faster, darker mean the water runs slower.

The other tiles are just painted by height.

20 cycles: At first the water gathers...

50 cycles: ...and forms rivers.

100 cycles: Then it reaches a stable state (It rains all the time and the water slowly drains/evaporates).

Sadly the erosion process is really slow...

I'll post again when I produced a random map with this.

The files:

FeXoR-hightmap2013-9-14.zip

Edited September 15, 2013 by FeXoR

[eduh]

Am I the only one that follows up closely FeXor's work?

I think this is work will create the biggest change to RTS style of games ever.

At last realistic terrain is coming!

[Lion.Kanzen]

Not,see map design forum.

http://www.wildfiregames.com/forum/index.php?showtopic=17642

Edited October 5, 2013 by Lion.Kanzen

[FeXoR]

eduh: Thanks for your interest.

Sadly my progress is slow ^^.

[niektb]

This sounds like a fun idea for generating realistic rivers:

http://playtechs.blogspot.nl/2008/11/rapidly-exploring-random-trees.html

[Radagast.]

Good find, looks promising to me. The problem is, this algorithm does not take terrain height into account.

The branches are generated by

generate a sequence of random points distributed uniformly over the [map]. For each point, find the closest point on the tree and create a new branch from there, headed toward the random query point. You don't go all the way to the query point, though; just a small step. The net result of this is that the tree tends to head toward open areas.

The difference for us were that we needed to avoid high ground when connecting two points. So following the steepest slope (gradient).

For this to work we first had to determine the higher of the two points, otherwise we never could reach the counterpart.

Looks like a terrain with determined height precondition!?

FeXoR's algorithm - in contrast - seems to erode the terrain while developing. This might be difficult impossible to bring into harmony with the proposed algorithm in the link. So FeXoR's rain river algorithm is more powerful. The other could still be used for adding rivers to already created maps where height is settled.

Thx FeXoR for the fun (and the snow tips). I will take a look at the rain. I imagine you even visualised the drops. It must have taken years to show us the results. Weren't there once this nuclear fusion reactor which went into service 4 years agon and whose form had to be calculated for 12 years by a supercomputer?

Oh, I forgot another difference - should we intend to consider Niek's linked algorithm. The width volume (due to narrow passes, obstacles) of the river can follow the colour darkness algorithm:

've shaded the tree edges as a function of how many other edges empty into them, so you can see the big rivers are darker than their tributaries.

Edited April 15, 2014 by Hephaestion

[FeXoR]

The problem with the approach of the link is that the algorithm only works on a uniform map (equal height everywhere).

The hight could then be changed according to the shading.

However, I think I can make the erosion work reasonably fast (I have a few more ideas).

My latest version is indeed more sophisticated then everything I've seen so far in code.

It roughly works like:

- Let it rain dependent on height (get/change water depth map)

- Get slope vector map (from height map)

- Get acceleration vector map dependent on slope and gravity (would be nice to have the correspondent variable from the engine at hand)

- Calculate total speed vector map considering acceleration, last steps water speed and friction (dependent on the water depth and previously calculated water speed)

- Change the water depth map accordingly and the height map dependent on water speed and soil portion (dependent on water speed as well)

(This takes longer to calculate for each step obviously but the erosion effect is much stronger then just considering water derivation to appending tiles so much less steps are needed)

However, there's only one direction all water flows from one tile (two appending tiles getting it) so in the end the resolution might always be a little bad.

And wraitii was right at the start: One problem of the actual implementation is the slope is calculated wrong (shifted half a tile) so the outcome gets edgy at ~100 cycles even if gravitation, rain and soil portion is quite low and friction is quite high (already did this for the realistic terrain demo so all I have to do is puzzle everything together).

After this change it might be possible to raise the erosion strength (raise gravitation and soil portion, lower friction) so less steps are needed (10-20 would be OK meaning about 2-3 min calculating for giant maps... yes, still a lot but some other random maps take longer).

If this (quite realistic) approach fails in speed I can still use an older, simpler one (though I'd be a bit sad ^^).

[ofc. this would all be much faster if implemented in C/C++ and given to the random map libs as a shared function]

Edited April 15, 2014 by FeXoR

[sanderd17]

FeXoR, if it can help you a bit, the Engine is made to allow a water height map (or at least different water heights). The method to query the water height does it on a certain point on the map.

I think, the main reason that different water heights aren't implemented yet, is because it's hard to design an Atlas GUI to allow different water levels in different places. But for random maps, this should be a problem.

[Stan`]

Can a water tile system be implemented ? Like 5x5 tiles with a water texture ?

[FeXoR]

Thx, sanderd17!

For the different water levels I'd need to know the structure of the water planes the engine should get from RMGEN..

Then I'd add it to the Map class in this (or a similar) structure (and maybe add a variable to enable different water levels which would be False by default to avoid breaking existing maps).

Not sure which part of code takes the outcome of the RMS then...

This would not help for erosion in any way though.

For that I'd need some C++ functions somewhere in the non-game-engine code that can be called by RMGEN (since RMGEN runs before the engine starts AFAIK).

I have simply no idea how to do that (only did this with C -> Python).

So if you could help here that would be terrific.

In general I'd really like if variables like min height, max height, gravity, wind speed, wind bumpiness, ... would be defined at exactly one place.

Some of those might be useful to be set from different parts of the code as well.

I don't know if the parsing will cause more trouble in the end then defining them over and over again in the different parts.

Some functions, however, would really be useful to have.

As an example fast slope calculation is needed by: Pathfinder, Unit AI, Player AI (simulations), random maps (RMGEN) and the graphics engine.

The specific needs for making water erosion for RMGEN faster would be a faster function to calculate the slope map:

- getSopeMap(heightmap)

Takes: heightmap (An rectangular (or square though I don't see the benefit) array of float32arrays)

Returns: slopemap (an rectangular array of arrays of arrays (size two, vector) of width and length one smaller than the give heightmap determining the incline of the surfaces between the vortices)

(This will also be useful for (non-tile centered) slope dependent terrain painting... and I don't see why the tile centered version should be used in these cases)

A similar function in javascript looks like:

function getSlopeMap(heightmap){heightmap = (heightmap || g_Map.height);var max_x = heightmap.length - 1;var max_y = heightmap[0].length - 1;var slopeMap = new Array(max_x);for (var x = 0; x < max_x; x++){slopeMap[x] = new Float32Array(max_y);for (var y = 0; y < max_y; y++){var dx = heightmap[x + 1][y] - heightmap[x][y];var dy = heightmap[x][y + 1] - heightmap[x][y];var next_dx = heightmap[x + 1][y + 1] - heightmap[x][y + 1];var next_dy = heightmap[x + 1][y + 1] - heightmap[x + 1][y];var vector_x = 0.5 * (dx + next_dx);var vector_y = 0.5 * (dy + next_dy);slopeMap[x][y] = Math.pow(vector_x * vector_x + vector_y * vector_y, 0.5);}}return slopeMap;}

It returns floats instead of vectors for each surface and could be optimized (e.g. it calculates every edge vector twice, once for each appending tile)

I don't have enough overview to decide whats best to do in general.

Edited April 15, 2014 by FeXoR

[Radagast.]

Random map generation seems like magic and a very important issue to me. It's connected to the real world and gives us the edge in realism. Thx for that.

For the C++ me myself is digging deep in there, though I'm not there yet and thus also have problems to find conclusions as to where to put what, so that it's best.

Nevertheless I will keep an eye on the Random Map Generation while further diving in the coral reef of pyrogenesis. Who I not also find a corn some time.

As to the function. Are you sure we can save one edge calculation. It seems to me that minuend (left of the -) and subtrahend (right of the -) are swapped? Edit:Oh I think you mean the last line being calculated twice?

var vector_x = 0.5 * (dx + next_dx);var vector_y = 0.5 * (dy + next_dy);slopeMap[x][y] = Math.pow(vector_x * vector_x + vector_y * vector_y, 0.5);

We could write as:

var vector_x = (dx + next_dx);var vector_y = (dy + next_dy);slopeMap[x][y] = Math.pow(.25 * vector_x * vector_x + .25 * vector_y * vector_y, 0.5);

Whose last line we could write as:

slopeMap[x][y] = Math.pow(1/4 * (vector_x * vector_x + vector_y * vector_y), 0.5);

And furthermore due to 1/4 == 1/(2^2) and sqrt(1/(2^2)) == 1/2 :

slopeMap[x][y] = .5 * Math.pow(vector_x * vector_x + vector_y * vector_y, 0.5);

Tell me if I'm wrong. Does only save one multiplication I'm afraid. Edited April 15, 2014 by Hephaestion

[FeXoR]

Hephaestion: You are right. I use the "* 0.5" in the lines "vector_x" and "vector_y" because otherwise it would be twice the vector.

What I mean is when I go through the grid I calculate "dx" and "next_dx".

For x = 0, y = 0 next_dx is heightmap[1][1] - heightmap[0][1].

For x = 0, y = 1 dx would be heightmap[1][1] - heightmap[0][1].

So they are the same but I calculate them twice.

For dx/next_dx I could just remember next_dx and use it for the next tile as dx (if it's not a new x line, which is the same as "if y != 0").

That way I'd replace the calculation "heightmap[1][1] - heightmap[0][1]" with "dx = next_dx" and the condition "if y != 0" (in most cases) which should be a bit faster.

For dy/next_dy this will not work though (because dy will never have been calculated in the last tiles calculations).

Originally I looped and only calculated the dx/dy, put them in an array to then use them to calculate the slope later.

That way I did only calculate everything once but then I needed two loops which in the end was at least ugly (and likely slower).

Further explanation to disenchant the magic:

The heightmap is an array of map size arrays with map size floats in them (the height dependent on x (first arrays index) and y (second arrays index) coordinates).

So the height at coordinates x/y is heightmap[x][y].

This points define the most accurate edges (e.g. peaks and pits) of the heightmap (further called vortices).

I usually think of it as a cross-section paper where the vortices are the crossings of the lines.

Tiles are the square areas between lines (with the cross-section paper in mind).

I want to know the direction (2 dimensional only) of the highest incline of the tiles and how extreem the incline is.

Tiles are placed between the vortices so e.g. the first tile would have the corners at 0/0, 0/1, 1/0 and 1/1 (so the center of this tile is 0.5/0.5).

The incline is usually represented by a vector.

The direction of the vector indicated direction of the highest incline.

The length of the vector indicates how extreme the incline is (The length is just (vector_x² + vector_y²)^0.5), theorem of Pythagoras).

To get a tiles incline direction I first calculate the incline (difference of heights) of the four edges of a tile (dx, next_dx, dy and next_dy).

Then I calculate the components (x and y direction) of the vector of highest incline by just summing up the x and y incline of the edges individually (vector_x/vector_y).

Since I only need a value for the steepness (in this case, realistic terrain demo) and not the direction I then calculate the vectors length (vector_x² + vector_y²)^0.5.

For terrain placement on realistic terrain demo I only do two different things dependent on the incline (on low and high incline) so I might as well get rid of the "normalization" to increase speed (the " * 0.5" and the " ^ 0.5").

Speed is not critical here though since it only runs once.

For erosion and in general I need the normalized vector though so there's not much to optimize.

And sadly here performance is vital because it will be used several times.

Edited April 16, 2014 by FeXoR

[Radagast.]

At the first look you could save the previously calculated row (and this way reuse it later) .. just like you do it within one row.

Probably Agentx could put his asm.js into action here. We should ask him.

I will continue thinking about it.

Sidenote:

Also below your profile in the upper right corner (in the menu that opens) is a button that reads "Your Content". This is what I mostly use to stay on topic. Though you could miss "important" new threads.

Edited April 24, 2014 by Hephaestion

[Radagast.]

var next_dx = heightmap[x + 1][y + 1] - heightmap[x][y + 1];
var dx = heightmap[x + 1][y] - heightmap[x][y];

var next_dy = heightmap[x + 1][y + 1] - heightmap[x + 1][y];
var dy = heightmap[x][y + 1] - heightmap[x][y];

For x = 0, y = 0 next_dy is heightmap[1][1] - heightmap[1][0].
For x = 0, y = 0 dy would be heightmap[0][1] - heightmap[0][0].
For x = 0, y = 1 next_dy would be heightmap[1][2] - heightmap[1][2].
For x = 0, y = 1 dy would be heightmap[0][2] - heightmap[0][1].
For x = 0, y = 2 next_dy is heightmap[1][3] - heightmap[1][2].
For x = 0, y = 2 dy would be heightmap[0][3] - heightmap[0][2].

For x = 1, y = 0 next_dy is heightmap[2][1] - heightmap[2][0].
For x = 1, y = 0 dy would be heightmap[1][1] - heightmap[1][0].
For x = 1, y = 1 next_dy would be heightmap[1][2] - heightmap[0][2].
For x = 1, y = 1 dy would be heightmap[2][1] - heightmap[1][1].
For x = 1, y = 2 next_dy is heightmap[1][3] - heightmap[0][3].
For x = 1, y = 2 dy would be heightmap[1][2] - heightmap[0][2].

You are right, that's tricky, neither iterating the other way round helps, nor iterating an alternating way (jumping around which would be quite complicated too and introduce new write operations due to adding the loops' increments).

Though if cost is free, there is a solution because array random access requires only a constant amount of time, we can:

var heightmap_subtraction_cache = []; // [x1][y1][x2][y2] = resultfor (var x = 0; x < max_x; x++){    slopeMap[x] = new Float32Array(max_y);    for (var y = 0; y < max_y; y++)    {        var dx = heightmap_subtraction_cache[x + 1][y][x][y] || (heightmap_subtraction_cache[x + 1][y][x][y]  = heightmap[x + 1][y] - heightmap[x][y]);        var dy = heightmap_subtraction_cache[x][y + 1][x][y] || (heightmap_subtraction_cache[x][y + 1][x][y] = heightmap[x][y + 1] - heightmap[x][y]);        var next_dx = heightmap_subtraction_cache[x + 1][y + 1][x][y + 1] || (heightmap_subtraction_cache[x + 1][y + 1][x][y + 1] = heightmap[x + 1][y + 1] - heightmap[x][y + 1]);        var next_dy = heightmap_subtraction_cache[x + 1][y + 1][x + 1][y] || (heightmap_subtraction_cache[x + 1][y + 1][x + 1][y] = heightmap[x + 1][y + 1] - heightmap[x + 1][y]);        var vector_x = (dx + next_dx);        var vector_y = (dy + next_dy);        slopeMap[x][y] = 0.5 * Math.pow(vector_x * vector_x + vector_y * vector_y, 0.5);    }}

Edit: The heightmap_subtraction_cache solution above ensures every subtraction is only calculated once.

Hephaestion: You are right. I use the "* 0.5" in the lines "vector_x" and "vector_y" because otherwise it would be twice the vector.

True, though for the scope the vector_x and vector_y variables are defined it doesn't matter if you half both initial vectors first or simply calculate with twice the length vectors and half the resulting vector afterwards. At least that's what my math calculations above showed.

If the JavaScript interpreter + compiler know math and do this implicitely that'd be great but I doubt they see this optimization of getting rid of one division by 2 (it's using shifting anyway so the performance gain might be hardly noticable though).

Edited October 4, 2014 by Radagast.

[FeXoR]

Well, I got a bit done here though focussing more on usability and speed than perfection ... and found out that water erosion works, well, without water x)

I call it "Splash erosion" - for it's like letting go a water baloon above each vertex - but before the next step all water is drained/evarporated ... so there's no need for a water plane whatsoever ^^

From left to right:

1) Base terrain (nice but unplayable) 2) Decay eroded (smooth but boring) 3) Water eroded (slow) 3) Splash eroded (Fast but conserving most of the structure)

Got that idea when playing arround with erosion_demo_simple_water.js (feel free to do so, see setup line 26 ff) which kept working when basically all parameters where 1

erosion_demo_maps.zip