Collision detection

One, quite old, approach is using portals. In short you (or rather some software) preprocesses the level data and split the level into convex areas.

The test is easy then: if all the faces of an area are facing the character, the charater is inside the area.

There are quite some ways of optimizing this test process (e.g., store the areas in an octree)

Read this to get an idea

Thanks for the reply! :D The article is quite interesting, I've just read it (and the one that follows) and it will surely help. However, this next question should be rather noob... How do you choose where to put the portals? In a BSP tree, my problem is where to put the first hyperplane, the rest would be easy since they are computed directly...

Btw, I have implemented an octree as you mentioned. However, it can only go up to 7 subdivisions of space. I understand that this is already a lot of data to work with, since it is not optimized yet, but I think that normal octrees go much deeper in recursion, am I right?

Thanks again!

Don't treat a room as a single object: treat each wall as an object instead.

As for trees, those are high-level optimizations - they're not strictly necessary and they usually don't affect the actual collision checks. Instead, they prevent unnecessary collision checks, at a certain cost.

EDIT: An octree divides it's space into 8 chunks, and each of these chunks is one level deep. If you divide all these chunks into 8 smaller chunks, your octree already contains 64 small chunks, but it's only 2 levels deep. Trees don't need to be deep to function properly - at some point, their performance will actually degrade.

You need to treat each wall as a seperate object (or triangle). Theres lots of shape-triangle sweep tests around. Then you try to collide your player with EVERY triangle/object (objects like tables and chairs etc could have bounding boxes to make it simpler). The idea is to find that closest collision and move your player as close to the point as possible.

Then you can think about culling, portals/octree/quadtree. I've no experience with portals so I can't comment but octree/quad trees can have varying depth per branch. Imagine you have one simple room, its huge but only has 4 walls, cfloor, ceeiling. It takes up alot of space but using a tree to cull that is pointless so using only one node would be fine. Then you might have a same sized room but with huge detail, looks of things to bump into. In that case high depth would be good.

When recursivly sub dividing nodes just set some stoppping conditions condition, Stop dividing this branch when depth > 5 or when volume < some value OR when the objects in the parent node are less that some value (if theres only say 6 quads in a node then it might be faster to check all 6 rather than check if your in/hit the node's volume and then check all faces in it.

I implemented this for my collision detection and culled faces with an octree

http://www.peroxide.dk/papers/collision/collision.pdf

Thanks for your replies! I will try to put every wall in its distinct object and perform collision with that method. I thought about that in the beginning, but I thought there was a better way... xD

Is that the method used by companies who develop commercial games? I mean, everything that is scenario (except terrain) will have each triangle tested individually?

Thanks again! :D

Quote:

Original post by Sagito Thanks for your replies! I will try to put every wall in its distinct object and perform collision with that method. I thought about that in the beginning, but I thought there was a better way... xD Is that the method used by companies who develop commercial games? I mean, everything that is scenario (except terrain) will have each triangle tested individually? Thanks again! :D

You wouldn't be testing each triangle, you'd be testing whatever proxy shape you decided on for the object (probably an AABB or sphere). You very rarely use the actual mesh data for collision.