Geo Realism: Discussion on a new SDK based map generator

Did you read that the recent earthquakes in the Indian Ocean may be due to the Indian-Australian plate beginning to break up because the Indian side is moving slower that the Australian side.
 
Something like a mud-crack algorithm, where a continent (area) is turned into generic polygon with more or less straight edges with the continent being part of the geometric polygon and includes part of an ocean to one side...
I'd suggest a probabilistic flooding algorithm.
Start from a random unmarked plot (one that is not yet assigned to a plate).
If it is an ocean plot, then consider the plate you are making an ocean plate, otherwise it is a continental plate.
Mark the plot as belonging to a plate.
You keep a list of plots that are next to your current plate. That list also assigns each of that plots a relative chance to be the next to be added to the plate. Keep track of the sum of chances. The chance is higher if it is next to 2 and even higher when it is next to 3 or 4 of your plate plots. Plots that are land plots for a continental plate or ocean plots for an ocean plate have considerably higher chances than the opposite plot type.
Get a random number up to the sum, then go through the list, summing up the chances until the current sum is higher than the random number. Add that plot to the plate. Mark it, remove that plot from the list and adapt your border plot list including the chances of neighboring plots and adding new neighboring plots to the list (adapt the total sum whenever you change a chance or add a neighbor plot).
Stop with a chance that increases from a certain size on.
Then start again from another random unmarked plot. If a plate cannot grow any more and is below a specific size, then assign the plots to a neighboring plate instead.
 
I'd suggest a probabilistic flooding algorithm.
Start from a random unmarked plot (one that is not yet assigned to a plate).
If it is an ocean plot, then consider the plate you are making an ocean plate, otherwise it is a continental plate.
Mark the plot as belonging to a plate.
You keep a list of plots that are next to your current plate. That list also assigns each of that plots a relative chance to be the next to be added to the plate. Keep track of the sum of chances. The chance is higher if it is next to 2 and even higher when it is next to 3 or 4 of your plate plots. Plots that are land plots for a continental plate or ocean plots for an ocean plate have considerably higher chances than the opposite plot type.
Get a random number up to the sum, then go through the list, summing up the chances until the current sum is higher than the random number. Add that plot to the plate. Mark it, remove that plot from the list and adapt your border plot list including the chances of neighboring plots and adding new neighboring plots to the list (adapt the total sum whenever you change a chance or add a neighbor plot).
Stop with a chance that increases from a certain size on.
Then start again from another random unmarked plot. If a plate cannot grow any more and is below a specific size, then assign the plots to a neighboring plate instead.

This was my original thinking a long time ago when I first tried to build a computerized plate tectonics generator on a real globe model. It is easy, it finds a good fit, and can make decent plates.

It turned out to be a disaster however. The problem is that while important, the shape of the plate itself isn't what really matters. In simulating plate tectonics it is the plate edges that matter. Regardless of the algorithm, the edges still have to be well defined. The happenings of plate tectonics really depend on the divergent margins (spreading centers) and determining what types of margins (edges) were which was impossible without well defined edges.

So plates have to be built and defined from the outside in. Hence the mudcrack idea.

Actually, I came up with an algorithm today that may have a shot at working. The basic idea is this:

Setup: find the center of an area (continent). Start with the plot that is furthest from the center and create an edge with A being the start and B being the end plot.

Assumption: Edges of a plate are kept in a stack-like structure.

Base Case (an edge with the length of one plot) and extrapolation:
  1. The current edge has a beginning (point A), a slope (which we will call an asymptote) and ends at point B.
  2. Find the next "border" plot.
  3. If the next plot crosses the asymptote (representing the area outside of the plate), then that plot become the new B plot (keeping the continent on the inside of the plate shape) making a new slope that is more inclusive of the area. Find the lowest edge in the stack that the plot crosses (usually the top one or the one underneath) and make that the top edge that includes (adding) the plots from all edges removed (making the current plot the point B of the new current edge).
  4. Grab the next "border" plot and create a new edge on the stack with the B of the previous edge being the A of the current edge and the new plot as B. Continue this set of steps until we come back to the original plot.

