Good evenin' all. So I gots this burnin question. How do you maintain the walkable-area data in a 3D map? And by that I mean, the state you would use to determine if a player is bumping into a wall, falling off a ledge, moving up a ramp, etc. My first thought would was, "well, if you have polygons that represent your map ANYWAY, why not just do intersection tests on them?" But then I remember how complex character models are, I can't go around checking every polygon on the model against a wall. Ok, so I maintain a bounding box/sphere/tube around my character, and check THAT against the walls. But what about parts of my map that have complex sculptures or plants, I don't want to check all of their polygons either. Ok, so I put a bounding box around them as well. So now I have some simple primitives in my map ( walls, floors ) and some bounding boxes ( characters, objects ) that I can do intersection tests on to determine if a collision would occur. But there are so MANY of these things in my map, do I really have to check ALL of them to see if my player is intersecting with them? Ok, so I implement an octree with my primitives and bounding boxes as leaves, so that I only have to check leaves that are in the lowest node( or nodes, if my player is in more than one ) of the tree with my player. This sounds reasonable to me so far. But what about GRAVITY? Does that mean I need to assume that my character is constantly falling, and hence every frame of physics I need to attempt to move downward ( and fail, if I intersect with the floor ) ? That is starting to sound nuts. So in addition to preparing the model/map graphics, and checking for collisions from player based or scripted motion, I need every single entity to attempt to fall through the floor on each physics iteration? Am I missing something that makes this easier? Or am I missing something that makes this even harder? Please feel free to share any wisdom you have about maintaining this data for collisions. Thanks much, Mike

Quote:Original post by Michael Kron
This sounds reasonable to me so far. But what about GRAVITY? Does that mean I need to assume that my character is constantly falling, and hence every frame of physics I need to attempt to move downward ( and fail, if I intersect with the floor ) ?

That is starting to sound nuts. So in addition to preparing the model/map graphics, and checking for collisions from player based or scripted motion, I need every single entity to attempt to fall through the floor on each physics iteration? Am I missing something that makes this easier? Or am I missing something that makes this even harder? Please feel free to share any wisdom you have about maintaining this data for collisions.

Thanks much,
Mike

Yes, you're right, however notice that your map is static, you dont need to apply gravity to it, "props" that are part of the map such as trees, plants and others do not need gravity applied to them, in the case of grass, you dont even need to do collision detection against it.

Props the player could grab, and throw, like say a brick, do require the gravity applied to them, however, being that they're pretty static, you may just set them to a "no gravity" state once they hit something, because you know, they wont move anymore until the player picks them up.

OR, you could just do it the old Quake way, and have no gravity other than for the player and NPCs, items just rotate floating above the ground until someone walks over them... dont know if that would apply to your game.

Now, what I am doing is have the static map be a bunch of convex shapes (brushes on the Quake lingo), and I handle player movement by first checking the movement vector against all close shapes, adjusting it each time it gets a "hit" sliding if necesary, then, once I have the new position to move to, then I check for the gravity vector (in my case: 0,0,-980.0 which is 9.8 meters per second), this is because I dont want the player sliding because of gravity, only for movement.

I am thinking about adding support for convex shapes to ODE (shouldn't be that hard) and then use ODE to handle physics for anything NOT being a game character or static map brush.

Hey Kwizatz,

What's the deal with using convex shapes? Are they easier to detect collisions against? Does anyone have any good links to tutorials or papers describing algorithems for collisions with various mathematical shapes ( intersections of rectangles, spheres, etc? )

Mike

Quote:Original post by Michael Kron
What's the deal with using convex shapes? Are they easier to detect collisions against?

Yes, they're easier to deal with than concave shapes since you can make many asumptions, for example given a convex shape, you know a point lies inside the shape if the signed distance to each of the shape's faces is negative, this is not always true for a concave shape.

Quote:Original post by Michael Kron
Does anyone have any good links to tutorials or papers describing algorithems for collisions with various mathematical shapes ( intersections of rectangles, spheres, etc? )

There is a matrix table with all sort of tests between shapes, but I cant find the link, it points to the paper or book (mostly books) that explains the algorithm.

I found this on my bookmarks, its got some interesting information, hopefully someone can link to the table I am talking about.

In addition, most game math books should include the basic tests, I recomend Christer Ericson's book Real-Time Collision Detection.