13 replies to this topic

[DewiMorgan]

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.

For example, I haven't given any thought to the fact that most MMO engines have a max zone size, which isn't just a "nobody will need more than 640k of memory" thing, but a real limit so that the physics can work within the dimensions of the area without maxing out the floats that the numbers are stored in when they square or multiply values.

[Reedbeta]

I think the limits on MMO zone size have much more to do with network bandwidth and limiting how many players/objects/whatever can be in a zone, so as to limit the processing power required to update it. I would be very surprised if it has to do with floating point precision.

FYI, single precision floating point supports exponents in a range of approximately +/- 127 - that means it can go up to 2^127 or down to 2^(-127), which is really an ENORMOUS range, so squaring and multiplying numbers really isn't likely to "max out" the exponent. What does happen is that precision is lost since only the most significant 24 bits of the number are kept. However, even then, if you want physics down to one millimeter you can still represent distances of over 16 km positive or negative, giving you a zone about 32km in diameter. I think that much bigger than your typical MMO zone, right? And that is without using any tricks to get around the precision barrier, like doing physics in a coordinate system centered on the player, or using fixed point arithmetic.

[DewiMorgan]

Enormous range, very low resolution. It's not the range of the exponent (8 bits) that's important for accuracy, or that gets maxed out, it's the precision of the mantissa ("significand" if you want to be picky). Since in a single precision float, that's only 24 bits ("16,777,215" when all 1s), you get about 7 decimal digits of precision.

A float could certainly cope with the *size* of the Discworld, but only to the nearest ten metres or so, since roughly seven significant figures is as much as the 24bit mantissa can deal with. Now, that ain't TOO bad, sure you'd drop stuff and it might land ten metres away, and you'd hit stuff and it might miss by that much, and collision detection would be unbearable, but it's almost reasonable. You could slice the world into chunks, a 100x100 grid, and you'd be OK to the nearest centimetre.

The trouble lies in squaring stuff, like in Pythagoras' equation, which requires that you square the X and Y numbers to find the distance.

For X*X to fit accurately in a 24bit mantissa X must be 12 bits or less: "4092" when all 1s.

Assuming you want to be able to move and measure things with an accuracy of one unit, that's 40 metres per zone. At 1cm per unit. About 130 ft.

You get similar problems when any numbers get big: high velocity, high torque, whatever you're using in your calculations: you lose precision, and once the precision drops below a unit or so, it starts getting noticeable. You should try to keep all your stuff within three orders of magnitude and avoid cubic maths like the plague.

Let's take a well-known expression: s=u*t+0.5*a*t*t

If you're measuring, say, milliseconds, then t could reasonably have a value of 4000 for something that's been moving four seconds. An acceleration of 9.8 units per millisecond will lose you your bottom significant figure, and your item will jitter by about 10cm as it travels.

At least, that's as I understand it, and as always, I'd be happy to be proven wrong :)

[Reedbeta]

Well okay, if you're trying to do something on the scale of the entire Discworld without using zones, then certainly that's bigger than a few tens of kilometers and so the argument I gave above would no longer apply. My post was intended to convey that it has nothing to do with the *range* of floating point numbers as your original post seemed to imply. You would need to use double precision to manage things on the scale of the Discworld, though you could still use single precision in local coordinate systems centered on different areas to do the majority of your physics.

[DewiMorgan]

Its not the "scale of the Discworld". 40 metres isn't "Discworld scale", it's "any-game scale". No game can avoid this problem with single precision floats.

Only something trivial like a pooltable sim can ignore it, since it'd only be dealing with low masses, velocities, and positions.

