Collision Avoidance

[MickeyB]

I have implemented the j3d.org collision avoidance routines in my app.  For some reason it is only pickiing up clossest objects and checking for collisions when I cross the cneter point (0,0,0) of my universe.  It then detects and somtimes shows possible collision iwht the avatar.  Any thoughts?

[MickeyB]

Further data...

My 'game' will consist of only boxes(QuadArray geom) the players box is followed by a camera.  

I have placed another cube out in space and use my own keyboard navigation to move the player around.  My collision detection detects my players cube constantly and never detects the other cube, even when passing thru it.

Any ideas? I want simple Box to Box avoidance so players can drive thru (or partially into) walls.   Driving thru each other is fine.

[Conzar]

I don't know if you have solved this problem or not but I'll respond.

What type of picker are you using?  A Ray might be the best thing to use here.

Games published by our own members! Check 'em out!

[Mithrandir]

The code uses a ray and a segment. The ray is used for the downwards pick to do the terrain following. The segment is used to do the "forwards" pick to know if you are about to run into something. This limits what is picked to only the closest object(s) so if the object is outside where you are now then it won't find it. From there, the code will run through all the picked objects and do a polygon by polygon check for the closest one to know the exact details of the "real" closest object (j3d sorts the pick by bounding box centre, not the intersecting polygon).

That said, we know there are some bugs in the code that have been causing us great frustrations. I think the problems are related to us not setting the forward picking segment in the right direction - probably an array multiplication bug somewhere. For example, while you are walking "forward" everything works fine, but if you walk "backwards" there are some oddities showing up. I'm expecting to start the debugging on that next week, as it is rather important for one of our current projects.

[Conzar]

Thats what I am doing too - got an example from j3d.org of the terrain following.  I am wondering if you really need the segment picker at all.  Because you are looking ahead 1 frame, your downward Ray picker should be able to detect a wall that you are about to run into (or anything for that matter).  

Things might  be getting messed up when doing both the forward detection and the downward detection.  

Well, thats just a thought.  You might have a really good reason for doing the forward detection as well.  

[Mithrandir]

You need the two picks to work correctly to do both collision detection and terrain following in the generalised case. There are certain optimisations you can make if you don't have to deal with just generalised geometry (I wrote the code initially for our VRML loader). For example, in a racing car game, you don't need any picking at all because you can run with a 2D height map that you do the lookups into for both terrain following and collision management. Where you have completely arbitrary geometry, that's when you need to do the full picking.  For the gaming situation, you can almost always make some sort of assumption to give you much better performance than the generalised method used in the j3d.org code.

The downwards picking is to know what the avatar position will be in the next frame and allowing you to adjust the height. That will do the first pick to know whether you have make a step or descent (eg walking down hill). If that works out OK, then you need to do the forward pick to know what may be in front of you to run into. For example, if you are moving at a fast rate, the movement may be faster than the width of the wall in front of you. Using just the down pick means that you would not run into anything because the avatar location would be on the other side of the wall. You need the forward pick to work out that the wall is in front of you.

[MickeyB]

So if my terrain will always be flat and say a "game level" has a pre-determined "map" of rectangluar walls, I could use a look-up map?   How would this be done and would it be faster than picking?

Here is a screenshot of what my game world will/should look like.  THe green cube is the player with the camera behind and up.  The blue cubes are opponent bots, they move around and collisions are irrelevant.  The gray long rectangle is a wall and will always be there on this level.  Right now I am use  a pick segment pointing forwards one frame.  Works pretty well, but if I approache at an angle and the corner of my players cube hits the wall before the pick segment, it enters the wall.  

http://www22.brinkster.com/mbowles/screenshot.htm

[Orangy Tang]

Rays are nice and all for generic tests, but more than a tad costly from what i've experienced. For something as specific as that screenshot, you could probably benifit from some form of grid based lookup or tree structure.

Tile-based is nice and easy (simply change your coords into tile indices and check the tile you're over/about to enter. Very fast, but means that your level geometry is limited in both resolution and variation.

If your terrain objects are static, then its time to wheel out the tried and tested bsp tree   Simplified to a 2d based tree, you can build the tree on level load or precompile it into the level file, then search though it to check if a given point is 'inside' or 'outside'. For best results you'll probably want a sealed level, but thats not really a major problem.

Should be plenty of papers etc. on 2d and 3d bsp's if you want more info. Bsp's have been around much longer than their much publiced use in the original Doom