I have no intention of writing a “serious” realtime physics system, but there will be a requirement in Subversion for some simple physics interactions. At the very least, people shouldn’t be able to walk through walls – that’s a physics interaction, albeit a simple one. People without ground under them (for whatever reason) should fall under the force of gravity. Sliding doors should jam if there is a bin blocking their way. So here’s a little bit of background on how this stuff works in games, for those that are interested.
A fundamental function of any physics / collision detection system is the Ray-Hit-Versus-Triangle function. This function performs the relatively simple job of calculating the intersection point between a ray in 3d space (a line), and a triangle in 3d space. This is extremely useful because everything you see in computer graphics is made up of triangles. So when I’m firing my ar15 carbine at the zombies in left4dead, the half-life engine is (almost certainly) doing a ray-hit-versus-triangle test, testing the line out of the barrel of my gun against the triangle mesh that is the zombie in front of me. When it detects a hit (and it will, because I’m an awesome shot), it can also calculate exactly where I’ve hit the zombie (the head), it can spawn blood particles, calculate damage, and do all that stuff you expect to happen.
The difficult part is the performance. Testing a ray against a single triangle is fairly quick, but as an example of the scale of the problem, the zombies in Left4Dead are probably around 10,000 triangles each – meaning 10,000 triangle intersect tests – but when you’re under attack from a horde of 50 of them, that could be 500,000 triangles to test against everytime someone fires their weapon!
So the trick is to limit the number of tests performed – ie to limit the number of triangles you test against. In the case of left4dead, the Zombie (almost certainly) has a bounding sphere – ie a sphere that completely contains every triangle that belongs to the zombie. When its testing my gunshot, it can first test against the zombie bounding sphere, which takes basically the same time as testing against a triangle. But if I’ve missed the target, it knows I’ve missed with just a single ray-sphere test, rather than a ray-triangle test against every triangle in the zombie shape. And this is how I can fire my weapon into a crowd of raging zombies, and it can reject most of the zombies very quickly with a single ray-sphere test, only doing the accurate triangle-hit test on a couple of zombies, and thereby maintaining my smooth framerate.
So as I was saying, I’ve been having a lot of fun in Subversion recently. The procedural generation system that underpins the world of Subversion generates the triangle mesh for the world as its final stage – ready for rendering. All I had to do was ray-hit versus all those triangles, and I very quickly had an accurate ray-hit function for the world. It was predictably far too slow because I was testing against every single triangle, so I made some serious optimisations and got it a couple of orders of magnitude faster. The generated data in Subversion is naturally hierarchical – you have a bounding box around a single building, which is internally subdivided into floors, then each of those floors is subdivided into rooms and areas. Each bit of geometry is completely contained within its parent in the hierarchy – a Floor in a building is completely contained within the building shape itself. So when I’m doing a ray-hit against a building, I can test once against the outer simple shape – and reject the entire building’s triangle mesh if that doesn’t hit. If I do detect a hit, I can recurse into the building and do more tests against each floor, quickly rejecting most of them.
Once you have working ray-hit, you can do collision detection. A ball bouncing down a staircase can do ray-hit tests against the geometry around it, and accurately detect collisions with the walls, and determine the bounce angles and forces. So I did all of that, spawned some particles, and applied some gravity to them. It wasn’t long before I made a particle hose that fires bouncing balls, and I then spent literally an entire afternoon playing with it. You may think it’s not _that_ interesting, but this isn’t your game! The moment you first get the basic physics of a world working, that world takes a massive leap forwards in terms of realism and sense-of-place. The buildings in Subversion now respond to the physical forces on them, and objects in those buildings behave in a believable manner. It’s the first step to a proper game-physics system, but arguably the most fundamental. And it’s awesome fun to play around with. Here's a video of the action.
No pictures this week - sorry - bouncing balls don't look like anything in static images. Now's the time to install the Xvid codec if you haven't already done so!
(xvid codec required)
