SYNOPSIS
Are there any procedurally generated terrain algorithms that are both deterministic (anyone generating a certain area will always get the same result, reguardless of what other zones they have generated or not) and congruent (so that a generated road that passes out of one zone, would also be generated to pass into the adjacent zone, if someone were to generate that zone without generating this one first)?
THE PROBLEM
What I want is to have a HUGE world map (erm, 800,000,000 sq km, yes I know it'll be as dull as ditchwater to explore, but I don't have a choice here), stored as a series of bitmaps for things like height, terrain type, etc, at a resolution of one "pixel" per 10x10 kilometre zone. [Edit: I was wrong - it's actually slightly over 200,000,000 square km. Not that this makes much odds.]
It's possible, knowing the coordinates of the square, to look up the terrain type and altitude of each corners fairly fast, and procedurally generate the terrain in a repeatable way. That much, I'm OK with.
The problem with this system is that I don't know a way for two squares to match up. I can make sure the terrain matches well enough, just by seeding the terrain edge with a fractal line generated from properties the two corner points.
It's the roads and streams and erosive features. How can I make a river that will flow 5,000 miles, when I can't even generate land where a road randomly generated in one square matches up with the one in the next? Sure, I have the heights of the corners of the 10km area, but that won't tell me where the streams and roads come in from adjacent squares.
I thought of various ways around this problem.
1) always, every 10km, have a river at *this* point and a road at *this* point, so the edges fit together like Lego... which sucks, but is the classic and trivial way of avoiding the problem.
2) store all linear features like roads, rivers, power lines, telegraph lines and railroads, from dirt track to highway, as a set of vector graphics using something like a satnav map, only thousands of times bigger, more like Google earth. Which isn't procedural at all, and destroys the whole point of a procedural system.
3) Store a series of endpoints, and make the lines between them fractal rather than straight. Have a mathemagical way to very quickly check whether a map pixel lies under one of these fractally-perturbed lines, and then generate the necessary fractals up to sufficient resolution to tell if they pass through that square.
I thought this one quite promising, at least for large roads and significant rivers. I could have a road marked as passing from Ankh Morpork to Klatch, with a peturbation of 15%. Any pixel that on the far side of either city can ignore the line. Any other pixel which is more than 15% of the line-length away from a direct line between the two cities can ignore the line. If the pixel does lie in that range, then generate the midpoint of the line, and test to see if the pixel is within 15% of a line from that midpoint to the closest city. Repeat until either it gets excluded or included.
The downside of it is that you'd need to check a *lot* of roads against each square each time, to see if they entered it: and you'd have very little control over them to resolve conflicts. For example, you'd often get a road that randomly weaves over another road, and then weaves back again. This is rather uncommon in reality.
4) [From a suggestion by "Daris Xiao or Benjy Wright" on forum.thegamecreators.com] Store the points that each linear entity crosses a square border.
Are there any standard algorithms for arbitrary road/river generation, though? Not that I have been able to find. Well that's not quite true, rivers are trees and fractal trees are standard.
I initially wanted to keep pregen'd map data to a minimum, as just 4 bytes per vertex for (height + type) = 3.2G for 1km squares. But since I am using fractal information, I can store a definable number of squares, just by setting the resolution of each one to depend on the popularity of the area. I could do the whole map at 10kmx10km I'd get a heightmap of just 32MB uncompressed.
But there's no point storing ten million square kilometres of desert that nobody ever visits at that resolution. But there's also no point repeatedly regenerating the one 10m square area that everyone visits when they are created. So instead of saying "I can store X amount at resolution Y", I should instead be thinking "each pixel can be any size, and the LoD will depend on the popularity of the area: I can store N of these bixels in M bytes. I'll increase the stored resolution of areas when people visit them, and either reduce the resolution of the less popular areas when I get low on disk space, or just buy more space." - in that case, the resolution of what I send to the client, instead of being fixed, can vary, and will be dependant on things like bandwidth and local detail and such.
So I *could* store the crossing-point for every linear entity passing a boundary. Using something like:
1 byte (entity type).
1 byte ("volume" or "quality" of the line at that point).
2 bytes (location to nearest metre of boundary crossing, within 10km range.
2 bytes (entity ID within square)
2 bytes (vector direction)
= 8 bytes/line/boundary, though what exactly I would pass would depend on the entity type.
Checking satellite photos, England has a line density ~100/km in towns, ~3/km in wooded hills. Even if the whole 8 million-10km-zone world were towns, it'd be only ~100 Gigs.
That's feasible. The line density'll be *well* below 100/km: ocean zones have no crossing lines, wilderness will have very few, villages and towns can be generated so they don't straddle boundaries, and small streams/tracks can generally avoid the zone boundaries. So in reality it'd be less than a gig for the initial 10x10km version. Cheap! And in server terms, just one cached lookup per person entering a zone, which is effectively zero cost.
Zone generation
HOWEVER. Zone generation must be:
* Congruent. A zone must always tile well with its peers. The above will fix this.
* Coherent. There must be no rapid jumps of altitude, terrain type, etc.
* Deterministic. A zone must always be generated the same way, so I initially thought that applying erosion at higher resolution than the stored pixel when pregenerating wouldn't work in this case, as I couldn't think of a deterministic way to reapply that erosion without considering boundary-crossing wear. Then I had a Thought... erosion as a linear crossing type!
* LODdable. Should be able to generate a specific section of the zone on its own at high res without needing to do the whole lot. This means the height *must* be fractally generated from the heightmapped corner points of the zone, using a fractal coarseness from the typemap. That will allow rapid recursion The specific *part* of the Zone the player is in should be able to be generated in high resolution, without generating the others.
* Fast. People can fly and so can see many zones at low res, and can teleport from one to another instantly, etc. It doesn't need to be "truly" fast, just has to appear that way. LOD and fractals will help a lot here.
ENTITY TYPES
Crossing Entity Types:
River: id, BorderCrossingPosition, altitude, size, and entry/exit angle.
Road: id, BorderCrossingPosition, size and entry angle.
Telegraph: id, BorderCrossingPosition, size and entry angle.
Powerline: id, BorderCrossingPosition, size and entry angle.
Pipeline: id, BorderCrossingPosition, size and entry angle.
XY Entity Types:
Since we're storing entities anyway, we might as well have some that we can place anywhere in the zone, as well as ones for the border.
Erosion: id, XYposition, entry angle, radius, falloff and magnitude (can be negative). Does nothing but erode/build terrain. Identical erosion IDs create an erosion "corridor" or "polygon". Very expensive type, to be used sparingly.
Terrain type: XYposition, position, radius, falloff, magnitude, entry angle, terrain type, cutoff-sharpness. Applies a terrain type to that edge. Overlapping types average. Identical terrain IDs create a terrain "corridor"/"Polygon"
Coast: id, position, altitude. For border-crossing lakes and the ocean, result in a flood fill from their point at their altitude.
Strata: Sets the direction of the underlying rock strata plane. Used in cliff textures, and in hills to give them a "sawtooth" effect. I have always felt that fractal terrain didn't portray underlying geography enough, this might help.
THE PLAN FOR THE CLIENT SIDE
So here's my plan of how the client will deal with the information from the server now: interested whether people can spot flaws in it.
1) Obtain the various values for the corner vertices from the server: "altitude", "cragginess", "fade rate", "terrain type", "terrain fade rate".
Cost: Network time
2) Set the mesh's zero Y to the average of the four "altitude"s.
Cost: 3 adds, one div, four subtracts = not significant.
3) Between any two corner vertexes, the speed of fade for contribution of one vertex' "cragginess" to the other is governed by the "fade rate" between the two sharpness values. So with two 100% sharpness values, you can switch instantly from crags to plateau, but with lower values you get a gradual fade from, say, plains to foothills. So with a certain fade F, the contribution from a vertex' cragginess "C" at P pixels along an L pixel-long line, is: DCC(F-1)/(2L) (done twice, once for each vertex)
Naive Cost: 1 add, 2 sub, 2 div, 8 muls per border vertex, fractally LODable.
4) For each of the four borders of the zone, use the x,y locations of the two vertexes at each end of the border as a random seed to fractally generate the terrain height along the line of the border, with the above cragginess. This ensures we get the same altitudes along that line as the adjacent square would. Generate all four borders at low resolution (1km or 100m pixels).
altitude = (P1.Alt+P2.Alt-C)/2 + RAND*C
Naive Cost: 1 RND, 3 add, 1 div per border vertex, fractally LODable.
5) Generate the rest of the terrain to the same low resolution (say, 0.1km squares, or 100x100=10,000 nodes), using the corner heights as initial heights to generate from.
Naive Cost: as above, but for four vertexes, so ~double the work per square. However, the C values could be stored along the borders so could be averaged without calculation? Again, fractally LODable.
6) Obtain the list of border-crossing entities for each border.
Cost: Network time
7) For each of the linear crossings for a border that has an altitude, erode or heighten the terrain to the correct altitude, using a brush radius dependant on the type. Raising the terrain to meet a river, for example, would need a large-radius raising or it'd look like an aqueduct. Dropping the terrain to meet a stream would be fine with a smaller radius: the stream has just "eroded" a trench. Apply largest radius effects first.
Cost: From here on, cost gets relatively expensive. Not just the radius-ordering sort, but also changing the altitude varies by the square of the radius. However, both can be preoptimised serverside: the corner vertices and crossing point should be chosen so the fewest altitude changes are needed; and the entities can be passed from the server in the order that their altitudes should be applied. If there are two things next to eachother with completely incompatible heights, then the result will be a mess: the world map will need sanity checking.
8) Find all duplicate "Entity IDs" - these represent linear entities that come into the zone and pass out again. Ensure that these are all connected, and generate a path between them using something like A*. For rivers, the width may not reduce below the smallest of its two entities, any dips in their path become lakes, and any impassible ridges that are higher than both endpoints, or which cause a lake to extend to the edge of the map, will need lowering.
Cost: depends on the entity type. Relatively expensive, though.
9) Find all singular Crossing entity ids, and find them an endpoint. For roads/telegraphs/pipelines, preferably at a junction with a more major entity of the same type, otherwise with a more minor entity, otherwise some random ending type from a terrain-aware list (road peters out, ends in a house, ends in a jetty, etc). For rivers, if their angle indicates they flow out of the zone, a spring; if they flow into the zone, then join with other rivers or oceans if there are any that leave the zone at a lower altitude, otherwise end in a sinkhole, swamp, or new lake.
Cost: depends on entity type.
9) Place bridges where roads cross rivers, lakes where rivers cross eachother (shouldn't happen, but still), merge nearby roads into one (possibly upgrading the "size" value for the merged stretch) waterfalls an rapids where rivers flow down steep areas, etc.
Cost: depends on entity type.
10) Obtain a list of any specific scenery details from the server, and add them.
Cost: Network time. Should be rare, but there are some major, marked cities at least. Since these will be player hangouts, this will actually be performed very frequently, even though very few terrain areas will use it.
11) Place scenery, random-seeded both by position within the Zone, and the Zone's id, taking into account terrain type (caves in crags, scarecrows in cornfields, no houses under lakes, randomly-created paths and streams don't lead onto zone boundaries, brooks only flow downhill to existing rivers, human habitations tend to be near concentrations of linear entities, human habitations can affect linear entities by broadening roads, walling rivers, subsuming or terminating pipelines and wires, etc).
THE PLAN FOR THE SERVER SIDE
Generating terrain iteratively from the "root" of each feature, then just storing and passing these entities, is a lot easier than generating the terrain deterministically.
The question then becomes, how do I fractally generate the linear elements?
Order of Calculation
Stuff that depends on other stuff should be done after the stuff it depends on. Most dependencies are two-way, but have a strong directional component. For example, towns form at river forks, but may then slightly modify the path of the rivers, and through irrigation, reduce the river volume.
So generally, I think the order should be:
Terrain typemap
Terrain heightmap
Strata
[Remodify the heightmap to account for strata]
Geological features: cliffs and mountains
[Remodify the heightmap to account for geological features]
Waterway paths
Waterway volumes
[Remodify the heightmap to account for waterway erosion]
Primary-level population centres and agriculture.
[Remodify terrain typemap to include manmade changes, waterway-imposed swamps, etc.]
Roads and other forking entities.
Linear nonforking entities.
[Loop back to generate secondary level pop centres, then tertiary, etc down to hamlets]
Strata
If the fractal deviation could be aware of the underlying geology (hardness of stone, angle of strata) that would be really awesome, and I could get fjords and islands and stuff for free. And anyone making a world would be proud of fjords, it's just the way we world-builders are.
Also it would allow for things like Benidorm's peacock island (eg http://media-cdn.tripadvisor.com/media/photo-s/00/1e/3b/d3/peacock-island-from-the.jpg), which very strongly shows that the underlying strata of the area rises up and to the left as you go out to sea. Or the white cliffs of Dover, or the maintains I remember from my own childhood, the cliffs of Albania, across the sea from where we lived in Corfu. Solid lines ran across them at an angle for miles and miles, linking the mountains together in a way that conveyed immense time, geological form, tectonic force, and all the sorts of things you don't get in a randomly generated and eroded world. Unfortunately I can't find any good pics, though this one http://www.summitpost.org/images/original/224424.jpg suggests that trees also follow the geology (left of the picture), possibly growing better over layers of more porous rock.
This is why naive fractal terrain generation and erosion never appeals to me - it just treats terrain as a heap of sand, and then widdles on it to make eroded terrain. It's just not believable without the underlying geology.
I know very little about the geology of discworld, simply because it hasn't been specified much, other than treacle mining and the hub. My suspicion is that the strata would be angling up to a point at the Discworld's hub. It would just make no sense to me to have crosswise strata on the hub. What would it have eroded from?
So I envision it as originally being like the surface of a paint-splash or milk droplet: rising to a point in the centre, spreading out with some rippling but basically flat, then a bit ragged at the edges. Then over time, stuff gets deviated by the stresses imposed by the rotation and changing pressures from moving from elephant-back to elephant-back for countless thousands of years: this can be either fractally generated or added as noise.
However, there is another possibility which would be possibly interesting: the Strata could be aligned like tree rings, around the Disc. But I feel would show itself more on the world map if it were the case.
And then of course, there are the vitae-liths.
Cliffs and mountain ranges
The problem with 10km pixels is that a 1km high range of mountains is a 0% gradient, and a 100m tall cliff across the whole pixel is just a 1% gradient. And neither is considered as significant for route-mapping as a gentle 2% (1:50) sloping plain.
Fractal generation is also very bad at generating such features anyway. Fractals are meant to be "self-similar", so having step changes isn't what they're about. And I can't think of any reasonable way to generate them. Sure, I can do cliffy coastlines easy enough just by specialcasing them to not pay attention to the height of stuff to the seaward side, and instead generate themselves fractally from "virtual" terrain that has "eroded into the sea" instead.
But on land, it's harder. Around the hub, cliffs will just happen, that's a given from the fact that you have a huge heightmap and massive variance going on.
But elsewhere I think they could be randomly generated depending on the strata angle. In fact, fractals with strata-sensitivity could generate believable cliffs. But even then they would need to be recorded as linear entities particularly if they were zone-crossing.
Then, when pathing linear entities, the "cost" for each potential path in a zone needs to be calculated. For a river, the cost (in the direction of flow) would be the maximum vertical distance it needed to travel from the start point to the end point, taking the lowest possible route. So if the lowest possible route passed over a 1km-high mountain range, the cost would be 1000. If the lowest possible route took it down ten metres, and passed over no lumps, then the cost is -10.
For roads, which are unidirectional, the costs would be abs(distance * slope * height), so a 10km 1% slope that goes up (or down) 100m only has a cost of 10,000, but 100m vertical cliff (100% slope) with 10km of flat plain above and below it, has a cost of 1,000,000.
It's not just cliff-crossings that would have costs. For a road, there would be a "bridging" cost for going over a river, possibly equal to the river's size squared or something.
Since it's not possible to generate paths for every point on a zone's edge to every other point, instead I'd just generate paths from the centre of each zone to the middle of each edge, and each corner, and then use those for pathfinding in A*.
Rivers
I think the answer here is that once I have my initial map with the main arteries and coastlines, I fractally deviate those, and have new "river seeds" placed whenever the river or coastline attributes are suitable.
I couldn't do it the naive way, though, just generating a random 2D fractal tree from each seed and plonking it on the 3D surface and saying "these lines are rivers". Then the rivers would have no relation whatever to the terrain, and the trees would overlap. Instead I'd need to use the existing terrain as the starting point for the probabilities.
A few different points are important when generating these rivers.
1) I need to reduce the number of waterways that reach each zone, for economy.
2) Every zone with a terrain type that has non-zero annual rainfall needs to be reached by at least one waterway. In practice this means "every zone", even if in some zones it'll just be a dry riverbed.
3) Waterways are trees which do not have cross-linked branches (except for canals, which would be applied later).
4) Water cannot flow uphill.
5) Water cannot avoid flowing downhill (again, except for canal locks and dams).
6) For working out terrain passage cost, water is therefore monodirectional.
7) Population centres are significantly more likely to be water nodes, particularly root nodes (in English: you often find towns at the mouths of rivers, and at river junctions)
To me, these constraints scream "elevation-aware perfect maze generation algorithm", rather than "fractal". A simple maze generation algorithm that repeatedly places a link at the cheapest transit it can find to an linked zone should work, and should generate believable rivers that fit the above conditions.
Once the river lines have been generated, setting the size of the river is next. The size of the waterway on entering a zone will be the size of all waterways that feed into it. The size on exit will be that, plus the size of any other zone-crossing rivers that joined it during the zone, plus the average rainfall of the terrain type of the current square, minus an "evaporation" amount for really hot terrain types, and those where irrigation is used. This can easily be calculated with depth-first recursion. I could cull all zero-size rivers (would be common in deserts, for instance), but I like the "dry riverbed" idea - it gives an impression of history.
Roads and other branching networked manmade entities
This class of things includes roads (most importantly), power lines, canals, railroads, telecoms networks, and others.
1) I need to reduce the number of roads that reach each zone, for economy.
2) Zones do not necessarily have any roads.
3) But zones with significant population centres must all have roads. Exceptions (would be manually applied): deliberately isolationist communities, and those which are reachable only by air or water.
4) Roads are networks with a high degree of interlinking.
5) Roads can travel up any slope (with zigzagging/tunnels), if necessary, but tend to take the flattest route.
6) Roads tend to approximate the shortest route.
7) There are no "closed networks" - all road networks on a continent will be interconnected.
Ah yes. Other than the Romans, people don't tend to make straight roads. Things like population centres and history and terrain matter a lot. So road generation is likely to be iterative rather than one-pass.
See, if you have three towns in a line, A-B-C, you'll get a road running through all three. If you move B a little, the road will continue to run through it. But what happens as you move it farther and farther out of a straight line depends, I suspect, on the relative dimensions of the towns.
If B is a city, it will "pull" the road to it with a large gravity. If it's a hamlet, it'll have a low gravity. That's easy enough.
But at some point, that straight road will become two roads, A-B-C and A-B. Go even further, and one of the arms A-B or A-C will break.
However, that's not all. So far I've been assuming that nodes must be population centres, but that's not true. You could have a non-populated junction J between all three towns, and have three shorter roads, A-J, B-J, and C-J. The distance that J would lie from any town would be related to the gravitational pull from each of the three towns. And the existence of a route via J doesn't preclude the possibility of direct roads *as well*, so you could have A-J, B-J, C-J and also an A-B-C-A ring road.
When are roads made? When do they break? To start off, this looks like an impossibly difficult travelling-salesman problem and we should just pack our bags and go home.
Not so! Roads are made by humans, so we will be fine so long as our system kind of works. Here's my attempt at an algorithm.
For each population centre, identify the N nearest neighbours and lay a road to each. N is an arbitrary number that determines how long calculations will take, and how accurate the results will be. There's a rapid falloff of how important they are. One road per town would be stupidly small, but ten would probably be excessive for all but the largest cities: most villages have only a couple of roads passing through, which would be four roads leaving.
Then remove any closed networks: make a list of all roads. Pick a road, and work your way through the network, removing all connected roads from the list. Do the same for the next (remaining) road. Repeat, and you will have a list of roads which are members of the isolated groups. Link them all, in a ring or something. It doesn't matter that you are not linking the nearest parts of the closed networks: the next step will deal with that and make it realistic. But there are nicer ways you could do this, like make each link from one closed network to its neighbours come from a different city.
Give each road a "size" value, which is (sum of both endpoint populations using it)/(N * length). We're dividing by N since since if a town only has one road leading from it, then it will be more travelled than if it has two. We're dividing by length as the number of people on the road will (simplistically and ignoring rush hour, night time etc) be spread evenly out over its length. The "length" value of the road however, is equal to the terrain cost that it passes through, not its length in space. The size, then, is the number of people per unit "length" that would be on the road if you sent everyone walking out from a city along a random road.
Now each road has a "gravity" value, distributed as a rope with a mass (the "size" value) spread evenly over its length, which can be considered to be split into manageable sized "sections" with a mass applied in the centre and connected to each other by springs with a strength that is again dependant on size. Each city has a gravity value, which is its population, and is applied at a point in its centre.
Apply these gravities to road nodes. Where road sections merge, add them together. Any road which passes within a population centre's radius gets linked to that town and the town's N increases by 2, which has knock-on effects to all other roads it is connected to. Merge all road sections with an angle between them less than some critical angle like 15 degrees. Any road that stretches "long" enough for a new section to be inserted, does so. Repeat iteratively until the system becomes stable (so, no road merges were made for the last N loops), or you get bored iterating.
Possibly either give rivers attractive gravity, or make riverbanks have a low travel cost.
Towns
Other than the "seed towns", towns need to be randomly generated entities.
They should appear by crossings of linear entities. A bridge, a fork in a river, a road down a cliff, a river hitting the coast. The larger the "size" of the entities that cross, the larger the chance that there will be a town there, the larger the dice used to generate the population size of the result, and the larger the radius of the town. So you need to grow these iteratively, since a small hamlet at a road entering a mountain pass may, once placed, have a river fall within its boundary, which will increase the population and hence radius enough that it overlaps the farm at the nearby bridge, and then the village grows larger and now has enough gravity that it can pull a road node into itself, and so it grows, until it hits stability and can't grow further. This iterative process should probably be done at the same time as the above road one.
There should probably be a total population cap, possibly a total population density cap that can be supported by each terrain type or something.
Point-to-point non-branching man-made entities
This class of things includes pipelines, telegraphs, and so on.
1) I need to reduce the number that reach each zone, for economy. Since they tend to be straight, I only need to store a single vector per zone, unless they bend within the zone.
2) Zones do not necessarily have any pipelines.
3) Zones with significant population centres are significantly more likely to have roads. Exceptions (would be manually applied): technophobic communities.
4) They are generally networks with at least some interlinking for redundancy, though not always.
5) The mesh nodes are always population centres, but start points can be resources (an oilfield, treaclemine, etc).
6) They can travel up any slope, if necessary, but many (pipes in particular) tend to take the flattest route.
7) They tend to approximate the shortest route.
Manmade linearities are easier, I think, since instead of being trees, they can be defined as straight lines between points that are trying to find a route around terrain as best they can, and then (for some at least) fractally deviated. The more major the feature, the less the significance intermediary terrain and human population centres have in affecting the route.
Though I suspect, again, that there is a certain complexity to this. While telegraphs and pipelines may indeed be straight lines between points, they will tend to travel along parallel roads where possible, for ease of maintainance, particularly through inhospitable terrain. This could be done again by considering roads to have a "gravity".
I'd be very appreciative of any feedback on this, though I suspect most people seeing this thread will just say "tl;dr" 
Re: [MMO] Dynamically created terrain - request for ideas.
I 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
I've had some good feedback on this in various places.
On http://forum.TheGameCreators.com, draknir_ suggested not making it so big. But I don't think anyone, particularly myself, would be satisfied with anything less than a 1:1 representation of Discworld. Not if we know that it's possible.
At http://MMORPGMaker.vault.ign.com, hallsofvallhalla suggested Daggerfall might be a good place to start looking for ideas, but sadly, I don't think that's open source. I would hope that in the 12 years since it's been out, fractal terrain generation may have advanced a little, but maybe not, as some things are just impossible: 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 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.
At www.devmaster.net, Reedbeta and Wernaeh have decided I don't know what I'm talking about... which is sadly true, and why I'd love more feedback on this. They also were at pains to reassure me that single precision floats were plenty for doing physics even in relatively large sandboxes. Which is nice to hear.
www.Gamedev.net has been the most interesting, giving me good pointers to places like www.vterrain.org (nice selection or papers and utilities for terrain generation, storage, and display). Various people commented:
Fingers_ had some good ideas, strongly advocating Perlin noise seeded from the coordinates rather than random fractals seeded by a hash of the coordinates. This would mean that I could change pixel size and still get the same result. He also suggested randomly generating some of the info on the entities: this would reduce their size. Another suggestion was to reduce each zone to a population number and then generate random roads from that: however, this would not be deterministic, so would not work, that I can see.
SpeciesUnknown suggested making the algorithm variable in scale, rather than sticking to 10x10km squares. I've already prettymuch decided that this is what I'll do: high res in populated areas, low res in areas people never visit.
NineYearCycle had a load of good stuff, pointing me to http://ebruneton.free.fr/rama3/rama.html (jawdroppingly good 3D generated terrain), "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." He also strongly advocated offline pre-processing, which suggests I might be barking up the right tree with it.
Yet another geek.
Re: [MMO] Dynamically created terrain - request for ideas.
I want to start by saying im not in anyway a coder or programer. Just another gamer geek very much interested in DW.
Im still trying to decide what it is you are doing, I gather its either 1. creating the world from the ground up with intelligent design to include unnatural, but reasoned human-social necesisties. ie: Where 3 rivers meet an ocean there should be a city and that city should effect the terrain around the rivers so the terrain around the rivers is created WITH the effect of the city. All of which to be eventually used as a static world map.
or 2. Creating an outline of a world map overlapping a terrain grid where each tile generates its terrain based on the surrounding tiles to have a non-static map that is LOD with client side and server side rules to apply a limited amount of static effects for areas that wont be high population - ie outside and between main cities, limiting or eliminating the need for an INCREDIBLY LARGE static world map.
If its the 1st... all I have to say is wow - it reminds me of the concept behind the original Ford assembly line - raw ore goes in and somewhere further down a car comes out. Wouldnt all of the rules start with each main city and its location on the disc and branch out from there? Instead of Heres a mountain thats high enough to have snow and therefore rivers, and the slope of the plains around it force these rivers together to a delta near a larger source of water, and so a city should go here and now it effects the river and the plains back up to the mounatin with roads and technology and smaller settlements following the roads and water courses or lines between other cities?
Because either way once the location of the city is determined it then effects everything around it in reverse because the ultimate goal is an 'existing environment' rather than developing one.
Btw I believe fjords require a personal touch. Some other world creators might be upset if you tried to just let a algorithm model them.
Hopefully my thoughts dont waste any of your resources.
Re: [MMO] Dynamically created terrain - request for ideas.
I reason this would make the game HUGE (and big on proccessing power) and would mean there was always something new to discover? But seriosly, youre going to need a HUUUUGE amount of proccessing power to do this, and make sure it runs neatly and smoothly. Then again, if only "squares" visited are designed to a high level, this would cut down the power needed. I havent played the demo, but is it 1st or 3rd person, because 3rd person usually works better in mmo's (especially with combat!!!).
Just ramblings really
Hexon
+++MelonMelonMelon+++
+++Ah, the nostalgia of using the +++'s+++
Re: [MMO] Dynamically created terrain - request for ideas.
Fithean: Um, bit of both? The idea is to make, piecemeal, the high res map, serverside. Storing the map at 1m resolution would take (8*10^14squares * N-bytes-per-square) bytes. Several petabytes, then. So it cannot all be stored, not for the foreseeable future.
What we can do is compress it. So instead of storing every square metre, we make a larger square of some size or other, and store just the corner points, and all points where something enters or exits the square. How big's the square? Doesn't matter, but a few metres at least. We then send just those squares to the client, and the client recreates the high-res, every-square-metre map of the world by interpolating the corner points. The client doesn't need to know anything about any adjacent squares, just the current square it's generating.
Hexon: Serverside, it's a single lookup whenever someone enters a new zone. That's incredibly cheap in terms of both CPU and hard drive activity. If I want the server to enforce things like the unwalkability of steep slopes, and water currents, then it gets harder, but it's still pretty tiny. Personally, I reckon in a social, user-created-content world, where everyone's view of reality differs by design, I don't care if the client is trustworthy or not: making themselves a broomstick to get past steep slopes, and over rivers, would be easier than hacking the client anyway. So the server can happily just treat outdoors areas as 2-D, and ignore terrain type and linear features.
Clientside, I think terrain generation can be optimised pretty thoroughly: the algorithms to create noise are cheap, and A* for finding a path between a river entrypoint and an exitpoint is also cheap. The client will be given everything it needs to quickly generate the square.
The thing that will be expensive is bandwidth. The more terrain types and possible object types that are created, the more texture types and stuff that are applied, the more data will need to be sent over the net. Now, sure, it'll all be cached, so after seeing your first cabbage, you don't need to be sent another cabbage model or cabbage texture, all the way to Ankh Morpok. But scarecrows, cabbage white butterflies, fences, carts, ploughs, cabbage-sheds, farmers, mattocks, hoes, pitchforks, horses, ... these all will need to be sent to you the first time you see them (the hoes should perhaps be sent to subscribers only).
The controls are togglable 1st/3rd person, though I am unhappy with the 3rd person camera at the moment.
Yet another geek.
Re: [MMO] Dynamically created terrain - request for ideas.
I am not really a friend of having such a huge area. It would take years to find another user and computer generated content isn't that interesting. Sahara desert is also much huger than Las Vegas , but I assume there is more to discover in Las Vegas. What about starting with a part of Ankh-Morpork and enhance the area with the increasing number of users.
Re: [MMO] Dynamically created terrain - request for ideas.
The size of the Discworld is fixed: it's 10,000 miles across and I can't tell it to be any other size because it wouldn't listen to me. (Actually, if I were to assume that that's just the nearest power of 10, I could get away with making it, say, 5k miles across. But that would only round the problem down to a quarter).
I definitely am starting with a part of AM: at the moment I have a single windowless, doorless room that will become a cellar. Finding other people in that room will hopefully not be too difficult.
A large world is definitely a hard problem, but at the same time, definitely has to be done. A "Discworld MMO" that's just a part of AM would be lying: it's not the Disc, it's just Ankh Morpork.
If you could create a world, would you be happy with just a city? I would not, cannot be happy doing less than I could. So the whole world needs making. Designing the system well in advance (years?) lets me plan for it.
I think the main problem people have with huge worlds is that they are, as you said, huge. They have a hard time finding other people. If someone made just "a part of London" as an MMO, and put people who arrived into it at random, then finding eachother would be near-impossible. Even some shooter (Quake/Doom) levels have this problem: it's all running around and no finding eachother and shooting.
The answer is not "make the world tiny". The answer is to make it easier for people to find eachother, and to join eachother. World navigation and communication are areas where I feel OK to break with canon in order to make it easier, though I'd rather have a canon "story" to explain it (perhaps everyone has a Gooseberry dis-organiser that manages these things for them, sort of a TomTom/people-finder/teleporter?). As well as instant personal teleportation, people should of course be able to get about by boats, stagecoaches, horses, broomsticks, dolmens/menhirs, and so forth, as well as longshank's pony. They should be able to communicate by letter and by clacks as well as by Gooseberry. It will be an interesting challenge to encourage people to do these things the slow, hard, expensive way when even the poorest newbie can teleport to Dunmanifestin in a second. Personally though, I look forward to spending days just sailing down the Ankh.
People, being people, tend to clump where there is interesting stuff. Most of the world will be... not featureless, empty or repetitive, but definitely bland, samey, huge and devoid of company. The interesting bits will be where people have made changes, where they congregate. I imagine I'd start people off somewhere well known - the cellar, the Drum, the courtyard of the palace somewhere like that. That area would be where people would tend to hang out, once they were done exploring and wanted to share tales of their adventures, or just socialise. That needs to be really easy for them to do, so perhaps their start point would be added to the top of the list of their teleport destinations.
You avatar does not even need to be in the same physical location as someone else in order to socialise. While exploring the world, you could chat to others on "channels" - the explorer's channel, the french speaker's channel, and so on. And why not play games against eachother via disorganiser? Play Thud against a klatchian!
So yes, making socialisation easy is definitely critical to the game's success, but is not necessarily mutually exclusive with having a stupidly huge world.
And at 203,417,191,000,000 (2*1014) square metres, the Disc is huge, but not really impossibly vast. By comparison, earth is more than twice the size, at 510,072,000,000,000 (5.1*1014) sq m. I also emailled Larry Niven recently (and was told to speak to his agent - meh) asking whether he'd be interested in making the Ringworld. That's about ten million times bigger, at 1,552,000,000,000,000,000,000 (1.5*1021) square metres. However, a Ringworld would have some advantages in terms of fractal creation: I think you'd expect the terrain to be fractally generated by the Ringworld engineers, so any scale invariance and tiling would look less weird to the mind. The disc, though, is meant to have every inch handcrafted by the gods, if I remember right? So needs to look a lot more "natural".
Yet another geek.
Re: [MMO] Dynamically created terrain - request for ideas.
Many years ago now, in the 90's, I went on holiday to Benidorm. Miserable town, but very dramatic geology. It was the last holiday I've had.
So I Googled for some pics of that to show the kind of thing I'd love to see being generated, and why I think that geology-aware terrain generation is definitely the way to go.
The following algorithm should allow all three of those to be created: "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 steeper than X degrees?), 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".
These pics were posted to TripAdvisor by their user Harley321 and are most likely copyright to one or the other of them. I use them here under the fair use statutes, but will remove if asked.
Yet another geek.
Re: [MMO] Dynamically created terrain - request for ideas.
[from a discussion on geologyrocks.co.uk]
To begin with (and probably forever) I don't intend to make a perfect geological model of the Discworld. I just want to fake it enough that people won't wince, and will, in some places, go "ooh... that's a nice touch." Like Slartibartfast, I'm engineering a world. If I can't get fjords, I will be irked.
Stream beds: I was planning to have the rivers flow in the most linear fashion, which is "correct" for steep slopes for not for, say, the Amazon basin, or places like it. So I'll have to give it a certain amount of randomness to the river path, enough that on a reasonable hill it would not affect it, but on essentially flat terrain the path would be close to random. This would give me the illusion of consequent and insequent rivers, which should, I hope, be enough to be convincing. Maybe even a system to generate oxbows in places where the land is very flat & softish.
Sediment at river mouths: This could be a tricky one. I was planning on purely dendritic rivers, because that's just the easiest to generate. But in deltas, it would be nice to have the path split around sediment banks and stuff. Islands in larger rivers would be nice too.
Scree/talus: I have systems designed for both coastal and inland "cliffs" (significant linear deformations in ground height, might affect the level of the underlying strata if they're caused by faulting, but not if they're caused by erosion). I can just add a rule that X% of the cliff height be diagonal.
Topples: these would have to be separate items, rather than just deformations of the terrain mesh, so would be placed at a later stage. Item placement is based partly on terrain type, so I can just increase the "large rock slab" chance near cliffs, I guess.
Glacial stuff: sounds difficult to engineer, and probably not relevant to the Discworld.
Dunes: I think I'll cheat with this and have any dunes be static. Still a challenge to generate them the right shape, though. I just spent an hour or so pootling about North Africa in Google Earth, and while they look fractal, it's a directed, meaningful kind of fractal. There are aeolean shapes the size of whole countries there, and I just don't see any way to generate those without very heavy cheating. So I'll just go for the smaller dunes, because people can't see larger features anyway, they're too big.
Volcanism: I kind of feel that volcanoes would be rare enough I could hand place them, so they needn't be generated automagically. Molten treacle volcanoes are an amusing enough idea that I would like to make at least one, though.
I'd think treacle beds under compression would experience diapirism, like a salt dome but faster. Eventually you'd get a sticky, tasty equivalent to a mud volcano when one breached the surface.
Rock types: Igneous, metamorphic and sedimentary rock definitely exists on the Disc because there are trolls named after it. But I don't think I need to model how the rock's created.
Karst, badlands, coral reefs/atolls, unconformities: No idea how to do any of these. Not sure their lack would be jarring to people, either, but if there are easy ways to fake 'em, they'd be "nice touches".
Caves: I think these would count as items too, placed after the terrain generation, and made more likely depending on terrain type (karst would have a high chance: swamp would have none).
Coastal erosion: got some vague ideas how to do these: for coastal cliffs, define a fractal coastline, then generate land that ignores the coastline, then slice a cliff at the coastline. Maybe.
Sandy/pebbly beaches: No idea how to do these, though if I'm luckier than I deserve, beaches below cliffs may fall naturally out of the scree/talus code, and beaches away from cliffs can just be a terrain type near where land meets sea. Ideally I'd have a system that makes headlands tend to be rockier, steeper, and less beachy than coves.
Flora and fauna: How are these affected by geology? I don't know, and don't know how to find out - searching for biogeology hasn't helped much either. But I remember looking across at the mountains of Albania in my childhood, and seeing a thin black line running all along the mountains that faced us. Through binoculars, this was clearly a line of vegetation, following some line of different rock under the earth - but what? More porus? Less? Clay? Chalk? I don't know!
Soil Erosion: I had intended to ignore this and just say "anything steeper than X degrees is bare rock". But http://en.wikipedia.org/wiki/Erosion_prediction gave me some nice simple equations for this stuff, so I might be able to get a bit more complex.
Yet another geek.