More height levels (in trunk since r27010)

[CommanderZ]

Some more work done on the map gen.

I had to tinker with it a lot more then I initialy intened to get from it something more than just random interpolated array of heights - I want the map to have some flatter and also some mountainous/higher located areas. I partially suceeded, this is how the very rough map looks for now.



I did not yet manage to get rid of the geometriness completely (you can see it on the big mountain in the top right corner of the picture).

Also, I encountered this glitch:

glitch.png (24.21 KiB) Viewed 5659 times

It appears only with vertical scrolling with the camera zoomed in. Imo it is what Rubidium tried to warn us before - the area queried for painting needs to be enlarged.

Also, do you plan to increase the height limit any furter?

[ic111]

Technically speaking the patch allows more heightlevels than you can have on a map.

But concerning map generators, in my opinion it's up to the map generator which mountains it produces. If the algorithm supports such a parameter, maybe some parameter "max. generated heightlevel" would make sense. In old games, this parameter would have been 15. But if this is not the case, I think there is no problem if some map generating algorithm never produces a mountain higher than e.g. height 32.

I am especially thinking about playing using heightmaps of real mountainious areas. For example, using a scale like 200m flat land in reality are 1 tile in OpenTTD and 100m of height difference in reality are one height level in OpenTTD, you can play a 200km x 200km mountainious area quite well on a 1024x1024 map.

Concerning the glitches: I am currently working in making the terraforming code robust even concerning really big height levels. Maybe the next thing I will look at will be the glitches.

[CommanderZ]

Oh, I thought I am limited to 32 heights


Could you please set up a patch setting for maximum height?

I would put there values like 16, 32, 64, 128 and possibly even higher (with warning that too high values drain CPU). The glitches make heights over 64 pretty undisplayable for now.

Btw, are you sure mantaining the old array is necessary?

And there is a little teaser what a 80 tile mountain looks like (I know, the terrain is ugly, but...)

EDIT: So with what max height should I account with with my map generator modifictions? 64? That might be enough (for maps smaller than 1024*1024 is 128 too much, but it gotta look gorgeous on very large maps).

[PhilSophus]

Btw, are you sure mantaining the old array is necessary?

At least for loading old save games it is to my understanding, at least in some form. Of course it could be freed or recycled after the conversion.

EDIT: So with what max height should I account with with my map generator modifictions? 64? That might be enough (for maps smaller than 1024*1024 is 128 too much, but it gotta look gorgeous on very large maps).

The height levels are said to be 50m, so 64 levels are 3150m. Seems to be enough for most purposes.

[richk67]

Great to see your work on this patch. I realised when writing the TerraGenesis code that the height levels were effectively unlimited - the algorithm can be scaled to whatever height or detail level you wish. In fact, I had a really awkward job condensing the results down into a clean 0-15 range.

Nice to see someone turning the possibility of extra height levels into a reality.

[CommanderZ]

Great to see your work on this patch. I realised when writing the TerraGenesis code that the height levels were effectively unlimited - the algorithm can be scaled to whatever height or detail level you wish. In fact, I had a really awkward job condensing the results down into a clean 0-15 range.

In theory, yes. But the terrain loses a lot of detail in the process. I'm currently trying to inplement a better interpolation which would took into account tiles in larger than one tile distance.

Beze jména, 27. led 1950.png

(154.04 KiB) Downloaded 147 times

I tried to toy with it a bit more, but this

is the best I could get from the current algorithm.

The extreme slopes are result of two random noise points with low frequency and very different values next to each other.

PS: The glitches make it look like there were lakes high in the mountains

[ic111]

Oh, I thought I am limited to 32 heights


Could you please set up a patch setting for maximum height?

No, I don't think this makes sense. I mean, putting a hardcoded heightlevel limit into the game which has no background in the data structures or in the code (I think the problems that still exist can be solved) isn't a benefit. But, I think, letting the player decide "I want to play on a scenario where the highest mountains have height X" makes sense, indeed. But the latter is a parameter to some map generation algorithm, not to the game itself.

I would put there values like 16, 32, 64, 128 and possibly even higher (with warning that too high values drain CPU). The glitches make heights over 64 pretty undisplayable for now.

Ok, making the painting code work efficient with big heightlevels may be a challenge. But lets see... For example, the terraforming code so far works in O(heightevel^4), where O(heightlevel^2) are the result of performing a linear search on an array of size O(heightlevel^2).

