I've recently been messing around with LibNoise and looking into ways to generate terrain. I know I want to generate a mesh from a heightmap created with some sort of algorithm that gives me a natural-looking planetary surface. The problem I have here is that I want this to look like a normal world, but with the constraint that all the land is connected in some fashion. Since I can't think of a way to guarantee that from something generated by LibNoise, I was wondering if you guys (I've been searching around for a while, and noticed that JTippetts is the procedural terrain guru) could think of any way to accomplish this?

An algorithm I can make up in my head would be to randomly generate points with connected edges (that would act as bridges?) and somehow expand terrain out from that data (no idea how I would accomplish that though). I suppose if I learned more about how perlin noise actually works maybe I could create my own noise thing. Something else off the top of my head could be to generate a voronoi diagram, pick clusters and connecting polygons and then do some midpoint displacement around the borders to make it look more "natural."

I've recently been messing around with LibNoise and looking into ways to generate terrain. I know I want to generate a mesh from a heightmap created with some sort of algorithm that gives me a natural-looking planetary surface. The problem I have here is that I want this to look like a normal world, but with the constraint that all the land is connected in some fashion. Since I can't think of a way to guarantee that from something generated by LibNoise, I was wondering if you guys (I've been searching around for a while, and noticed that JTippetts is the procedural terrain guru) could think of any way to accomplish this?

An algorithm I can make up in my head would be to randomly generate points with connected edges (that would act as bridges?) and somehow expand terrain out from that data (no idea how I would accomplish that though). I suppose if I learned more about how perlin noise actually works maybe I could create my own noise thing. Something else off the top of my head could be to generate a voronoi diagram, pick clusters and connecting polygons and then do some midpoint displacement around the borders to make it look more "natural."

You could check this out
http://http.developer.nvidia.com/GPUGems3/gpugems3_ch01.html

Also more details on marching cubes
http://paulbourke.net/geometry/polygonise/

The basic idea is you create some density function, maybe with noise, and then you run marching cubes algorithm to generate geometry over the surface you define with the density function.

If you have a single point of view and you just want to move across the landscape and never run out of land, then the solution is to always make sure there's somewhere else to go.

Split the landscape into a triangular mesh. Perturb the triangle corners using perlin noise or similar across the 2D plane. You now have an infinite plane which is covered with irregular triangles. Consider these corners to be the nodes of a network. Each node has a state "undecided", "land", "ocean".

Find the node where your camera is, make that land.

So there are actually two rules in your universe. The first is that there must be unallocated nodes somewhere next to a land node -- because there must always be somewhere unallocated to turn into land. The second is that all land nodes must be connected to a land node -- because all land must be reachable.

So then, consider an undecided node which neighbours at least one decided node. Call this the candidate. If all the candidate's neighbours are decided and ocean, it must be ocean.

If the node has a land neighbour, it might be land. In order to tell, we need to know how many other potential nodes there might be. If this is the LAST unallocated node next to land, it MUST be land. Otherwise you could allocate it randomly or you could bias the random chance by the count of pending nodes.

So the easy thing to do there is keep a running count of unallocated neighbours of land nodes. When you allocate a land node, add the count of unallocated neighbours to the total.

Once you know what the node is, pick a suitable height for it. You can then interpolate all the intervening points inside each triangle, and use Perlin noise on top of that to break up the surface.

Arrrgg!!!

I've just spend half an hour in the bath thinking. Apart from what a git my ex-husband is, the other conclusion I came to is that that scheme, lovely though it is, won't work.

If you set off from the origin and walk in a circle, it's possible that the "last way out" ends up trapped inside the circle. Your land-bridge off the current continent is actually just a peninsula into a lake...


So here's my next plan. You start at the origin which must be land. You have to extend map edges in their entirety. You keep track of how many map edges currently have a way off it -- a "land" tile at the edge.

When you come to add a row, decrement this counter. If it's zero, then and the edge you're expanding contains a land tile then the row you're currently adding to an edge MUST contain a tile which is land and connected to an existing land tile. All other tiles can either be land if they have at least one land neighbour (either in the new row or in the edge you're connecting to).

If you added 1 or more land tiles to this edge, then increment the counter.

As you expand you'll want to keep track of the ideal density of land in the world and the actual density of each row. The tile type choices should be biased by this, otherwise the land will tend to become straggly. The bias will encourage lakes to close off and the land to form loops when possible.

Because your "edge" is straight, the defined map is definitely convex... and that means you can't trap your land bridges inside a loop. You could also do the same with any convex polygon shape; a hexagon might work well, because the land shapes will be less prone to producing obvious diagonals.