Patch: The Rainfall River Generator

Forum for technical discussions regarding development. If you have a general suggestion, problem or comment, please use one of the other forums.

Moderator: OpenTTD Developers

User avatar
JGR
Tycoon
Tycoon
Posts: 1951
Joined: 08 Aug 2005 13:46
Location: Ipswich

Re: Patch: The Rainfall River Generator

Post by JGR » 13 Nov 2015 21:22

ic111 wrote:Thanks, I´ll have a look at them. Do you use standard compiler warning settings, or do you use somewhat more restrictive settings?
I did a standard Linux compilation with no configure flags, using gcc 4.9.2 on a x86_64 Ubuntu 15.04 system.
Ex TTDPatch Coder, Grumpy Greymuzzle
Avatar by MoonsongWolf.
Patch Pack, Github
Dad-Coder since April 2018

ic111
Director
Director
Posts: 608
Joined: 17 Jul 2007 17:56

Re: Patch: The Rainfall River Generator

Post by ic111 » 16 Nov 2015 18:48

I use gcc 4.9.1 on Debian, so I doubt that the gcc version is the problem.

What is the supposed way of determining those compiler warning flags? At first glance, I assumed that configure uses some OpenTTD-specific settings that reflect the code conventions of that project - but that doesn´t seem to be the case?

Can anyone provide a set of warning settings that is regarded useful with respect to this project?

User avatar
JGR
Tycoon
Tycoon
Posts: 1951
Joined: 08 Aug 2005 13:46
Location: Ipswich

Re: Patch: The Rainfall River Generator

Post by JGR » 16 Nov 2015 19:00

If you run `./configure` towards the bottom of the output the warning switches are included in CFLAGS and CXXFLAGS.

On my system I get (trimming defines and other things out)

Code: Select all

using CFLAGS... -O2 -fomit-frame-pointer  -Wall -Wno-multichar -Wsign-compare -Wundef -Wwrite-strings -Wpointer-arith -W
-Wno-unused-parameter -Wredundant-decls -Wformat=2 -Wformat-security -Winit-self -fno-strict-aliasing -Wcast-qual -fno-strict-overflow
-Wnon-virtual-dtor -Wno-free-nonheap-object -rdynamic -DUNIX -D_FORTIFY_SOURCE=2 ...
using CXXFLAGS...  -std=gnu++0x -Wno-narrowing
Ex TTDPatch Coder, Grumpy Greymuzzle
Avatar by MoonsongWolf.
Patch Pack, Github
Dad-Coder since April 2018

McZapkie
Tycoon
Tycoon
Posts: 1175
Joined: 18 Jan 2014 18:10

Re: Patch: The Rainfall River Generator

Post by McZapkie » 17 Nov 2015 10:14

I found another artefact:
Image - this pit appear just before and of map creation.

I still have a feeling, that "Fine tune terrain to make slopes valid against rivers, while keeping them connected" is very volatile - too much cases.
On the other hand, seems that all patch works perfectly for real-life based heightmaps.

Therefore, maybe erosion model of valleys carving is better solution than all these fine terrain adjustments?
If you need to run rainfall routine/flow again, maybe it is sufficient to track only tiles with high amounts of water/flow?
My experimental openTTD server: 149.156.194.203:3979 non-standard client, now testing: JGRPP http://tiny.pl/ggnch
Projects: Reproducible Map Generation patch, NewGRFs: Manpower industries, PolTrams, Polroad, 600mm narrow gauge, preindustrial houses, wired, ECS industry extension, V4 CEE train set.
Addicted to freeciv longturn.

ic111
Director
Director
Posts: 608
Joined: 17 Jul 2007 17:56

Re: Patch: The Rainfall River Generator

Post by ic111 » 17 Nov 2015 21:36

JGR: Could you post the compiler output of the warnings you refer to? It should contain the gcc flags that triggers them.

The only difference between our settings was that you additionally had -DFORTIFY_SOURCE=2, but adding this on my side didn´t change anything. Maybe Debian has another notion of Wall?
McZapkie wrote:I found another artefact:
Image - this pit appear just before and of map creation.
You mean that tile going downwards without any continuation, three tiles to the northeast from the position of the selected tile?
Yes, this happens sometimes, and I don´t regard it exactly nice either. It happens, because some part of my algorithm decided "this tile should become river", in this case probably the wider river generation, and because none of my algorithms detect the problem so far.
I still have a feeling, that "Fine tune terrain to make slopes valid against rivers, while keeping them connected" is very volatile - too much cases.
The most important part of it uses the strategies defined near the end of river_rainfall.cpp, e.g.