The problem can be reduced by reorienting the world every few metres to place the player at the origin (but this would really mess up most physics engines because it would give a huge linear velocity to all objects that were shifted); having physics only take effect nearby; using double precision floats for stuff farther away (but stuff like Ageia PhysX uses single precision internally, so you don't get that luxury); scaling stuff in Z so there's less distance than it looks would help (but this will break any maths applied to those areas); skyboxing the farthest stuff (also prevents maths being applied to those areas); just accepting that physics won't be terribly precise.

[Wernaeh]

Hey there !

You won't actually do

Quote

s=u*t+0.5*a*t*t

this for a t=4sec time slice....

Usually, you'd have

// externally applied, time-sampled acceleration, think player input here.
(I) a = a(t)
(II) v = v0 + a(t0) * deltat
(III) x = x0 + v0 * deltat + 0.5f * a(t0) * a(t0) * deltat

for a first- to second-order approximation (simple Euler integration, I'd guess, but there are more sophisticated schemes available, RK-integration, etc)

You won't actually use a single deltat from the start to the end (since in this case, you'd linearize a(t), which probably isn't what you want - this essentially always gives you a motion that will be straight). You'd rather iterate these equations on given x0, v0, then iterate as x0 = x, v0 = v, and start over with a new a(t).

Now for rounding errors (I won't do a fullblown error analysis, for that, have a look at any numerics primer text book), but there are several things to consider:
How large do you choose your deltat:
Too small => rounding errors have a more prominent influence on the result, since in the end, the values you add to x0 are small in regards to x0.
Too large => linearization errors of a(t) become noticeable, as well as a lack of physics updates.

Usually, for a video game you'd take a delta t somewhere between 1 / (30hz) and 1 / (100hz), which is somewhere between an update each 30 to 10 msec, so say, we have the physics locked at 20 msec for now (dynamic physics framerates are a topic on their own).

Say, the we'd have a world diameter of 5km, and the usual player speed is around 20 km/h (fast walking), this is around 5 m/sec. We'll now do a first order approximation of (III) above:

(III.2) x = x0 + v0 * deltat = 5000 m + 5 (m/sec) * 0.02 sec = 5000m + 0.1m = 5000.1m

Now, for the interesting part:

Say you have a normal float, with 24 bits of manitssa. Consider an exponent of 0: Then, your number has the format 0.bbbb...bb with 24 b's representing either a digital 1 or 0. All of these are equally spaced, and for all of these numbers: 0 < number < 1. You have a total of 2^24 numbers in this interval, so the number spacing (and thus the precision) is 1 / (2 ^ 24), which roughly evolves to (1 / 10000000), which is smaller than 0,0000001, which gives you at least 7 digits of precision. Thus your 5000.1 metres will suffer from roundoff at 5000.100x which is well in the millimetre range, and thus not really noticeable. For each factor of 10 you add to your world scale, the x will move out by a factor of 10 as well. So, for a 50 clicks world diamter, your errors still will be in the millimetre range. For "jumps" or ugly movement, you need to have discretization problems in the range of an entire centimetre to decimetre for human-sized worlds (dependent on the speed of an object, the faster it moves, the less you'll note errors)

The mathematician in you might now ask, how about error propagation -> the answer is simple: We don't care! Humans usually percieve the world in differential form: They see one frame, and another directly thereafter, and they'll see any large discretisation error jumps, but they won't notice that a tracer bullet is off from its initial course (see quake 2 for this: you can influence rounding errors by adjusting logics timesteps - this gives you a higher jumping range for certain physics framerates - but this doesn't influence feeled "robustness" for moving).

Larger worlds (~~planetsized, continents, etc) anyways need to have some sort of sectoring to keep everything organized, adding local coordinate systems and doing a simple IsSameSector() check before distance calculations is pretty straightforward.

Small-scale animations (skeletal animation, ragdolls, etc) should be carried out in local space anyways, and just recieve their forces from global space.

Finally, another thing, more on the implementation side: Always have roundoff errors in mind when programming. For collision, don't test against triangles, but blow them up to be rather voluminous, and spanning at least 3 or 4 of your discretization "cubes" at the maximum allowed distance to the origin.

Hope this helps,
Ask if you need any more elaborations,

Cheers,
- Wernaeh

[Reedbeta]

DewiMorgan said:

Its not the "scale of the Discworld". 40 metres isn't "Discworld scale", it's "any-game scale". No game can avoid this problem with single precision floats.

Only something trivial like a pooltable sim can ignore it, since it'd only be dealing with low masses, velocities, and positions.

That's an interesting position considering that MANY games do physics using single precision in worlds with tens or hundreds of meters scale and don't have any problems with it, nor do they need tricks like you suggested.

[Wernaeh]

I guess the main problem with this precision thing is not that its not there, but its more or less the point that it isn't noticed.

@Reed:
There are several points in his math that don't work out. I'm strongly in favour of the idea that he doesn't actually have all to much of an idea what he is talking about...

There are problems with mangling squared and non-squared units, but usually, they are _multiplied_ into either order of magnitude, which _doesn't_ create all to large roundoff errors ! It's addition and subtraction of differing magnitudes that is a problem - and only if the lost lower magnitude still is in the visible range for absolute errors.

Cheers,
- Wern

[DewiMorgan]

Wernaeh said:

I'm strongly in favour of the idea that he doesn't actually have all to much of an idea what he is talking about...

Oh definitely :) I'd be the first to admit it. It's why I'm asking for help - though I'm not asking for help on floats, that's just the thread drifting wildly, wildly offtopic on the strength of a throwaway comment I made.

