Patch: The Rainfall River Generator

[ic111]

And in this version, the above mentioned problem of rivers flowing upwards is fixed.

The solution is calculating flow values for all tiles of a wide river (the flow value of the "parent" tile in the middle of the river is used for all tiles that are added for it). Inclined slopes are possible only if the above tile has equal or smaller flow.

EDIT: File deleted because of a patching mistake, see next post.

[ic111]

Sorry, a small mistake in dealing with the patches, in the previous v18 release.

Here is the corrected file.

For those who already downloaded:

In rivers_rainfall.cpp, function IsInclinedSlopePossible, the "+" at the beginning of the following line is of course nonsense. Remove it, and continue compiling. Don´t ask me how I added that to the file...

Code: Select all

+ 		clause_seven = water_flow[water_neighbor_tiles[direction]] <= water_flow[tile];

[ic111]

And, BTW, this is my most frequent testcase for this patch.

The heightmap is based on a real world height map of the region around western Austria. The large mountainous part in the middle is more or less unchanged from real world, the two coast lines are manually generated in scenario editor.

It is intended for 1024x1024, and max heightlevel 60. River settings e.g. include "Create river if flow >= 200", "Flow consumed per lake tile volume zero", "Flow modifications per 1000 tiles = 30", "Wider rivers on, multiplier = 40", "Wider valleys on, multiplier = 5".

[ic111]

Again an intermediate release.

I realized that the way lakes, wider rivers, wider valleys, and the algorithm for assuring legal slopes for rivers influence each other is a harder problem than I first thought.

I improved some aspects of how rivers especially near lakes are treated, but the problem that due to the restriction "water can only be placed at flat or inclined slopes" the lake outflows aren´t guaranteed to be generated properly is not yet solved.

Probably I will have to add another step before the final finetuning of slopes, where based on some known problematic patterns, terraforming can be performed, and certain tiles can be declared to be no river although the generator decided for river in a previous generation step.

For example, islands inside a wide river that occur because a slope in the middle of the river isn´t suitable for water are not always bad; but when the fine tuning step tries to get rid of them, it has to move the whole stair towards the next heightlevel, until it finds a situation where all tiles of the river can ascend simultaneously.

Thus, if I declare such an island to be land, I avoid a potential situation where in the end, half of the adjacent lake is lowered by one heightlevel...


On the other hand side, I can probably get rid of some other terraforming code I implemented long before recent improvements to the final terraforming step.

[ic111]

And the next version.

Changes:
- Some bugfixes regarding bookkeeping
- The wider rivers and wider valleys patches (formerly 200 and 210) are now merged; in fact the main difference between generating wider rivers and generating wider valleys is a case distinction in a quite low level function call; so two patches for this purpose have little benefit, but are somewhat tedious to maintain.
- New patch 210: Now, there is an extra postprocessing step, where river tiles that have wrong slope, and that have a diagonal lake neighbor are merged with that lake. This prevents one case that caused lakes to be lowered.

Known bug, and (for programmers familiar with the code) a chance to help this patch:
In rare cases, at coasts, an incorrect slope/ tile type combination is calculated, which crashes the game when trying to paint it.

This is based on a problem I was unable to solve up to now: I introduced support for calling terraform operations from the map generator, as my river generator depends on a valid landscape after terraforming, i.e. I cannot work like tgp and ignore landscape concepts while terraforming. Somehow, in that case, my code seems to fail to correct the tile type, which is done perfectly when terraforming in-game.

Up to now, I was unable to identify what step is missing in my terraform changes, so I introduced a temporary workaround step in patch 063, namely function FixShores. And, the crash above is probably caused by one location where FixShore is not called.

Thus: If anyone could have a look / has a clue, what step is missing in my terraform code, this would be quite helpful. Patches 060, 062 and 063 are related to this issue. Once it is solved, patch 063 and all calls to FixShores can be discarded as a no longer needed workaround.

[Eddi]

missing a "Clear" command? Or some commands have different behaviour depending on the game mode (main menu, scenario editor, game)

[ic111]

In the river generator, I not really execute commands.

Instead, I extracted the functionality of the terraforming command, and made it accessible from the map generator (together with a clear comment to only use that function in map generation...).

One reason to do so is, that in some circumstances I need to be able to inspect the internal planning state of the terraformer before deciding wether I actually want to terraform (SimulateTerraforming). E.g. if one of the affected tile is planned to be river, was flat before and would be a one-corner-up-slope afterwards, I might come to the conclusion that proceeding wouldn't make things better, and stop with terraforming at this place.

Seems that I lost something during that refactoring.

So, maybe you are right, I just didn't discover the point in code that is missing yet.

[ic111]

The next release.

The bug regarding not cleared water (and other tiles, but for them it didn´t matter) is solved. The reason was, that the clear commands were executed without DC_EXEC flag. And this happened, because they are placed above the execution block (since they need to be tested as well), and I moved that block of code into SimulateTerraforming, and missed the fact that I need to execute that commands in ExecuteTerraforming as well.

The other change is another algorithm for fine tuning tiles: After certain river tiles became lake tiles, now that algorithm iterates over all problem tiles (= tiles planned to be river, but having invalid slope), and tries certain terraforming operations on them. In code, for example:

Code: Select all

std::vector<TerraformingScheme> slope_to_schemes[31];
(...)
slope_to_schemes[SLOPE_NWS].push_back(TerraformingScheme(SLOPE_SW, -1));

... reads like: If you have a tile with SLOPE_NWS, that is planned to become a river, then try wether you can make it a river if you terraform it to SLOPE_SW at one heightlevel lower.

E.g. for SLOPE_NWS, currently 9 different such rules exist. All of them are evaluated using SimulateTerraforming. For each of them, (1) the number of (planned) river tiles that were not suitable before, but are suitable afterwards, and (2) the number of (planned) river tiles that were suitable before, but are no longer suitable afterwards, is counted.

If more tiles become ok, than not ok, then the terraforming improves the overall situation, and can be executed. Of all evaluated terraformings for some particular tile, the best one based on that score is actually executed.

Using that algorithm, on the test case heightmap I posted above, the number of problem tiles decreases from 5900 to 1600 by using this algorithm.

[ic111]

Changes in this version:

- Remove the first tile fine tuning step (declaring tiles part of lakes, if they are a diagonal neighbor of a lake tile), since when executed in an iterative manner it can enlarge a lake more than one wants. Code is still there, just the call is outcommented at least for now.
- Up to now, the fine tuning step trying local terraformings (as described above) would alter the height of lake tiles to a different value than defined by the surface height of a lake. As river and lake tiles are in terms of OpenTTDs model the same, in theory this shouldn´t matter, however in practive this could lead to unwanted terraformings. Thus this is now forbidden.
- More terraforming operations that algorithms tries for SLOPE_N, SLOPE_W, SLOPE_E, SLOPE_S
- A new fine tuning step that discards river tiles that are not relevant for keeping lakes / rivers connected.

The criterium for the latter check is rather simple: I step around the 8 neighbor tiles of the tile at hand, and count the gaps (regions of at least one land tile) between the water tiles among those neighbor tiles.

Example:
WWLWWWWW gives one gap
LWWWLLLL gives one gap
LWWWLLLLW gives two gaps

If there is not more than one gap, we know for sure that all neighbor water tiles of the tile are connected, and thus we can safely discard the tile.

Beside more cases of problem tiles, the following two situations introduced as a side effect of the local terraformings need to be addressed in future versions. If you want so, known issues.
(1) Because local terraformings are allowed to raise terrain, it may in particular raise former ocean tiles. Thus, currently, it may produce gaps between river and ocean at the end of a river towards the ocean.
(2) Rivers flowing upwards.

[ic111]

Now, if a problem tile is really impossible to terraform towards water, and two of it straight neighbors are already planned as river, but the diagonal neighbor tile in between not, I instead try to make this one a river.

Before I started this series of patch versions, on my testcase map,I had about 6500 tiles the final "make everything lower until valid" algorithm had to process. Now I have about 350, so I am approaching a state where that final algorithm doesn´t demolish the river system...

BTW, reasons for releasing that often:
- Backup, this way I don´t have to worry about a backup for the patch files while I am preparing the next release
- Keeping merges small: The absolutely annoying thing about patch queues for such a big patch is, that you spend hours and hours for placing changes into the right patch of the queue. For this version, I just spent about 90 minutes of copying code from one patch file to another, hg qpop things, make changes, compile (everything since hg qpop had to pop patches with changes to english.txt), hg qpush to another patch, fix rejects, and so on...
I am *really* glad that I don´t have to work this way in real world at work...

[JGR]

I am *really* glad that I don´t have to work this way in real world at work...

If that's the case, why are you using mq at all, out of curiosity?

[planetmaker]

Now, if a problem tile is really impossible to terraform towards water, and two of it straight neighbors are already planned as river, but the diagonal neighbor tile in between not, I instead try to make this one a river.

Before I started this series of patch versions, on my testcase map,I had about 6500 tiles the final "make everything lower until valid" algorithm had to process. Now I have about 350, so I am approaching a state where that final algorithm doesn´t demolish the river system...

