Pixelate:Issue 10/3D Concepts

From Allegro Wiki

Collision

Collision is probably one of the most important things in 3d games. I mean just look around at some 3d games collision is used for everything to see if your shooting someone in the arse, driving into a telegraph pole or whether your going to hit an asteroid in the next galaxy. You need collision!

All right so you need collision you know what you need it for. But wait before you put collision into your game stop and think will it really work. Tons of games out their have good collision some have really bad collision. I won't name the ones that have bad collision, as that will put their creators down, and they're working hard enough just to get their games out so we should congratulate them.

So how do you have good collision in a game well lets take a trip down memory lane and just how collision has been done. In the first old 2d games such as Biomenace and Commander Keen collision was done as a rectangle and if something was in that 'bounding box' then it was colliding. Then games got smarter they could test any polygon against another polygon.

All right that's 2d collision but what about 3d collision. Again the 'bounding box' idea of simply putting a rectangular prism around the object and testing that was and still is used in games today. Of course you can still do 2d collision in a 3d game just look at games such as Wolftenstein 3d(original dos version), Doom 1 and Duke Nukem 3D. They used a method where nothing is on top of each other so although things are drawn in 3d collision is simply tested on the x and y planes. Now this works great until you start moving up and down and all around like modern 3d games and then you need full 3d collision, such as the rectangular prism bounding box.

But its not incredibly accurate so what do you do. Well there is a solution; lets say you have a person in a 3d shooter. What you could do is instead of putting a 'bounding box' around the entire character put a 'bounding box' around each individual body part say a leg an arm, if you have bone animation you could but a 'bounding box' around each moving bone. And you can do it as detailed as you wish say around each part of the finger or something. Not only would this dramatically improve accuracy but you would also be able to do area-based damage. But this opens up other problems. What if you do animation per vertex in your game you must store 'bounding box' info, of course this isn't a problem if you use bone animation like most games do, so I'm sort of rambling here.

Now of course everyone knows you can't just use a 'bounding box' for everything. I mean you couldn't put 'bounding boxes' around parts of the level; you would have to be insane. Instead you would see if one of the levels triangles is inside the characters bounding box(s).

But there is another option instead of 'bounding boxes' you could also test every single triangle with every other triangle. Meaning. You test all you characters triangles to see if they are colliding with the level, other person or a bullet. No this is perfectly accurate but think about SPEED! This would slow the game down dramatically because now day's games want more detailed characters with more polygons then you could be doing millions of collision tests every frame and this isn't acceptable. In fact if you get a ten thousand-polygon model and collide it with another ten thousand-polygon model you do one hundred million collision tests. This is unacceptable, you can do every optimization possible for your collision tests but it simply won't work.

So we have examined different ways of how to do collision but it seems like no matter which one you pick you can't use it. That's because you need a mixture. This is a list of a good way of doing collision in different situations

• Character models - level: Collide character 'bounding box(s)' with level triangles.
• Character models - character models: Collide there 'bounding box(s)' together.
• Bullets - character models: Collide the bullet line with the models 'bounding box(s)'
• And so on. These don't tell you how you SHOULD do things just damn good general ways that you COULD do it.

There is also another problem you going to encounter in games and that's "what if the objects moving?" Well what in deed. So what do you do? Well you could use a massively complex formula and put time into the equation or you can simply use rays and test at many points along the move, obviously simple yet probably one of the better ways. It too has it's downfalls such as the object might be moving so fast that you miss where it collides and you go straight through something. Experiment to see what works and what doesn't; generally if you have the size of the object you can work out the number of times you need to test.

You see that it's not that hard. Generally you can get away with 'bounding box' collision but you MUST make sure you choose what's best for your game. There is just one last problem that must be mentioned. I said you should collide characters 'bounding box(s)' with level triangles, but your level has so many triangles that you can't do that. Well don't despair generally a level will be in an Octree or a BSP tree and you can use these to increase speed to acceptable levels, I might explain this concept in a future column.

I personally think that you could use perfect triangle collision sometimes but for most games 'bounding boxes' are fine around certain parts of objects or sometimes even the whole object. It depends on the game.

Lets face it even the most whiz bang game can suffer without good collision. The more accurate the collision the better and area damage is really cool. But speed is also necessary. Balancing these is probably one the hardest parts of writing a full-fledged 3d game but when done well the player will simply enjoy the game more because no one wants to able to shoot anywhere and hit something behind them. Do collision well and people will love your game even more.