From what people are saying here, it's less of a problem than I'd thought from reading the PhysX boards, where they strongly suggest keeping world sizes less than 4000 units.

I had assumed that this was because two numbers multiplied together at that range is 24 bits, which is the max precision. But maybe it's completely unrelated. And maybe they're talking out their asses. I don't know, I'm just a noob.

I suspect though, that they got that number by assuming that the world *cares* about the accuracy of the physics simulation.

In my case in particular, I can only use physics for cosmetic stuff (particles, fine control over the player controller, etc). Stuff that matters, I can't trust the client for anyway. So I don't care about local physics, really, so long as my player's camera doesn't start juddering badly or somesuch.

I still worry about things like having world objects fall through the mesh, but I guess that's something I'll deal with if it happens.

Still, whether 40 metres or 40 kilometres, I am going to have to slice it up, and finding nice ways to do it is one of the things I'm hoping for in the feedback to the original post [Which nobody has even mentioned here, and it's honestly way WAY more interesting than single precision floats! Really!]

[Wernaeh]

Heh well, no offense meant there, I'm sorry if this sounded kind-a hard.

A "true" overall physics simulation might have problems with large numbers, but most of these are tricky to get stable even for very limited-scale worlds. In most game cases, you won't actually use a fullblown physics system for everything by the way. You can usually get away by faking most - if not all - of it. For example, most games just have a constant acceleration on the player, rather than considering contact forces and impulse transfer between the player's feet and the ground.

And no, the 24 bits in the mantissa are not a problem really, you don't very easily have precision problems because of multiplication:
Say you multiply two numbers a * e^b , c * e^d, then the result will be (a * c) * e^(b + d) ... thus, you add up exponents, with a maximal exponent of 127 for floats, so there is lots of room left up to the maximum. Problems might arrise from the mantissa multiplication (a * c), but this is handled by performing the a*c multiplication in higher precision (the CPU automatically does that), and then renormalizing this to the valid mantissa range from 0.1 to 1.


A good idea I once tried out in a smaller system was sectoring the entire world into quads, each with a certain border length (around 2 km). Then, each object in my world carried two coordinate pairs: one integer pair (this may be x,y coordinates for a flat world) which gives the sector coordinates, and one floating point precision pair which gives the coordinates within each sector.

Distance calculation, pathfinding and so on all need to take sectors into account.

Sectors may dynamically be loaded and unloaded, which is done dependent on the distance to the players.

This is a strategy I assume is also used in some of the larger space simulators (Elite 3, both I-Wars, and so on)

