Jump to content

  • Log In with Google      Sign In   
  • Create Account

Terrain Generation with Plate Tectonics


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
13 replies to this topic

#1 lawrencemann   Members   -  Reputation: 139

Like
7Likes
Like

Posted 09 April 2012 - 07:41 AM

Greetings everybody,

For a long time now I've been desiring to see a terrain generator that relies on plate tectonics. The projects that have such a goal seem to be few and far between, so it seems that it's too difficult to do or that the approach is too unpractical when compared to more artificial/direct methods (like fractals). In any case it seems like it's not a very popular topic in the (hobbyist) game programmer scene. A quick search on the GameDev forums gave only one topic that uses plate tectonics (it was posted two weeks ago) - Carradine described in his "Vantage: Prehistoric Simulation Game (online) - Pre-Alpha" topic that

You use a “plate tectonic simulator” to design the initial creation of the world, which places mountains, plains and islands in the world by simulation millions of years of tectonic movement, then edit the specific placements, use temperature terraforming and moisture algorithms.


It would be interesting to learn more on his plate tectonic simulator and the way he uses it to create worlds, but in any case this seems to be the only game that utilizes plate tectonics. To find out why it is so, I decided to try to make terrain with plate tectonics myself.

For my bachelor's thesis (that I started some 10 months ago) I made a simple terrain generator that loosely mimics plate tectonics. It starts with a flat fractal generated terrain that is randomly split into plates. The plates are moved linearly until they grind to halt due to friction. Sometimes plates overlap i.e. collide. If the overlapping portions of the plates are continents and there's "too much" overlap, then the continents are merged together. If oceanic crust collides with any other plate, the sea floor "subducts", meaning that the subducting crust is moved from the denser plate onto the overlying plate. After the rate of action on the "lithosphere" drops too much, the terrain is split into new set of plates and the process just described is repeated.

The results are rather good considering the simplicity of the implementation:

tectonics_ultim3.png

tectonics_ultim6.png

tectonics_ultim5.png

The thesis is freely downloadable from http://urn.fi/URN:NB...mk-201204023993 .
There's also a Youtube video showing the simulator in action:

Lastly, the source code is distributed under GPLv3 in SourceForge: http://sourceforge.n...rojects/platec/

It seems to me like even the most naïve model of plate tectonics is able to produce more convincing heightmaps than conventional fractal based methods. That's why I'm really wondering why it's not used in more projects? And as a continuation to that, what would be needed for plate tectonics to make its way to the game industry - or is it worth it at all?

So, what do you think? :)

Sponsor:

#2 colinhect   Members   -  Reputation: 193

Like
2Likes
Like

Posted 09 April 2012 - 03:48 PM

It seems to me like even the most naïve model of plate tectonics is able to produce more convincing heightmaps than conventional fractal based methods. That's why I'm really wondering why it's not used in more projects?


Fractal-based methods are often used because it is fast enough to be computed on the fly for procedural terrain (see Minecraft). For extremely large scale terrain you simply can't have all of the terrain in memory (see I-Novae). This is the main reason why fractal-based methods will continue to be very popular.

Your work looks awesome. I don't have time to read your thesis though. Do you have any rough numbers on how long it takes to simulate and what resolution height-maps it can run in reasonable time?

#3 Bacterius   Crossbones+   -  Reputation: 8880

Like
0Likes
Like

Posted 09 April 2012 - 10:58 PM

The main issue with conventional fractal heightmaps is that they are isotropic and self-similar, i.e. they look similar at any scale and in any direction, which makes them rather dull. There are ways to remedy to this but they are rather non-standard and not obvious to implement, and also reduce performance.

Hopefully more realistic terraforming algorithms perhaps based on plate tectonics will become standard soon, but as Colinhect says it is not immediately obvious how to put this to use in the context of a "infinite world" kind of game. That said it should still be useful when it comes to pregenerating very high quality maps for, say, an MMO or a flight simulator.

The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

 

- Pessimal Algorithms and Simplexity Analysis


#4 lawrencemann   Members   -  Reputation: 139

Like
3Likes
Like