Code: Select all

	this->slope_to_schemes[SLOPE_W].push_back(TerraformingScheme(SLOPE_FLAT, 0));
	this->slope_to_schemes[SLOPE_W].push_back(TerraformingScheme(SLOPE_SW, 0));
The strategy which fixes most tiles is taken.
Therefore, maybe erosion model of valleys carving is better solution than all these fine terrain adjustments?
The problem with only lowering tiles is that it can alter landscape significantly. For example, in my test heightmap, I prepared a lake of height 4, and about 20 tiles away a lake of height 8, Through both, a big river flows. Before I implemented the above strategy, the algorithm usually lowered the former lake to height 1 or 2, and the latter to height e.g. 4. Additionally, it often left a stair in the middle of the lake. Only with those strategies, and some additional cases, I succeeded to generate a terrain that (a) keeps the height of the lakes, and (b) is friendly to the river in that it only removes a few tiles from it that cannot be terraformed to a correct slope (e.g. because a series of NW slopes meets a series of NE slopes in a ENW corner).

And here, I regard correct landscape in the large scale as more important than avoiding the last flaw in small scale. I.e., when I prepare such a heightmap in scenario editor, then I simply expect that the lake is at the height I want it to have, and not 4 tiles lower.

At least, my experience of the last weeks teached me that changing less tiles is the better strategy.

In terms of source code, those different strategies are implemented in a way that makes them easily exchangable. E.g.

Code: Select all

	this->FixByLocalTerraforming(problem_tiles, water_flow, water_info, define_lakes_iterator);     // slope_to_schemes
	this->FixByMovingProblemTiles(problem_tiles, water_flow, water_info, define_lakes_iterator);
or

Code: Select all

	this->DeriveRivers(river_map, river_iteration, id_to_river, water_flow, water_info);
	this->ConnectRivers(river_map, river_iteration, id_to_river);
	this->FixUpwardsRivers(river_map, river_iteration, id_to_river, water_flow, water_info);
	this->TryLinkRiversWithOcean(river_map, river_iteration, id_to_river, water_flow, water_info);
so, one can throw away them and implement something different without needing to refactor the remaining code. I mean, if someone can implement something better for some of those aspects, this is not forbidden. Just I tend to regard this as a (in terms of correctness of the algorithms) 99% finished project that in some details can be fine tuned to improve it further, and not as a project where I want to exchange fundamental parts of my algorithms or strategies. In a project of this size, IMHO you at some point in time need to live with the infrastructure you have.

I.e. it took me two or three weeks of frequent OpenTTD coding (in October, we had pretty wet weather which was good for OpenTTD, this changed towards November ;-)) for coming from the situation where it all the time damaged my lakes, to the current situation. And speaking from my experience, I doubt that what you call carving would be done significantly quicker. And I doubt that it would really help at all, after all at some point, rivers need to make the height difference, and if that point (on a heightmap) is diagonal, you somehow need to deal with the situation.

To summarize, we have:
- Rivers flowing upwards: I (not yet released) connect logical rivers now. On this basis, maybe one could improve that. (Un)fortunately, I just wasn´t able to find a single testcase for the problem on a 1024x1024 map, so in my experience, it seems to be rather seldom. So I currently tend to leave this at least for now.
- What you show as in the screenshot above
- Rivers, where the fine tuning step leaves a situation where the river more or less flows on a dam for a short distance.

User avatar
JGR
Tycoon
Tycoon
Posts: 1951
Joined: 08 Aug 2005 13:46
Location: Ipswich

Re: Patch: The Rainfall River Generator

Post by JGR » 17 Nov 2015 21:52

ic111 wrote:JGR: Could you post the compiler output of the warnings you refer to? It should contain the gcc flags that triggers them.
Configure and build log is attached.
Attachments
build-jgr.log.txt
(25.76 KiB) Downloaded 41 times
Ex TTDPatch Coder, Grumpy Greymuzzle
Avatar by MoonsongWolf.
Patch Pack, Github
Dad-Coder since April 2018

McZapkie
Tycoon
Tycoon
Posts: 1175
Joined: 18 Jan 2014 18:10

Re: Patch: The Rainfall River Generator

Post by McZapkie » 18 Nov 2015 15:32

ic111 wrote: You mean that tile going downwards without any continuation, three tiles to the northeast from the position of the selected tile?
Yes, exactly. It doesnt look like wide river, rather wrong delta formation.

