Sign in to follow this  
Dewi Morgan

Dynamically created terrain - request for ideas.

Recommended Posts

Dewi Morgan    122
I just made a post in my game's forum about fractally/procedurally generated terrain. It's long and boring, at least to people to whom the idea of creating an entire world of your own is a bit blah (are such people insane? I feel so). So I won't paste the whole thing here unless people ask. But to me it's fascinating stuff, and I suspect it might be handy for people here too. If I ever write it, it'll be public domain, so you could include it in your own stuff without problems. Would love feedback and suggestions about my ideas. I'm sure there are ways to make it better, reduce the system load impact, speed it up, or make it more friendly to more systems. I am sure there are things I have got wrong or just plain stupid, or ignored. [Edited by - Dewi Morgan on March 3, 2008 3:43:09 PM]

Share this post


Link to post
Share on other sites
Dewi Morgan    122
Fixed link - thanks :)

There are lots of good posts on here about dynamic terrain, but they mostly seem to cover the heightmapping side (which I've mostly mentioned only in passing, since it's massively well-documented already), rather than the linear entities side. But I'm sure I can't be the *first* to try to create fully dynamic terrain, so I'm sure there are algorithms for the linear bits too.

VTerrainorg is meanta be good for this stuff, but their section on roads (and so other linear entities) is limited just to how to store them, and doesn't cover generating them in the first place, which it seems to me is the Hard Bit. Their software list only shows software that displays already-generated roads.

The other problem is distance-scaling. With most 3D engines limited in the X/Y they can display, I think I would need to find some way to compress the "distant" terrain in Z, so it's all a lot closer than it looks. But that could then bork the physics. But that's really a topic for another post, on another forum (3D programming). This post's about generating the terrain in the first place.

I also realise in re-reading that I may have offended some terrain generator authors by saying that often terrain generation works basically by "widdling on sand". I apologise :(

Share this post


Link to post
Share on other sites
Fingers_    410
One potential approach to the road issue would be to use a deterministic random algorithm (like something based on Perlin noise) to create the edges of each square sector, including points where rivers and roads cross the sector boundary. The number and type of such crossings would be "random" but depend on the coarse world map data. (e.g. no roads in the deepest wilderness)

Because the right side of sector (X,Y) is the same edge as the left side of sector (X+1,Y), you'd use the same random seed for both, and all the crossings would automatically match the neighboring sector. The code that then creates the interior of the sector doesn't need to know anything about the neighbors, only that it needs to draw roads and rivers from one edge of the sector to another. This would make the process more local and allow creating the sectors one at a time on the client.

I would also make "major river valley" a terrain type on the world map, as it would definitely affect the 10km zone around it. A feature like the 5000km river should be visible from the moon.

Share this post


Link to post
Share on other sites
Dewi Morgan    122
Two good calls, Fingers_!

1) I was looking for a deterministic algorithm (as I wrote in the tl;dr article :), though was planning on fractals seeded with a hash of the line endpoint positions instead. But Perlin stuff has the advantage (if I understand right) that it will give the same terrain for a set stretch of land, even if I seed it with the coordinates of two different zone sizes that include that land.

2) I hadn't thought of randomly generating some of the info on the entities: doing that I could reduce the storage they take up!

The trouble is, they can't be very random. There is (I believe) no deterministic algorithm for rivers, because height is important, as is the size of the tree above them (which determines the river flow rate).

There is also (I believe) no deteministic algorithm for roads, since where they are going from or to is important to their location, direction, and size. Randomly perlin-generating a massive highway on a tiny 2-zone island would not work well, especially if all it connected was a pier on each end.

I'd love to be proven wrong on both these counts.

So it looks like I need to procedurally pregenerate on a large scale, and that rivers in particular need precise information on at least their size and altitude entering and leaving the square, and roads need precise information on at least their volume.

[Edited by - Dewi Morgan on March 3, 2008 6:52:31 PM]

Share this post


Link to post
Share on other sites
Fingers_    410
Yeah, for realistic rivers the distribution shouldn't be all that random. That's why I'd suggest putting major rivers on the world map. I assume the world map is at least partly "hand-drawn" if you're depicting an existing world?

The random road system should be feasible. When generating road crossings for a given edge, you'd of course have to take the terrain type and population density of the two zones into account. Maybe each zone just has a population number and this determines the volume of roads leading into it. The population would be seeded by major cities and spread out into neighboring areas based on how hospitable they are.