Note dynamic loading / unloading also has its countersides: For example, you might unload mission-critical objects, and handling object destruction due to unloading isn't trivial either. For example, consider a scripted scene where the player has limited time to keep a base from being overrun by enemy forces. Obviously, this can't be simulated in real-time if the base sector has been unloaded, and the two simple options (mission fail on distance, or running a mission proxy timer) aren't too great either.

So, you need some strategy beyond player distance for deciding what objects to keep and which ones not. One of these strategies assigns each object with a "relevant" flag, if set, the object, and its surroundings, may never be unloaded. This, on the other side, still disrupts large scale pathfinding, and may create a huge memory load if the relevant objects are distributed badly enough.

Then, another thing remains to consider: Even if you have a really large world, will the player like this ? Or will he feel disoriented or lost ?

If you take Morrowind / Oblivion as an example, their world is pretty small actually in regards to border length, but it is filled with unnatural dense content. In reality, you can't just walk through a forest in five minutes, but it may take you several boring hours - so why the need for size here ?

"The party finally sees the weather elemental after a weeklong, tiring travel in the mountain range" -- this is a good plot point for a movie or a book, simply because they can shorten down the weeklong tiring travel to a single blend, showing the characters leaving the city, and then showing them atop the mountain.

In a computer game, you cannot provide the player with said travel - or he'll probably hate mountains for the rest of his life.

It is a game, after all, not a fantasy movie, and you won't ever get these to match up...

Just some points to consider :)
Cheers,
- Wernaeh

[Sol_HSA]

I've been thinking about huge procedurally generated world as well, and this thread is rather interesting.. =)

My approach would be to have a huge grid with nodes, and there's several fractal layers on the whole world, with parameters tuneable per node. Low-frequency, high-amplitude base plus higher-frequency, low-amplitude local modifications; vegetation thickness/seeds, whatnot.

In addition to this, there's a modifier stack per node for two reasons: first, the game designer can add human touches to the world, and second, if the player causes some changes (chops down tress, detonates a huge explosive, whatnot), these can be saved along with the player's other progress.

This would, as far as I can see, let the designer tune the world in pretty fine detail, while still keep the stored data set relatively small. Of course, if the player starts on a quest to chop down every single tree in the world, the save files will grow quite a bit =)

Whilst playing the game, a grid of 3x3 nodes around the player would be always kept in memory, plus a cache of N nodes on top of that - if the player moves slowly enough, the (re)generation of nodes can be easily done in the background.

The node border matching is one thing I do not have a perfect solution to so far, but I think it would be enough to simply calculate average of the border vertices of two or (in case of corners) four nodes. These edges are always so far away from the player that popping shouldn't be visible. Not a perfect solution, but hey, it's a game..

[DewiMorgan]

Wernaeh said:

I'm sorry if this sounded kind-a hard.

Well, I sounded kind-a dumb, so we're even :P

Quote

In most game cases, you won't actually use a fullblown physics system for everything by the way. You can usually get away by faking most - if not all - of it. For example, most games just have a constant acceleration on the player, rather than considering contact forces and impulse transfer between the player's feet and the ground.

Yup, been working on the player/camera controller and finding that it's a lot more complex than it looked. Stuff like gravity, auto-step, auto-stand, auto-duck, not straightening up if there's not enough space (tried raycasting to the ceiling, but that didn't always work, had to change to floating an invisible trigger box over a ducking player's head and testing for collision), etc.

Turns out players don't *like* to be subjected to real physics. If they aren't moving at full speed as soon as they hit forward, and stop dead when they let go, then the controls are "mushy". If you even smooth the camera movement too much, it's "mushy". Smoothing a little when they step, jump, or duck is just about acceptable, but that's it. Looks like a lot of FPS type games also either cap the velocity from gravity, or have a constant velocity gravity, and I can see the appeal of that, it prevents velocities getting too high, and mesh-tunnelling when you hit bottom.

Quote

performing the a*c multiplication in higher precision (the CPU automatically does that),

S'good to know :)

Quote

two coordinate pairs

