[QUOTE=BBeck1;1284267]You can do it any way you like. 
There are many ways to do it and collision detection is a pretty complex subject.
The most simple for walls and floor is when they are axis aligned and you just have an if-then statement that sets the location equal to that point any time they try to go past it. That doesn’t help with objects in that room or multiple rooms or different floor levels though.
Collision detection algorithms increase in complexity pretty rapidly and the more complex they are the more difficult they are to understand how they work and the more computer resources (like CPU time) they take to run, slowing down your game. So, you want to use the least expensive method you can get away with.
Probably the most simple is spherical collision. You create an invisible sphere around the objects. This can be as simple as a 3D point indicating their center and a float to represent their radius. Every frame you test the distances of their centers from one another. If their distance between their centers is greater than the sum of their radii, they cannot be intersecting/colliding. If the distance between the points is less than the sum of their radii, they are intersecting/colliding.
I usually write my code to “ask permission” to move from a collision routine each frame. The collision routine then decides if the requested movement would cause a collision and either grants or denies the movement. If it denies the movement, the object can’t make that movement (can’t go in that direction). There can be situations where things are moving so fast that the collision isn’t detected, and for that you have to evaluate the entire movement. For example, if you are moving at 10 meters per frame (extremely fast since that’s 600 meters per second at 60 frames), and the wall is even 1 meter thick (very thick), in a single frame you would likely start on one side of the wall and in a single frame already be on the other side of the wall with no collision/intersection. That’s kind of an extreme example, but with smaller objects moving very fast there might be less tolerance. For example, testing a 1 cm object against a 2 cm object when the movement rate is a just 5 cm per frame or 300 cm per second which is 0.3 meters per second.
So, what I’ve done in the past was ray casting where I treat the wall as a plane (in game math that’s just a vector normal and a position that represent a vector that points straight out of an infinite plane and the position of that plane). With ray casting, I can get a point where the collision occurs with that plane and detect whether the movement distance would pass through or not. In one example, I even calculated a reflection off the wall for the remainder of the movement so the overall distance remained the same with part traveling to the wall and the other part reflecting off the wall (for my 3D Pong Game project).
But at significantly slower speeds, you may not have to worry about over-shooting the collision. Try just the simple spherical method to get started. At walking speeds, you may not have any problem with ghosting straight through objects.
Obviously, you quickly notice that not all objects are sphere’s and a sphere that doesn’t match the shape of the object can cause collisions that don’t really make sense. One solution to that is to use a lot more spheres. For a humanoid, you might use 6 for each arm and 8 for each leg and so forth. For a cube, you might use 4 that you can fit in the cube or 5 to fill the center since otherwise you might have a big hole in the middle. This makes a lot more sense for bullets and arrows and trying to determine if they collide with an object and in the case of the humanoid what part of the object they collide with.
Doing all these collisions over and over again every frame will get super expensive real quick even with simple spherical collision. So, it may be helpful to use methods to cull out tests that are not needed. View Frustum Culling is one way to approach that problem. And I think it’s a good idea to have a master sphere for each object that envelopes the entire object no matter how much extra un-needed space there is. I would use this even with more complex methods, in fact, especially with more complex/expensive methods.
So, for a humanoid example where you want to detect collision with an arrow head being fired at the humanoid, I might have a single big master sphere for the humanoid and if the arrow head’s sphere isn’t in collision with it, then there’s no point in doing any other tests. One quick simple test and I know if further tests are needed. Still, if there is a collision that doesn’t mean there’s really a collision because it’s mostly empty space in that sphere; it just means I need to do further testing. Then I could have a sphere for each major body part like, arms, legs, head, torso. (These would probably have to be attached to an animated humanoid and animated along with the model which requires a good knowledge of skinned animation. But for non-skinned objects they could have a fixed position relative to the object.) Then I could test if the arrow head is in collision with that body part. Still, a single sphere is awfully big compared to a leg. So, a collision here just means I need to do further testing, not an actual collision. But it rules out collision with all the other body parts unless it’s in a spot where the sphere’s overlap. Or you could just go straight to having several small spheres for each body part and testing each of them.
After spheres comes Axis Aligned Bounding Boxes. This is really good for buildings and things that never move and can be aligned with the axis without people noticing. It’s somewhat more expensive than spheres, but it’s a lot cheaper than what comes next. This would allow you to stand on top of the box too and potentially use it as a floor or ceiling. You could probably build an entire multi-story building with these and have an elevator to get beween floors. I suppose one for each step could even in theory make stairs possible although you have to use more than one for the floor since you can’t easily poke holes through them.
For interiors, you could axis align them regardless of what direction the building “supposedly” faces if the exterior and interior are two different “levels” like with Skyrim for example. You zone into the interior and walls and such tend to be axis aligned regardless of which way the building faced on the exterior. Although, I think they use set pieces where one piece might be an entire half of a room, and I believe you could in theory rotate them in any direction. So, they may have not used AABB’s for that. But as long as things can’t be rotated and can remained aligned with the axes, this is a nice and cheap method for collision detection.
I spent at least an entire day banging my head against the wall trying to figure out why I couldn’t rotate my Axis Aligned Bounding Boxes when I first started out. lol By definition, they can’t be rotated because they must always be axis aligned. Rotating them will just resize them, not rotate them.
For boxes that can be oriented in any way, you need Oriented Bounding Boxes. How these work gets into some pretty complicated 3D vector math. But you can have a collision box that has any dimensions and is oriented in any direction. It can be rotated on all 3 axes. But it’s a lot of vector math and thus not cheap. You might use these for stairs as box can be angled upward between floors, and maybe another for the stair railing. Also for floors, walls, and buildings they don’t have to be axis aligned which allows you to make them face any direction.
After that there’s more complex methods all the way to testing whether individual triangles in a mesh are intersecting.
Here is the book on collision detection. The math in it is not for the math challenged or faint of heart, but it gives lots of coding examples that you can pretty much copy and paste. I greatly treasure this book.[/QUOTE]
Thanks Beck! I just finished my radius collision function, I’ll give it a try. Checking others options as well.
[QUOTE=john_connor;1284269]there are 2 ways to detect collisions:
– using the graphics card
– using the cpu
if you want to do very precise collision detection, for example checking each face of 2 models (lets say each has about 10k faces) for intersection, use your graphics card (shaders)
the simplest form of checking wheather 2 arbitrary models collide is using a “spherical collider” for each model:
– wrap the smallest sphere possible around each model (of course “virtually”) and check wheater both spheres collide
vec3 distance(AB) = position(B) - position(A)
float distance_sq = dot(distance, distance)
now you have the the distance (^2) between the center of A and B
you should know (determine it when loading) what vertex is furthest away from the center of the model
then sum up the sizes of each model:
float distance_min = radiusmax(A) + radiusmax(B)
// determine radiusmax(A) and radiusmax(A) when loading model A / B (if these are static meshes)
to avoid to calculate the square root (for the exact distance):
float distance_min_sq = distance_min * distance_min;
if (distance_sq > distance_min_sq)
… then A and B cannot possibly collide
if (distance_sq < distance_min_sq)
… then A and B could collide, but a more precise method (bounding box ? pyramid ? you know what …) would be helpful
collision avoidance:
if you have 2 movable objects (e.g. balls), and at least one of them can be controlled, you might want to know wheater both objects will colide next frame:
– increase the “radiusmax(A)” value by the speed(A) x frametime
– increase the “radiusmax(B)” value by the speed(B) x frametime
– check if those spheres collide as shown previously, if they collide / intersect, tell 1 object to start evading the other …
another thing is to detect collision between the camera and any model in your scene
you could use a kind of collision “grid”, a 2D bool array:
when loading the scene, create a bool [width] [height], and set all the values where the camera is allowed to go
then when you want to move your camera, check:
int x = cameraposition.x + desired_movement.x
int y = cameraposition.y + desired_movement.y
if (bool [y]) // if new position is allowed to go to …
… camera.move(desired_movement)[/QUOTE]
Thanks, I was looking for collision avoidance too, so no need to ask that question now 
Thanks for the links! I went with the Gamasutra one though.