Btw, are you sure mantaining the old array is necessary?

Yes and no. Yes, because maybe some people don't want to spend some extra space for extra heightlevels. Those people can happily keep playing using the traditional 16 heightlevels - I think both solutions can live parallel, if we want so. Also, the upper four bits of the tile_height field contain pretty important information, so you might use the lower bits for something else, but you can't remove the tile_height field completely from the Tile datastructure.

And no, when the patch is on, one doesn't need those 4 bits for anything.


And there is a little teaser what a 80 tile mountain looks like (I know, the terrain is ugly, but...)

EDIT: So with what max height should I account with with my map generator modifictions? 64? That might be enough (for maps smaller than 1024*1024 is 128 too much, but it gotta look gorgeous on very large maps).

If introducing a parameter for that is possible - I think doing so is the right thing.

[CommanderZ]

No, I don't think this makes sense. I mean, putting a hardcoded heightlevel limit into the game which has no background in the data structures or in the code (I think the problems that still exist can be solved) isn't a benefit. But, I think, letting the player decide "I want to play on a scenario where the highest mountains have height X" makes sense, indeed. But the latter is a parameter to some map generation algorithm, not to the game itself.

It makes sense. I don't care about how you solve it internally (the "paint only what is used" thing sound cool), but players should be able to control how high mountains are generated. Not everyone wants to deal with 60 tile high mountain ranges. This can be already controlled by the Terrain type setting. This works in default as tarray converting setting => maximum map height this way:

Very flat: max height is 6
Flat: max height 9
Hilly: max height 12
Mountainous: 15

I changed it to

Code: Select all

_max_height[4] = {
	TGEN_MAX_HEIGHT / 4,       ///< Very flat
	TGEN_MAX_HEIGHT / 2,       ///< Flat
	TGEN_MAX_HEIGHT * 3 / 4,      ///< Hilly
	TGEN_MAX_HEIGHT       ///< Mountainous
};

But this means very flat with 64 max height = mountainous without max height!

There is plenty of sandboxers (mostly beginners I guess) who love their almost absolutely flat plains.

If introducing a parameter for that is possible - I think doing so is the right thing.

It is possible, but map smothness tables (7 integers for each smothness, so 28 values total) will probably need to be adjusted to the map height (you could see what original very smooth map setting did with 128 levels here). Simply dividing/multiplying doesn't work very well. I also guess parameters optimized for 64 won't do any good for 16, so I will have to add third dimension - a max map height.

Btw, the parameter you are speaking about would be the patch setting I was asking you for

[ic111]

Btw, the parameter you are speaking about would be the patch setting I was asking you for

Ok, then I misunderstood you. I thought you were talking about an internal parameter beyond terrain generation.

[CommanderZ]

Ok, then I misunderstood you. I thought you were talking about an internal parameter beyond terrain generation.

I meant it so originally, but if you are able to effectively decide maximum used level automatically, then it is of course unnecessary.

[ic111]

Hello,

small technical question:

Can anyone tell me how to print money using a DEBUG-statement? If I try

DEBUG(map, 0, "Terraforming cost using old algorithm: %i", total_cost.GetCost());

the compiler complains with the

warning: cannot pass objects of non-POD type 'class Money' through '...'; call will abort at runtime

[yorick]

Hello,

small technical question:

Can anyone tell me how to print money using a DEBUG-statement? If I try

DEBUG(map, 0, "Terraforming cost using old algorithm: %i", total_cost.GetCost());

the compiler complains with the

warning: cannot pass objects of non-POD type 'class Money' through '...'; call will abort at runtime

Code: Select all

DEBUG(map, 0, "Terraforming cost using old algorithm: %i", (int)total_cost.GetCost());

[ic111]

Hello,

I have finished version 2 of the more heightlevels patch.

What's new?

I rewrote the terraforming code. Now, it can deal with any heightlevels, there is no bound enforced by fixed sized arrays any more. In detail, the terraforming code is now based on a concept of calculating bounds for allowed heightlevels for all tiles near to the terraformed tile(s). Those bounds are saved in a map from tiles to bounds. The algorithm continues until the bounds are consistent with the (new) reality, then based on the bounds, new heightlevels are generated.