Yep, sounds the smart thing to do. I think I might be going with variable-sized sectors, though, so I might have to specify the first coordinate as a location in a tree rather than x/y. Maybe both.

Quote

Distance calculation, pathfinding and so on all need to take sectors into account.

Hrm, good point, I hadn't put any thought into long-range pathfinding yet. I think it should be easy enough though, since the plan already calls for storing "terrain travel costs" for each terrain type, to work out where to lay roads - so I could pathfind to the terrain edge, then pathfind at a coarser level using those costs. And cheat, of course: I'm a big fan of cheating where it saves the CPU work, and doesn't affect fun.

Sectors may dynamically be loaded and unloaded, which is done dependent on the distance to the players.

This is a strategy I assume is also used in some of the larger space simulators (Elite 3, both I-Wars, and so on)

Quote

a "relevant" flag

This is similar to an idea from back in the days of MUDs where objects were responsible for their own garbage collection. Downside is, objects tend to be a bit lackadaisical about killing themselves, and since I want user created content, the idea's right out, since it would be trivial attack to just activate a whole mass of zones and bring the server to its knees.

So far as I can tell, the best solution seems to be "make your content not mind if its unloaded and paused". Just make it a limitation of the game.

But it shouldn't matter if the client unloads stuff. Because, the server will still know. And we don't want to trust the client about much anyway.

Actually, I intend to trust the client about a whole lot of stuff I oughtn't, and save my distrust for the really important things like secure trades between players, what's in their inventory, combat, etc. I don't really care if they walk through walls.

Quote

Then, another thing remains to consider: Even if you have a really large world, will the player like this ? Or will he feel disoriented or lost ?

Disoriented, alone, lost, and isolated. Also bored. Very, very bored. I can prettymuch guarantee it. Doing a world this size is a Really Bad Idea. Procedurally generated worlds are staggeringly bland and repetitive. As dull as ditchwater, only without all the interesting living things in.

Given that I know it will suck deeply at this size, why so big? Simply put, I know it is possible to create a 1:1 simulation of Discworld. Why would I be satisfied, then, to generate just a small slice of it? Nobody who played the game and who knew the Discworld would be satisfied to hear "yeah he's only implemented the area around Ankh Morpork". They'll want to check out the rimfall, Cori Celesti, Ephebe, Lancre, the counterweight continent... if I'm going to make it big enough that I need procedural generation (ie, big enough for an MMO) then I might as well make it full size.

It's also a matter of the license. I am more likely to get a license if I show I can do all of it than if I just show I can do a teensy slice of it.

You also suggest that it might be a fun game, possibly even that it *needs* to be fun. But how do you define "fun"? Fun is a complex topic, and different people find different things fun.

For explorers, huge areas are good. For socialisers, they are bad, they mean it's hard to find people to socialise with. Google Earth is "fun" for some people, but why?

The solution to the problem will, I suspect, be a combination of unnaturally dense content, cheap rapid travel, and very well-signposted "nexus" areas where people can be made to naturally congregate. These things would be needed even at the expense of gaming "realism" just to make it playable.

[DewiMorgan]

[quote name='Sol_HSA']My approach would be to have a huge grid with nodes, and there's several fractal layers on the whole world, with parameters tuneable per node. Low-frequency, high-amplitude base plus higher-frequency, low-amplitude local modifications; vegetation thickness/seeds, whatnot.[/quote]

Seems prettymuch what I'm planning: your "nodes" are my "zones", only difference is that I'd have the zones variable size, with smaller (more detailled) zones for the more heavily-travelled areas; your "Low-frequency, high-amplitude base" is my serverside heightmap which sets the basic shape and terrain types of the zone by defining the properties of the four corner points; your "higher-frequency, low-amplitude local modifications" are my clientside fractal interpolation between those points interpolated between.

[quote]In addition to this, there's a modifier stack per node for two reasons: first, the game designer can add human touches to the world, and second, if the player causes some changes (chops down tress, detonates a huge explosive, whatnot), these can be saved along with the player's other progress.[/quote]