BTW, reasons for releasing that often:
- Backup, this way I don´t have to worry about a backup for the patch files while I am preparing the next release
- Keeping merges small: The absolutely annoying thing about patch queues for such a big patch is, that you spend hours and hours for placing changes into the right patch of the queue. For this version, I just spent about 90 minutes of copying code from one patch file to another, hg qpop things, make changes, compile (everything since hg qpop had to pop patches with changes to english.txt), hg qpush to another patch, fix rejects, and so on...
I am *really* glad that I don´t have to work this way in real world at work...

Maybe you should give the evolve (mutable history) extension a try?
http://www.gerg.ca/evolve/user-guide.html
https://www.mercurial-scm.org/wiki/EvolveExtension

[ic111]

Thanks for the links.

Is anyone actually using those extensions in the context of this project, or are they more keywords that came across you?

Anyway, probably the generator is in a state where finishing it in the current implementation workflow seems feasible. If I would do it a second time, maybe postponing the step of splitting up the algorithmic parts of the generator into separate patches until it is really really finished would be a senseful (= less time consuming for me) option.

@JGR: Because it is part of the way OpenTTD as a project works.

[JGR]

@JGR: Because it is part of the way OpenTTD as a project works.

OpenTTD is not tied to Hg or Hg/mq specifically.
I used to use Hg with mq and found it uphill work, and even lost data using it at one point. At present I use git for all my projects (including work on OpenTTD).
OpenTTD provides git and Hg mirrors, but you're not limited to using those and can import the source into whatever source code management system you like.

Anyway, probably the generator is in a state where finishing it in the current implementation workflow seems feasible. If I would do it a second time, maybe postponing the step of splitting up the algorithmic parts of the generator into separate patches until it is really really finished would be a senseful (= less time consuming for me) option.

What I would generally suggest in a case like this would be to linearly make lots of small commits as you go, and then re-order and merge them into meaningful units when you have something working that you want to export. This is so that you don't have to do any splitting, as this tends to be labour-intensive. (I usually use `git rebase -i` and sometimes `git merge --squash` for this sort of thing).

[ic111]

Well, eventually someone has the task to merge things, and that´s me

I mean, if I do things like, adding an extra parameter in function foo in line n in patch 220, and add another function bar in line (n+1) in patch 230, then I will create a reject. And I doubt that I could get rid of that by what you call "reorder commits". And if I could, then the underlying system would be that heuristic that I would not trust it in managing a codebase of 5000 lines of code over many commits without introducing some maybe not immediately noticed errors.

And the smaller the commits are, the more conflicts between them will arise. If e.g. one helper function is introduced in a commit, and the context for the commit (where should it placed in the file?) involves the end of the previous function, then it will fail (for good reasons) if it doesn´t find that previous function because I added another commit with another function at that point of code.

This kind of work IMHO is inherent to working with patches in a distributed version control system. This is not svn, where a commit is something permanent I don´t have to bother with afterwards as long as I don´t create a conflict with someone else...

And yes, I could import it into what I want, but in the end if one thinks about the chances for trunk (probably, the biggest contra-argument for this anyway is the time needed for reviewing thousands of lines of code) given what I read so far I need this kind of setup.

[ic111]

Some bugfixing.

[wallyweb]

Some bugfixing.

Finally a pause when I can compile

Compiling City generation = Off fails:

compile_fail v24 cityOff.png (41.88 KiB) Viewed 2597 times

However adding 320_GenerateCities.patch for City generation = ON works. Here is the Windows 32bit binary:

OpenTTD 1_5_2 Rainfall_v24_cityOn_Win32.7z

City generation = ON

(4.38 MiB) Downloaded 57 times

Note that I am still unable to generate a map larger than 512x512.
Can this be due to a resource issue with my computer?

[ic111]

Mistake of me when merging and moving code.

The usage of max_river_flow is in patch 105, the declaration in patch 320...

Note that I am still unable to generate a map larger than 512x512.
Can this be due to a resource issue with my computer?

Maybe. I have some sets and maps of non-trivial size. Once in the beginnings of implementation, I debugged that on my machine, I got segfaults out of the innermost regions of std::set once it grew beyond about 500000 entries. I changed code to avoid such big datastructures then, although I did not completely understand why that size is a problem.

[Wahazar]

I tried to import 2048x2048 heightmap: http://149.156.194.203/~mczapkie/Train/ ... alecs2.png
using OpenTTD 1_5_2 Rainfall_v13.7z Win32 release, but openttd quits silently (without any crash log).
Generally any map above 512 size ends with silent crash.

[planetmaker]

Thanks for the links.

Is anyone actually using those extensions in the context of this project, or are they more keywords that came across you?

It's what I use for quite some time. It combines the ease of use of making normal commits while allowing to modify history (like using amend, folding patches, rebasing) *and* keeping the old versions around as obsolete changesets in your (local) repository and easily allowing to update patches further down the road onto their changed parents using the evolve command (which in essence is a special rebase).