You could even create the town and road network using a more complex process and then "compress" to a system like this. For example, as in your original plan you could first create major cities, then long roads in between them, add smaller cities along the roads, more roads to connect those etc, increasing the population along the roads. Then throw all of the road data out the window and only keep the population number. Because the population growth was dependent on the road system, the towns and roads "randomly" generated from the population numbers should produce an approximation of the original network without actually storing it.

Share this post


Link to post
Share on other sites
speciesUnknown    527
You state that you want a resolution of 10x10km. How will you put roads on this? They will be too thin. Contrary to popular belief, the great wall of china is too thin to be seen from space. (Although the mountain range it tracks is visible, perhaps this is the source of the myth)

Perhaps you should write an algorythm for an n*n km resolution? This would be more useful if you did make it public domain. Roads would, at higher resolutions, be visible.

Share this post


Link to post
Share on other sites
Dewi Morgan    122
Quote:
Original post by Fingers_
Yeah, for realistic rivers the distribution shouldn't be all that random. That's why I'd suggest putting major rivers on the world map. I assume the world map is at least partly "hand-drawn" if you're depicting an existing world?


Well if I'm storing them, I might as well store every river that crosses a zone boundary. The way I suggested doing it (as a perfect maze generator), that's only one leaving each zone anyway, plus 0 to 3 that enter it.

Quote:
You could even create the town and road network using a more complex process and then "compress" to a system like this. For example, as in your original plan you could first create major cities, then long roads in between them, add smaller cities along the roads, more roads to connect those etc, increasing the population along the roads. Then throw all of the road data out the window and only keep the population number. Because the population growth was dependent on the road system, the towns and roads "randomly" generated from the population numbers should produce an approximation of the original network without actually storing it.


The approximation would be... somewhat imprecise, I feel. You couldn't go from just two adjacent population numbers (which could both be 0) to generating the position and size of all roads passing through the zones from anywhere on the map.

Quote:
Original post by speciesUnknown
You state that you want a resolution of 10x10km. How will you put roads on this? They will be too thin. Contrary to popular belief, the great wall of china is too thin to be seen from space. (Although the mountain range it tracks is visible, perhaps this is the source of the myth)

It's visible from LEO, like a lot of other stuff. At a resolution of 10km/pixel it is definitely too small though. Hence the "entities" thing.

Sounds like you only skimmed the article, though, or I was unclear. 10x10 is just the most *likely* resolution of the "seed terrain" that I'd use to generate the higher res stuff. Some areas would be higher or lower res, depending how popular they were with players. Actually most likely a power of 2, so 2^20cm ~ 10km.

For linear features, each of those pixels would store "zone-crossing entities" as a single entry and exit vector and factal generation would provide the detail within the zone.

So for the Great Wall, you would have a 10x10km pixel that would show nothing about the wall, but you'd also have two data points on the border of the pixel, saying "wall enters here" and "wall leaves here".

Quote:
Perhaps you should write an algorythm for an n*n km resolution? This would be more useful if you did make it public domain. Roads would, at higher resolutions, be visible.


You seem to be thinking in terms of "terrain type". You would need a resolution of perhaps 5mx5m before you could begin to use a "road" terrain type. That'd be a slightly high resolution to store the whole world in, and would still give you lousy, imprecise, blocky roads.

Even at 1mx1m, you'd get very pixellated roads. Roads just aren't a terrain type, they're a vector. You don't want them to be "visible" on the pixel scale, you just want to store their vectors.

[Edited by - Dewi Morgan on March 4, 2008 8:25:09 AM]

Share this post


Link to post
Share on other sites
NineYearCycle    1538
Wow that post is insane. You're really trying to eat the entire tree rather than starting with an apple!

What you're doing is mixing different sets of data into the same final local map. Roads and rivers can be described as graphs and terrain is commonly a heightmap (I realise that you already know most of this from that post). Mixing those, i.e. taking the _full_ heightmap and generating the river graph could be done as a pre-processing step.

Actually a lot of what you're talking about is going to have be pre-processed because you can't do iterative high-resolution generation of linear features that cross boundaries such as cities/rivers/roads etc on the fly. Ok I concede that there might be a way but I've never seen one that didn't look terrible, repetitve or simplistic.

This isn't a bad thing but doing it could also lead to massive amounts of data, as you've noted 100s of GBs for the area that you're looking at.

Perhaps the best way would be to pre-generate the road/river graphs etc but stitch them into the terrain in real-time. There's topics on GD.net for doing this kind of thing so I won't cover them but you're probably either going to layer road geometry over the terrain or actual stitch it onto it during heightmesh generation.

