Patch: The Rainfall River Generator

[ic111]

Thank you, I chose the PRINTF_SIZE, using find&replace it was done quite quickly.

The changes in this release are related to bad inclined river tiles, i.e. tiles that have no adjacent upper/lower river tile. The strategy now is:
- Remove them if they are a "dead end" pointing downwards (already implemented in the previous release)
- Remove them if they are not necessary to keep the river connected
- Regard them as ok, if they just move the river sidewards by one tile
- Of course regard them as ok, if they are the source of a river
- In the (seldom) case of an inclined slope towards height zero, that ends up in an opposite inclined slope: Terraform that one to height zero, to (hopefully) create a visible link to the ocean.
- If one of the adjacent upper/lower tile is a flat river tile, try to make the corresponding direct upper/lower neighbor tile a flat river tile either. Try to terraform it to SLOPE_FLAT of the respective height if necessary.

This way, at least most of the problems McZapkie pointed to should be solved. If you don´t find severe problems, I will now probably switch to document things, again have an overall look on the algorithmic patches, improve the progress indicator, and similar things.

[wallyweb]

Thank you, I chose the PRINTF_SIZE, using find&replace it was done quite quickly.

This cleaned up most of the warnings. A few remain and the list is below.

OpenTTD 1_5_2 Rainfall_v49_Win32.7z

(4.49 MiB) Downloaded 126 times

New Game worked without incident.

rivers_v49_warnings.txt

(10.17 KiB) Downloaded 154 times

None were lost to scroll.

[ic111]

Fixed those warnings that are under my control - some of them are triggered by external libraries, one comes from the SaveLoad code of OpenTTD.

Beside this, I refactored the main generator function, to make it more straightforward and understandable. Its comment can be read as "River generation in 19 steps":

Code: Select all

/** The generator function.  The following steps are performed in this order when generating rivers:
 *  (1) Calculate a height index, for fast iteration over all tiles of a particular heightlevel.
 *  (2) Remove tiny basins, to (a) avoid rivers ending in tiny oceans, and (b) avoid generating 
 *       too many senseless lakes.
 *  (3) Recalculate HeightIndex and NumberOfLowerTiles, as step (2) performed terraforming, 
 *       and thus invalidated them.
 *  (4) Calculate flow.  Each tiles gains one unit of flow, while flowing downwards, it sums up.
 *  (5) Modify flow paths, to make the result look like rivers with curves and corners, 
 *       and not like straight channels.
 *  (6) Define lakes, i.e. decide which lake covers which tiles, and decide about the lake surface height.
 *  (7) Prepare rivers and lakes.  Add additional corner tiles to rivers, if flow is diagonal.
 *       Terraform to lake surface height.
 *  (8) Generate wider rivers and valleys.
 *  (9) Find problem tiles, i.e. tiles whose slope is not suitable for becoming river.
 * (10) Try to fix them using terraforming on the small scale.  Do (among a number of possible actions)
 *        what fixes most problem tiles.
 * (11) Try to fix them by moving them, or by declaring them no water if they are not necessary
 *        for keeping the river connected.
 * (12) Derive logical rivers.  Used for fine tuning like preventing upwards flow.  Might be useful for 
 *        generating river names.
 * (13) Set up connections between the logical rivers.
 * (14) Get rid of rivers flowing upwards.
 * (15) Link rivers with the ocean.
 * (16) Raise lower terrain near rivers, to avoid the picture of "why doesn´t it flow down there?"
 * (17) Improve bad inclined river slopes, i.e. (some of) those that have no direct upper 
 *        or lower counterpart.
 * (18) Lower tiles with not yet valid slope, until they are suitable for river.
 * (19) Finally make all tiles planned to become river/lakes river tiles in OpenTTD sense.
 */

i.e. for those asking what I do in which order, this is the answer to that question

[wallyweb]

Fixed those warnings that are under my control - some of them are triggered by external libraries, one comes from the SaveLoad code of OpenTTD.

Here is the latest Windows 32bit binary:

OpenTTD 1_5_2 Rainfall_v50_Win32.7z

(4.49 MiB) Downloaded 138 times

I compiled an unpatched copy of OpenTTD 1.5.2 stable and the same warnings appeared. This confirms that these do not originate with ic111's excellent work. For those who may be interested, the warnings are posted below:

openttd_1_5_2_warnings.txt

(3.07 KiB) Downloaded 127 times

[Eddi]

For those who may be interested, the warnings are posted below:

did you know that there is a proper place where bug reports go?

[Rubidium]

The first warning, about the unused function, is in theory valid in case assertions are disabled. These are disabled for stable releases, but for release candidates and anything else they are enabled. In any case, disabling asserts stops about 20 added asserts in the patch from doing their intended work, and all existing asserts won't be doing their checks on the result of the code. This means that many issues that would be caught by asserts might go unnoticed or throw the person doing the debugging off course (e.g. assuming code cannot have followed a path because assertions were thought to be enabled).
In any case, this is one of the hazards of patching stable releases; you lose much of the sanity checking that other binaries have. Having said that, we could fairly easily prevent the warning with some strategically placed #ifs.

The other issues about arithmetic with NULL are due to your environment. Microsoft defines HIMC as a "handle to input context", whereas a handle is defined as "void pointer". However, your environment defined HIMC as a unsigned integer (DWORD) which makes your environment think that you are comparing a pointer (NULL) against a normal number. If you mess about with your environment so it defines HIMC as HANDLE and not DWORD, then the warnings are gone. It is definitely not something that falls within the scope of OpenTTD's code.

[wallyweb]

It is definitely not something that falls within the scope of OpenTTD's code.

Thanks to you and Eddi for looking at this. I had already logged a bug report, task/6396. My environment is MinGW from the OpenTTD wiki. The only change I made was a bit over a year ago I updated gcc. Has anybody else noticed this when compiling OpenTTD for Windows using MinGW? I would imagine that most people would go straight for the binaries rather than compiling.

If you mess about with your environment so it defines HIMC as HANDLE and not DWORD, then the warnings are gone.

I wouldn't know how to begin to do this.

[ic111]

I added some overview, which step needs how much time; primarily intended as debugging hint. Below you see the times measured on my 7 year old laptop, for a mountainious 1024x1024 map.

Guided by these numbers, I found and fixed two remaining problems:
First, the number of lower calculation interacted with the algorithm for removing small basins in a way that triggered way too many connected component calculations. I.e. setting all tiles at map edge to zero lower tiles is a bad idea if you start a connected component calculation (with some limit, so not the whole map was searched) at each of those tiles.

Second, I realized that the upwards river treatment can be done with much simpler, and at the same time quicker code. I.e. in this release, that step should become faster by a factor 5 or 10.

One well-known situation is not fixed by that algorithm: If you have a river flowing over some small mountain (or from the mountain down to two sides), and the river bypasses that mountain on some other path, then this is not detected.

(I simply calculate a chain of connected components of some height while following down the river, and if at some point, one of those connected components has no lower neighbor tile (and is no final lake, and no ocean-neighbor), then I know that I´m within a basin, and raise the last connected component).

Code: Select all

dbg: [map] Running time for step  (1) HeightIndex: : 0.30s
dbg: [map] Running time for step  (2) Removing small basins: : 3.698s
dbg: [map] Running time for step  (3) Number of lower tiles: : 3.441s
dbg: [map] Running time for step  (4) Flow: : 1.709s
dbg: [map] Running time for step  (5) Modify flow: : 1.467s
dbg: [map] Running time for step  (6) Define lakes: : 0.307s
dbg: [map] Running time for step  (7) Prepare rivers and lakes: : 0.575s
dbg: [map] Running time for step  (8) Wider rivers: : 5.76s
dbg: [map] Running time for step  (9) Find problem tiles: : 0.10s
dbg: [map] Running time for step  (10) Fix by local terraforming: : 2.640s
dbg: [map] Running time for step  (10) Fix by moving problem tiles: : 0.322s
dbg: [map] Running time for step  (12) Derive rivers: : 0.85s
dbg: [map] Running time for step  (13) Connect rivers: : 0.1s
dbg: [map] Running time for step  (14) Fix upwards rivers: : 0.644s
dbg: [map] Running time for step  (15) Link rivers with ocean: : 0.10s
dbg: [map] Running time for step  (16) Fix lower terrain near rivers: : 1.614s
dbg: [map] Running time for step  (17) Fix bad inclined river slopes: : 0.33s
dbg: [map] Running time for step  (18) Lower tiles until valid: : 0.60s

Further remaining problems:
- Connected component calculation can step from inclined slope A to inclined slope B of the same slope type. While not being upwards flow in the GetTileZ sense, this at least give the impression to the player.
- Fixing bad inclined slopes (which runs later) in corner cases can remove a tile (because not needed to keep things connected) that was indeed necessary to avoid the impression of upwards flow.

Regarding the bypass problem described above, probably, stepping over all river tiles in ascending order, and inspecting tiles that are higher than the lowest tile seen before in more detail should be able to solve the problem.

Maybe even running the "lower tiles until valid" step twice, i.e. a first time before setting up logical rivers, is a good idea, it runs (on my system / test case map) in the order of 0.1s anyway).

[Eddi]

for a one-time calculation like map generation i wouldn't be too concerned about speed. as long as it's not taking minutes, and provides visual progress...

[ic111]

This isn´t my concern either. Nevertheless, it gave me some insights of the kind "why does this run for 8 seconds??? does it really do what I think it should do?".

Also, I at some time need to decide wether I need additional generation progress steps. The problem with some of my steps is that the current generation progress framework needs the total number of steps in advance (e.g. 1/540), but some of my algorithms are iterations that proceed until everything is fixed or no further progress can be made. I.e. difficult to put into the generation progress system.

[ic111]

Added a detection for small raised sections of a river.

If such a section is smaller than 12 tiles (more or less arbitrary constant, but it shouldn´t be too big to avoid demolishing senseful landscape), the inclined slope where it starts has bigger flow or river iteration than its lower neighbor tile, and there is no link to terrain higher than height + 2, then I assume that the whole section can be lowered to the base height.

[wallyweb]

...

Which version of OTTD do you use to test your patches?

[ic111]

Well, I checked out current trunk via hg.

I.e. see here under "Obtaining the source code": https://www.openttd.org/en/development

[wallyweb]

Well, I checked out current trunk via hg.

I.e. see here under "Obtaining the source code": https://www.openttd.org/en/development

Yes, but are you using stable, beta (RC) or nightly?

[Alberth]

Development is done on trunk, during the day new additions and changes are made, and you get a new revision with each change.
"current trunk" is any of those revisions.

Once every 24 hours, the trunk version of that moment is build as binary program, for testing. That is called "nightly"

A new release is copied once a year, and build as binary programs in the form of RCs and stable versions.


Bugs that get in trunk (and become automatically available the next evening). The bug fix is also copied (back-ported, as a plain copy doesn't always work) to the next RC and then stable.

[ic111]

Moved the step of fixing bad inclined slopes (i.e. river slopes that have no direct neighbor river upwards or downwards) to a point earlier in the generation, and significantly improved it.

Beside some rules for fixing rather simple situations, it can now fix such slopes by lowering tiles until they fit. Again, special care is taken towards lakes, i.e. the algorithm is only allowed to touch 10 lake tiles, if more would be necessary I regard that as failure.

I can work this way, because SimulateTerraformTileToSlope introduced by this queue can be called multiple times with the same terraformer state; each call operates on top of the result of simulating the previous terraforming operation. This way, I can develop a terraforming until I know wether it works, and cancel the whole operation (= not executing ExecuteTerraforming) without leaving any change to the map, if it turns out to be impossible.

Generating a map with this version of the patch, I see no remaining kind of problem that occurs more frequent than very seldom. For example, on my 1024x1024 test map, the algorithm leaves in the order of 20 inclined river tiles without direct upper or lower neighbor tile.

Thus: I have no plans for additional algorithms left.

[ic111]

Two bugfixes:

(1) The algorithm raising lower terrain near a river did not work for the last heightlevel for a logical river. Fixed.

(2) In very seldom cases (about once in five generations on a 1024x1024 map), the pathfinder reported about not being able to find a path through a lake. Strange since lakes are supposed to be connected.

The reason was, that when one lake consumes another lake (when they grow and finally merge), I make the bigger lake consume the smaller one for performance reasons (less work with the containers). During consumption, lake tiles of the other lake that are too high for the current surface height are discarded.

... and I did not use the surface height of the other lake, if I switch them. So, if the other lake had a lower surface height, and more tiles, it occasionally lost some tiles during merging. Not really visible, just in corner cases, the path finder failed to find a path within the lake...

[ic111]

Refined the prevention of upwards rivers, that code now does its work with much less terraformings.

... and some movement of former bugfixes to the patches they belong to.

[ic111]

Improved the generation progress. In particular, I added the ability to run a generation progress step without in advance known number of total steps.

E.g. when improving things by performing local terraforming, I increase generation progress each time I perform a terraforming operation - but I cannot know in advance how many I will have to perform.

[ic111]

Some small refactorings, many additional comments, and general sourcecode improvements, mainly for patches <= 220.