Similar glitch (waterfall without continuation) can be spotted very often, for example at previous screenshots, for example
http://www.tt-forums.net/download/file.php?id=188075 right upper corner or http://www.tt-forums.net/download/file.php?id=188132 on the left.
But it looks rather like wrong flow calculation - terrain should affect flow.
EDIT:
Here is another example:
rfrg-wf.png
rfrg-wf.png (51.56 KiB) Viewed 1794 times
flow is more than 450 at each of three waterfall tiles (and 455 above, 463 below, almost zero for dry tiles - no reason for three waterfalls),
one East (as shown), two NorthWest - maybe it would be sufficient if you force flow NorthEast (in case of such tile)?

Generally, flow direction should always be along tile gradient, except of flat tiles.
My experimental openTTD server: 149.156.194.203:3979 non-standard client, now testing: JGRPP http://tiny.pl/ggnch
Projects: Reproducible Map Generation patch, NewGRFs: Manpower industries, PolTrams, Polroad, 600mm narrow gauge, preindustrial houses, wired, ECS industry extension, V4 CEE train set.
Addicted to freeciv longturn.

ic111
Director
Director
Posts: 608
Joined: 17 Jul 2007 17:56

Re: Patch: The Rainfall River Generator

Post by ic111 » 18 Nov 2015 20:41

McZapkie wrote:
ic111 wrote: You mean that tile going downwards without any continuation, three tiles to the northeast from the position of the selected tile?
Yes, exactly. It doesnt look like wide river, rather wrong delta formation.
You are right, I had the wrong picture in mind when I wrote that.
Generally, flow direction should always be along tile gradient, except of flat tiles.
In a continuous landscape, without any tile boundaries and slope restrictions, you would be right. In OpenTTDs world, unfortunately, things are not that easy.

Please have a look at the attached screenshot. It shows a valley in unchanged manner, as generated by the heightmap loader. A bit right of the middle of the screenshot, you have two flat tiles, left of them SLOPE_S, SLOPE_NW, SLOPE_SE and SLOPE_N in a combination that reduces the valley to just one corner. In the left section of the image, before the valley enters the wider plain area, we have a SLOPE_ENS / SLOPE_E combination. Similar towards the right section.

If I would follow your rule, then I would generates lakes and lakes and lakes in such a valley. Because those slopes partition the valley into many small flat or non-flat areas.

And, please keep in mind, what you see here is a quite frequent output of a heightmap loader for a mountainious map, since real slopes are often steeper than OpenTTD allows, which tends to narrow valleys.

What I instead do when calculating the number-of-lower-tiles-measure is, I first consider (among connected tiles of the same GetTileZ) the flat neighbor tiles, then those with one corner up, then the inclined ones, and so on. Once I again find a flat etc. slope, I again first consider that one. This way, my number-of-lower-tiles measure increases from bottom-left towards top-right.

Then, the flow calculation goes the opposite way, starts at the top of landscape, and distributes the flow towards tiles with lower number-of-lower-tiles.
Later steps involve flow manipulation to add curves to the rivers (the number-of-lower-paths are rather straight), generation of wider rivers (i.e. declare tiles near the original river river tiles, but without any respect to flow), and terraforming.

First calculating the number-of-lower-tiles is necessary to (a) find out where lakes need to be situated, and (b) find paths to the ocean in huge plain areas, where no gradient can help you.

So, unfortunately, this is not a problem that can be solved by gradients alone. In earlier versions of the patch, I actually tried to take slopes more into account when deciding which tiles are lower than other ones, but in the end, I realized that this (1) didn´t improve landscape, (2) triggered more lakes than necessary, especially in situations as you see in that screenshot, and (3) resulted in a significantly more complicate code with many case distincations. If I remember correctly, that change eliminated in the order of 500 lines of code.

This doesn´t mean that those problems cannot be solved, it just means that river generation on a discrete map is more than just using gradients.

BTW, concerning the compiler warning problem, I don´t know what happens on my system. Even if I explicitely add the warnings that show up in JGRs log (they are supposed to be triggered by Wextra (shortcut W), but I didn´t trust that 100 percent), I don´t get them. Log is attached.

I think I´ll fix the current problems based on JGRs log, and maybe at a later time install OpenTTD on some other machine I have since October.
Attachments
Unbenannt, 1. Jan 1905#2.png
(235.06 KiB) Not downloaded yet
mywarnings.txt
(21.49 KiB) Downloaded 45 times

ic111
Director
Director
Posts: 608
Joined: 17 Jul 2007 17:56

Re: Patch: The Rainfall River Generator

Post by ic111 » 18 Nov 2015 22:02

To conclude, after thinking a bit about those problems, I think what I can do is a final scan over all river tiles after all other calculation steps have succeeded.

In that step, I can search for certain patterns that are considered bad. For example:

Inclined river slope, the lower tile has no river, nor do the diagonal lower tiles => Remove the river tile, or raise it.
Inclined river slope, the lower tile has no river, but the adjacent inclined neighbor tile of same height, and one of the diagonal lower neighbor tiles are river => Declare the straight lower neighbor tile river, or lower tiles by terraforming to make them flat.
Flat river tile, adjacent non-river tile is lower => Raise that tile.

I have the helper functions to simulate a bunch of terraformings in one attempt to fix such a problem, but after such an attempt, always all planned river tiles need to stay with valid slope. In particular, I certainly cannot change the height of a lake in that step.

The advantage in this step will be that we only talk about flat and inclined slopes, as all other river slopes were eliminated before anyway. This makes formulating rules as above quite a lot easier.

McZapkie
Tycoon
Tycoon
Posts: 1175
Joined: 18 Jan 2014 18:10

Re: Patch: The Rainfall River Generator

Post by McZapkie » 18 Nov 2015 22:31

ic111 wrote:
McZapkie wrote: Generally, flow direction should always be along tile gradient, except of flat tiles.
In a continuous landscape, without any tile boundaries and slope restrictions, you would be right. In OpenTTDs world, unfortunately, things are not that easy.
...
If I would follow your rule, then I would generates lakes and lakes and lakes in such a valley. Because those slopes partition the valley into many small flat or non-flat areas.
But aren't you calculating 2x2 or 4x4 areas? In such case, average gradient would give better chance of proper flow.

ic111
Director
Director
Posts: 608
Joined: 17 Jul 2007 17:56

Re: Patch: The Rainfall River Generator

Post by ic111 » 19 Nov 2015 08:10

Probably, average gradient would point to the inside of such a pseudo-basin either.

One might implement it based on average gradient, but as I didn't do so, the discussion would be somewhat theoretical...

ic111
Director
Director
Posts: 608
Joined: 17 Jul 2007 17:56

Re: Patch: The Rainfall River Generator

Post by ic111 » 19 Nov 2015 21:12

A new release. Changes:

- (Hopefully) fixed the warnings JGR provided. Thanks.
- Added (to struct River, i.e. to the logical concept of a river) the notion of a connection to a downwards river. Beside the completion of the data structure (as I have said some time ago, it might be used for things like river name generation), this allowed to fix a remaining case of upwards rivers.

- Remove inclined river tiles that only have a connection to another river at their upper side.

Some similar cases of bad inclined river tiles might be fixed by future releases. However, rivers will still in some cases change direction somewhat to the right or to the left in a series of inclined slopes (forming a big multip-tile slope). First, I don´t consider that bad, it makes river behaviour more random, than if it would just always flow straight down, and second, changing that wouldn´t be feasable without damaging landscape too much.
Attachments
rivers_v47.zip
(252.63 KiB) Downloaded 36 times

User avatar
wallyweb
Tycoon
Tycoon
Posts: 5519
Joined: 27 Nov 2004 15:05
Location: Canada

Re: Patch: The Rainfall River Generator

Post by wallyweb » 20 Nov 2015 03:22

ic111 wrote:A new release.
:bow:
OpenTTD 1_5_2 Rainfall_v47_Win32.7z
(4.49 MiB) Downloaded 40 times
New Game worked without incident.
- (Hopefully) fixed the warnings JGR provided. Thanks.
I use MinGW (gcc v 4.8.1 ) to compile for windows.
I am not able to log warnings.
The compile flows in a msys command prompt window and the flow disappears beyond the scroll making it very difficult to highlight and copy warning messages.
The attached text file is quite complete with only a part of one section of warnings being lost to the scroll.
I hope this helps.
rivers_v47_warnings.txt
(28.91 KiB) Downloaded 40 times

McZapkie
Tycoon
Tycoon
Posts: 1175
Joined: 18 Jan 2014 18:10

Re: Patch: The Rainfall River Generator

Post by McZapkie » 20 Nov 2015 10:20

Works much better now. Double waterfalls can be still spotted, but are rare.
BTW, I don't understand, how this flow is calculated - why there are 2 waterfalls with similar flow value, let say 650, and similar flow above 620 and below 680. It broke fundamental law of conservation of mass :)

ic111
Director
Director
Posts: 608
Joined: 17 Jul 2007 17:56

Re: Patch: The Rainfall River Generator

Post by ic111 » 20 Nov 2015 16:21

Flow is calculated initially top down, each tile gains flow 1, i.e. out_flow_of_tile = sum(in_flows_of_tile) + 1.
(side note: That "+1" might be made tile-dependent to some extent in the future, e.g. in a rainforest it might be set to 5, and to 1 in a desert. However, values would need to be chosen small enough to avoid overflows (flow has datatype int32))

