Ground simulation

I was thinking of this recently myself. Here's what I'm thinking:

You'll want to have your "base" mesh into which the player is digging (I'm assuming you mean 3D). You'll then want to apply these "digging" changes to the mesh as a kind of postscript, afterthought when you load the mesh.

Depending on the size of the world, and the sort of digging you want the player to do, I see two primary methods.

The first is to create a giant uniform grid. As the player digs, the grid square suddenly becomes "empty", and thus a hole is formed. The benefits of this is that it's very easy for the player to create regularly sized tunnels (if you're after tunnels). A negative consequence is that digging has to be done discretely, which means you're going to end up with a very smooth terrain filled with very square holes. Although I imagine there are ways you could smooth this out, it'll probably always be apparent to the player that the ground is divided into grid squares.

The other method is to use planar boundaries for the ground. As the player digs, you'd just add another few planes the your terrain mesh. For instance:

---------------------- becomes_   ____________________ \_ \_                     \_ \____________     \_____________/

This obviously is going to make collision detection and response with your terrain much more difficult than a simple relatively planar terrain mesh. It does make changing your terrain mesh (digging) rather natural. You just add some extra boundary planes. Creating regularly sized tunnels (if that's your goal) that the player won't get stuck in is going to take a modicum of work. There'd be nothing worse than digging a tunnel, digging it too small, and getting stuck in the ground. Or worse, falling through the world as the collision detection doesn't properly react and you get "squeezed" out beneath the world.

Either way, you're going to be changing the world from a static mesh to a moderately dynamic one, which is going to change the way you can optimize the mesh for display speed and view culling, etc.

I think I like the mesh idea. Have a digging object deform the mesh by "pushing" it. I would want for there to be some way for the excavated earth to persist though, so that it doesn't just vanish. This could make things a bit more complicated. Any ideas? I was thinking that if the mesh becamed pinched in an area that it would split the mesh into two seperate meshes. The seperated mesh could just act like a rigid-body rock, and when it is placed on the terrain it just makes a mound by raising the terrain mesh, and gets removed from the scene.

Also digging objects are going to be implicit, meaning that an object is just an object and if it pushes hard enough on the ground it should move some earth. What is a good way to decide if the earth should be affected or not. It could be done by dividing the force on the ground by the area at which it is applied, basically pressure (like N/m2) and have a threshold pressure. In this case though, say you had a particularly heavy object, and set it down on the terrain. If there was enough pressure, it would for ever sink into the ground. Maybe I should vary the threshold pressure with the inverse of the terrain height?

You should look into Portal Engines, they are well suited to tunnel-like map structures, and dynamic changes like extending the tunnel through digging. (all you'd need to do is extrude a new sector from a targted wall polygon)
You'll probably need a hybrid system to handle the normal terrain aboveground though.

I did a quick search on the portal engine. Unfortunately, I would not expect the walls of the tunnel to be cube like.

Another thing I just realized will be a point of concern. What about collapsing? It would probably not be necessary for most digging, but I would not want the user to be able to create an island of dirt suspended in the air. [smile]. This would be resolved using the mesh pinching idea to some extent. I would need to be able to determine if the pinched area is capable of supporting the weight... eek! It just keeps getting more complicated... should I forget about the collapsing issue? Or maybe exclude digging all together? The age old question: How do I decide where to trade realism for efficiency?

[Edited by - coder0xff on May 15, 2006 8:32:24 PM]

You will have to perform some sort of test every time a modification of your mesh occurrs to find if you have an "island" of excavated ground. However, even if an island is connected, if the connector is like a thin inch long piece you'd expect the rock "island" to collapse.

You might run some sort of test every time you modify the mesh to identify what parts of the terrain are under stress, and collapse them if they reach a certain threshold. You could make the equation fairly complex, since you can distribute the calculation over multiple cycles (the user's rock island can collapse 2 seconds later instead of 2 milliseconds, it's not going to matter too much).

As to compression, you can "weight" each face on your terrain with some sort of compression factor. Each time the terrain is compressed instead of just moved, the faces involved might increase their compression factor. This would make it harder for future compression to modify it. That would slow your sinking cube without resorting to strict altitude properties.

Numsgil > excellent ideas.

I was actually thinking of putting in some code for deformation and fracture of polyhedrons under exceptionaly forceful conditions. It may be feasible to use the same code for the terrain, since as you said, computation need not be per frame (boy that'll suck when you get trapped underground [grin]). The only concern I can think of now is the deformation of the mesh. When thinking of a shovel type apparatus, it cuts into the earth, pressing a ridge into the terrain mesh. I will have to put a bit of thought into this. Perhaps decomposition of the non-convex objects will help. Also the part about pinching a mesh into two meshes will be rather difficult for me. Any further suggestions are much appreciated. Thanx

Deformable terrain is quite a problem.

Many games use a regular heightmap grid mesh for much of their terrain.
A mesh like that cannot be changed more than pushing individual height points up or down (no overhangs). Transitions to some seperate 'tunnel' structure is hard to make seemless (its hard to make a 'hole' in the regular mesh and you now need exception cases in the collision/navmesh methods).

Even full mesh systems have complications (many have the data on the game CD and you would have to send 'mods' to patch the terrain data 'on the fly' for any changes made by players). You also might need a seamless transition (else its just a teleport point to your new 'tunnel' area) which many 'room' oriented engines dont do. Dynamicly growing meshes pose limitation problems (whats to keep players from growing the zone until it exceeds hardware limit...

The tunnels themselves arent that hard to auto create meshes for, but the complexities of physics for collapses and deformation on impact (etc..) are aspects of 'realism' missing from most games today (#$%^$% locked doors you cant batter down/pry open if you want to).


It can be done, it just requires a more generalized terrain system (eliminating many efficiencies of more restrictive (and currently used) systems.

Quote:

Original post by coder0xff I did a quick search on the portal engine. Unfortunately, I would not expect the walls of the tunnel to be cube like.

Who said anything about cubes?
The site you saw probably used cubes since they are a simple example for a tutorial, but you can actually get quite complex in a Portal Engine.

Doom3 for example was portal based, and so was the original Unreal.
An I'm pretty sure that Red Faction was too, Red Faction btw was famous for having deformable levels like what you wanted, you could blow holes in walls with rockets and stuff....

A friend of mine recently done such a thing.
Basically he used a kind of brute force way.
The terrain and the hole where both meshes and he used
CSG to subtruct the hole from the mesh.
If you have some sort if spatial partitioning that shouldn't be to much
cpu intensive..

Hope this helps.

I would recommend creating a voxel terrain engine. Something like this. There's a good demo of it here and they even released the full source to the engine.

Another interesting solution would be to use cellular automata. This would handle the "floating islands" very nicely. Haven't done anything like this myself, but it is another option. There's a nice article in GP Gems 3.

--
Kory

A Fairly impressive voxel terrain engine

There's a more impressive one... something like ieovohah but I can't find it on google today. He gave up on the project due to gainful employment at a very respectable company but it shows what you can do!