Collision Distance Question

Scripting Issues
1

I’m looking for an easy way to get the distance to a collision entry stored in a collision handler queue. The best explanation of what I want is the distances used to sort the entries when you call sortEntries() on the handler.

Here’s the reason I’m asking. I am working on a small game that uses squads of AI controlled drones that all move together. When things start shooting, I want to check collisions with a large collision sphere belonging to the squad before I bother checking collisions with spheres representing the 10-20 drones in the squad. If the shot doesn’t collide with the squad’s larger sphere, the shot won’t need to check for collision with the 10-20 drones.

To that end, I have the large collision spheres for the squads in a different part of the scene graph than the small spheres the drones use. Thus, I can traverse the part of the scene graph with the squads, without checking collision with the drones (and without having to change bitmasks when I use the same From collider to check collisions with drones later).

The problem is that I need all of the eventual drone collisions in one list, sorted by distance, so I can get the nearest one. If two squads are very near each other, I need to check the drones in both (two collision traversals) and find out what the closest collision out of all of them is.

Of course, I could just calculate all of the distances in my own code, but from my understanding a collision test with two spheres is just a distance check anyway, so if I go and recalculate the distances myself I’m pretty much doubling the labor.

That’s why I’d like to be able to either get the distance that was calculated in the collision detection, or somehow use that distance to sort all of the collision entries from all of the traversals I need to do.

Is this possible?

2

I just checked to make sure I can’t move all the entries into one handler and then sort them, but that doesn’t seem to be possible.

Right now the best solution I can see is to call sortEntries() after each traversal, store the nearest entry from each traversal, and then only compare the distances between those nearest entries.

3

The distance calculation from sortEntries() isn’t saved beyond that function call, but you can compute it again. For the record, it is computed thusly (for a particular CollisionEntry):

distance = entry.getSurfacePoint(entry.getFromNodePath()) - entry.getFrom().getCollisionOrigin()

Still, you may be over-complicating your design. If your goal is to reduce unneeded intersection tests, the collision traverser will already do exactly the optimization you describe, if all of the drones have some common ancestor node they are all directly or indirectly parented to. When the collision traverser visits that node, it will compare your collision object with that node’s bounding sphere. If it doesn’t intersect the bounding sphere, it won’t proceed further. If it does intersect the bounding sphere, it will proceed into the sphere and test against each of the drones.

David

4

The only problem I see with letting that optimization happen automatically is that I have a number of things I want to check collisions with the bounding sphere, using your term, that I don’t ever want to penetrate further.

I might be able to limit that with bitmasking though… how would I set a specific radius on the bounding sphere you’re referring to if the parent nodepath is empty?

5

Hmm, I’m sorry, I’m a bit confused as to what you’re describing.

Every node has a bounding volume, usually a sphere, which is computed automatically to fit around everything within the node itself and all of its children. As objects move around in the scene graph, the bounding volumes are automatically updated. These volumes are used to optimize several different kinds of traversals, including the cull traversal (for drawing) and the collision traversal.

If you want to specify a particular custom volume for a node, you can override the automatically-computed volume with NodePath.setBounds(BoundingSphere(…)). Actually, this isn’t a complete override, because you can’t make the bounding sphere smaller than the one that would enclose all of the node’s children, but you can make it larger.

But perhaps I’m misunderstanding your overall design anyway, and this isn’t useful to you.

David

6

I didn’t know the bounding volumes automatically sized themselves to encompass all children. I thought they only encompassed the node itself. If I’m understanding you correctly, by making all of the drones in a given squad children of a particular empty nodepath, that empty nodepath will automatically be given a bounding sphere that completely surrounds the drones, and updates every frame so even if the drones drift apart the bounding sphere will increase in size to compensate.

Furthermore, if I run a collision traversal that includes the empty nodepath parent, a collision check will be performed with the bounding sphere, and if no collision is detected, none of the empty nodepath’s children, meaning none of the drones, will have any collision checking performed on them during that traversal.

If this understanding is correct, then it’s a very big help.

I have been using a less convenient solution to do something very similar. I have a collision sphere I created myself for each squad, and I am not putting the drones in the same branch of the scene graph as the squad collision sphere, so that when I check for collisions with squad collision spheres, the drones aren’t considered. Then, when I want to collide with drones, I first collide with squad collision spheres, and for each squad collision sphere I get a hit on, I then traverse the scene graph branch where that squad’s drones are located.

There are times when I want to check collisions with squad collision spheres, but I don’t want to check collisions with drones. Specifically, this happens when squads are looking for other squads in range to be picked up as targets. When I think about it, this range checking might be better left to a distance calculation. I was using collision checking because a long time ago I asked if a sphere to sphere collision check or a distance calculation was faster, and you said the collision check is a bit faster because it is handled by C++ instead of python.

Now I have another question about that specific point, that a sphere to sphere collision is faster than a pythagorean theorem calculation in python. Would the collision check still be faster if instead of doing the full pythagorean theorem:

dist = math.sqrt( math.pow( pt2.x - pt1.x, 2 ) + math.pow( pt2.y - pt1.y, 2 ) + math.pow( pt2.z - pt1.z, 2))

I used a simplified formula that didn’t take a square root, and therefore left me with the distance squared.

dist = math.pow( pt2.x - pt1.x, 2 ) + math.pow( pt2.y - pt1.y, 2 ) + math.pow( pt2.z - pt1.z, 2)

My understanding right now is that the difference in speed of the collision check vs. the distance calculation in python is small enough as to be unimportant, but I’m still curious about this point.

7

I just discovered another problem. My intention was for the drones to move independently of one another, but if I have to parent them all to a nodepath, and that nodepath must closely approximate their average position, that’s going to be difficult.

Is it possible to make a nodepath ignore setPos calls made on its parent? Something like setCompass, but for position instead of rotation?

If it comes down to it, I can deal with the drones being moved as a group, but I’d rather avoid it.

8

Yes, this understanding is exactly correct.

Right, I’m unclear as the precise tradeoffs here; I suppose the only way to satisfy your curiosity fully would be to try both approaches and measure their speed. As you say, it’s probably not a big difference either way.

Not to worry. The transform applied to the common NodePath is not important. It doesn’t matter where the average position of the drones falls within the parent NodePath’s space, it doesn’t have to be near (0, 0, 0). The bounding sphere is centered around their average position regardless of the parent NodePath’s transform.

David

9

That is freaking fantastic. Thanks for the clarification, David.