Patch: The Rainfall River Generator

[Eddi]

i'd make it quadratic

[ic111]

It works now, but in some cases OpenTTD hangs when defining lakes (viewport doesn't update or react to interaction, window can only be force-closed). Tested with the "East Africa (High Terrain)" height map at 1024x1024 and "Moderate" rivers.

Caution, give it a bit of time. The feedback progress isn´t yet completely useful (compare what I wrote right after releasing it about that topic).

This patch also tends to generate clustered short rivers, at least on OpenTTD-generated maps.

tgp tends to generate many basins, especially small areas of ocean, which makes the way to the ocean often short. A screenshot would be good to discuss such things in more detail.

On height maps, some rivers do become nice and long, but there still tend to be multiple rivers in the same area.
Rivers really ought to be merged if they run parallel and relatively close to each other.

Generally, here just helps increasing the flow needed for a river, to get less of them. Merging isn´t actually feasible.

I also think the default river width increase is a bit too conservative, and does it really make sense for the flow required to add another tile of width to increase exponentially?

The idea was avoiding that a river that gains flow from half the map grows really wide. On my test map, one of the rivers has flow in the order of 200000, flow for a small river needed is typically in the region of 100 to 300. If you´re not cautious, the 200000-river quickly is 10 or 20 tiles wide, which probably wouldn´t be what you want either.

i'd make it quadratic

You should be able to do so already, by using multiplier 2, or do I misunderstand you.

[Eddi]

you probably misunderstand me.

2^x (1,2,4,8,16,32,...) is something very different from
x^2 (1,4,9,16,25,36,...)

quadratic generally grows a bit faster in the beginning, but slows down significantly on higher values

i'm not sure if it makes that much of a difference in TTD scale, though.

[ic111]

Ah ok, I probably read too fast

But how would the number series look in detail?

Min. flow 300, factor 10:

Currently: 300, 3000, 30000,300000
Quadratic: What would be your x? Which numbers would you generate?

[planetmaker]

A bit nitpick...

Currently: 300, 3000, 30000,300000

That's not exponential increase of width, but logarithmic: w = log10(flow/30)
Though Eddi doesn't suggest quadratic width dependence either. (rather quadratic or more generally power law series for values which mean an increase in width)

EDIT:
logarithmic: w = log10(flow/30): 300, 3000, 30000, 300000, 3M, 30M, 300M
powerlaw (sqrt): w = (flow/300)^(1/2): 300, 1200, 2700, 7500, 10800, 14700, 19200
powerlaw (4th root):w = (flow/300)^(1/4): 300, 4800, 24300, 76800, 187500, 388800, 720300, 1.2M ...
powerlaw (5th root): w = (flow/300)^(1/5): 300, 9600, 72900, 307200, 937500, 2.3M, 5.0M, 9.8M

[Eddi]

Ah ok, I probably read too fast

But how would the number series look in detail?

Min. flow 300, factor 10:

Currently: 300, 3000, 30000,300000
Quadratic: What would be your x? Which numbers would you generate?

it's really not that difficult
your current (exponential) progression is "a*b^x", where a is your initial flow, b is your factor and x is the width of the resulting river.

let's fix a at 300, and watch the progression over b:

• b=2: 300, 600, 1200, 2400, 4800
  b=5: 300, 1500, 7500, 37500, 187500
  b=10: 300, 3000, 30000, 300000, 3000000

a quadratic progression would be "a*x^2", or a more generic power progression would be "a*x^b".

• b=2: 300, 1200, 2700, 4800, 7500
  b=5: 300, 9600, 72900, 307200, 937500
  b=10: 300, 307200, 5904900, 314572800, 2929687500

(Disclaimer: do not ever trust my calculation skills)

anyway, the higher exponents in the power progression probably do not make a lot of sense, but fractional exponents in integer logic are tricky. although, in map generation you are not necessarily limited to integer logic.

[oberhümer]

The idea was avoiding that a river that gains flow from half the map grows really wide. On my test map, one of the rivers has flow in the order of 200000, flow for a small river needed is typically in the region of 100 to 300. If you´re not cautious, the 200000-river quickly is 10 or 20 tiles wide, which probably wouldn´t be what you want either.

I thought the whole point was to be a bit more realistic. A 10-tile width would be fine for a large river. Even 20 tiles actually aren't enough for an exact representation of very large rivers, but then you're reaching the limits of OpenTTD scale.

[ic111]

A test version where I implemented a scheme like proposed by Eddi.

The multiplier you enter is now 10 times the b in the last post of Eddi.

Example: If you enter 35, you will get a * 2^3.5, a * 3^3.5, a * 4^3.5 etc. Internally, it calculates using pow (double, double), i.e. no integer arithmetic.

This means, entering values close to 10 or even below will probably crash the whole thing.

Please test wether this is a better scheme than the old one.

I thought the whole point was to be a bit more realistic. A 10-tile width would be fine for a large river. Even 20 tiles actually aren't enough for an exact representation of very large rivers, but then you're reaching the limits of OpenTTD scale.

Yes, it´s realism vs. playability. My whole point was, it clearly cannot grow in a linear manner. (it doesn´t in reality either, e.g. as rivers also have a 3rd dimension).

[oberhümer]

With the new version, map generation hangs even on 64x64 maps, outputting something like

Code: Select all

dbg: [misc] Generated curr_bound = 596700, curr_step = 15825646
dbg: [misc] Generated curr_bound = 596700, curr_step = 15825647

and incrementing both continuously until OpenTTD is force-closed.

[ic111]

It´s this loop:

Code: Select all

	/* Alternative way to calculate flow */
	int64 curr_bound;
	int curr_step = 1;
	do {
		curr_bound = (int64)_settings_newgame.game_creation.rainfall.flow_for_river * (int64)pow((double)curr_step, (double)_settings_newgame.game_creation.rainfall.wider_rivers_multiplier / (double)10);
		curr_step++;
		DEBUG(misc, 0, "Generated curr_bound = %i, curr_step = %i", curr_bound, curr_step);
		if (curr_bound < INT32_MAX) {
			bounds.push_back((int)curr_bound);
		}
	} while (curr_bound < INT32_MAX);

What I just don´t understand is how (assuming multiplier > 10) with continuously increasing curr_step, curr_bound can stay constant at a value ways smaller than INT32_MAX.

[Eddi]

This means, entering values close to 10 or even below will probably crash the whole thing.

that would easily be fixed by having "b=(factor)/10 + 1"

(where "factor" is a total misnomer)

[ic111]

Yes, of course, I just wanted to set up a test version quickly to find out wether this is the way to go.

If yes, then of course I would adjust the bounds for the GUI elements etc.

And if the non-termination problem above persists, please exchange that code by the following snippet (I didn´t changed the code, just added an extensive logging statement), in order to find out what´s going on there. If the multiplier is correctly set, then there must be some unexpected problem with the data types, or similar...

Code: Select all

	/* Alternative way to calculate flow */
	int64 curr_bound;
	int curr_step = 1;
	do {
		curr_bound = (int64)_settings_newgame.game_creation.rainfall.flow_for_river * (int64)pow((double)curr_step, (double)_settings_newgame.game_creation.rainfall.wider_rivers_multiplier / (double)10);
		DEBUG(misc, 0, "Generating bounds: curr_step = %i, flow_for_river = %i, flow_for_river_i64 = %lli, multiplier = %i, multiplier_double = %f, exponent = %f, pow = %f, pow_i64 = %lli, curr_bound = %lli, INT32_MAX = %i",
					  curr_step, _settings_newgame.game_creation.rainfall.flow_for_river, (int64)_settings_newgame.game_creation.rainfall.flow_for_river,
					  _settings_newgame.game_creation.rainfall.wider_rivers_multiplier, (double)_settings_newgame.game_creation.rainfall.wider_rivers_multiplier,
					  (double)_settings_newgame.game_creation.rainfall.wider_rivers_multiplier / (double)10,
					  pow((double)curr_step, (double)_settings_newgame.game_creation.rainfall.wider_rivers_multiplier / (double)10),
					  (int64)pow((double)curr_step, (double)_settings_newgame.game_creation.rainfall.wider_rivers_multiplier / (double)10),
					  curr_bound, INT32_MAX);
		curr_step++;
		if (curr_bound < INT32_MAX) {
			bounds.push_back((int)curr_bound);
		}
	} while (curr_bound < INT32_MAX);

[andythenorth]

Fun gameplay > realism. The 10 tiles wide thing is a red herring.

I haven't tried the patch yet, but my favourite thing in the doc was the treatment of valleys, to leave room for building routes along them. That's thoughtful.

[ic111]

A new release that addresses some of the issues.

First of all, I improved the map generation progress; in most situations, you should now get a relatively close feedback about the progress.

It works now, but in some cases OpenTTD hangs when defining lakes (viewport doesn't update or react to interaction, window can only be force-closed). Tested with the "East Africa (High Terrain)" height map at 1024x1024 and "Moderate" rivers.

You were right, this was a case in lake consumption where generation more or less stopped.
I fixed it by introducing a map "tile --> Lake instance" where I previously for the sake of saving memory calculated a connected component for inspecting the consumed lake when necessary.

This made the code somewhat easier, however some problems related to keeping lakes connected persist: On my heightmap-driven testcase, things work quite well, on tgp generated maps, the code has some problems.

One problem is that keeping lakes connected in some cases needed (up to now) path-finding inside the set of Lake tiles. And this is more expensive in terms of CPU than I first thought, thus I intentionally left it our for now at two pieces of code. I will have to think of a way to make this better.

Also, the lake generation code suffers a bit from the fact, that tgp or heightmap generation code leaves quite a lot of tiles where flow cannot flow further downwards. Most of those 20000 tiles on a 1024x1024 map don´t actually trigger any calculation, but still, the lake consumption code (merging lakes that flow over each other before they find an outflow) is called more often than I would wish. Maybe I can think about some preprocessing step that reduces the number of those tiles.

This patch also tends to generate clustered short rivers, at least on OpenTTD-generated maps.

I now discard all oceans that fill less than one percent of the map; i.e. I transform them into land tiles, this way they run through the lake generation code. Together with the "reduce lakes to their necessary tiles" setting this in theory should help gaining longer rivers, however the issue described above still works against this.

Also, this way you shouldn´t any longer see the case "huge river ends in tiny ocean".

Actually, in the end my vision for longer rivers on tgp generated maps is a combination of the settings
- Lakes consume zero flow per tile volume ===> they grow infinitely until they find an outflow
- Lakes are reduced to their absolutely necessary tiles always (probability 1000) ===> they look more like a river than a lake
- High probability for digging an outflow canyon ===> those inverted pyramids are connected by valleys

This, however, doesn´t yet work completely as intended.

[ic111]

This release should fix the remaining lake and flow related problems.

- Lake generation has become faster by a not-too-small factor (by always merging the smaller into the bigger lake I could get rid of a lot of container manipulations)
- I take another detailed look on flow propagation in lakes, when they are consumed or revisited because another Lake above was calculated and propagated its outflow downwards, several cases have to be handled

Also, now there should actually be a path to realistic rivers and valleys on tgp-generated maps. Choose the settings
- flow consumed per lake volume = 0
- probability for outflow canyon = 1000
- probability for reducing a lake to its necessary tiles = 1000

... and you should get something like in the attached screenshot (generated on a 512x512 map).

Unnamed, 1st Jan 1930#5.png

(397.18 KiB) Downloaded 4 times

The idea is simply,
1. fill up all those small basins tgp generates. This alone will generate a lot of lakes, needed flow per volume = 0 guarantees that we never stop before actually an outflow can be found.
2. Then dig outflow canyons for all those lakes (i.e. dig a valley for their outflow river at the heightlevel of the bottom of the lake. This accounts for valleys. But still, we have big lakes.
3. Reduce those lakes to their necessary tiles to keep them connected. Now, they look more like rivers.

If you want some lakes indeed, reduce the probability in 3., and maybe instead play with the probability settings for islands etc. below.

One small drawback with this variant is, that the algorithm for determining the guaranteed lake tiles doesn´t run through the flow modifications. This is the reason why the rivers (rather: minimized lakes) in the screenshot often look quite straight.

Have fun.

rivers_v7.zip

(182.73 KiB) Downloaded 114 times

[andythenorth]

That screenie with TGP looks good

I wouldn't mind if I never saw one of these daft inland seas again either.

[ic111]

Yes, they will be catched by my new logic, that I transform all oceans that account for less then one percent of the map size into land (at least if they are within the map, at the map border, some post-processing code in the tile loop after the generator runs unfortunately fills them with water again).

They will then often fill with water, and become lakes. In some cases, as a result I´ve seen lakes at height zero, that turn into ocean without further height difference. But this doesn´t seem to be any harm, as ocean doesn´t seem to flood river, as far as I´ve seen.

[andythenorth]

They will then often fill with water, and become lakes. In some cases, as a result I´ve seen lakes at height zero, that turn into ocean without further height difference.

Sea doesn't flood canals (hence the zero-height canal-bank build-on-sea hack), rivers probably handled identically.

Might be worth testing the sloped tile with industry newgrf that wants to use sloped coast tiles for location (e.g. FIRS fishing harbours). I think it will be fine, but worth checking the behaviour. Or reading src may be enough (might be in industry_cmd.cpp or a call to a landscape function from there).

[Dave]

I concur with andy - the inland seas infuriate me!!!

ic111 - some excellent work here, please do keep going!

[Eddi]

Sea doesn't flood canals (hence the zero-height canal-bank build-on-sea hack), rivers probably handled identically.

man, always these pesky dutch people abusing the zero-height hack.