The International Simutrans Forum

 

Author Topic: Automatically generated valleys  (Read 7080 times)

0 Members and 1 Guest are viewing this topic.

Offline jk271

  • *
  • Posts: 292
  • Languages: CZ, EN, DE
Automatically generated valleys
« on: June 05, 2012, 09:26:41 PM »
Having rivers on hills seem a little bit strange for me, so I have decided to do something with it.
After several months of thinking and some trials I have created an algorithm for automatically generated valleys. Code is not ready for release yet but result can be seen on picture - screenshot of a map.
I plan to make rivers to use the generated valleys.
Unfortunately it has one drawback -  it is increases significantly map creation time. I intend to make it as optional feature.

What do you think about such a feature - a little bit more realistic landscape?

Offline alexbaettig

  • *
  • Posts: 132
  • Languages: DE, EN, FR
Re: Automatically generated valleys
« Reply #1 on: June 05, 2012, 09:53:35 PM »
I like it very much! This way topography gets its proper place. I've also got a question: What do you mean by significantly? If it means 30 minutes for a map it's probably a bit long but if it's just 5 min it isn't that bad. If you really want to follow a map over more than some months this is acceptable… I think…

Offline isidoro

  • Devotee
  • *
  • Posts: 1119
Re: Automatically generated valleys
« Reply #2 on: June 05, 2012, 10:41:22 PM »
It is a very nice feature.  And a realistic valley-mountain combination makes way design a bigger challenge.


Offline jk271

  • *
  • Posts: 292
  • Languages: CZ, EN, DE
Re: Automatically generated valleys
« Reply #3 on: June 05, 2012, 10:49:27 PM »
Thanks  for support!
It lasts to generate around 5 minutes for map 512x512tiles and around 20minutes for 1024x1024 for my computer. Do not take it as an exact time it is very approximate. Some time increase is caused by debugging symbols etc. It is first working version - first version doing what was expected.
I know about some bottleneck of current implementation,  so I am expecting speedup.

Some another screenshots

Offline Dwachs

  • DevTeam, Coder/patcher
  • Administrator
  • *
  • Posts: 4477
  • Languages: EN, DE, AT
Re: Automatically generated valleys
« Reply #4 on: June 06, 2012, 06:02:10 AM »
I would not care about computation time at this early stage of development. Each such algorithm can be optimized later ...

@jk271: as you seem to use git for development, why open up a repository at github and publish your work there?
« Last Edit: June 06, 2012, 06:10:34 AM by Dwachs »

Offline Combuijs

  • Web Team
  • Devotee
  • *
  • Posts: 1391
  • Maintainer of maps.simutrans.com
    • Combuijs
  • Languages: EN, NL
Re: Automatically generated valleys
« Reply #5 on: June 06, 2012, 10:43:34 AM »
I like the valleys very much and it is a significant improvement. But is there also a possibility to get large flat planes with your method? The examples you give have all a very mountaineous terrain.

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9286
  • Languages: De,EN,JP
Re: Automatically generated valleys
« Reply #6 on: June 06, 2012, 07:54:57 PM »
If the valleys are put into the the initial terrain map before smoothing, it will be much faster. Do not worry too much about this at the moment. Does those base on the initial see, like the perlin noise? Otherwise map extension will have some strange effects.

Offline jk271

  • *
  • Posts: 292
  • Languages: CZ, EN, DE
Re: Automatically generated valleys
« Reply #7 on: June 07, 2012, 10:29:44 PM »
I have done some time measurements:
initial version
map     size            time
4809    256x256         <1s
4809    512x512         22s
9756    512x512         17s
4809    768x768         258s
9756    1024x1024       859s

first speedup (with vector as stack)
4809    256x256         <1s
4809    512x512         19s
4809    768x768         235s

I have created account on github today, but I have not managed to upload any line of code.
Address is https://github.com/jk271 but nothing can be found there yet.


I have not changed current map generation process.
My algorithm takes generated map without any object on it as an input.
It changes terrain to let water flow to the sea from each vertex on map. It work similar to water erosion.

Unfortunately it is complicated to describe whole algorithm on several lines. 

If original algorithm in game provides planes it is possible to have large flat planes too.


Map extension is an unsolved matter yet. Simplest solution is to switch it valley generation off in map enlargement and enlarge map without valleys.
Solution 2: It could be solved also by some flags denying my algorithm to use older part of map. On the other hand it could make some strange landscape - rivers ending in nothing (= not in sea or lake) on the boundary between old and new part of map.

Figure: map 4809, size 768x768, water level -4, mountain height 160
(figures in previous posts had mountain level 320, thus there are much more mountains)
Edit 8th July 2012: Make it more clear.
« Last Edit: June 08, 2012, 07:19:09 PM by jk271 »

