Map generator model II

[Mark_Everson]

Hey primemover, hope things are treating you well!

Looks very cool, with lots of fairly deep options. Can't wait to see what kind of worlds you get out of it!

Do you envision doing resource placement also? At least for minerals? That should probably be mostly done after, but things like oil might need to be kept track of during.

Any timeline for when we should expect world generation? Will it have to wait til the summer, or might you get out a first shot earlier. I guess its not urgent, since your version now is in C++ anyways.

BTW, do you want me to delete the abortive "picture post" thread? If it comes up in the future that you want me to get rid of something just edit the post to say something like "Mark, could you get rid of this".

Cya,

Mark

[primemover]

Resources, Goods, etc...

Just got back Sunday from a week trip to Chicago (for Christmas). Anyway... to answer the rest of your questions:

Do you envision doing resource placement also? At least for minerals? That should probably be mostly done after, but things like oil might need to be kept track of during.

I should probably post a rundown of exactly how I envisioned this thing working, that would help answer your deadline questions as well. But here are the quick answers...

Yes... *lots* of things are kept track of during world creation. I have several files of documentation that have variables I intend to keep track of and what they are for. If you would like me to attach them (and explain them), I can later.

EVERYTHING in the world is "grown" from the conditions that give birth to them. This includes resources/goods. In my model, there are three types of goods: floral, faunal, and mineral (including mineral, fossil fuels, generic such as salt or glass).

Life goods and resources

the floral goods setting affects forest and naturally occurring crop distribution.

the faunal goods setting affects animal distribution.

BOTH of the above are "life" distributions. In the timeline of the generator, these settings affect the origin of life. The ratio floral/faunal will determine which type of life develops first (in evolution).

Placement of the above resources are also affected by soil types and biome types which are all affected by climate (produced by the weather simulator... another part of my "geogenesis" model)

Mineral goods and resources
This includes many different types.

In actuallity, FOSSIL FUELS will be created by mass life goods (plants become coal and natural gas, animals become oil, sea life gives birth to frozen methane (if we take this game into the future, this will be a resource harvestable by a future technology)) being deposited in a specific area and under the needed conditions to create them (as in real life).

MINERALS will be deposited in generic conditions that would naturally give rise to their existence. Uranium, Iron, Gold, Silver, Platinum, Copper, diamonds, evaporites, and others will be distributed in environments where they would be found in the real world.

COMPOSITE GOODS... by this I mean goods that are produced from raw materials such as glass. These goods will be located in areas where their composites are located in abundace... such as a desert for glass.

Any timeline for when we should expect world generation? Will it have to wait til the summer, or might you get out a first shot earlier. I guess its not urgent, since your version now is in C++ anyways.

This is a good question that brings up some things.

First, I cannot say wether I will have time over the next few months. I am anticipating some time... but my model is fairly complex and will take time to develop. With help, it could go a lot faster... but much of that help is going to have to be in the form of working on an algorithm that does what we need it to do (such as how do we implement a "Crack and fill" algorithm for plate generation). People who don't know much about how the processes of plate tectonics and trends in weather patterns are going to have a difficult time helping with the overall model and what exactly needs to be done. Basically I would have to say... "ok... now we need a practical way to implement such and such in the tectonic process," after which I would have to explain how it should work and then they take it from their. Programming it all myself would take QUITE a while... (I think working full time on it, I *may* be able to get a basic version of the engine done by the end of next summer).

As far as the language... I am not sure that programming it in Java would be necessary. I am thinking C++ would be better because it is very calculation intensive. But perhaps it could be done quicker in java... (except that I would have to learn the details of the language). If it was done in C++ we could spawn the map generator from the Java Program itself. The map generator for my game was intended to be a seperate program because of its complexity and because it was just generating a map file to be used by the main program (It is not necessary to have it be a part of the main program... the only thing shared by both is the data in the file it generates).

And YES... please delete that entire thread I... that was a complete accident.

[Mark_Everson]

Re: Resources, Goods, etc...

