Thread: Updated space game

I needed a method to easily reduce the working set of testable objects.

A super fast/easy check is to create a bounding sphere that encapsulates the move, from the desired_pos - current_pos vector, then just do a radius^2 check between the two objects you are doing a collision detection for. The move between frames will be small, and this test actually tends to require fewer calculations than traversing a bsp/quad/octree to find the leaf that something resides in. After that, if you choose, you can dot these two vectors together, because there are cases where they may be inside this imaginary bounding sphere but the objects are moving away from each other (just test the sign of the dotproduct). No normalizing, don't need to traverse a partitioning tree.

As of right now in my little Hovercraft simulation this is how I 'cull' collisions between moving objects.

EDIT:
>>works quickly, and it works
Then it's a good implementation and I wouldn't dream of changing it!

Workable for a small scale loaded world, but when the loaded set of entities begins to reach into the thousands, and most of these objects (in my case) are in some way moving, then you're testing 1000 entities against 1000 entities (999 I suppose ). My entities track their own location in the Tree. This requires a slightly higher memory hit per entity, some initially difficult code, and an annoying cross-dependancy between entities and the Tree, but the result is that the entity being checked can jump straight into the node that it resides in, check against the objects there, and be done with it quickly.

I do like the simplicity of your encapsulated move-sphere though, as I'm currently having a hell of a time debugging collision irregularities with my system. I think sometimes that a small frame time hit would be outweighed by code that is easy to write, maintain, and debug.

What type of tree are you using, dawn? Also, when you say 'keeping track of their location in the tree,' doesn't this require a bit of calculations (plane traversals)? For each node in your tree, do you also store the parent node such that you can traverse up the tree? The way you described it that is what it seems you are doing.

The engine can handle Quad Trees or Oct Trees. I'm using Oct Trees due to the 3D nature of the space. And yes, each node (CDynamicTreeNode) contains data in this form:

Code:

	CDynamicTreeNode * pStem;
	CDynamicTreeNode * pBranch[EM_TREE_BRANCHES];

	CSafeList<CEntity *> slEntityList;
	unsigned int ParentID;

So a jump into any location in the Tree will allow the caller to start traversing to anywhere else in the tree. Not the standard method I know, but it made sense in the context of my engine. Having never recieved any kind of formal education in programming, I tend to come up with some unorthodox solutions at times.

And how goes the frustum culling, Bubba?