An example of someone using this mixed mode heightmap/graph system would be Eric Bruneton on his Rama which uses his (warning gogle translation from French) ProLand generation system which is pretty impressive stuff.

For generating zones with those features you only need to divide your graphs along with your heightmap. I.e. once generated you can divide them up by turning edges that cross boundaries into vertices within the graph. Then you'll have zoned graphs and heightmaps that always meet up with their neighbours.

*insert-metaphorical-deep-breath*

As for terrain generation that is coherent across you're whole world you could use, multiple noise sources. You've already said in your post that terrain generation algorithms miss the point that the underlying geology informs the overlying foliage and morpholgy. However that underlying geology can be defined using different coherent noise alogithms (Perlin et al) too and used to inform/modify a surface generation algorithm based on standard heightmap generation. By using overlaid noise algorithms you'll get a continuous surface that is deterministically based (since noise is seed derived) regardless of the scale of your environment and thus you remove the problem of boundaries between zones not matching.

If you generate or sample these noises at different resolutions you can build you graph data based on varying levels of detail but always garuantee that they match up at the boundaries between zones and from the highest level (sea->floodplain->river->tributary->stream->marsh) to the lowest.

The next thing is to use different noise algorithms for different LODs. You can't use Perlin noise all the way down to the centimetre level from the continental because you'll see the repetition, so don't. Switch to different functions be they Ridged Multifractals or Plamsa whatever suits for that type of terrain and fade into them. Libnoise (sourceforge) has some good examples of this terrain type function stuff.

You're post (on your site) seems to be taking a very forward way of processing a lot of this stuff by fixing up the terrain to match where you put the linear features but if you're going to do that then you're going to get hideous results. Especially if your linear feature generation is totally ignorant of the terrain.

So yes I'm advocating the offline pre-processed idea. The linear graph based features like road, telegraphs, tunnels and rivers/stream/etc are going to end up being a small amount of data in grpahed format, and they can be easily zoned to reduce in memory footprint. Blending them into the terrain that they've been generated for, with per-node hints on blend/stitch method in the graph, at run time means that you don't have to bloat or modify your heightmap data meaning that you also don't have to do anything with brushes except along the length of the edge that you're modifying. The graphs don't have to describe straight lines either, rivers and road can be made of Bezier curves for example.

I think that doing that should give you far fewer artifacts than attempting to generate large scale linear features in real-time over your terrain.

Though I'd like to see your in action since you've clearly given it a lot of thought compared to me hammering this out whilst at work ;)

Andy

Share this post


Link to post
Share on other sites
Dewi Morgan    122
[First: I apologise if I come across in any of these posts as "argumentative" - sure, I'm trying to debate the ideas, but I don't want to be crabby about it I want dialog, and really, really appreciate the replies here. I'm a total n00b in this field, so anything at all that people say will be useful to me, even if I disagree.]

Quote:
Original post by NineYearCycleWow that post is insane. You're really trying to eat the entire tree rather than starting with an apple!


Oh, I'm doing the apple too. I've a li'l program in the same forum with just a room, some tables, and some chairs, where I'm working on the character controller, to get the GUI nice and intuitive. It really shows how massively far I have yet to go!

But planning is cheap. If I implement even 1% of the stuff I've *planned*, then I'll be happy. Not satisfied, but happy.

Quote:
What you're doing is mixing different sets of data into the same final local map. Roads and rivers can be described as graphs and terrain is commonly a heightmap (I realise that you already know most of this from that post). Mixing those, i.e. taking the _full_ heightmap and generating the river graph could be done as a pre-processing step.

Very good synopsis of the problem, yep :)

Quote:
Ok I concede that there might be a way but I've never seen one that didn't look terrible, repetitve or simplistic.
Yeah, the "Lego" systems, that say "everything must tile like THIS and no other way!" - I wouldn't be happy with that.

Quote:
100s of GBs for the area that you're looking at.
In hard drive terms that's not a problem at all. Heck, a couple terabytes isn't a problem, so long as lookups are fast. And at that size it's well worth skipping the whole filesystem thing, just creating a blank partition and filling it with the data directly, then directly calculating the cylinder/head/sector of the zone you want to look up. Should make for way faster access times than scanf, and use the disk more efficiently too.

But though it shouldn't be a problem in hdd terms, it's a big problem in core memory terms and in network bandwidth terms. You can't just send someone a terabyte over the net, not pull a Tb into memory to play with.

But I think, not as big a problem as all that. Entering a zone, the low-res heightmap for just that zone could be compressed and sent as a progressive image while the client is generating the high-res noise overlay seeded from the coordinates. When the data has arrived, client deforms high-res noise by low-res heightmap. For stuff further away, much, MUCH lower res can be sent.

Quote:
ProLand

Oh that is awesome. Quite breathtaking. I particularly like the fields, they are something I was wondering about myself, and kind of skimmed over in my doc, with a handwaving "apply agriculture magic here" :)

As for terrain generation that is coherent across you're whole world you could use, multiple noise sources. You've already said in your post that terrain generation algorithms miss the point that the underlying geology informs the overlying foliage and morpholgy.

Quote:
However that underlying geology can be defined using different coherent noise alogithms (Perlin et al) too and used to inform/modify a surface generation algorithm based on standard heightmap generation.


Wish I knew more about geology :)

For the moment all I can think is simple stuff like "store the 'normal' vector of the underlying strata, then when generating slopes, make them tend either toward the normal, or toward a plane perpendicular to it, whichever is closer. Make the tendency vary according to the strength of the strata vector. Where it is decided that the rock is exposed (wherever the slope is parallel to the vector?), display strata from the global 'rock sandwich image', aligned according to the height of the vector, so that strata can line up over entire continents".

I need to speak to some geologists to find out what other cool stuff I could do to make it more convincing.


Quote:
The next thing is to use different noise algorithms for different LODs. You can't use Perlin noise all the way down to the centimetre level from the continental because you'll see the repetition, so don't. Switch to different functions be they Ridged Multifractals or Plamsa whatever suits for that type of terrain and fade into them. Libnoise (sourceforge) has some good examples of this terrain type function stuff.


Thanks for the warning and the pointer. I was completely planning to use perlin for about everything, so would've fallen right into that problem.

Quote:
You're post (on your site) seems to be taking a very forward way of processing a lot of this stuff by fixing up the terrain to match where you put the linear features but if you're going to do that then you're going to get hideous results. Especially if your linear feature generation is totally ignorant of the terrain.


Well, I was planning to have "terrain travel costs" so that they would be generated to follow the terrain.

But the serverside generation and the clientside would be different, since the clientside one wouldn't have done the iterative high-res erosion that the serverside would have: it would just to one-pass generation, then read the entrypoints of the linear entities, then "cheat" stuff to fit them. The server could reduce the amount of "cheating" by, once it'd done its own map, doing the generation that the clientside would do, and then "jiggling" the crossing positions to get the best fit with the two squares either side.

I described the clientside version as taking terrain into account for rivers, but it needs to take it into account for roads too, and to deform the mesh so that roads are flat, if necessary adding embankments, bridges over ravines, switchbacks up hills, etc.

Quote:
The graphs don't have to describe straight lines either, rivers and road can be made of Bezier curves for example.


I thought about beziers, but I think storing every curve the road makes in 10km would be too expensive, compared to just storing entry and exit points and letting the client sort it out between those two points. Beziers are cheaper than point-to-point, but they are still very expensive.

The only problem I have with having the client generate it, isn't the artefacts, it's the time it'll take. That "fixing" of the terrain will take considerable time.

Sure, I can do it as a background thread, "generate whichever adjacent zone you're closest to", and I can cache 'em, but still. Slooow.

[Edited by - Dewi Morgan on March 4, 2008 12:29:53 PM]

Share this post


Link to post
Share on other sites
NineYearCycle    1538
Quote:

First: I apologise if I come across in any of these posts as "argumentative" - sure, I'm trying to debate the ideas, but I don't want to be crabby about it I want dialog, and really, really appreciate the replies here. I'm a total n00b in this field, so anything at all that people say will be useful to me, even if I disagree.


No need to apologise all of your arguments are seemingly well reasoned etc.

Quote:

Oh, I'm doing the apple too. I've a li'l program in the same forum with just a room, some tables, and some chairs, where I'm working on the character controller, to get the GUI nice and intuitive. It really shows how massively far I have yet to go!
But planning is cheap. If I implement even 1% of the stuff I've *planned*, then I'll be happy. Not satisfied, but happy.


Yeah I saw that too, from the posts you've made I take it your attempting to procedurally generate the rather _unique_ DiscWorld. It does make me wonder what kind of terrain and foliage you'd find above a Treacle mine, I mean how does Treacle under extreme compression behave? Does it stratify or form shale, seperate into oil and sugar? if you got a blow out would everyone in the vincinity just taste delicious for a week? :D