Offline isidoro

  • Devotee
  • *
  • Posts: 1119
Re: Automatically generated valleys
« Reply #8 on: June 07, 2012, 11:24:09 PM »
[...]
Map extension is an unsolved matter yet. Simplest solution is to switch it off.
[...]

In fact, that would be the solution a politician will give to you...  :P

If map extension is changed, there is another problem that may be looked at: since map borders have to be at the same level, iirc, when extending the map, an artificial straight "scar" appears where the old map border used to be...  Simple solution would be to allow border tiles to have relief as well.

Offline kierongreen

  • Dev Team, Coder/patcher
  • Devotee
  • *
  • Posts: 2256
Re: Automatically generated valleys
« Reply #9 on: June 07, 2012, 11:27:48 PM »
Quote
when extending the map, an artificial straight "scar" appears where the old map border used to be...when extending the map, an artificial straight "scar" appears where the old map border used to be...
Simutrans tries to "heal" this "scar" if it can when extending :)

Quote
Simple solution would be to allow border tiles to have relief as well.
I'm not sure how simple that would be...

Offline jk271

  • *
  • Posts: 292
  • Languages: CZ, EN, DE
Re: Automatically generated valleys
« Reply #10 on: June 08, 2012, 07:32:14 PM »
I have reached significant performance increase  in valley generation time.
Time depends on map size mountain height and water level: More mountains - more time needed. Lower water level - more time needed. So following setting - used in this time measurement - should be the worst case. Time depends also on particular map.

mountain_height = 320
water_level = -10

map     size            time
4809    512x512         1s (water_level=-10)
4809    768x768         <1s (water_level=-10)
4809    1024x1024       <1s (water_level=-10)
4809    1280x1280       2s (water_level=-10)
4809    1536x1536       1s (water_level=-10)
4809    2048x2048       3s (water_level=-10)
4809    3072x3072       7s (water_level=-10)
4809    4096x4096       13s (water_level=-10) it is the biggest map I am able to create

Edit: "time" is time used for creation of valleys only.
« Last Edit: June 08, 2012, 09:17:38 PM by jk271 »

Offline VS

  • Senior Plumber (Devotee)
  • Devotee
  • *
  • Posts: 4852
  • Vladimír Slávik
    • VS's Simutrans site
  • Languages: CS,EN
Re: Automatically generated valleys
« Reply #11 on: June 08, 2012, 08:52:18 PM »
13s per map sounds very acceptable... but how strong is the machine? (processor and bus speed)

Offline jk271

  • *
  • Posts: 292
  • Languages: CZ, EN, DE
Re: Automatically generated valleys
« Reply #12 on: June 08, 2012, 09:13:32 PM »
13s is time used for creating valleys. Map generation process take more time.

My computer is a notebook with processor Intel Core Duo T2400 (32-bit, 2 cores at 1.83GHz) and 4GiB RAM (upgrade, originally it was 1GiB). Bus should run on 533MHz, throughput is unknown for me.
It is roughly six years old machine, but I would not change it for any common currently produced computers.

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9286
  • Languages: De,EN,JP
Re: Automatically generated valleys
« Reply #13 on: June 08, 2012, 09:51:18 PM »
I was wondering in what respect your code is different fro them river code, which also tries to flow down (+randomness)? But git will tell ...

And should those valleys not be filled with a river?

Offline jk271

  • *
  • Posts: 292
  • Languages: CZ, EN, DE
Re: Automatically generated valleys
« Reply #14 on: June 08, 2012, 10:19:19 PM »
It will take me more time to set up github repository. So there is a patch containing current working version of algorithm.
I call it "bottom-top front flag flood algorithm" or "bt3fa". It took me two years (incl. closed streets) to think it out to it's details. Improvements resulted that flags are not necessary to use.

Patch has a little bit messy code - it is before code cleanup. Some parts will go to header files.

Quote
And should those valleys not be filled with a river?
Yes, rivers will follow. Valleys without rivers have no sense.  ;)

Offline isidoro

  • Devotee
  • *
  • Posts: 1119
Re: Automatically generated valleys
« Reply #15 on: June 08, 2012, 10:39:01 PM »
Simutrans tries to "heal" this "scar" if it can when extending :)

Somewhat, but not completely.  An artificial straight line can be observed, even if there are no cities on the frontier.  I would give an example, but my game was lost.  It would be nice if the extension would be the same as an original map of that size.

Btw, why borders are forced to be at the same height?

Offline kierongreen

  • Dev Team, Coder/patcher
  • Devotee
  • *
  • Posts: 2256
Re: Automatically generated valleys
« Reply #16 on: June 08, 2012, 11:14:18 PM »
Quote
Btw, why borders are forced to be at the same height?
It comes down to how the edge of the map is drawn. Simutrans draws the world in an infinite ocean. An alternative that some games use is to have the world surrounded by black, with vertical sides. Vertical slopes down to the ocean would look odd.

Offline jk271

  • *
  • Posts: 292
  • Languages: CZ, EN, DE
Re: Automatically generated valleys
« Reply #17 on: June 10, 2012, 07:10:03 PM »
I am tinkering with change of river creation algorithm, but it is not fully working. Now you can let program to generate valleys and than make rivers manually.
If you set number_of_rivers to 0 new river creation algorithm is used. Otherwise current river algorithm is used. It is temporary solution enabling to see differences.

My github repository has
https://github.com/jk271


Edit: Topic changed. Thank you for move thread to correct place.
« Last Edit: June 10, 2012, 08:19:34 PM by jk271 »

Offline Dwachs

  • DevTeam, Coder/patcher
  • Administrator
  • *
  • Posts: 4477
  • Languages: EN, DE, AT
Re: Automatically generated valleys
« Reply #18 on: June 11, 2012, 06:55:31 PM »
Thanks for creating the repository. For anyone who is interested in the difference to trunk, check this:

https://github.com/jk271/simutrans/compare/master...rivers2012

.. and the files changed.

I still have to figure out, what the algorithm in create_valleys is doing. Any hint appreciated ;)

Edit: The implementation creates valleys with 90 degree turns. Map generation number 33, size 512 x 512.
« Last Edit: June 11, 2012, 07:08:20 PM by Dwachs »

Offline jk271

  • *
  • Posts: 292
  • Languages: CZ, EN, DE
Re: Automatically generated valleys
« Reply #19 on: June 11, 2012, 08:31:20 PM »
I will try to describe briefly an algorithm.
Data structures:
I needed more detailed height and some flags. Height is stored in integer variable "z_detailed" of class coord3d_t.
First part of "z_detailed" contains "shifted" height of vertex of grid - height is counted from sea level.
Second part (last 16 bits) contains "detailed" height - shortest distance from edge between same and lower level.
Flags are not currently used. I plan to use it in process of map enlargement and to deny algorithm to reach vertices too close to map borders.

Algorithm:
1. Firstly edges between land and sea are detected. Vertices one tile above sea have "detailed" height of "1". Vertices are stored in vector current_step[i=0].
2. Secondly process all vertices in current_step: look up their nearest neighbours not being sea or previously processed. Store such a neighbours in next_step with "detailed" height assigned to 1 + 1 = 2. (current "detailed" height +  1)
2.1. If neighbour is one tile higher than currently processed vertex, store it in current_step[ 1]
2.2. If neighbour is one tile lower and has not been processed (water from such vertex could not go to sea), dig valley,  append coordinates of valley end (closer to sea) to current_step[-1], decrease i by 1 and go to step 2. This condition is always false with i==0.
3. Clear current_step[0].
4. Swap current_step[0] and next_step[0].
5 Continue until current-step[0] is not empty.
6. Increase i by 1 and to step 2.

If you want to see details, uncomment following lines in karte_t::create_valleys(), it is around line 1202. You will see numbers on the terrain.
ATTENTION! It slows down valley gemeration significantly (around 20 times), I do not recommand to use it with maps larger than 512x512.
//                                              char tmp_string[20];
//                                              sprintf(tmp_string, "%x", z_detailed_next);
//                                              lookup_kartenboden(next_k)->set_text(tmp_string);


I have an idea, how to avoid valleys having 90°, but did not have time to code it yet.[/i]
« Last Edit: June 11, 2012, 08:40:05 PM by jk271 »

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9286
  • Languages: De,EN,JP
Re: Automatically generated valleys
« Reply #20 on: June 11, 2012, 09:35:32 PM »
The perlin noise input for the height on map generation are already floats. Thus there is more precise heights already there for the start, which could also be used for valley creation.

If I understood you correctly, this routine make sure, that any tile is connected by a route only downwards to the sea?

Offline jk271

  • *
  • Posts: 292
  • Languages: CZ, EN, DE
Re: Automatically generated valleys
« Reply #21 on: June 14, 2012, 09:16:12 PM »
Quote
The perlin noise input for the height on map generation are already floats. Thus there is more precise heights already there for the start, which could also be used for valley creation.
I will have to look deeper on map creation algorithm and consider using values from floats. It would help me to do more realistic valleys on "flat" (with low height differences) maps too.
Height values in my algorithm are currently stored in "fixed point" format similar to "money format". Money amounts are stored in integer containing values in cents to avoid rounding errors in calculation with floating point numbers.

Quote
If I understood you correctly, this routine make sure, that any tile is connected by a route only downwards to the sea?
Yes, routine does it.
If any tile has not such a connection tho the sea, connection is created by digging a valley.