13-03-2003 20:24									#1
	Map Generation and Rivers. Support Apolyton, buy Civilization: The Boardgame

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)

	14-03-2003 10:34									#2
	Tired of ads?

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.

	14-03-2003 11:50									#3
	Increase Your PM Length

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?

	18-03-2003 18:24									#4
	Get a bigger avatar today!

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.

	19-03-2003 07:37									#5
	Lose 30 kilos (of popups)

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.

Attachment: medium.jpg
This has been downloaded 71 time(s).

	21-03-2003 00:50									#6
	Remove this text

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?

	21-03-2003 02:36									#7
	Support Apolyton, buy Galactic Civilizations: Deluxe Edition

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.

	28-03-2003 17:02									#8
	Put an end to popups!

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.