Quote:

*snip*
But I think, not as big a problem as all that. Entering a zone, the low-res heightmap for just that zone could be compressed and sent as a progressive image while the client is generating the high-res noise overlay seeded from the coordinates. When the data has arrived, client deforms high-res noise by low-res heightmap. For stuff further away, much, MUCH lower res can be sent.

Well it depends, if that low-res heightmap comes from a procedural system then there's no need to send it either. Or just have it send the low-res data the once, i.e. when they install the game. Even generating a lot of the intermediatary stages data is ok if its done once before run-time to improve ingame performance. It all depends on the acceptable footprint of your game on the users machine.

Quote:

For the moment all I can think is simple stuff like "store the 'normal' vector of the underlying strata, then when generating slopes, make them tend either toward the normal, or toward a plane perpendicular to it, whichever is closer. Make the tendency vary according to the strength of the strata vector. Where it is decided that the rock is exposed (wherever the slope is parallel to the vector?), display strata from the global 'rock sandwich image', aligned according to the height of the vector, so that strata can line up over entire continents".

Thats quite a neat idea, I've no idea how you'd actually implement it but that doesn't mean it isn't a great way of bringing the sub-surface out of the ground and into plain view!

Quote:

Quote:

Quote:
The next thing is to use different noise algorithms for different LODs. You can't use Perlin noise all the way down to the centimetre level from the continental because you'll see the repetition, so don't. Switch to different functions be they Ridged Multifractals or Plamsa whatever suits for that type of terrain and fade into them. Libnoise (sourceforge) has some good examples of this terrain type function stuff.

Thanks for the warning and the pointer. I was completely planning to use perlin for about everything, so would've fallen right into that problem.

Well you could indeed use it all of the way down, but it gets both expensive to call at fine grained details (I suppose this becomes less of an issue with async' terrain generation and faster multi-core PCs) and I've always found that generating ALL of your detail from a single course is why you end up with terrains that look like your heap-of-widdled-on-sand analogy. Noise should really just be one of the inputs that leads to your terrain from many factors. The making of Dwarf Fortress on Gamasutra has a really interesting discussion of how they generated the world layout and details.

Quote:

But the serverside generation and the clientside would be different, since the clientside one wouldn't have done the iterative high-res erosion that the serverside would have: it would just to one-pass generation, then read the entrypoints of the linear entities, then "cheat" stuff to fit them. The server could reduce the amount of "cheating" by, once it'd done its own map, doing the generation that the clientside would do, and then "jiggling" the crossing positions to get the best fit with the two squares either side.

That's only necessary if you're going to have the terrain implemented on the server at all of course. It might be worth seriously considering only using the players 2d positions on the server and the graphs of things like roads, towns, etc. The client can generate all of the terrain that it likes but the server is only really interested in the positions of players relative to one another for facilitating awareness of one another.

Erm, to put that in a more coherent way: The server doesn't care what the world looks like, only the view of other players that each individual player has. There's more too it than that, for example in our MMO we have towns and mountains etc so you need to be able to confirm on the server that an actor is actually able to walk somewhere when they attempt to do so. So we have some terrain/town information on the server its a very different kind of information, mostly concerned with slopes and portals etc rather than being the actual terrain and geometry.

Quote:

I thought about beziers, but I think storing every curve the road makes in 10km would be too expensive, compared to just storing entry and exit points and letting the client sort it out between those two points. Beziers are cheaper than point-to-point, but they are still very expensive.
The only problem I have with having the client generate it, isn't the artefacts, it's the time it'll take. That "fixing" of the terrain will take considerable time.
Sure, I can do it as a background thread, "generate whichever adjacent zone you're closest to", and I can cache 'em, but still. Slooow.

Probably not as slow as you'd think. You don't have to stitch it into the terrain itself for things like road and telegraph poles etc they can just be geometry over the surface. Rivers are a bit different but they're also a single pass that you could integrateas you generate the high-res terrain itself. At walking/running speeds you'll probably not notice it doing the work (i.e. any popping etc).

This might take you a couple of years to write in total! So think about the hardware that you'll have by the time you're hoping to have thousands of people wandering in your procedural (Disc)World MMO, probably quad-core target machine, dual-core base spec (they can turn down the detail!) so don't worry about aiming a little high for some things.

Good luck, hope my ramblings make some sense.

Andy

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this