Patch: The Rainfall River Generator

[wallyweb]

This is the beginning of the main calculation function.
The question is, does it crash if you (after you made a copy of the file) remove everything but the very beginning of that function? E.g. such that it looks like:

Code: Select all

bool RainfallRiverGenerator::GenerateRivers()
{
	HeightIndex *height_index = new HeightIndex();
	delete height_index;
	return false;
}

If yes,

No ... Did not crash

If no, you might do the same, but keep the code block above including the number of lower tiles calculation, followed again by

Code: Select all

	delete lower_iterator;
	delete height_index;
	return false;
}

I am not sure that I did this correctly, but the following crashed as before.

Code: Select all

bool RainfallRiverGenerator::GenerateRivers()
{
	HeightIndex *height_index = new HeightIndex();

	SetGeneratingWorldProgress(GWP_RAINFALL_NUMBER_OF_LOWER, (MapSize() / 1000) + 1);
	DEBUG(map, RAINFALL_PROGRESS_LOG_LEVEL, "SetGeneratingWorldProgress: GWP_RAINFALL_NUMBER_OF_LOWER = %u", (MapSize() / 1000) + 1);

	/* For each tile, calculate the number of reachable lower tiles.  See the iterator for a more detailed
	 * description of that concept.  Start at the lowest parts of the map */
	NumberOfLowerHeightIterator *lower_iterator = new NumberOfLowerHeightIterator(height_index);
	for (uint h = 0; h <= _settings_game.construction.max_heightlevel; h++) {
		/* For a particular heightlevel, first look at the flat tiles, then at those with height difference 1,
		 * and finally at the steep tiles.  Having a look at map geometry, this order does what we want, beside
		 * the fact that the heightlevel is always the one of the north corner. */
		lower_iterator->Calculate(h, HLIM_ZERO_OR_ONE_CORNER_RAISED);
		lower_iterator->Calculate(h, HLIM_TWO_OR_THREE_CORNERS_RAISED);
		lower_iterator->Calculate(h, HLIM_STEEP);
	}

	int *calculated_number_of_lower_tiles = lower_iterator->GetNumberOfLowerTiles();
	delete lower_iterator;
	delete height_index;
	return false;
}

[ic111]

Thank you, I have a picture what might be the reason:

The connected component calculation I use for finding all tiles that are connected to the current tile at the same heightlevel. I just realized that it is currently implemented in a way that tends to degenerate to a depth first search. Conceptionally, this is no harm, but in practice, this can lead to a huge callstack (i.e. the function calls itself calls itself calls itself ... and this many times) - maybe too big for your system.

To verify this, could you search the following line in rivers_rainfall.cpp, about line 393, and reduce the number at the end:

Code: Select all

	this->connected_component_calculator->StoreConnectedComponent(tile_to_lower_tiles, tile, 100000);

Currently, 100000, choose, say, 10000 and if this doesn´t help either, give it a try with 1000.
(it is the maximum number of tiles it is allowed to store in one connected component).

Independent of that, I think I will change that code to a breadth first search, to avoid such big callstacks. But it would be good to know wether this actually was your problem.

[ic111]

Not yet the aforementioned change, I first finished the topic I started yesterday.

A couple of small changes improve the way rivers end into the ocean. Still, probably some fine tuning step adding some water tiles at that positions might be a good idea, but at least rivers now usually aren´t cut short before the ocean, as it happened before often.

Changes I plan for the near future involve:

1. Exchange depth first search by breadth first search as mentioned

2. Get rid of all those very small depressions (e.g. adjacent slopes SLOPE_NWS, SLOPE_WSE, SLOPE_SEN, SLOPE_ENW, leaving exactly one deeper corner) both tgp and heightmap generation tend to place into the map before my generation actually starts. They have a very bad influence on both generation time and the result, as each such depression triggers a lake.

As a result, on a big tgp generated map lake generation has to take care about thousands of lakes, with the corresponding running time, and additionally, valleys with such depressions in them tend to be filled by long lakes, instead of a river that actually is supposed to be there.

Probably, I have to run the number of lower tiles generation twice, since this is probably the best way to find them. Unfortunately, once terraforming to get rid of them has taken place, I have to throw away the generated number of lower tiles values...

3. The GUI for city generation.

[ic111]

Finally fixed the problem regarding the degenerated depth first search for calculating the connected component.

It is now a breadth first search, and I also removed the limit towards the container size when calculating connected components for number of lower tiles and flow.

Please test, wether this fixes your crashes at the beginning of the calculation.

(when I wrote above, I forgot that there was a second location with similar code in flow calculation, there also was a constant of 100000 as container size limit).

Now I wonder wether staying without any limit for the container size of the connected components is a good idea? Conceptionally, having no limit of course is the right thing. On the other hand side, this means that in worst case, if one generates rivers for a completely flat 4096x4096 map without major ocean parts, 4096 * 4096 = 16 million tiles are added to a std::map. (the values of the map are integers)

