Mapgeneration

[Nym Traveel]

Name: Mapgeneration
Summary: Generation of heigthmap and final terrain
Scope: Core Content
Current Goal: Evaluating different methods, deciding on the focus
Phase: Design
Curator: Nym Traveel
Related:

Ok, so here's the incubator thread for this huge topic.
I want to mention that the goal of this thread is to generate a nice terrain - biomes and stuff will be discussed in another thread.

As I need to make a big edit on this I may also rewrite the whole thing.
I think our best bet for the game world is a finite map with warparound edges (topological like a donut )
I outlined the necessary points in -this- google document, feel free to ask questions.
It's currently in read-only, if you want to change sth, just send me a pn.
Also up on google docs is -this-, a little sheets with some calculations regarding the size of the map in various aspects.

near future todolist:
- getting an prototype for the temperature simulation ready
- making a uml (or simmilar) diagramm describing the whole process. (tedious for me as the lecture on software engineering wasn't my favorite one )

Old post:

Spoiler

As of now a finite terrain is in my opinion the best to handle.
My current plan for the generation is as follows:

1, A huge heigthmap representing the whole map is generated

Possible methodes: Plate Tectonics, Polygone, etc.​

Problem: Size. Imagine a map with edgelength 128 km and one pixel per meter... Therefore we take a rasterisation of 16 (may change) blocks and interpolate between them. Heigthvalues will be saved as 2 byte which could handle 65 km heigth difference(or maybe 14 bits what would be 16 km heigth difference, would require a new datatype)​

2, The actual map is generated using perlin noise added to the heigthmap

Ok, thats the current plan.
- Get in contact with the guy who made the plate tectonic thing - talk with him about licensing
- convert the programm to java
- follow the other steps on the plan I posted
I hope to find some time this afternoon to write down these steps for better discussion and clearness.

I made a Google Document summarizing some of the above. Feel free to play around and leave a suggestion.

Edit: -Here- is a nice project: someone converted WoW into MC, whopping 24 gig I think this is a good reference - the highest peak is 1 km above sea. Heigth limit workaround for minecraft was needed

 

[Immortius]

Perhaps an intermediate work around for heights would be a per-chunk vertical offset. Then while you would be limited to 256 blocks at any point, it would be 256 blocks around a base height of your choice. All blocks below can be bedrock, and above can be air.

 

[Nym Traveel]

This definately would be a good solution until the chunks are ready.
Maybe take the intermediate value determined by the heigthmap as reference where to place the chunk.
As it is a workaround we should also not worry about players falling of the world when digging at lvl 0
But honestly I have no idea how to implement it :O

By the way: We would like to have a little talk about mapgeneration on Saturday, either 4pm or 9pm german time (gmt+2)
Who'd be in?

 

[Cervator]

I've only heard from Immortius so far, and am leaning toward the later time at least during this out of sync period with daylight saving time - Immortius also seems substantially more of a morning person than me

In that case later is probably better, but I expect we can get some people on IRC early and talk other stuff in the meantime. I've got a couple co-workers lined up for Saturday to do some Android talk / research.

And that height offset thing was what I meant on IRC the other day - which I figured would work as we aren't likely to have a deep sea trench and a mountain peak in the same chunk, needing more than 256 height combined

The height offset might also help during terrain gen to determine flow of water and such at a high level, pun intended

 

[Skaldarnar]

I will try to swing by to the meeting.
Map generation is an important topic, and I think we have to consider all aspects of it right at the beginning (how to determine city places, what can we do about rivers/lakes/oceans, even some basic biome stuff).

 

[Josh]

I'll stop by the meeting also, since it's related also to the height change.

 

[Nym Traveel]

Nice, sounds good!
Somebody on irc (sorry, forgot who) suggested some open source talk software in substitution to ts or skype.
I would definately prefer some voice for the meeting - just goes so much faster
So I think 9pm at gmt+2 is the most wanted time

 

[Josh]

Nice, sounds good!
Somebody on irc (sorry, forgot who) suggested some open source talk software in substitution to ts or skype.
I would definately prefer some voice for the meeting - just goes so much faster
So I think 9pm at gmt+2 is the most wanted time

that's what i've been telling Cervator

 

[Cervator]

That's Mumble - it works great. I have a server working on one of my (offline) home servers, I could probably get it back online for tomorrow. It has survived a WoW raid with a dozen or two people on it, but likely they were most/all in the US. I might be able to set one up on our webhost instead if mine doesn't work well, will try to test early.

Personally I'm still a much bigger fan of pure text for larger discussions. Voice is great for very small and fast-paced topic-specific stuff, bigger stuff can get jumbled, especially with an international project. I should be able to participate either way though.

Might aim for some Android stuff early and world gen later after we see if Immortius can make it on (or get lucky with Begla able to make it)

 

[Nym Traveel]

Just a little Update because of the lack of time

in the attachment you find my concepts of how I imagine the world gen.
Areas with double boarder: one generation step (not neccessary one generator)
Red: todo, possible sources of trouble
blue: annotation
green everything else

Detailed information somewhen this we.
I will also contact the author of the plate tectonic thing and try to understand/rewrite the code this/next week.

 

[Nym Traveel]

Updated the initial post and wrote an email to the University of the tectonics guy as I'm not able to find him anywhere else :O

 

[Skaldarnar]

That sounds good, I hope you're successful

 

[Laurimann]

Hey all!

This is a really neat project! So is the idea of incorporating plate tectonics into this great 3D sandbox.

I've been thinking about what the OP wrote and i think that before we reach 2013 it is possible to have a C library that the Java program calls for tectonics based terrain. Choosing C+JNI over porting the whole thing to Java is the very simple fact that porting code that relies heavily on bit twiddling and UNSIGNED integers is very very difficult to get correct - especially on java, which doesn't, as far as i know, support unsigned numbers.

But nothing comes off easy:

1. The original C code must be ported for 32- and 64-bit Linux and Windows. If Mac OSX is added, the number of versions grows to six. That's a lot more to maintain than just one binary - but hey, think of it as "downloading a driver for your video card."
2. JNI is new to everyone working with the project (i assume) and at any rate C structure to Java class mapping must be done in either case. This introduces a new dependency that makes maintaining the code(s) even more problematic.

The library, i thought, could offer two entry points:

1. Generate and return an initial map.
2. Simulate one step of the tectonic process for the map provided.

Benefits of this are:

1. Multiple maps can be generated simultaneously
2. Map generation doesn't halt the computer and can be done in the background.

So, for now here's my two cents.
-Lauri

 

[Immortius]

I have done JNI wrapping before.

The JNI wrapper would be best done outside the main Terasology project as its own project, I would think. The main project shouldn't have to deal with compiling C code.

I would like to treat the multiple versions of the binaries the same way we deal with the LWJGL natives at the moment - we'ld have all of them present but hook into the correct one based on the OS. Assuming there's no issue with distributing them with Terasology? We definitely would want to continue supporting Windows, Linux and OSX.

The real trickiness is memory management on 32-bit systems with their 4GB per application limit. If the native end tries to allocate too much memory and pushes into the memory reserved for Java it will likely crash pretty hard. Would be good to have some hard guarantees on how much memory the native end will use.

There is actually some support for unsigned numbers in the Guava library, but nothing in standard java.

 

[Cervator]

Hi Laurimann nice to see you on the forum! Have a World badge

For those unaware this is our new Finnish friend who did the interesting thesis on plate tectonics in procedural map generation

I'd be thrilled to see your tectonic world maps in-game before the year is over and don't mind the idea of keeping some native stuff around if we can make it work. And with some JNI knowledge here that does sound doable!

Lauri - would you mind if we get your source up on GitHub? I know it is on SF right now but it'll be easier to collaborate on GitHub. We've got multiple things on there already and a Jenkins set up to build everything. Up to your preference how we do it. If you're not familiar with Git / GitHub then we can do all the work and put the code in a new repo under our MovingBlocks organization account and make you an admin for the repo, or alternatively you could put it under a personal account so you're the "root" of the tree and we can fork your code for our organization repo instead

The wrapper / bridge stuff in JNI would live in another repo in the same way. Immortius can help set that up and would be perfect to help get the infrastructure like that worked out between your code and ours.

Nym Traveel - as world lead can you then take care of the step of putting working input to use inside our game somehow? Which could be as simple as displaying the step-by-step map as it changes on a new GUI screen for starters, then maybe a good step two would be to use it to determine biome zones as an alternative for what we've got now, and finally we'll have to figure out how to actually turn it all into blocks! I figure we still need the over-arching generator framework for that ultimately, not to mention the fun with heights

Lauri - with your source in a nice place, could you work with Immortius on the wrapper and different OSes we'll need natives for? Along with Nym on the content if we need that in a specific format and what not. And if you can find the time the idea of making Dwarf Fortress-like geological layers using multiple height maps would be sooooo tasty

Maybe that's more of a 2013 thing, but in the meantime I've now posted a DF intro event that would be a good way to finally fire that game up to see what it can do

 

[Nym Traveel]

I updated the initial post, longer response tomorrow, too tired to think atm

 

[Laurimann]

If the native end tries to allocate too much memory and pushes into the memory reserved for Java it will likely crash pretty hard. Would be good to have some hard guarantees on how much memory the native end will use.

Indeed that is a good point. There is an upper bound to the amount of memory allocated by the simulation depending on map size and number of plates. Running time affects the probability of ever reaching that maximum. Some example values are listed in the thesis. However, in practice the problem has workarounds such as giving java only the "identity structure" (or just a text string) of a map, which is then used by the C program to fetch the "meat" of the simulation from a file. If the file is also (later on) treated as storage from which plate data is read for updating and written back again to, then the total memory requirement for one simulation step decreases (dramatically) being independent of amount of plates and simulation duration. When the map is ready, only the final height field is returned to the calling java program, in which case the exact amount of required memory is 4 * "map width" * "map height". Problem solved?


I feel most comfortable with first trying to port my project in SF repo for as many platforms as i can. Maybe, as Immortius seems to be the one with the skill and will to do the JNI layer, that would be the point to copy the entire thing to github for co-op. Simultaneously, as the sole author of the software until that point, i could change the title and most importantly the licence to something you guys are more comfortable with, like LGPL or MIT license. I hope that by doing so i do not break the GPLv3 of the original project myself.

-Lauri

 

[Cervator]

I just noticed the Youtube video is available again - it is quite something to see the simulator in motion rather than just the end-product

That, and I can just picture having that display running inside Terasology like the world generation phase in DF

 

[Esereja]

will tectonic plates simulate only the lowest layer of generation or will it ocupy more layers of world generation?

will fractals or noise be used in any part of generation?

and is it realy that big proplem to port code in java, even as simplified version?
(I understan if there is so much code that it is annoying to port)

 

[Cervator]

Hey Esereja - the current tectonic generator just provides a final height map, but I've suggested the idea of doing one height map of sorts per major geological layer (like in Dwarf Fortress) too. Then actual distribution of minerals likely would be done with some sort of noise process within those layers

A Java port is likely plenty possible, especially if there's general demand for it, but on the other hand with Laurimann helping out by making the native simulator more sophisticated it might be a fair bit of duplicate work. There may be some nice performance benefits too, or clever ways to use the generator separately.