Your "modifier stack" is my "entities", implemented a little differently. I had considered an object entity, so that players could leave objects and come back later and pick them up, but there are so any problems with that, that I thought I'd just let the objects disappear when the zone got unloaded. And players modifying the terrain, that's an interesting idea. But makes my head hurt with the possibilities. Like, one modification they could make to the terrain is build a house. Or a village. Ow ow ow...

The problem there of course is the huuuuge amount of data to store.

[quote]This would, as far as I can see, let the designer tune the world in pretty fine detail, while still keep the stored data set relatively small. Of course, if the player starts on a quest to chop down every single tree in the world, the save files will grow quite a bit =)[/quote]
Understatement :) Remember the lesson from Ultima Online. They unleashed the players into the world, and got desert. If chopping trees can be done, and can result in a profit, then once you let the players loose on your world, you will have no more trees.

In a 10x10km forest, that's a lot of trees. Even one every ten square metres, that's still 10,000,000 trees. Possibly the players couldn't chop them all down. 100 players, one a minute, would take more than two months to chop them all.

[quote]3x3 nodes around the player would be always kept in memory, plus a cache[/quote] 3x3+cache sounds good. Given my node sizes, though, I might possibly use 2x2, loading only the three closest to their current corner. Depends on the size of the zone they're in, I guess.

The node border matching is one thing I do not have a perfect solution to so far, but I think it would be enough to simply calculate average of the border vertices of two or (in case of corners) four nodes. These edges are always so far away from the player that popping shouldn't be visible. Not a perfect solution, but hey, it's a game..[/QUOTE]

Sounds like it'd work, but using "noise" to generate the terrain is better. Perlin noise, for example. Key it off the location, and the zones will match up, deterministically.

NineYearCycle over on GameDev.Net had this to say:
[quote]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.[/quote]

Which sounds like good advice to me.


There's a related issue, of terrain type borders. Normally you can only texture a mesh so many ways, I think. But if you have each terrain type as a separate mesh, you get rectangular areas. Someone on OpenMMORPG suggested a thing they call "Statics", which are areas of different terrain, which drop in height at their borders, so can be butted together to give a "jagged" edge instead of a straight one. Personally I'd rather a slower fade between terrain types, though this might be a good way to do roads without figuring out how to best deform the mesh to make them flat: have a separate mesh embedded into the land.

[Sol_HSA]

There's one big difference between our designs: my goal would be to make a single-player, client-only game, while yours is a multiplayer client/server thing.

DewiMorgan said:

Your "modifier stack" is my "entities", implemented a little differently. I had considered an object entity, so that players could leave objects and come back later and pick them up, but there are so any problems with that, that I thought I'd just let the objects disappear when the zone got unloaded. And players modifying the terrain, that's an interesting idea. But makes my head hurt with the possibilities. Like, one modification they could make to the terrain is build a house. Or a village. Ow ow ow...

The problem there of course is the huuuuge amount of data to store.

In a single-player scenario, these things would be quite possible. =) Plus, if the storyline in the game was made so that after each "chapter", time passes (like years), these could be used to prune the modifier stacks - grow some new trees, discard any items the player has dropped around the world etc..

Actually, you could do a simple algorithm based on the value of an object and where it's dropped to see if it should be discarded once it's away from the player's view. Drop a pile of rocks in a forest? It'll stay there. Drop a bag of coins in a city? ermm..

[node border matching]

DewiMorgan said:

Sounds like it'd work, but using "noise" to generate the terrain is better. Perlin noise, for example. Key it off the location, and the zones will match up, deterministically.

Everything would be generated by "noise" (multifractals most likely), but different layers of it, and since the designer can tune the parameters of local noise per node (mainly the random seed(s)), the node borders are never going to match automatically. I think this is a fair tradeoff considering the editing capabilities that are gained. The world will not be totally random and boring - it'll still be procedural, but the designer has at least SOME say in it.

edit: fixed typo