"Feeler" for detecting collisions

This relates to something I posted here a while back but never finished due to other issues, but now I'm revisiting it.

I'm trying to have entities detect when they're about to collide with others. To do this, I'm using feeler volumes that extend along the entity's course and, should they collide, messages are sent letting the entity know about the impending collision.

I seem to be getting warnings at extreme and close range, however. This makes me wonder if entities are being swallowed up by the feeler volume. In other words, I make a cylinder of radius X, but if the collision victim has radius x/2 then it collides with the cylinder caps only, not with the intervening cylinder body.

Do the various collision tests check for cases where one object is inside another, or do they only trigger if objects intersect with the outer edges of the geometry? If not, and if I'm right that cylinders (I've tried boxes as well) are hollow as far as the intersection tests are concerned, is there any way to make a solid volume which does test for containment?

Or am I on the wrong track with this? A ray seems like the wrong approach because, unless I have several, they won't prevent side-swipes, and that doesn't really solve for the "swallowing" phenomenan if the collider is too large and the collidee too small. A solid, non-physical volume seems like the best approach to me, but I may be missing something better.

Ah I was just about to do a similar thing :slight_smile:

There is some very good information here about steering:

Steering Behaviors For Autonomous Characters

For avoiding spherical obstacles:

Obstacle Avoidance steering behavior

For avoiding general obstacles:

Containment steering behavior

I wrote most of the following reply, then looked back at your question and realised I had answered slightly the wrong question, but I thought I’d leave it all in for the hell of it. If I (now) read the question right, you have multiple spherical entities buzzing about trying to avoid each other? If so, you need unaligned collision avoidance: http://www.red3d.com/cwr/steer/Unaligned.html. The main part of this is being able to calculate the closest approach of two moving points, which you can then use to detect a possible collision, then steer away from the collision point. There is some code already in the aircarrier CVS (net.java.dev.aircarrier.tracks.ClosestPointOfApproach) for calculating closest approach of lines, segments and tracks, which is what you need for the moving avoidance thing (in my case, stopping AI planes crashing into each other). (I was thinking this might be useful for jME, unless it is already in there somewhere and I’ve missed it :slight_smile: A natural place to put it would probably be com.jme.math.Line, although the code actually treats Lines as sometimes being segments or tracks, depending on which method you are using, which could be changed if jME gets a Segment or Track interface). The closest approach code is pretty much complete with tests (the method you want is timeOfTrackClosestApproach()), but you would need to add the avoidance logic itself, which is quite simple. You can either wait for me to do it, or do it yourself. It shouldn’t be hard, and it might be a while until I get around to it :slight_smile:

In the case of avoiding static spheres, you can use a purely geometrical approach, which solves all the problems like being contained within, etc. You can read up on this on the pages, but basically you just need to convert the sphere centers into the local coordinate space of the entity, and then it is very simple to check if a sphere will collide (since it looks like a circle in the entity’s up/sideways plane, so you can just work out its distance from the origin compared to the radius of the entity and the obstacle). You could use the non-aligned stuff, but basically it would work out the same and be more expensive to calculate (I think).

When avoiding general static geometry, the approach on that page is to use simple rays as feelers. So you just fire out rays from your entity center, either in a fixed pattern or a random one. I was thinking you could also use rays starting inside your entity’s collision bounds, rather than exactly on the center, if you are worried about sideswiping. The jme ray tracing should be fine for this. Depending on what you are ray tracing (geometry or bounds) you may or may not allow for the case of the entity being inside whatever it is colliding with. Thinking about sideswiping again - you need to make sure you trace in such a way that you detect obstacles that are within your “steering range” - there is no point looking for obstacles next to you that are at a great enough angle that you can’t steer into them any more, even if you want to, similarly to why there is no point in tracing behind you.

I’ve actually implemented some code for steering behaviours at http://aircarrier.dev.java.net/, in the AI package. So far there is code for following a target, predicting a target for firing a “bullet” at it, maintaining range to target, and avoiding a terrain. The terrain avoidance uses a technique similar to that on the pages above, where it samples the terrain height at slightly randomised positions along the future track of the plane, then calculates whether the plane is capable of turning away from the terrain (along a circle) fast enough to avoid. When the radius of the turn required is approaching the maximum the plane is capable of, it starts turning away.

I’m going to have a look at doing some more general avoidance myself soon, specifically of static spherical objects, and of moving spherical entities.  I’ll do some avoidance of general shapes later using ray tracing, but at the moment my levels are mostly terrain and roughly spherical objects, so specific avoidance techniques for those shapes will work better.

Ah, similar problems, and I might be able to use some of the stuff on steering in the future, but that isn't quite what I'm aiming at here.

My game is an enhanced version of Asteroids. There are a number of spherical targets moving about, but they can't change course unless they bounce off something else. What I'm trying to do is a collision alert system wherein an alarm is sounded if an asteroid collision is iminant. At the moment with my cylindrical feeler model, I'm getting alerts at extreme range and close range occasionally, leading me to believe that I'm colliding with the cylinder end caps but not the cylinder walls themselves. So all this needs to do is note that a collision is impending. It doesn't need to avoid the collision at all.

Good old asteroids :slight_smile:

Well that's fine then, the code is all already there - all you do is make a Line for each asteroid, with the line origin at its current position and the line direction as its velocity (in units per second). Then for each pair of asteroids, call timeOfTrackClosestApproach() with the pair of Lines, and it will tell you when they will move closest (in seconds from current time). If that time is positive, the asteroids are moving together instead of apart. So use distanceBetweenTracksSquared() with the two Lines and the time you just got, and it will tell you the closest they will pass (squared). Compare that to the sum of the squares of the asteroid diameters, and if it is lower, the asteroids will collide. You can use non-squared distances, but it will be a little slower from the square root involved.

The collision will be "exact" in that it will never miss a collision between two spheres moving with constant velocity, no matter how long your frame times, and it doesn't care if the asteroids are inside each other, next to each other, etc. The only thing it doesn't do is calculate the exact time the asteroids first touch, but that could be worked out with a little more effort.

The process above is the first step in collision avoidance, since you need to detect the possibility of a future collision before you try to avoid it, but as you say you don't need to do the avoidance.

The entire code for handling collisions is actually also in my old puzzlebeans.sf.net code from when I started making a 2D shoot 'em up, but its obviously in 2D only, so you are better off with the aircarrier code plus a little bit more as described above.

Excellent! Just implemented this and it seems to work nicely. I like that it seems to work equally well with objects at rest and in motion, so my collision alert sounds both on direct collisions, and on collisions where courses converge. Thanks a bunch!

Cool, I'm glad it works. Let me know if you want a play tester, I like asteroids :slight_smile: I remember writing a version back on the Amiga in Blitz Basic 2, those were the days!