Originally posted by primemover
First, I cannot say wether I will have time over the next few months. I am anticipating some time... but my model is fairly complex and will take time to develop.

Hey primemover. I'd say as much as you can just do a very crude cut at things first, otherwise it will take forever. As soon as you can get the plates to generate reasonable continents and put even vaguely ok vegitation and resources on it, we can start using it.

In terms of discussions, maybe we can just hope for a few people who know what they're doing to show up that can discuss details intelligently with you. From most of our perspective it'll be the verisimilitude of the output that counts, and that's about it. Perhaps we can lure Paul Crocker and Henrique Duarte back for discussions.

As far as the language... I am not sure that programming it in Java would be necessary. I am thinking C++ would be better because it is very calculation intensive. But perhaps it could be done quicker in java... (except that I would have to learn the details of the language). If it was done in C++ we could spawn the map generator from the Java Program itself. The map generator for my game was intended to be a seperate program because of its complexity and because it was just generating a map file to be used by the main program (It is not necessary to have it be a part of the main program... the only thing shared by both is the data in the file it generates).

I think the separate program would be off-putting to some, but during the alpha stage of development I guess its ok. And as you say, if it takes too long, it might as well be a separate program.

And if Gary comes back, he was hot to do a map generator, he'd probably be willing to code it in java given whatever you have at that point in C++.

Well, I think long-term we'd want to have it in java. But since you already have a C++ framework I can live with sticking with it intermediate-term. That means needing to figure how to distribute the exe and make it run for Win, Mac and Linux boxes.

Have a great new year,

Mark

[LDiCesare]

I probably don't know enough about plate tectonics to be of much help. I probably could implement hot spots, though .
The language issue can be solved several ways:
The UI has to be in java for portability reasons. Or you can write a cross-platform UI, but well, I don't think you want to.
Otherwise you can give java a try, it is basically C++ without delete, runtime cast checking, and better exception enforcement. So if you know C++, it is very easy to learn.
Other ways to deal witht the program are:
- If there is no UI in the program, it should compile on all platforms quite easily, unless you use some non-standard libs. It could then be plugged through JavaNatveInterface protocol. That could be worth it because there would be only ONE call to jni to lauch the program and retrieve a big map data object. If we make many more calls, the overhead of calling C++ from java would be too much. We'd have to check out technical details, but basically what is needed is an entry point with a vector of inputs and an output map object.
- Translate the program from C++ to java. This one could be done easily but can take time depending on the number of Lines Of Code. How big is it? I am not yet volunteering to make a translation, but if the code is not too big or too dependent on C++ specifics (like operator overloading), then it could be done and would be interesting for you to see the loss in speed and the gain in size/maintainability.
- Of course it can also be rewritten from scratch in java.

[Lord God Jinnai]

I would help you, but i don't seem to be on the level of understanding of plate techtonics as you are.

Anyway you gonna add, in future versions, hotspots like Hawaii, yellowstone, etc which don't follow plate techtonic areas?

Also areas such as where I live (St. Louis), which is on a mid-plate faultline. Are you going to be implimenting anything like that? I know it may be difficult as the ideas of what causes such mid-plate faultlines is still out.

Again some ideas may depend on what theories you rely upon also.

[primemover]

Regarding UI:

There would be no UI to speak of when the final version is out. However, there needs to be a UI while it is developed. It would be very difficult to track problems without one. I haven't decided yet which way I am to go. My biggest problem is this: I don't really know how to use the Java UI libraries, and from what I understand they are somewhat difficult to use. I already know enough of java to know that I could write most of the program in Java. I would have to brush up on uses of classes and would have to learn the UI (or maybe one of you could implement that part of it). But I also worry about how long it will take to do the calculations necessary in Java.

Regarding knowledge:

I am not sure how much one would need to know to do some programming. If communication was clear enough on what needs to happen, this might not be a problem. But it sounds like the details on how we would need to implement plate tectonics and a weather generator might be up to me...

[LDiCesare]

But I also worry about how long it will take to do the calculations necessary in Java.

Don't.
Computation in java with a jit are about 4% slower than in C++. What is slow is, actually, the User Interface.

[Gary Thomas]

I would like to point out that all the scenarios we have at present have maps that represent a small proportion of a single plate. Using a plate tectonics model may be all right for the whole world (in which case the map should be a projection of a sphere, not a rectangular section of a plane), but is not helpful for the small areas we are using. Of considerably more importance are weather patterns and their effect on vegetation, and the soil types related to this.

In this area, a fractal approach does seem quite promising.

Cheers

[primemover]

I would like to point out that all the scenarios we have at present have maps that represent a small proportion of a single plate.

I noticed. I was under the impression though that we did want a large map in the final product... are we still headed in that direction?

In this area, a fractal approach does seem quite promising.

Eeewww... Yes... to generate the initial topography, but fractal patterns NEVER (at least that I have seen... and yes, I have seen the suggested pattern generator listed above) produce a geologically accurate map unless you take your resulting pattern and run it through a simulation of plate techtonics.

And the above fact makes perfect sense when you realize that on fractal maps, "mountains" are formed from the highs and the "oceans" from the lower parts of the map. This creates mountains that are not realistic in two ways:

1) In such a generator, the mountains tend to end up in the centers of continents which isn't consistent with the way that *most* mountains are formed (though there are exceptions)

2) Mountains on a fractal map do not end up in ranges. Instead, they end up circling a highest peak. Mountain ranges are regularly tens to hundreds of times as long as they are wide.

If we have a weather simulator as well, this will also cause major variations in the way weather works from the real world.

[LDiCesare]

I noticed. I was under the impression though that we did want a large map in the final product... are we still headed in that direction

I certainly hope we are.
I tried once to make by hand a map of Europe (the only region of the world with which I am familiar enough to try this), and it is a lot of work (you need a really big map if you want to get the English channel drawn properly for instance, and still see Greece on the same map).
So current scenarios shouldn't be seen as a limitation. They are small because it is easier to test the game on small maps, and because until ship transport worked, it was of little use to have huge lumps of water.

[Mark_Everson]

Yeah, for sure we eventually want good whole-world maps. But Gary's point is that in terms of what to do first, simulation of weather would help more than plate techtonics. I certainly find that argument fairly persuasive.

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.

[Mark_Everson]

Simon Loverix tried to post this, but because of technical difficulties at the site was unable to, so here it is:

Weather mainly concerns temperature and moisture and in fact I have a
way to determine those in the ecology model. It's very simple, and you
can leave out specials, currents and possibly water. If for those small
maps a uniform temperature and/or climate is used, it's even more
simple.
It requires only height and terrain type (flat, rolling, etc.) and
generates temperature, moisture, water, BM and food sites. You can use
these numbers to let the computer pick an appropiate tile from the ones
that are in use up till now.

For a quick and dirty continent:
1. Pick a random square. that square has height 1 (or whatever)
2. Pick any other random square. If adjacent to another square with
height 1, it's also height 1.
3. Repeat 2 until the land mass is large enough.
4. Randomize terrain type (flat, rolling, etc.) and/or height (a little)

That's it.

[Dale]

Hope this helps you guys out, and it provides a different way to generate decent random maps without the massive processor overhead of fractals or plate tektonics simulation. I found it while I was searching for a good fast mapgen model for my use. I can't remember who posted it now, but it was in comp.programming.irc.

Creating Landscapes
>I am currently working on a project where I will need to create a >random map for a tile-based game. I would like a map that makes
>sense, and can have parameters such as how much water (%),
>allowable terrains, etc. Something like what SimCity or Empire
>Deluxe, etc. all can do. Any advice?


I did this once. First I chose a number of squares randomly toward the middle of the board which I assigned a random (bell curve) altitude to. Then I ran an algorithm where each square's altitude would be adjusted according to a weighted average of its own altitude and the altitudes of its neighbours. ie:

Let's say 'R' is some random number...

NewAlt = (Alt * R +AltAdj1 + AltAdj2 + AltAdj3 + AltAdj4) / (R+4)

You run this on the whole map a number of times, and the altitude begins to spread out from the squares that started with an initial altitude value. By fiddling with how R is assigned and with the number of times you apply this, you can get either rolling hills or craggy peaks. You can also fiddle around with the number of squares you assign an initial altitude to and what those initial altitudes should be. (ie, choosing 1 square would grow a single mountain.) Actually, you can see that there's thousands of ways to fiddle with this.

Since I was making islands, I initialized the values of the edge squares to negative altitudes, and ran the algorithm so it would skip the edges. (ie, the altitudes of the edge squares didn't change.) Then when I was done terraforming, I ran a 'fill' algorithm from the edge squares (same algo used in paint programs), which would fill with water all squares that have a negative altitude. Bingo -- an island.

This works well even if your map isn't 3d -- it produces realistic shorelines with harbors and peninsulas. But it doesn't produce lakes. To make lakes, I put a water value into each of the same squares I assigned an initial altitude value to. (The 'peaks'.) Then I ran an algorithm where a portion of each square's water value would dribble into an adjacent square only if that adjacent square had a lower altitude value. And after each pass of the map, the water values for the 'peak' squares are reset; in other words the peaks act as water supplies, like springs. You run this algorithm long enough for the water values to disperse throughout most of the map. After it's done, any square with a value that exceeds a certain threshold is taken to be a water square.

That gives you small mountain lakes and big great lakes out in the flat lands. You can use this to generate rivers, too, by keeping track of the total amount of dribble from every square to each of its neighbours. After the algorithm is done, if the total amount that dribbled from square A to adjacent square B exceeds a threshold, then you put a river from square A to square B. (Although lakes take precedence over rivers.) This trick produces amazingly realistic rivers that wind around, join up, and flow into lakes or out to the ocean.

So now after you're done with mountains and water, you can make the different terrain types -- deserts, plains, forests, etc. (If a square is a water square its type has already been determined, so you can skip it.)

Every square has three values to work with; altitude, water, and water flow. You can calculate a fourth value, 'steepness'. A square's steepness is the altitude of its highest neighbour minus the altitude of its lowest neighbour. Now you can come up with something like this:

high altitude = snow
very low water / low steepness / low altitude = dessert
high water / low water flow = swamp or marsh
low steepness / medium water = plain
...and whatever else you can come up with.


You might want to normalize the values first; ie, divide every water value by the amount of the largest water value, and the same with the other values.

A cool refinement is to simulate weather by adding a 'water in air' value for each square. As you run the 'dribble' algorithm above, a certain proportion of every square's water value evaporates into the 'water in air' value, and the water in air values continually disperse into adjacent squares. If a square's 'water in air' value exceeds a threshold, it'll rain, and a portion of the 'water in air' value will then be returned to the 'water' value, where it'll flow according to the dribble algorithm running concurrently. If you keep track of total rainfall for each square, you can use that value to help determine that square's terrain type. (ie, rainforest)

If you do it this way, you won't need a continual water source at the peaks -- you could just add a fixed amount of water to the system, let it run, go get some coffee, and see what you've got when you get back.

If you want to get *real* fancy, you could add temperature. A square's temperature would be determined by its altitude and the time of year. If temperature is below freezing, the 'water' value begins to transform into a 'snow' value, which doesn't dribble.

It seems to me you could also use the temperature values and the altitude values to somehow determine how the water-in-air values disperse.

[LDiCesare]

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

[Martin the Dane]

As far as I can see this algorithem does not produce maps at all, it only modifies a map. After reading the above post I had an idea:

If we take the starting maps from primemovers system, semmi randomly desides wich way the plates are moving and wich plate is moving under wich plate. Thereby we determine wich edge will have a mountain chain, when the the above mentioned algorithem is applied to it, we might have a workable map-generator, at least untill primmovers more complex and better model is up and running.

And what we have untill then is in essence an expanded wether system, without couriolis forces, but that could be added to the airwater disipation part of the algorithm. I do like the weather part of the algorithem, it's simple and with some degree of realism.