I tend to leave it as is without limit, especially, because I don´t regard such worst-case-maps as the primary target of this patch, but if people run into problems with this, I may have to change that decision (which would be simple, as it would just involve adding a max size parameter to a function call).

Opinions?

[wallyweb]

Please test, wether this fixes your crashes at the beginning of the calculation.

Before I compile and test, when applying 240_FixByDiscardingProblemTiles.patch, I got the following message:

240_FixByDiscardingProblemTiles.png (3.83 KiB) Viewed 2261 times

Is this a problem or can I go ahead and compile?

rivers_rainfall.h.rej:

Code: Select all

--- src/rivers_rainfall.h
+++ src/rivers_rainfall.h
@@ -114,6 +114,7 @@
 #define RAINFALL_LAKE_CORNER_LOG_LEVEL 9
 #define RAINFALL_LOCAL_TERRAFORM_LOG_LEVEL 9
 #define RAINFALL_MOVE_WATER_LOG_LEVEL 0
+#define RAINFALL_DISCARD_WATER_LOG_LEVEL 9
 
 /** Just for Debugging purposes: number_of_lower_tiles array used during river generation, preserved
  *  for displaying it in the map info dialog, in order to provide easily accessible information about

[Alberth]

"reject" means that in the file you are changing, the context lines (lines starting with a " " in the .rej file), or the removed lines (you don't have them, but they are lines starting with a "-" in the rej. file) were not the same.

The usual tactic is to open the src/rivers_rainfall.h file, around line 114 (which contained the first line "#define RAINFALL_LAKE_CORNER_LOG_LEVEL 9" when the patch was created).
(Roughly) there you should find the same context lines, and removed lines (which were not removed since the patch was not applied, so they still exist).

Then check what was actually changed between both files. My guess is the "0" of the RAINFALL_MOVE_WATER_LOG_LEVEL line is different in your .h file. That should be fine (log levels are about the quantity of debugging output, which should not have functional changes).


Applying the patch is done by removing all lines in the .h file that have a leading "-" in the patch file (ie the removed lines), and adding all lines that have a "+" in the patch file to the .h file (while removing the leading "+"). The context lines (" " lines) should not change.

[ic111]

Here is the next revision.

I added a preprocessing step that gets rid of all small basins on the landscape, by raising the terrain.

The implementation basically is a composite of code I already had, i.e. I calculate the number of lower tiles measure for the whole map, for all tiles with number_of_lower_tiles == 0 I calculate the connected component of tiles lower than <height> + 1, with a tight limit on the size of the component, and if I find one, I raise land.

The effect is, that I reduce the number of lakes considerably. Decreases calculation speed, especially in some corner cases (e.g. tgp, high quantity of land, flat land), and improve generated landscape, as generally in a long valley, a river looks nicer than a lake that fills the whole valley.

(the point is, if I have a location where a lake starts, and there is enough water, it will expand the lake until it finds an outflow tile, where water can flow to - thus a tiny basin in a huge plain area can trigger a not-too-small lake - and once such lakes join, a sophisticated calculation to distribute the water in the correct way, and merge them correctly, starts)



The next tasks are, I can improve some cases when calculating the number of lower tiles measure, where it currently doesn´t find a valid path downwards, although if you look at the landscape, it could. I.e. water could flow through a valley, but currently doesn´t because my algorithm prefers to produce lake...

And I have a rare condition for an endless loop either in PrepareRiverTile, or in PrepareLake.

[wallyweb]

Here is the next revision.

Unfortunatly the same patch fail as was seen with v33 (above post) still exists. Compile also failed with both v33 and v34 with the same message:

Code: Select all

make[1]: *** [rivers_rainfall.o] Error 1
make[1]: Leaving directory `/usr/home/Adminguy/_Patches/ic111/ic111_rivers_v34-c
ityOn-1_5_2/objs/release'
make: *** [all] Error 1

[Eddi]

Here is the next revision.

Unfortunatly the same patch fail as was seen with v33 (above post) still exists.

are you sure your directory is actually clean, and you are applying to the correct revision?

Compile also failed with both v33 and v34 with the same message:

Code: Select all

make[1]: *** [rivers_rainfall.o] Error 1
make[1]: Leaving directory `/usr/home/Adminguy/_Patches/ic111/ic111_rivers_v34-c
ityOn-1_5_2/objs/release'
make: *** [all] Error 1

that is not an error message. that is just followup from an earlier error.

[wallyweb]

are you sure your directory is actually clean, and you are applying to the correct revision?

Absolutely! I create a new directory for each version so as to prevent cross contamination.

that is not an error message. that is just followup from an earlier error.

Agreed. But it does indicate the presence of an error.

Note that both versions produced the same patch error and the same reject file.

[Eddi]

Note that both versions produced the same patch error and the same reject file.

As Alberth tried to explain, you have to add the line starting with "+" from the reject file manually to the right place (without the +), because the patch program couldn't figure out the right place to put it.

if you are sure the version is right, and the surrounding text looks the same, then the problem might be a wrong newline character.

[wallyweb]

Note that both versions produced the same patch error and the same reject file.

As Alberth tried to explain, you have to add the line starting with "+" from the reject file manually to the right place (without the +), because the patch program couldn't figure out the right place to put it.

if you are sure the version is right, and the surrounding text looks the same, then the problem might be a wrong newline character.

Considering that this is ic111's project and I am merely providing Windows 32bit binaries, I feel I would be imposing to play with his code without his direction.

[Eddi]

i'm not quite sure i understand what you're so afraid of...

[wallyweb]

i'm not quite sure i understand what you're so afraid of...

Replied by PM

[ic111]

First I just thought about improving some conditions during calculating the number of lower tiles measure, but then I realized that I can replace the whole calculation scheme by a much simpler one.

Originally, I tried my very best to detect combinations of neighbor tiles, especially with equal GetTileZ, where one neighbor tile can be regarded being below the other one, i.e. water can flow in a specified direction between them.

Since then, I implemented things like wider rivers and valleys, and a extra treatment against water flowing upwards.

Now, I realized that in fact I don´t need that slope based scheme, as tiles near a river quite probably are terraformed anyway at some time during the calculation, and if in the end some bad combination of slopes lets the river flow one heightlevel upwards, I detect that anyway...

Instead, I just do some breadth first search, and just take care that if I have the choice, I process the flat tiles of a heightlevel before the inclined ones (and similar).

So, in this release the patch got some hundreds lines of codes shorter (which, given its size, is no bad news I think...).

[ic111]

Changes this time:

Improved flow calculation. I also switched to a connected component for this. This avoids situations where a lake is created just because tiles are processed in the wrong order. Now, I first calculate the connected component of all tiles of the given height near the given tile, and then process them in descending sort order (sorted by number of lower tiles). This way, I have the guarantee, that the nearer a tile is to the ocean, the later it will be processed, which is what we need, as water flows top-down, i.e. the flow up in the mountains needs to be calculated first, followed by the flow down in the valleys.

Furthermore, I use the algorithm for removing tiny lake basins now also for removing tiny oceans. Tiny oceans are a problem tgp produces. They disturb the river generator in that they can be the destination of smaller or bigger rivers, i.e. this can lead to the effect that the Amazonas ends up in the small swimming lake in your backyard.

Probably, I´ll make the number of tiles when a lake basins / ocean is regarded tiny configurable in a future release.

[ic111]

Finally forbid the final fine tuning step to lower lake tiles if the lake is bigger than 40 tiles.

It is better if some river tile doesn´t become river, than if one lake tile is lowered, and causes a cascade of lowering tiles until a valid configuration is found.

[wallyweb]

@ic111 - Unfortunately it has been impossible to compile your patch since v33.
With help from Alberth and Eddi ( ) I have found the problem and two possible fixes, both tested.

240_FixByDiscardingProblemTiles.patch fails at line 114 of rivers_rainfall.h

#define RAINFALL_LAKE_CORNER_LOG_LEVEL 9
#define RAINFALL_LOCAL_TERRAFORM_LOG_LEVEL 9
#define RAINFALL_MOVE_WATER_LOG_LEVEL 9

/** Just for Debugging purposes: number_of_lower_tiles array used during river generation, preserved
* for displaying it in the map info dialog, in order to provide easily accessible information about

@@ -114,6 +114,7 @@
#define RAINFALL_LAKE_CORNER_LOG_LEVEL 9
#define RAINFALL_LOCAL_TERRAFORM_LOG_LEVEL 9
#define RAINFALL_MOVE_WATER_LOG_LEVEL 0
+#define RAINFALL_DISCARD_WATER_LOG_LEVEL 9

/** Just for Debugging purposes: number_of_lower_tiles array used during river generation, preserved
* for displaying it in the map info dialog, in order to provide easily accessible information about

Is RAINFALL_MOVE_WATER_LOG_LEVEL supposed to be changed to 0, or is it supposed to stay at 9 ?

Possible Fix #1 - To stay at 9:
Change your patch so that you have

Code: Select all

 #define RAINFALL_MOVE_WATER_LOG_LEVEL 9

Possible Fix #2 - To change to 0:
Change your patch so that you have:

Code: Select all

-#define RAINFALL_MOVE_WATER_LOG_LEVEL 9
+#define RAINFALL_MOVE_WATER_LOG_LEVEL 0

Let us know when your patch is fixed so that we can continue testing.

[ic111]

0 makes it produce logging output about some attempts to adapt rivers and slopes such that they fit (i.e., the generator prints information about why it does something to the console)

For you, probably 9 makes more sense (as you can´t do anything with that output unless you really dig into the code).

But in the end, this doesn´t affect functionality, just the running time can increase by quite a big factor if too much logging is turned on.

Usually, I set all those constants to 9 before a release, but when one moves code between several patches, such mistakes sometimes happen...

[Alberth]

You can make your debugging changes a separate patch applied as final change, and not distribute that patch.