Generating seabed heightmap

For code related discussions and questions
User avatar
NoQ
Special
Special
Posts: 6226
Joined: 24 Dec 2009, 11:35
Location: /var/zone

Generating seabed heightmap

Post by NoQ » 12 Jan 2013, 00:05

Asking for some help: everybody who ever had anything to do with map generation, or any fractal landscape generation, are welcome to join.

I've started looking for an algorithm to generate underwater heightmaps.

Currently the game generates it by randomly lowering all vertices related around water tiles before starting the game (in map.cpp/mapLoad() function). This lowering is relative to the map's heightmap terrain, of course, so we can still make things like mountain lakes or waterfalls.

What i'm trying to do is make this random algorithm a bit more clever and sensible. The easiest idea i had so far is to make the seabed smoothly deeper when far from the coast and shallower near the coast. The result is shown on the screenshot below. I'm not yet posting code because it's a bit rusty. I'm still adding some random noise to it.
new_seabed.jpg
Now, what i'd really like to see is a fractal seabed generation, which will give us a varied realistic underwater terrain as we see in seas. Not sure it's necessary, and not sure what exactly is realistic, but it'd be great if somebody comes up with any effective solution.

What we need to code is a function that will lower the seabed. It has access to all vertices of the map (by vertice i mean a common vertice of any 2x2=4 adjacent tiles) and knows whether a certain vertice is to be covered by water; it needs to calculate new heights for all water tiles.

Something like this:

Code: Select all

// produces a dull flat seabed
void generateSeabed(void) {
    int i, j;
    for (i = 0; i < mapHeight; i++)
        for (j = 0; j < mapHeight; j++)
            if (isWaterVertex(i, j))
                mapTile(i, j)->height -= 100; // we refer to the tile, but mean its top-left vertex
}
The code should work pretty quickly, so that it didn't slow down the map loading too much even if the map has a *lot* of water; mapWidth and mapHeight parameters are known to be bounded by 256. Additionally, it would also be cool (but not too much necessary) if the seabed depended only on the shape of the sea (that is, on a symmetric map symmetric pieces of sea would have symmetric seabeds).

Originway
Trained
Trained
Posts: 412
Joined: 08 Aug 2012, 06:22

Re: Generating seabed heightmap

Post by Originway » 12 Jan 2013, 00:27

doesn't the map maker get to pick how they want the water bed to look like or is this extra processing done to what the map maker has already done?

User avatar
aubergine
Professional
Professional
Posts: 3459
Joined: 10 Oct 2010, 00:58
Contact:

Re: Generating seabed heightmap

Post by aubergine » 12 Jan 2013, 01:18

This merits "an sg1efc": :bow2:
"Dedicated to discovering Warzone artefacts, and sharing them freely for the benefit of the community."
-- https://warzone.atlassian.net/wiki/display/GO

User avatar
NoQ
Special
Special
Posts: 6226
Joined: 24 Dec 2009, 11:35
Location: /var/zone

Re: Generating seabed heightmap

Post by NoQ » 12 Jan 2013, 05:09

Originway wrote:doesn't the map maker get to pick how they want the water bed to look like or is this extra processing done to what the map maker has already done?
No, the map maker paints only one heightmap, which equals to height of waterlevel for watered tiles.
Painting seabed is a nice idea for a new map format, but we'd still need to do something with maps where it's not painted.

User avatar
Emdek
Regular
Regular
Posts: 1329
Joined: 24 Jan 2010, 13:14
Location: Poland
Contact:

Re: Generating seabed heightmap

Post by Emdek » 12 Jan 2013, 11:14

NoQ, first off, use preincrementation instead postincrementation for counters in code (++i instead of i++). :-P
As discussed on IRC it could be good idea to explore possibility of ditching water tiles (not completely, to be backwards compatible) and going for simply setting sea level, or something like that. But it wouldn't be able to satisfy all users since it would mean end of individual levels for different water bodies. And making individual sea levels would be insane.
So the only idea that I could think of would be to add some kind of fluid dynamics to game engine, so we could get it done right. Then we would first create terrain and then use some tool to drop specified amount of water to specified place and let it filling so long as we get body water that we want. Which such system we could get "natural" water flow, proper rivers and waterfalls (by defining sources producing water at specified rate and kind of black holes to consume it, to avoid floods ;-)).
Such thing would require lots of work and change way how maps are done but would give lots of possibilities, just imagine scenario when you must fight with enemies to control shrinking land area due to progressing flooding or maybe even things like enemy destroying dam to generate tide to destroy enemy base (I was always curious what would happen if we would be able to destroy that dam in beta campaign). :-D
Nadszedł już czas, najwyższy czas, nienawiść zniszczyć w sobie.
The time has come, the high time, to destroy hatred in oneself.


Beware! Mad Qt Evangelist.

User avatar
NoQ
Special
Special
Posts: 6226
Joined: 24 Dec 2009, 11:35
Location: /var/zone

Re: Generating seabed heightmap

Post by NoQ » 12 Jan 2013, 11:27

Emdek, 100% agree. It's true that even simply separating ground heightmap from water heightmap will create amazing possibilities (you can see another example in the screenshot thread). I just don't want to discuss the new map format in this thread; cause i'm afraid that people who could actually help, if any, may be scared off by necessity of looking through off-topic messages.

Yeah, our main problem is that, despite having a new map renderer, we don't have a map format to make use of it, but only an increasingly ugly in-game converter from the old format; this thread is about making this converter even uglier to produce more beautiful result.

User avatar
Emdek
Regular
Regular
Posts: 1329
Joined: 24 Jan 2010, 13:14
Location: Poland
Contact:

Re: Generating seabed heightmap

Post by Emdek » 12 Jan 2013, 11:31

NoQ, the point is, that basic support doesn't require big format changes, simply define coordinates and amount of water to spill. ;-)

Dedicated topic:
viewtopic.php?f=30&t=10473

EOT
Nadszedł już czas, najwyższy czas, nienawiść zniszczyć w sobie.
The time has come, the high time, to destroy hatred in oneself.


Beware! Mad Qt Evangelist.

User avatar
NoQ
Special
Special
Posts: 6226
Joined: 24 Dec 2009, 11:35
Location: /var/zone

Re: Generating seabed heightmap

Post by NoQ » 12 Jan 2013, 14:28

If anybody wants to try this in-game, here's finally a working patch.

User avatar
Shadow Wolf TJC
Regular
Regular
Posts: 1047
Joined: 16 Apr 2011, 05:12
Location: Raleigh, NC

Re: Generating seabed heightmap

Post by Shadow Wolf TJC » 12 Jan 2013, 15:07

Keep in mind that not every body of water rests on the same level, even in the official campaign. Case in point: Beta Mission 6 (where you have to destroy the Collective Nuclear Power Plant), which has a river at the bottom of a cliff, and a lake at the top of the cliff.

We may need to consider adding a new type of paintbrush for FlaME that places vertices whose height values override the randomly-generated height values. With such a tool, we could carve out underwater trenches or place underwater mountain ranges.
Creator of Warzone 2100: Contingency!
Founder of Wikizone 2100: http://wikizone2100.wikia.com/wiki/Wikizone_2100

User avatar
Rman Virgil
Professional
Professional
Posts: 3812
Joined: 25 Sep 2006, 01:06
Location: USA

Re: Generating seabed heightmap

Post by Rman Virgil » 12 Jan 2013, 15:16

.

Look forward to trying this out. Will add depth to the basic play experience and, as Emdek has described, fresh gameplay mechanics down the road. Another fine piece of work, as is your wont. On a personal note, my attempted waterfalls of the past won't look as silly and weird. Even just realistic looking waterfalls will open up fresh gameplay design opportunities, I believe, even before all the cool stuff Emdek has described. However, another problem I experienced when making 'em in the past was that the water appeared to be flowing up. Probably what made it wierd and silly, now that I come to think of it, which would involve how the animation is implemented.
.
.

Impact = C x (R + E + A + T + E)

Contrast
Reach
Exposure
Articulation
Trust
Echo
.

raycast
Trained
Trained
Posts: 131
Joined: 12 Sep 2012, 19:16

Re: Generating seabed heightmap

Post by raycast » 12 Jan 2013, 21:03

I don't think fractal is worth the effort. Unless you are talking about the super primitive stuff such as the diamond square method.

An approach that should work sufficiently fast to do it at load time is this:

1. for every water tile, compute the distance to the nearest shore (you can do this in a flood fill style, starting with all shore as seeds). Use the distance to the shore as baseline for depth.
2. Add perlin simplex noise to make it look more random, or maybe the current random.

Perlin simplex noise is a classic CGI effect. It's somewhat balanced noise, and you can compute it at the desired resolution and it will be smooth. Just drawing random numbers means it gets more noisy as you increase resolution.
http://mrl.nyu.edu/~perlin/homepage2006 ... index.html

On the long run, we'll need a new map format. For example, water tiles should have an orientation to indicate the desired direction of flow. We may want to have different types of water tiles: water falls, sea, rivers, shore, ... I'd also like to see built-in support for vulcano, paradise and glacier tilesets, for example. I'd love to see higher resolution, in particular for the heighmap. 256 levels is nice for painting them in a graphics application. But for some cool mountaineous maps, the value range is actually quite limited. But this is off-topic for this thread. My point is just that I'd say: keep it simple, and instead of optimizing for the old map format, how about finally moving on to a new format? Then we could use much more complex alogrithms, since they could be computed once when converting the maps only.

User avatar
NoQ
Special
Special
Posts: 6226
Joined: 24 Dec 2009, 11:35
Location: /var/zone

Re: Generating seabed heightmap

Post by NoQ » 13 Jan 2013, 15:29

Thanks raycast, we're finally on topic!
An approach that should work sufficiently fast to do it at load time is this:
That's exactly what i already have; you can see the result on the screenshot(s) and (by the way) it's already in master (:
Perlin simplex noise is a classic CGI effect.
I'll try to see that now. Thanks for a precise and simple link!
My point is just that I'd say: keep it simple, and instead of optimizing for the old map format, how about finally moving on to a new format?
We will have a new format, for sure; once the new ini approach reaches tilesets (see also the newterrain branch in wz git), we will hopefully be having many tilesets, many water types, and a lot of other stuff. In this thread we're talking about hundreds of existing maps that nobody will ever want to convert to any new format; they should still look good even when they lack information inside them.

User avatar
Shadow Wolf TJC
Regular
Regular
Posts: 1047
Joined: 16 Apr 2011, 05:12
Location: Raleigh, NC

Re: Generating seabed heightmap

Post by Shadow Wolf TJC » 13 Jan 2013, 17:06

Hopefully, this new format would be compatable with older maps.
Creator of Warzone 2100: Contingency!
Founder of Wikizone 2100: http://wikizone2100.wikia.com/wiki/Wikizone_2100

User avatar
Emdek
Regular
Regular
Posts: 1329
Joined: 24 Jan 2010, 13:14
Location: Poland
Contact:

Re: Generating seabed heightmap

Post by Emdek » 13 Jan 2013, 17:45

Shadow Wolf TJC, surely it need to use compatible basic concepts, then the only issue is to get someone to work on more than one map parser (I'm planning to have readers for all map types supported so far by WZ in my map editor). ;-)
Nadszedł już czas, najwyższy czas, nienawiść zniszczyć w sobie.
The time has come, the high time, to destroy hatred in oneself.


Beware! Mad Qt Evangelist.

raycast
Trained
Trained
Posts: 131
Joined: 12 Sep 2012, 19:16

Re: Generating seabed heightmap

Post by raycast » 18 Jan 2013, 19:44

My point is: if we would offer a conversion tool, that converts old format maps to new format maps, we could

a) at some point drop the code for reading the old map format from WZ.

b) do much more complex processing, as it doesn't need to be fast. If it takes 5 Minutes to convert a map from old to new, so what. As long as you have to do this conversion only once, then save it in the new format and load the converted file in WZ fast.

Post Reply