Posted 10 April 2012 - 02:41 AM

Colinhect,

The thesis contains a table of measured running times and (horribly unoptimized) memory usage per map size (chapter 8.2 or page 55). The running times are
  • 8-15 s for 128*128 map,
  • 25-37 s for 256*256 map,
  • 70-140 s for 512*512 map and
  • 300-480 s for 1024*1024 map
on a Pentium 4 CPU. So, adding even more size and detail would mean hours of running time per map. That forces the map generation to go offline. However, I was thinking that the output from tectonic generator could be used as a template for fractal generator. E.g. take a 128*128 map, scale it by 4 and fill 75% of the map with such fractals that they preserve the original 25% of the heightmap data ("corner points"). This might result in very detailed maps that have quite realistic landforms very fast. But, i haven't tried it out yet. :) Should'nt be too difficult to do. If there's interest, I might try to find time to do it and tell you how it turned out.

The a "infinite world" kind of game mentioned by Bacterius never crossed my mind when I was thinking about where to apply plate tectonics based terrain generating. Unless someone comes up with a way to segment the world into separate tectonical entities that can somehow be vowen together when its needed (FYI I think it's not possible), then the only option is to generate an entire "infinite world" at once using "infinite amount of memory".

Maybe there's a way around this, but like I said, the project never aimed there. IMHO fractals are for those who desire infinity.

#5 Postie   Members   -  Reputation: 965

Like
0Likes
Like

Posted 10 April 2012 - 10:56 PM

Interesting idea!

I can see this technique being useful at a high level for producing the general shape and positioning of continents in a finite world, and then using some sort of fractal approach to fill in the local details as required.
Currently working on an open world survival RPG - For info check out my Development blog: ByteWrangler

#6 colinhect   Members   -  Reputation: 193

Like
0Likes
Like

Posted 11 April 2012 - 01:54 PM

However, I was thinking that the output from tectonic generator could be used as a template for fractal generator. E.g. take a 128*128 map, scale it by 4 and fill 75% of the map with such fractals that they preserve the original 25% of the heightmap data ("corner points"). This might result in very detailed maps that have quite realistic landforms very fast. But, i haven't tried it out yet. Should'nt be too difficult to do. If there's interest, I might try to find time to do it and tell you how it turned out.


Outerra renders an entire planet using real-world elevation data for low-resolution and fills in details using fractal algorithms. I believe they are interested in eventually supporting completely procedural planets as well. The low-resolution data could easily be generated using an algorithm similar to yours to provide more realistic continent-level terrain while still providing details via fractals.

In fact, I'm sure this would generate some interest by the Outera devs and community if you were to post this in their forums.

#7 lawrencemann   Members   -  Reputation: 139

Like
0Likes
Like

Posted 16 April 2012 - 09:33 AM

In fact, I'm sure this would generate some interest by the Outera devs and community if you were to post this in their forums.


I wonder if they would warm up for a redirection here. I mean it doesn't feel good idea to spread this topic all over the internet, especially when the discussion has calmed here, so maybe it wouldn't be such a big etiquette blunder to go to their forums and tell them to come here?

#8 cameni   Members   -  Reputation: 462

Like
3Likes
Like

Posted 17 April 2012 - 03:00 PM

This is actually pretty cool, with simple rules and quite nice results. Of course, technically it's still just a concept, and I guess the devil will show up in the details. Mapping it onto a sphere, getting a better set of rules that respect the energies needed (occasionally there's a sudden large-scale unrealistic shift).

It would be best to move this process to the GPU. With a kilometer resolution on an earth-sized planet it would need simulating a 40000x20000 region. That would take quite a long time with that algo on the CPU, but optimized on the GPU it could run quite fast. On the other hand, even 1km resolution is too detailed for this anyway (without simulating erosion), so maybe a much coarser set would be sufficient as well. However, the fractal algorithms in Outerra are currently tuned for below 100m detail, so it would not look as good as it could. It would be best to augment it with some erosion simulation later.

Btw no need to be shy about it Posted Image
I only found it by a chance, you should have gone to our forum without hesitation. Yet another forum can't be considered "all over internet" anyway Posted Image

