Multiwinia

[Chris]

I’ve been having a lot of fun with Subversion recently. I’m heavily into the Simulation task now, and I’ve been working on the supermarket sliding doors for a while. I started thinking ahead and decided it was time to implement some proper collision detection, so that the doors would crash into each other if pushed too hard, or would crash into their outer mountings if opened too far. Of course I then started thinking about situations such as placing a bin in-between the two sliding doors – the doors would push the bin inwards until it blocked both doors, at which point the doors would jam and then re-open. And before you know it, we’re into the deadly realm of realtime physics.

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)

[jelco]

Okay then, I think it's decided. We need to visit IV HQ during the meetup and challenge Chris to a game of L4D.

Other than that: ooh, ball bounce-athons. It's more and more starting to look like some sandbox world simulation game. Looking great.

Jelco

[Wasgood]

I am at a loss to explain what this game is. That is a good thing.
I'm still hoping we get to blow up the procedurally generated city.
Edit: Gotta be a building site simulator or something like that.

Last edited by Wasgood on Thu Jan 22, 2009 1:28 pm; edited 1 time in total

[Xocrates]

Wasgood wrote:

I am at a loss to explain what this game is.

What are you talking about? Chris just confirmed that Subversion is, in fact, Left 4 Dead.

Unless of course you're suggesting he's been spending his time playing L4D instead of working (more) on Subversion



PS: I think the IV folk are allowing Chris too much time out of the basement.

[Wasgood]

Or bedroom.

[blackpudding]

Can you render these in split screen cross eye 3d please? Bouncing balls and so forth always look WAY more impressive when they're really in 3d.

[vanarbulax]

Just downloaded and watched the video. That was actually quite fancy looking it does add a sense that this world is manipulatable instead of just imposing buildings. My favorite part was when the cubes were shot through the elevator and bounced back at an angle to the floor below. I also liked the cubes falling of he edges of the floors to the ground below, though presumably walls will be put in eventually.

Hopefully this physics system will mean we can actually do damage to the buildings themselves, messing with security systems and the like by destroying motors will be fun (if this is the type of espionage game, that's probably all in my head, that I dearly hope it will be) but it would be great to be able to destroy a few support pillars and watch the building topple.

[MaximusBrood]

Shiny. I can certainly see the fun in getting this to work properly
(oh, and here's a mirror to the video download, which was giving me only 20 KiB s^-1)

[johndrinkwater]

Oh my, that looks enjoyable enough already!

[Galo]

Man, that is sick chris, nice work!

[Phelanpt]

Bouncy!

At least now we know a bouncy-ball-cannon-in-office-building simulator would be fun.

[Weatherproof]

Holy crap that is unbelievable!! Thanks for the quick lesson on simplified in game physics too!!
The video looks amazing and Subversion has come a long way.

[Cooper42]

Office buildings.
Floor.
Staircases.
Physics.

I proclaim this the worlds largest virtual slinky playground.

[RagingLion]

Chris wrote:

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.

I think this is perhaps the most useful piece of info for updating impressions on what Subversion may be like. This seems to be the first guarantee that there will definitely be people walking about in this world - I don't think it can be taken to just be a figure of speech. The image of the guy lifted from Google Sketchup in the last post hinted at this but we couldn't be sure then.

We still don't know if we'll be playing as a person walking around, but I'll be very interested to see how Chris and Introversion implements people in these environments to see how realistic they'll try to make them graphically and in terms of their AI.

[VelvetFistIronGlove]

Quote:

In the case of left4dead, the Zombie (almost certainly) has a bounding sphere

It's not really relevant to the discussion, but Left 4 Dead uses a collection of bounding boxes for each zombie: one for the head, one or two for the torso, ones for upper arms and forearms, and thighs and calves, and hands and feet. The collision detection is done against these boxes (12 triangles per box, about 15 boxes, so only 180 ray/triangle tests per zombie), which gives much better performance than testing against the thousands of triangles in the models.