Map generator model II

[primemover]

long time no see..

Hey guys... I've been gone a while. Extremely busy with teaching, and its going to stay like this for a while, so I am going to have to surface every now and then and offer what I can. I have a moment this holiday weekend.

To comment on recent posts:

Its nice to see some of you from the CTP2 forum (Martin and Dale)!!!

Actually... Dale, your "water" idea is similar to one of mine... but reading it through tonight as tired as I am I was not able to make sense of it all. I got the general idea, but could you be a bit more clear on the specifics of your hill/mountain algorithm?

Does that algorithm produce realistic mountain ranges (near the side of a continetn rather than the middle, and in ranges)? I doubt it.

If I understand Dale, the part he is explaining mainly talks about normalizing mountain altitude. I am not clear how he picks the areas where mountains are going to be (other than on an island). A variation of his algorithm if we found an accurate method for picking where the mountains should be a quick momentary solution to my hopeful geology engine of the future and could probably work fine for now. But I will have to read it again when I am more coherent.

Weather is not as complex as plate tectonics. The most difficult part of it will be determining the general direction of coastlines. Once we have that, ocean currents can be determined. From location of continents, bodies of water, and overall planet tilt (because of its affect on general wind direction and speed), we can from there determine locations of large air masses, and then just take them through the motions of what those masses encounter (terrain wise) as they move in the direction of wind.

This will take time and programming, but I think that Dale's idea may suffice until the more robust model can be developed.

[Dale]

The explanation I found above is not my idea guys, I found it while searching for a mapgen algorithm. I'll have a go at trying to explain how it works though.

The way I understand it, is you normalise the entire map at sea level. Then you select a number of random seeds at random locations around the map (say for example 100 seeds in your map, which on a 100x100 map is 1%). A random height is given to those random locations giving a range of heights for example -5 to 5 (0 being sea level). Then using the algorithm supplied you use a random number generator to pass through the entire map averaging tiles heights based on neighbors heights making sure not to change your seeds. The first pass will only change the neighbors of the seeds. The second pass will change the neighbors of the seeds, and their neighbors. Simply it works like a radial. Start from a point and work out each pass. After say 50 passes you should have been able to radial out the entire map. From there, you say that values -5 to -1 is sea (if using deep water as well to create continental shelves -5 to -3 being deep water if you want), 0 and 1 is flat land, 2 and 3 is hills, and 4 and 5 is mountains.

To try to explain a picture of it:
- Seed located and given random height of 4.
- First pass changes first radius from seed to either 1's, 2's or 3's (depending on random number put into the algorithm).
- Second pass changes second radius from seed in the same manner, and the first radius changes as well to create a slope from sea level (radius 3) to mountain peak at seed location. So logically if the seed hasn't changed we should be looking at a bulge in the map with highest point (seed location) being 4, and sides spreading 2 radials out with diminishing heights back to 0 on the 3rd radius.
- Continue in this manner for a few more passes, and eventually the bulges and dips (depending what the original seed location height was) meet. This is where I believe the above algorithm gets funky.
- I believe if you keep making passes over the map with the algorithm, then plains, plateaus, lakes, hills etc will start forming.
- From what I can tell of the algorithm, if two bulges meet, then a range will form, and if there's a dip nearby this would create a coastal mountain range similar to the east coast of Australia, or the north-western coast of USA.

Hope this helps explain it. This is how I see this mapgen model working anyways.

[primemover]

ok... now i get it.

I can see how it is trying to make a more realistic map. We may be able to modify it a bit and make it work for a first go (until we get a real tectonic model).

The problems we need to address using this model as it is currently are these:

1. Placement of mountains is not truly random in real life.
2. A radial approach will not mimic true mountains because ranges will be the exception rather than the rule. (and they still have the radial look.)
3. We need to have a larger scale than -5 to 5. (Thouth this is simple enough to change)

Actually, the pass idea may work. We just need a different way to place the "seeds" so that ranges are the rule rather than the exception and so that placement within 500 "miles" of continental margins is also a rule (rather than an exception).

This has also got me thinking about a way to simplify my own model for right now.

[Martin the Dane]

Last night I experimented a little with the model. What I got was seashell shaped mountains. This morning I made a new attempt, this time I got it right, so now the seashels are less pronounced.

The normalization is ok, but as primemover says we need a better way than random to place the seeds.

If you want to see how far I've got, unzip and run MapGen (only Windows). The source code is Pascal (Delphi).

There are two ways of normalizing, Star and Circular:
Star takes only the four neighbours with a full side in common with the poit being normalized.
Circular uses all eight neighbours.

[primemover]

Actually, after seeing Martin's little trial (Thanks a bunch Martin for that experiment!) I see several more problems.

1. The "seeds" in most cases end up being significantly higher or lower than any of the surrounding area even after pressing the normalize button 50+ times. This will cause a problem with spears at the top of our mountains (actually, kind of humorous)

2. It seems as though black seeds (I'm assuming to be depths) are not making as much of an impact as we thought (I had several black holes in the middle of a mountain range). This might be suitable for a fantasy!

3. It seems as though that some continents are now completely surrounded by mountains

Now for a plus: When mountains ranges are close, the two of them seem to form a continent between, which makes them coastal... but this happens as a side effect of the process, not because it is being attempted. The drawback is #3 above.

I think we may be able to use this (or something similar) as a normalizing strategy for height of mountains, but not as the actual creator of the continents and where the mountains are on those continents (pretty much what Martin said... but more specific)

[Martin the Dane]

Just a quick comment

Re 1. This can be taken care of by not protecting the seeds for a the last couple of passes. As it is now, the seeds are not changed at all.

[primemover]

new plate model

Sounds good martin.

As far as picking spots for the continents that can be used for placing spots now, and for the actual plate tectonic system later, I have a new idea in mind for coming up with a system of plates using a crack pattern instead of a flood fill.

We have a spring break coming up in two weeks and I may take a day or so out of that to work on my idea. My little trial will be written in C++... which reminds me:

We will need to translate all these ideas into a Java version if we want to keep everyone on the project happy... so when you come up with these little programs, keep that in mind.

As far as actually producing the maps, does anyone on the mapping know how to deal with Java GUI? Because I have no clue! I can brush up on objects and sytax when the time comes, but while I can do that for java programming, the GUI is a completely different ballgame. From what I remember, the GUI was a pain.

[Martin the Dane]

As far as actually producing the maps, does anyone on the mapping know how to deal with Java GUI? Because I have no clue!

Well I guess my Java knowledge is even less. I believe I could translate my routines into both C++ and Java without much trouble, but as to GUI I wouldn't even know where to start.

When programing I always try to keep the numbercrunching and GUI elements seperate, mainly because it makes the programs run much smoother, and often significantly faster, so It should not be much trouble for someone else to code the GUI for anything I produce.

But if someone reading this know of some good literature on GUI programing in Java, I’d be interested. (I have both Borland JBuilder 7 Personal and Sun ONE Studio 4 CE)

[primemover]

Mark's earlier question about local maps

Sorry Mark... missed your question when I started responding again.

My question, primemover, then becomes, how about coming up with a crude way to generate the sort of local maps we're using now, and for the next several demos? It could be a kludge, or use a simplified version of the plate tectonics code with only a few plates. Then apply a sophisticated weather-simulator to get the terrain types. The weather generator is something that's needed anyway, and will be useable when your plate tectonics comes online. It certainly would be more beneficial to the project in the intermediate term that way. And I think good weather generation is probably of the same order of difficulty as plate tectonics anyway, though I could easily be wrong.

As I answer this, I am going to number issues/problems that would need to be addressed if we want a good simple map generator.

Actually the tectonics in this sort of situation could probably be very easily done. Not a problem at all. Especially if I used the crack model that I am working on (very slowly... ) right now. Since local models would only deal with between 1 and 3 separate plates, it would be pretty simple to generate (using a variation on the recently mentioned ideas) a map.

The only difficult part of creating such a map is coming up with a drainage pattern (1)... actually this opens up an another idea about the map!

Should we have several modes of map generation? Whole world and small area for people who want to create scenarios with a generated map? An idea anyway...

To move on with your question:

(1) We need a way to quickly calculate a drainage pattern. This would produce any rivers/streams to be drawn on the map.

Finally, in general, weather patterns/soil/terrain profile depend on lattitude and longitude, nearness and direction of water, location of any mountains, prevailing wind direction, (jet stream at correct latitudes), and "nearby" air mass types (2). Although programming will be a tedious, the basic idea is not as difficult as coming up with a way to model tectonics.

Air mass types brings up another (probably the biggest) problem we will have with local scenario maps:

(2) The main reason I wanted to work on geology and weather for the whole world together is because air masses that move into a particular area can depend on areas of the world as far away as 3000 miles or more. Take the US for example. US weather is dependent on the interaction of four different air masses that are generated at significant distances away: a dry polar air mass that generates over canada, a maritime (wet) polar air mass that generates just south of Alaska over the Pacific, a maritime warm air mass that generates over the Gulf of Mexico, and a semi-arid warm air mass that is generated over the western US and Mexico itself. (Rarely a fifth that is generated over the northern atlantic can also intervene). Each of these air masses affect local weather all over the US... so the BIGGEST problem in coming up with a weather simulator for a randomly generated local terrain would be to decide what kinds of air masses will move into the area without knowing the shape of the rest of the world.

If we can find an easy solution to (2) I think we will be able to come up with a relatively simple local map generator for the time being.

[Mark_Everson]

Re: Mark's earlier question about local maps

Hi primemover, thanks for responding to the issues I'd forgotten I'd brought up .

Originally posted by primemover
Should we have several modes of map generation? Whole world and small area for people who want to create scenarios with a generated map? An idea anyway...

Sounds useful to me long-term.

To move on with your question:

(1) We need a way to quickly calculate a drainage pattern. This would produce any rivers/streams to be drawn on the map.

Finally, in general, weather patterns/soil/terrain profile depend on lattitude and longitude, nearness and direction of water, location of any mountains, prevailing wind direction, (jet stream at correct latitudes), and "nearby" air mass types (2). Although programming will be a tedious, the basic idea is not as difficult as coming up with a way to model tectonics.

This sounds fine to me. You can allow the designer to specify all the external factors, or let the map generator pick them randomly.

Air mass types brings up another (probably the biggest) problem we will have with local scenario maps:

(2) The main reason I wanted to work on geology and weather for the whole world together is because air masses that move into a particular area can depend on areas of the world as far away as 3000 miles or more. Take the US for example. US weather is dependent on the interaction of four different air masses that are generated at significant distances away: a dry polar air mass that generates over canada, a maritime (wet) polar air mass that generates just south of Alaska over the Pacific, a maritime warm air mass that generates over the Gulf of Mexico, and a semi-arid warm air mass that is generated over the western US and Mexico itself. (Rarely a fifth that is generated over the northern atlantic can also intervene). Each of these air masses affect local weather all over the US... so the BIGGEST problem in coming up with a weather simulator for a randomly generated local terrain would be to decide what kinds of air masses will move into the area without knowing the shape of the rest of the world.

If we can find an easy solution to (2) I think we will be able to come up with a relatively simple local map generator for the time being.

For the smaller maps my take is to put a boundary region into the simulator that will not be part of the generated map. On the boundary you could then specify vectors for airflow at what temperature and what humidity is desired. So you could duplicate crudely the US climate factors using this sort of effect.

Would that work for you? Ideas from others?

[primemover]

Well... that depends. Are you saying 1) make the region bigger than the map will be? Or are you saying 2) make a few variables that are assigned the nature of the the surrounding areas? The way I see it, their are advantages and disadvantages to both.

