Map Generation and Rivers.

[Lemmy]

mk..i think this is my first post in this forum...so be gentle

Anyway, lot's of civ-projects here, and i guess most, if not all, support random map generation. (i only skimmed through a few posts)

What i'm wondering about is, what algorithms do you use for your maps?
And do you also generate rivers, if so, how does your algorithm work?

I've written my own hex-based implementation of the mid-point division algorithm, there are still some glitches due to constraints i put on it (i want it to be an island, always), but the overall terrain is generated nicely. I also added river generation algorithm, which is basically a depth-first search, starting with a peak, and following the lowest tile next to it untill it either encounters a valley (a tile with no lower bordertile) or the sea.

two older screenshots:
http://www.xs4all.nl/~munishm/screens/terrain1.jpg
http://www.xs4all.nl/~munishm/screens/terrain2.jpg

White tiles are peaks, yellow tiles are beaches, blue is water, green is land. Darker color means higher/lower altitude (depends on tile type: water or land)

[Dale]

My algorithm in Empire is a little different to yours and produces some excellent results.

1. Produce terrain height from 1-50 (1-25 = sea level).
2. Place an amount of water on the peaks. I use 100 water units.
3. I run a check through every tile on the map 50 times (to ensure water "flows" through the below process).
3a. If the tile contains water (in the first pass it's the peaks), I check all surrounding tiles for the lowest. If more than one I randomly pick two of them.
3b. I pour 100 units of water into each tile and mark them as river.
3c. If no lower tiles I convert the tile to "lake".
3d. If the originating tile is a lake I raise the height check by 1 to see where the water leaves the lake (basically too much water into the lake cause another river to leave it).

I find this algorithm produces rivers flowing out from the mountains, pooling in the flatlands and plateaus causing lakes of varied sizes, with a lot flowing further on till it reaches the sea. Interestingly, my model creates occaisional deltas, lake systems, long windy rivers and river systems where a number of rivers will converge to create one big flow (or a lake), just like in the real world.

I quite like my model.

[Lemmy]

cool!

I originally tried something similar, but it didn't work out the way i meant it to be...
I ended up getting huge lakes, flooding half of my land, with only 1 river

Do you have some screenshots by any chance?

[Lemmy]

I decided to change my algorithm and also use water units. It makes more sense, and this way i can get thick and thin rivers. However instead of giving each tile 100 units, i'll have a variable starting amount of water units, maybe depending on height. The units will be distributed along the river. based on the height difference between the tiles...i think...i still have to work out the details on that. But i'm pretty sure that the water units will be spread over the entire river.

[Dale]

I've finished up my mapgen model, and have been able to produce random maps such as attached. I've only gone for one thickness of river, but it still looks good all the same.

[LDiCesare]

Dale, your maps look like the mountains are in big patches rather than ranges. Do you think you could put something like an edge-detection routine to put some mountain ranges near some coasts? Or do you obtain mountain ranges from time to time?

[Dale]

LDiCesare:

Not in ranges? How bout the island right in the middle. That's a coastal mountain range. That range would be about 5-10 tiles from the coast, and on the scale I'm using for my cities where an average city is between 5-10 squares radius, they enjoy being between coast and mountains. Also, the zig-zag island just to the left of the middle island would've been caused by a mountain range (like New Zealand). It looks like the age normalisation has flattened the peaks a little though.

Though I know what you mean. If I decrease the weighting on the highest altitude it'll cause the land to drop more rapidly. Though then you'll end up with a lot less flatlands and that would be disastrous for Empire's game model. It would be very simple to do though, just a one mapgen input variable change.

For what I need and want for Empire, I've got very nice maps to play on. Of course, what Clash needs and wants may be a totally different thing.

[Impaler[WrG]]

I about a year ago I was a part time member in the late Stela Polaris project and I had I consider my "Magnum Opus" to be the idea for a map generator based on emulating plate tectonics. I was not involved in the coding of the generator but I can give you some of the details of how it worked.

The sytem starts with a map of diamond squares much like Alpha Centauri (using a more primitive map generator first and then applying this generator may help produce more interesting results, as the map will not start flat). A random number generators pick 6-12 tiles on the map, these points become "seeds" that later produces "plates". The next algorithim them asignes every other tile on the map to one plate based on which seed tile it is closest too. The plates will be iregular polygons with 3-5 sides and various sizes. (finding a way to create curved plate boundarys would be an excelent addition) Next each plate is randomly assigned one of the 8 cardinal directions as its direction of movment and a speed of 0,1,2 or 3. Each individual tile in the plate is then transposed that many spaces in that direction (all that is moved realy is the plate designation and elevation, so for example the value of Plate A-2300ft is moved from grid location 45,67 to 45,69), each plate takes turns so for example plate A move 1 space north, plate B moves 2 space SW, C moves 0 NW, D moves 1 East and then we begin again with A.

Each time a tile is transposed ontop of another tile the elevations are added together and the designation of the moving plate replaces that of the stationary one. After each plate movment if any "void" tiles (at the tail end of the plate) were created then they are assigned a low elevation and made part of the plate that just moved. Ocean tiles should have positive elevation values durring this stage so that when they subduct they push the land up. When the whole process is over these values can be altered or ignored but durring calculation they need to be positive.

Run the plate movments for 20-30 cycles, the number of cylces could also be a random choice too by the way. Then apply an Erosion algorithim, basicaly cut all evelation by 20%-50% and spread the resulting mass around to adjasent tiles keeping the total the same, make shure to alow oceans to be filled in by this process. If possible try to use something similar to the river simulator mentioned earlier to move the "dirt" downstream untill it's in the ocean.

Now start all over again with a new and independed set of seeds plates and movment, again run this for a bit and apply another erosion. Repeat the seed, plate, movment cycles, erod a total of 3-4 times possibly droping in some effects like random volcanos, meteor impacts ectt to give it a bit of spice.

This map generator idea was never fully developed in the time that I was with Stella Polaris but the initial versions made in only a few days work proved to be the best map generators I have EVER seen, huge very ralistic 600x800 maps can be spit out in mear seconds and best of all small and large map sizes do not disrupt the program and produce "chunky" maps as is common with other map generators. Hope this helps yall out and I promise you will not be disapointed if you go to the effort of codeing this.

[laurimann]

Do you still have any contacts to the programmers for screenshots and such?

[laurimann]

I about a year ago I was a part time member in the late Stela Polaris project and I had I consider my "Magnum Opus" to be the idea for a map generator based on emulating plate tectonics. I was not involved in the coding of the generator but I can give you some of the details of how it worked.

Never mind. I implemented this algorithm exactly as you described here and i must unfortunately admit that the results are nowhere near

the best map generators I have EVER seen, huge very ralistic 600x800 maps can be spit out in mear seconds,

quite the opposite.

So i decided to make my own algorithm. That in turn DOES produce quite playable maps that, i think, are far more realistic than fractal based maps. You can read the entire story from my Bachelor's thesis, available at urn.fi/URN:NBN:fi:amk-201204023993 . The related source code is downloadable from sourceforge.net/projects/platec/

And here's few screenshots of the output of the plate tectonic based terrain generator i made:
9935848.jpg
and:
9935847.jpg

[Last_Evolution]

So i decided to make my own algorithm. That in turn DOES produce quite playable maps that, i think, are far more realistic than fractal based maps.

Are they really playable? Since production in civ games is based on "hills" then you will get areas with lot of production and areas with no production. The players with no hills will be in big disadvantage. Your map gen produces lot of flat areas with no hills.

[laurimann]

Are they really playable? Since production in civ games is based on "hills"

Well, are fractal maps playable? Secondly, don't civ maps always put some player more or less in an disadvantage?

All the same, you are right. The maps contain vast flat areas that when translated to civ like tiles would mean that someone must spend their first 100 turns trying to find hills. However, it doesn't need to be that way. At the pixels-to-civ-tiles translation step the map can be enhanced with added accuracy by spreading hills where the elevational difference between pixels is large enough.

[Last_Evolution]

Actually I have played with your mapgen already and the problem is the opposite - there were large areas of grassland, but it was no problem, there were occasional hills or there were lot of hills reasonable number of tiles away. The problem is the hills - there was too much of them. In alpha centauri it would not be probably a problem, but in civ you have to translate heights into tiles. Example: img27.imageshack.us/img27/9328/scenez.png

[laurimann]

The problem is the hills - there was too much of them. Example: img27.imageshack.us/img27/9328/scenez.png

Awesome, you've done something practical! I like.

I see now what you ment and realize that I didn't fully understand it in my previous post. The amount of hills is clearly over the top. However, the only thing your screenshot shows is that a heightmap cannot be translated to a civ map by linear heightmap resampling. You must also implement additional neighbourhood and/or distance based restrictions. Another, IMHO much much better, option would be to apply erosion that simulates water flows. This would result in (large) valleys between the hills and mountains. Anyway, it's too bad civ doesn't support "plateau" concept.

[Last_Evolution]

Do you plan to continue development of platec? I would add rivers and (very rare) asteroid hits.

[laurimann]

Yes, rivers are actually implemented already. The current method just simulates the erosion caused by running water in a very simplistic manner every N iterations due to performance reasons and the fact that plate tectonics have a completely different timescale than rivers. The final output could have rivers and lakes (and climate in general), but for now it's out of scope - platec is a topography generator, not a planet simulator. The effect of asteroid hits on the topography is neglible and therefore i have no interest in implementing them.