A simple example: Consider flat land at level 3. Now, you want to rise one tile to level 4. So the algorithm starts with a bound of (4,4) for that tile. It then looks at its neighbor tiles. Given that (4,4)-bound, the neighbor tiles must all have between height 3 and 5, so they get bounds (3,5). As they all already have height 3, the algorithm can stop here. If they would have height 2, the algorithm would have to inspect their neighbor tiles either.

Computational complexity of terraforming now is O(h^2*log(h^2)) instead of O(h^4) before, which could be reduced to O(h^2) if one would use hash_map instead of map. (h is the height of the tile).

The place to start when inspecting the code is probably the new function terraform. It takes such a map and then performs the whole terraforming. The map may initially contain any bounds - if the gui would support this, you could e.g. terraform a tile of height 2 to height 6 using exactly one call of the algorithm.
In the present implementation, terraform is called both from CmdTerraformLand and CmdLevelland. Both just insert the wanted heightlevel information into the map and call terraform.

I let the old code in terraform_cmd.cpp for now, but major parts of the code placed there can be removed given the new code.

Furthermore, I included the change to heightmap.cpp made by Terkhen. I didn't yet include the moreheight_tgen_adapter patch, since CommanderZ stated that it needs the patch being set to on for now, so it doesn't seem to be that stable to me yet.

So, I think problems (2) and (4) from my original post are solved; the heightmap code should also generate higher maps now. The next thing I will probably look at is the painting code (problem (3)).

BTW: What is the best strategy to make such a release post sticky at the beginning of the thread? Just edit the first post until it contains about the information my version 1 post combined with this post contains?

[Terkhen]

I'll try to make a version of the heightmap code for selecting a maximum map height (32, 64, 128, etc) before generating the scenario. I'll just have to understand widgets but that's something that's been bugging me for a while anyways

[CommanderZ]

About the very smart algorithm

Sounds clever. I think you should post this to bug spray as patch on its own. Devs like these code improvements.

Did anybody try this with the freeform map edges patch?

[ChillCore]

i have both in my patchpack and i nearly wet my pants

i am able to build spikes without asserts.
in terraform_cmd.cpp:
line 24 :
static const int TERRAFORMER_MODHEIGHT_SIZE = 2 * MAX_TILE_HEIGHT_OLD * (MAX_TILE_HEIGHT_OLD + 1) * 4;

line 30:
static const int TERRAFORMER_TILE_TABLE_SIZE = 1 + 2 * MAX_TILE_HEIGHT_OLD * (MAX_TILE_HEIGHT_OLD + 3) * 12;

anyway heres a little patch for the smallmap_gui.

edit: but i still have the glithes...
edit 2: i posted this before integrating version two
i can still build spikes. but i adjusted my file to the patch.
so my hack is no longer valid.

[Roujin]

Hello,

I have finished version 2 of the more heightlevels patch.

What's new?

I rewrote the terraforming code. [details]

Did you think about what happens if terraforming fails for some reason (because there's some object in the way)?

Currently if you level an area of land (actually the raising and lowering by the human player is also a form of leveling since raise-level and lower-level was coded by me and adapted to trunk), it will level the area "as best as possible", even if there's something in the way somewhere.
Just reading through your description, your new algorithm sounds like he would give out an error and not level anything at all, if there's some little object somewhere in the way. Is this true?

[Flavius]

Hi CommanderZ

Yikes! just love those alpine lakes in Beze Jmena.png. If only but i can dream i suppose.

[CommanderZ]

Hi CommanderZ

Yikes! just love those alpine lakes in Beze Jmena.png. If only but i can dream i suppose.

Look closely, they are nothing more than a huge graphical glitch

I am afraid multiple water levels are quite not an aim of this patch.

[PhilSophus]

Can anyone tell me how to print money using a DEBUG-statement? If I try

DEBUG(map, 0, "Terraforming cost using old algorithm: %i", total_cost.GetCost());

the compiler complains with the

warning: cannot pass objects of non-POD type 'class Money' through '...'; call will abort at runtime

The first part to solve this is easy: Cast the Money explicitly to int64. The second part is a bit problematic: Use a format specifier appropriate for int64 and portable (32 vs. 64 bit OS is the issue here). C99 defines macros like PRId64 in <inttypes.h>, but given that C++ isn't C99, I'm not sure that every supported compiler of OpenTTD supports this.

If it does, the following should work:

Code: Select all

DEBUG(map, 0, "Terraforming cost using old algorithm: %"PRId64, (int64)total_cost.GetCost());

(Please note the closing quote and no comma between quote and PRId64)