Finally... combine edges with similar slopes (which will be rather sequential), possibly adjusting the edge of the plate to make sure that it encloses all continental plots. (Doesn't have to be perfect... the San Andreas Fault divides the north American plate from the Pacific plate after all. It has a little sliver of North America on it).

Once all continental plates are created, we can carve up the ocean using the continental shapes as a basis... spreading a mudcrack system, moving the continental plate borders out using some randomness and some thought out ocean dissection to include some ocean. Some plates will be purely oceanic.

The one disadvantage I see this algorithm posing is one of time. It will probably be a little time consuming.
 
Map generation can be time consuming IMO, so long as the use of the simulation is optional (i.e. - people can still use old-style 'cheap' generators if that's what they want to do). Personally I'd be happy to leave a map generating while I have dinner or something, since playing the resulting game will usually take a month or more.
 
Map generation can be time consuming IMO, so long as the use of the simulation is optional (i.e. - people can still use old-style 'cheap' generators if that's what they want to do). Personally I'd be happy to leave a map generating while I have dinner or something, since playing the resulting game will usually take a month or more.

Yeah, a Gigantic PW3 can take up to ten mins for me. Hopefully merging some of the calculations into the SDK will speed things up, but still, that's pretty rough.
 
With graphics for the terrains you should remember that we have two graphics for the same terrain available in C2C. The alternate, by QuestDog, is in the modmods. I can't use the default terrain graphics because they make me ill so I use the alternate.
 
Yeah, a Gigantic PW3 can take up to ten mins for me. Hopefully merging some of the calculations into the SDK will speed things up, but still, that's pretty rough.

With the full simulation being worked on I was more thinking for 30-60 minutes. Personally I think that's fine - you have a choice as to whether to use such a generator, and for me map generation is a once per couple of months thing.
 
With the full simulation being worked on I was more thinking for 30-60 minutes. Personally I think that's fine - you have a choice as to whether to use such a generator, and for me map generation is a once per couple of months thing.

That'd be cool except that if you end up with an untenable starting location (or your partner does... ;) ) and have to start with a map rebuild... eugh...

I have no problem waiting a long time for the world to generate, but would there be a way to just reshuffle the starting positions ON that world without regenerating the map all over again?
 
With the full simulation being worked on I was more thinking for 30-60 minutes. Personally I think that's fine - you have a choice as to whether to use such a generator, and for me map generation is a once per couple of months thing.

LOL. It wont take THAT long...

Of course I have never played with such a big map so who knows. I am thinking 5-10 min tops.
 
With the full simulation being worked on I was more thinking for 30-60 minutes. Personally I think that's fine - you have a choice as to whether to use such a generator, and for me map generation is a once per couple of months thing.

Really? Wouldn't it go faster than a Python mapscript, which has to be run through the interpreter, because it is already compiled fully in the DLL?
 
That'd be cool except that if you end up with an untenable starting location (or your partner does... ;) ) and have to start with a map rebuild... eugh...

I have no problem waiting a long time for the world to generate, but would there be a way to just reshuffle the starting positions ON that world without regenerating the map all over again?

We do have a task asking us to check that starting positions are not untenable. The example had the settler on a 2-3 plot peninsula which had a mountain range cutting them off from the rest of the continent. It would need work on figuring out what was untenable.

Really? Wouldn't it go faster than a Python mapscript, which has to be run through the interpreter, because it is already compiled fully in the DLL?

Not as much as you would think. A Python program doing the same big thing as a compiled C program does not have to be much slower even when both languages are programed well.
 
Not as much as you would think. A Python program doing the same big thing as a compiled C program does not have to be much slower even when both languages are programed well.
Depends on what you are doing but in the case of serious number crunching like such a map generator is C++ is considerably faster (if done well of course).
 
And parts of it could theoretically multi-threaded.
Yes, unlike the Python variant used by Civ4 which seems to use a global interpreter lock (I tried some multi threading for the PerfectMongoose map script a year ago).
 
Of course, for serious numerical simulation task (like this if it were to be done accurately [which isn't necessary for Civ]) GPGPU would massively trump any other method (probably by a couple orders of magnitude).

Realistically, for this sort of thing, given the constraints of the Civ environment (and the boost Python interpreter - note 'interpreter', NOT JIT) my best guess is that our best C++ effort would be around 20-50 times faster than our best Python effort.
 
Of course, for serious numerical simulation task (like this if it were to be done accurately [which isn't necessary for Civ]) GPGPU would massively trump any other method (probably by a couple orders of magnitude).

Realistically, for this sort of thing, given the constraints of the Civ environment (and the boost Python interpreter - note 'interpreter', NOT JIT) my best guess is that our best C++ effort would be around 20-50 times faster than our best Python effort.
Small remark: Boost only provides the link between Python and C++, not the Python interpreter itself, which I think is CPython. As it compiles into bytecode, it is not quite as slow as direct sourcecode interpreting would be.
 
In the BiomeInfo files thread ls612 asked the following question. The answer goes best in this thread, especially considering the current discussion in the last several posts:

@primem0ver: How will the GeoRealism generator link into the existing map generation? Will it have adjustable settings like a normal mapscript, or will it be hardcoded as an alternative to the current mapscripts? That has been the question that has been confusing me slightly with regards to this project.

This is an SDK based map generator.
It will make use of several info classes (including the two classes being discussed so far) and several new standard sdk classes to generate the final map. I say final because the maps will still be initially created by the traditional generator. This will allow people to use their preferred map script as long as it generates a complete world on which plate tectonics could occur.

I have not yet delved into the depths of exactly when or where the python map generator script is called in the SDK but the map will be grabbed as soon as this is done and passed to the GeoRealism Engine. From there the following things will happen using the current model:

  1. A CvGeoStatsPregame instance(inherited from the CvGeoStats class) will created for each plot that duplicates current location data and all the necessary stats used by the engine. This inherited class has several extra fields (pieces of data) that are not used in-game. These instances are also essentially moveable plots that will change location during the engine.
  2. The engine will divide the map (these moveable plots) into plates based on existing areas in the game that both make use of and further divide the over-all map wide ocean area.
  3. The plate boundaries will be analyzed and "spreading centers" (divergent margins where new crust is created) will be picked. The direction will be largely based on the position of these spreading centers, and the plate drift speed will be randomly assigned.
  4. The simulator will then start consisting of a "year" timer. Each loop through the timer causes the plates to "drift" a certain distance (based on the map size chosen) over time based on the randomly chosen rate in the direction that was assigned. As soon the "distance" adds up to the approximated distance for a single tile (vertically, horizontally, or both) a "move plate" event will trigger.
  5. Whether we keep this a "single tile" move can be changed to more depending on how long the engine takes... the point is still the same. The "move plate" event creates new crust (instances the GeoStatsPregame class) near the spreading centers and pushes the plate out (moving any GeoStatsPregame that belong to the plate to a new plot location). Overlapping areas will then be converted into plate folding (mountain building) and the underlying plate will be "converted" into volcanic activity among the rising mountains.
  6. Every so often the climate simulator, the drainage simulator, and a plate change simulator (to randomly determine the change in direction of or creation of a new plate) will update other geophysical data.
  7. Finally, the GeoStatsPregame instances will be converted into GeoStats instances and removed. The new GeoStats instances will be bound to their current plot (by position) for in-game use. When the geostats instance is bound to its plot, the geostats data is converted into actual plot data including terrain, features, bonuses, climates, bedrock, etc... all based on the way the engine uses the data in the new (and old) info files.
  8. Essentially this means that the binding process literally re-draws the map.

Upon return from the GeoRealism engine control will be relinquished back to the normal game engine and it will continue with whatever it does next.

The Map Options Screen will need some redesigning
Since the traditional map scripts are still used, some redesigning is necessary so that we can present the GeoRealism options in a separate panel. There is no GeoRealism "script" per se. These options will be available for use with all applicable map scripts. GeoRealism options should also be disabled for incompatible map types. The planned options are listed below.

  1. Reverse direction of earth's spin checkbox (will reverse direction of ocean currents causing the east and west coast climates to swap coasts).
  2. A slider option that allows for a longer time span (more mountains and mineral resources) versus a shorter time span (fewer mountains and mineral resources)*
  3. A set of slider options that allows for more time (more realism) versus less time (less realism) for each of the following map features: geography (land shapes), geomorphology (the geological layout of the land), and drainage.
  4. A plate speed range slider. Higher speeds means more and "taller" hills mountains (which will only be evident by width of mountain ranges and on the "altitude" Geolayer).
  5. A plate speed variability slider (which results in more variability in the mountains).

*EDIT: it should be noted that this 2nd option does not necessarily mean there will be more mountains in the long run. If the user creates a "humid" world this will not change since rain will erode the land just as fast. For "normal" humidity, it will be somewhat random. (Yes... erosion rates are part of the engine). However, it does mean that either mountains, hills, or the "remains" of mountains will be more widespread (more mountain ranges).
 
Wow... truly amazing work. You mentioned in there that the system wouldn't keep running during the game? I thought you might be able to actually allow it to continue so that the map CAN make some drastic changes now and then (even though uncommon).
 
Wow... truly amazing work. You mentioned in there that the system wouldn't keep running during the game? I thought you might be able to actually allow it to continue so that the map CAN make some drastic changes now and then (even though uncommon).

Thanks. The geologic time table is much too slow for the a game that only spans 50,000 years or so. Therefore it is unnecessary. However, weather/climate changes during the game are being planned for.


@ls612
LOL. I am just getting started the actual engine. Laskaris is working on filling in the climate data necessary for the biomes/climate determination. Hopefully he or someone else can take care of most of the xml changes from here on out. I will take care of ones that I need to deal with but some details can be filled out by others.

As of writing this I am working on the base calculations for temperature wind characteristics for each latitude (almost done). I will probably do the climate engine first so that we can start testing its ability on real Earth maps to improve its accuracy.
 
Back
Top Bottom