1) More accurate, but geology may become more complicated.

2) Less accurate and likely to introduce errors in landscape (they would probably not be noticeable to most people), but less complicated as well.

Any ideas on how we can compromise?

[Mark_Everson]

Hi primemover, I was suggesting #2. I think it should work reasonably well. Perhaps a compromise is best in that you woudn't want the edges right where the external conditions are imposed. So how about you make the map about 20% bigger than required, and put the discontinous stuff out there. Then when you are done creating the map you chop off the 20% framing boundary zone. That should at least give a reasonable result since the big influences will be smoothed out a bit before reaching the "real" map. Anyway, that's the best I can come up with given my very limited understanding of such things!

[primemover]

Next Task: Terrain/Weather types.

Ok Mark. That sounds agreeable provided we can come up with a working algorithm for what you are saying. I believe we can (but I would like to make it more true to life later on).

The next thing we need to figure out is what types of terrain/vegetation/weather designators already exist in the game, and then if we want to include them or more.

Personally, I think terrain should be divided into three concepts that work together to form the final terrain features.

1. Weather (moisture, temperature, wind, location)
2. Geology (floodplains, flatland, hilly, mountains, ice)
3. Soil/Vegetation/animal types (soil is a combined result all three: geology, weather, and life type/density)

What is the current model? And is that model extendable?

I will need to know these things so we know what we are working toward and what factors will be involved. From their I think we can outline the tasks to be performed by the generator.

[Mark_Everson]

Re: Next Task: Terrain/Weather types.

Originally posted by primemover
The next thing we need to figure out is what types of terrain/vegetation/weather designators already exist in the game, and then if we want to include them or more.

You will see most of the existing terrain types in the latest demo. They are not very refined.

Personally, I think terrain should be divided into three concepts that work together to form the final terrain features.

1. Weather (moisture, temperature, wind, location)
2. Geology (floodplains, flatland, hilly, mountains, ice)
3. Soil/Vegetation/animal types (soil is a combined result all three: geology, weather, and life type/density)

What is the current model? And is that model extendable?

Check out the ecology model on the web page, and the "latest thread" listed therein. Its about a year old now. It can be extended or modified to suit our needs. Best to put thoughts in that thread, and email Simon to let him know its being discussed again.

Just let me know what else you need.

[Dale]

I can't remember who asked what my mapgen model generated (earlier in the discussion), but I have a couple of images that shows the map generation for the small (150x75 tiles) and medium (300x150 tiles) maps. Rivers don't show on the minimap, but they do flow in logical real-world ways to the coast forming lake systems, deltas and river systems/river basins. See below.....

Oh, and also notice the mountain chains, and how they can appear as coastal mountain chains.