More height levels (in trunk since r27010)

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
CommanderZ
Tycoon
Tycoon
Posts: 1872
Joined: 07 Apr 2008 18:29
Location: Czech Republic
Contact:

Re: More height levels

Post by 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.

Image

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
glitch.png (24.21 KiB) Viewed 4151 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?
Attachments
very rough.png
(82.09 KiB) Downloaded 813 times

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

Re: More height levels

Post by 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.

User avatar
CommanderZ
Tycoon
Tycoon
Posts: 1872
Joined: 07 Apr 2008 18:29
Location: Czech Republic
Contact:

Re: More height levels

Post by CommanderZ »

Oh, I thought I am limited to 32 heights :oops:


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...) :P

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).
Attachments
Trindtown Transport, 18. úno 1950.png
(88.87 KiB) Downloaded 197 times

PhilSophus
Chairman
Chairman
Posts: 776
Joined: 20 Jan 2007 12:08
Location: Germany

Re: More height levels

Post by PhilSophus »

CommanderZ wrote: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.
CommanderZ wrote: 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.
"The bigger the island of our knowledge, the longer the shore of our ignorance" - John A. Wheeler, Physicist, 1911-2008

richk67
Tycoon
Tycoon
Posts: 2363
Joined: 05 Jun 2003 16:21
Location: Up North
Contact:

Re: More height levels

Post by 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.
OTTD NewGRF_ports. Add an airport design via newgrf.Superceded by Yexo's NewGrf Airports 2
Want to organise your trains? Try Routemarkers.
--- ==== --- === --- === ---
Firework Photography

User avatar
CommanderZ
Tycoon
Tycoon
Posts: 1872
Joined: 07 Apr 2008 18:29
Location: Czech Republic
Contact:

Re: More height levels

Post by 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 :P

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

Re: More height levels

Post by ic111 »

CommanderZ wrote:Oh, I thought I am limited to 32 heights :oops:


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.
CommanderZ wrote: 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).
CommanderZ wrote: 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...) :P
CommanderZ wrote: 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.

User avatar
CommanderZ
Tycoon
Tycoon
Posts: 1872
Joined: 07 Apr 2008 18:29
Location: Czech Republic
Contact:

Re: More height levels

Post by 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 :roll:

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

Re: More height levels

Post by ic111 »

CommanderZ wrote:
Btw, the parameter you are speaking about would be the patch setting I was asking you for :roll:
Ok, then I misunderstood you. I thought you were talking about an internal parameter beyond terrain generation.

User avatar
CommanderZ
Tycoon
Tycoon
Posts: 1872
Joined: 07 Apr 2008 18:29
Location: Czech Republic
Contact:

Re: More height levels

Post by CommanderZ »

ic111 wrote:
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
Director
Director
Posts: 608
Joined: 17 Jul 2007 17:56

Re: More height levels

Post by 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
Engineer
Engineer
Posts: 80
Joined: 23 Mar 2008 08:53

Re: More height levels

Post by yorick »

ic111 wrote: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
Director
Director
Posts: 608
Joined: 17 Jul 2007 17:56

Re: More height levels

Post by 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?
Attachments
moreheights-version2.patch
Version 2 of the moreheights-patch, this time generated from one level above the src directory.
(58.52 KiB) Downloaded 125 times
Last edited by ic111 on 15 Dec 2008 21:19, edited 1 time in total.

Terkhen
OpenTTD Developer
OpenTTD Developer
Posts: 1034
Joined: 11 Sep 2008 07:32
Location: Spain

Re: More height levels

Post by 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 :)

User avatar
CommanderZ
Tycoon
Tycoon
Posts: 1872
Joined: 07 Apr 2008 18:29
Location: Czech Republic
Contact:

Re: More height levels

Post by CommanderZ »

ic111 wrote: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?

User avatar
ChillCore
Tycoon
Tycoon
Posts: 2658
Joined: 04 Oct 2008 23:05
Location: Lost in spaces

Re: More height levels

Post by 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.
Attachments
moreheight_better_smallmap.patch
(3.98 KiB) Downloaded 137 times
Last edited by ChillCore on 17 Dec 2008 13:37, edited 1 time in total.
-- .- -.-- / - .... . / ..-. --- .-. -.-. . / -... . / .-- .. - .... / -.-- --- ..- .-.-.-
--- .... / -.-- . .- .... --..-- / .- -. -.. / .--. .-. .- .. ... . / - .... . / .-.. --- .-. -.. / ..-. --- .-. / .... . / --. .- ...- . / ..- ... / -.-. .... --- --- -.-. .... --- --- ... .-.-.- / ---... .--.

Playing with my patchpack? Ask questions on usage and report bugs in the correct thread first, please.
All included patches have been modified and are no longer 100% original.

Roujin
Tycoon
Tycoon
Posts: 1884
Joined: 08 Apr 2007 04:07

Re: More height levels

Post by Roujin »

ic111 wrote: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?
* @Belugas wonders what is worst... a mom or a wife...
<Lakie> Well, they do the same thing but the code is different.

______________
My patches
check my wiki page (sticky button) for a complete list

ImageImage
ImageImageImageImageImageImageImage

User avatar
Flavius
Tycoon
Tycoon
Posts: 1531
Joined: 22 Apr 2003 03:55
Location: Gold Coast, Queensland, Australia.

Re: More height levels

Post by Flavius »

Hi CommanderZ

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

User avatar
CommanderZ
Tycoon
Tycoon
Posts: 1872
Joined: 07 Apr 2008 18:29
Location: Czech Republic
Contact:

Re: More height levels

Post by CommanderZ »

Rollo wrote:Hi CommanderZ

Yikes! just love those alpine lakes in Beze Jmena.png. If only but i can dream i suppose. :shock:
Look closely, they are nothing more than a huge graphical glitch :D

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

PhilSophus
Chairman
Chairman
Posts: 776
Joined: 20 Jan 2007 12:08
Location: Germany

Re: More height levels

Post by PhilSophus »

ic111 wrote: 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)
"The bigger the island of our knowledge, the longer the shore of our ignorance" - John A. Wheeler, Physicist, 1911-2008

Post Reply

Return to “OpenTTD Development”

Who is online

Users browsing this forum: astralmati and 3 guests