Flow modification changes flow paths to get more curves in the river, but should update the flow values accordingly.

What can happen is, that e.g. a small river flowing parallel to a big river from the visual point of view merges with the latter one. This effect sometimes leads to quite interesting result, as sometimes the end result is the impression of an island inside a river...

Also, at some points of code, where additional river tiles are added for some reasons, flow values are simply copied. While some later code uses the property that flow increases along rivers, more sophisticated schemes than just copying the values aren´t actually needed in such cases.

I don´t know what situation you mean exactly, but this are some aspects concerning flow...

ic111
Director
Director
Posts: 608
Joined: 17 Jul 2007 17:56

Re: Patch: The Rainfall River Generator

Post by ic111 » 20 Nov 2015 20:33

The next release.

Changes:
Upwards river detection now looks into the next river; this should catch situations where the offending upwards-river-tile is where river A flows into river B.

I added a separate step that terraforms lower tiles near a river to the height of the river. In detail, a breadth first step of at most three iterations, with the river tiles of some particular height as start set, is performed. The search is restricted to non-water tiles of exactly the next-lower heightlevel; if I need to go more than one tile downwards, I consider this some bigger slope where terraforming might leave the small scale.

In particular, I forbid any terraforming of river/ocean tiles in that step, as I only regard this as improvement of the river-near landscape. If I would consider neighbor river tiles, I would need to take care about not introducing new flaws to the rivers...

wallyweb: Thanks for your warnings, however my impression that your compiler is somewhat funny in some circumstances. For example, in lines with a %zu pattern, it warns about an unrecognized %z pattern, and in a %s pattern feeded with string.c_str() it warns about feeding the pattern with size_t (might be a follow up of the first one).
Attachments
rivers_v48.zip
(256.9 KiB) Downloaded 35 times

User avatar
JGR
Tycoon
Tycoon
Posts: 1951
Joined: 08 Aug 2005 13:46
Location: Ipswich

Re: Patch: The Rainfall River Generator

Post by JGR » 20 Nov 2015 22:06

ic111 wrote:wallyweb: Thanks for your warnings, however my impression that your compiler is somewhat funny in some circumstances. For example, in lines with a %zu pattern, it warns about an unrecognized %z pattern, and in a %s pattern feeded with string.c_str() it warns about feeding the pattern with size_t (might be a follow up of the first one).
%z for size_t is a glibc extension which would not be present when linking against MSVCRT on windows, so the compiler is entitled to complain.
Ex TTDPatch Coder, Grumpy Greymuzzle
Avatar by MoonsongWolf.
Patch Pack, Github
Dad-Coder since April 2018

User avatar
wallyweb
Tycoon
Tycoon
Posts: 5519
Joined: 27 Nov 2004 15:05
Location: Canada

Re: Patch: The Rainfall River Generator

Post by wallyweb » 21 Nov 2015 03:49

JGR wrote:
ic111 wrote:wallyweb: Thanks for your warnings, however my impression that your compiler is somewhat funny in some circumstances. For example, in lines with a %zu pattern, it warns about an unrecognized %z pattern, and in a %s pattern feeded with string.c_str() it warns about feeding the pattern with size_t (might be a follow up of the first one).
%z for size_t is a glibc extension which would not be present when linking against MSVCRT on windows, so the compiler is entitled to complain.
Thanks.
The question now is how to deal with this.
It does not seem to affect how OTTD and the patch function on Windows, but are there problems that will appear later in the game?

ic111
Director
Director
Posts: 608
Joined: 17 Jul 2007 17:56

Re: Patch: The Rainfall River Generator

Post by ic111 » 21 Nov 2015 08:32

Good question. While I doubt that it has bad effects on generation, of course it should compile without warnings...

Is there any alternative pattern I might use?
Or is casting to uint the solution? I.e. something like

Code: Select all

DEBUG(map, 9, "Size of your container: %u", (uint)your_container.size());
Would the latter work on all systems without warning?

User avatar
JGR
Tycoon
Tycoon
Posts: 1951
Joined: 08 Aug 2005 13:46
Location: Ipswich

Re: Patch: The Rainfall River Generator

Post by JGR » 21 Nov 2015 11:41

You could cast it, or there's the PRINTF_SIZE macro which expands to the correct size_t format code for the platform.
Ex TTDPatch Coder, Grumpy Greymuzzle
Avatar by MoonsongWolf.
Patch Pack, Github
Dad-Coder since April 2018

Post Reply

Return to “OpenTTD Development”

Who is online

Users browsing this forum: No registered users and 3 guests