#9 deadhopeful   Members   -  Reputation: 124

Like
1Likes
Like

Posted 21 April 2012 - 07:04 AM

Hey, I found this thread by googling for "procedural tectonics" Posted Image I read through your thesis a bit and found it really interesting! It was cool that you distilled all of the information on Earth science I've been trying to absorb the last few days.

I would have liked to see a lot more examples like Fig. 24. Maybe you could post more in this thread? Your results are pretty fascinating.

Thanks for sharing your work, it's very helpful!

#10 lawrencemann   Members   -  Reputation: 139

Like
0Likes
Like

Posted 08 May 2012 - 11:20 AM

I would have liked to see a lot more examples like Fig. 24. Maybe you could post more in this thread? Your results are pretty fascinating.


Thank you so much for the positive feedback! Posted Image I'm especially joyful to hear that you enjoyed the theoretical portion of my thesis - I put a lot of effort in it because I wanted to produce a comprehensive yet easy-to-read introdution to the theory of plate tectonics. I hope it helps you and many other people interested in this topic!

What comes to new screenshots I must disappoint you for a moment. The pictures visible here and especially in sourceforge.net pretty much cover the most interesting aspects of the simulation/terrain generator. I am currently making some adjustments to the code - addings super simple river erosion simulation, improving subduction, making the output more rough to improve the natural look and feel of it... But I've been super busy, far more than I'd like, thus I haven't been, and in few weeks still won't be, able to share anything with you. But just wait... ! Posted Image

#11 lawrencemann   Members   -  Reputation: 139

Like
0Likes
Like

Posted 20 May 2012 - 11:27 AM

I would have liked to see a lot more examples like Fig. 24. Maybe you could post more in this thread? Your results are pretty fascinating.


Finally! I pushed my timetable this weekend and managed to implement all the improvements I desired - erosion caused by rivers, more rugged texturing, fixed "long finger-like islands" subduction bug and added some curvedness to plate trajectories. The results are not incredibly good but significantly better than earlier!

platec-new01.png
Pay attention to much rougher yet far less abrupt mountain slopes. The whire pixelated ring is there to hide the not-yet-fixed subduction bug.

platec-new02.png platec-new05.png
In the last two pictures you can see long and island chains and islands too. However, none of them looks like a "long finger". Quite the opposite - there's cool looking archs and angles here and there, much like in the real world. Posted Image

#12 Clotaire   Members   -  Reputation: 104

Like
0Likes
Like

Posted 07 August 2012 - 04:12 AM

Hello lawrencemann

Nice job! That's what I was looking for for a while now, to make more realistic worldbuilding. I've downloaded the sources but, as I don't know any programming in C++, I wonder if you could give me some indications about how to make you program work under windows.
Thanks in advance.

Clotaire

#13 lawrencemann   Members   -  Reputation: 139

Like
0Likes
Like

Posted 08 August 2012 - 03:22 PM

Nice job! That's what I was looking for for a while now, to make more realistic worldbuilding.


Thanks! I'm always happy to hear that someone enjoys my work or finds my effort helpful. Posted Image I agree with you: by simulation of physical processes produces much more realistic terrain than fractal based methods!

I don't know any programming in C++ ... how to make you program work under windows.


I did my work on Linux for Linux. I have absolutely no intentions to port the code to any other platform. For those who want to do it themselves, I suggest the following:
  • Learn some C/C++ (if you don't know it already).
  • Get make & gcc for Windows (optional).
  • Fix the Linux specific parts of code (like include paths) to match your system.
If somebody does any porting and feels like they want to share it with others, please contact me and we'll commit your code to the SourceForge repository. Posted Image

Edited by lawrencemann, 08 August 2012 - 03:24 PM.


#14 jefferytitan   Crossbones+   -  Reputation: 2126

Like
0Likes
Like

Posted 08 August 2012 - 04:14 PM

Very cool. I too like the idea of using real physical processes because of the improved results. Sadly the fractal methods I've seen yield a certain predictablity, and (as it says on the box) suffer from scale invariance.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS