About destructible terrain

A while ago I returned to my roots, so to say. Started to work on my space game from the ground up (again). This time C# and OpenGL. Made a nice little framework for dynamically reloading running code, and all! This enabled me to quickly iterate on code, and allowed me to put some effort on destructible meshes, among other things. I even made this little video about the thing in action!

What you see here is a simple one-polygon shape, that is then repeatedly shot with a cannon, and each hit removes some of the material from the mesh. Late last year I made the initial version for this, using Clipper and LibTessDotNet to do the heavy lifting. Initial results were quite poor, as I directly fed all the hits to the cutting pipeline.

Then I made the discovery that I should only ever try to cut things if they are really hit. This way the tesselator doesn't generate extraneous polygons that quickly explode the computational requirements. But the performance still wasn't quite as good as I desired.

Today I optimized the those manual collision tests by using AABB tests before moving on to the more expensive tests, while also optimizing some allocations to only happen once. This lead to a close to an about 9x speedup. Even with the large amount of projectiles and hits visible here, the solution performs adequately and keeps a stable 144 Hz refresh rate.

Future performance optimizations include using even better collision detection algorithms. Currently there's no spatial acceleration apart from the AABB tests. By implementing one (or perhaps by interfacing with a physics engine), these collision detections can be accelerated by a large amount, I think. As seen on the timers, about 2/3 of the computation time is used for these collisions (the Cost includes CostCut). Another acceleration avenue is multi-threading. This doesn't really make sense here, but will in a full game where there are multiple independent more complex objects.

There's also fidelity improvements to be made. Of these I'm most excited about. But these might also turn out to be far too complex for me to have the motivation to implement them. The results aren't really that bad even now. Anyway. For simplicity of implementation, the collisions are initially computed as line segment collisions: instead of the full mesh of the projectile, only the simpler (and cheaper) 1d velocity vector is the hitbox (hence the edges might not always hit something). Once a hit of this is found, the full mesh is applied as the cutter on submeshes that that full mesh itersects with.

This is apparent in the diagram above. Projectile P₁ moves near the edge of the mesh, but as the central velocity vector doesn't touch the mesh, the collision is not detected. Neither would it be detected if the meshes of the projectile were checked, as it sweeps past the mesh in just one tick. Projectile P₂ on the other hand collides with the mesh. The would-be location is shown in red. As a collision is detected, the mesh is moved to the collision point, and then then mesh is cut.

The better collision mesh could be acquired via the Minkowski sum of the projectile mesh and its velocity vector, I think. Unfortunately the collision mesh is then a lot more complex (although the AABB checks help a lot on that, and maybe that spatial partioning system). The goal of this is of course to make sure that the fast-moving projectile that just barely touches the target mesh (P₁) is counted as colliding. But unfortunately, even this approach falls apart when the bodies are rotating. By my initial research at that point the only possibility is to simulate the rotations (and movement) on a smaller timescale. I haven't found a way to do it analytically. And even if there was a way, I'm quite sure that it would be very expensive, and out of the reach of my abilities. I hope I'd be wrong.

I initially thought that these destructible meshes would be reserved just for asteroids that the player can mine, but I'm also tempted to apply them to ships, too. But to make the system fair and predictable, that higher fidelity feels like a must-to-have feature. Player frustration is most likely immediate if projectiles tunnel through armor plates and damage the vital components that armor was supposed to be protecting. Future will tell how this develops. If it eved does. That's always a possibility when my projects are concerned.

No comments: