   Collision Detection and Movement
  Hey guys,I've given this problem the old college try, but its solution continues to evade me, so I thought I'd see if someone here could help.Basically, I've set up a quasi-collision-detection system that checks to see if the player is inside a bounding circle, and if so, moves the player around the circle until it can move forward without entering the circle. I'm hoping I'll be able to integrate this code into some sort of path-finding for the AI later on.The problem is that right now the player can only go around one side of the circle, which causes obvious problems: say, if two objects are next to each other, the game may well take the longest path around the two. It's possible to change the direction (based on whether x is positive, say), but that causes problems of its own, because there's necessarily a point where the direction shifts from -1 to +1 and the player gets stuck.I've had some luck with the cross product (as suggested in a thread on these forums), but for some reason this introduces other problems where the collision detection utterly fails -- when trying to circle an object right in front of another object, for instance. It works well with a single object, but has the same "sticking" problem on the Z-axis.Here's the relevant code. vec[0] is the x-axis and vec[2] the z-axis. I'm not sure why they're reversed in the atan function, or the Target.set function, but it works so I'm just letting that be for now.void objList::collisionDetection(Object *Current, int Dir){Vector3 Radius;Vector3 Cross;Vector3 Target;float Angle;float FacingAngle = (Current->Rotate * (M_PI/180)) - (M_PI/2);int Collision = 0;Object *Obstacle = head;Target.set(sin(FacingAngle) * Dir, 0, cos(FacingAngle) * Dir);while (Obstacle != NULL){if (Obstacle != Current){Radius = Obstacle->Position - Current->Position;if (((Radius.vec[0] * Radius.vec[0]) + (Radius.vec[2] * Radius.vec[2])) < 9){Cross = Target.cross(Current->Position);if (Cross.vec[1] < 0) Dir = -Dir;Collision = 1;Angle = atan2(Radius.vec[0], Radius.vec[2]);  // the order here dictates movement direction  // -,+ moves left around circle; +,- moves rightCurrent->Position.vec[0] -= Dir * 0.1f * cos(Angle);Current->Position.vec[2] += Dir * 0.1f * sin(Angle);}}Obstacle = Obstacle->next;}if (!Collision)Current->Position += (Target * 0.2f);}And a screenshot for reference:http://img97.imageshack.us/img97/3323/screenshotgamecb4.pngAny suggestions would be appreciated. The pun about going around in circles is too obvious, but that's all I'm doing right now. If it needs a complete overhaul, let me know; I've considered looking into ellipses, and managing several close obstacles as a single obstacle, but I'd like to avoid adding unnecessary complexity.Apologies if this post is too long -- and thanks if you got this far ;)   
  Err, wait, what is this doing:Cross = Target.cross(Current->Position);It doesn't look right to me; a collision shouldn't depend on where the coordinate system is based! Are you sure you didn't mean Target.cross(Radius)? (I don't understand what this step is for, though – please enlighten me!)A couple of code tidiness points (minor): Radius would be better called deltaPosition, or Difference, or something like that (perhaps not ds as mine tend to be!), as radii are generally scalars; and it would be a nice addition to your Vector class to have a MagSquared method (then the check would simply be if(deltaPosition.magSquared < 9)).I don't quite understand what your correction code is trying to do; I would just move the object back along the intersection normal far enough for it to no longer be in collision, viz:if(Radius.magSquared < 9){ // a collision! // How far in collision are we? float depth = (3/Radius.magnitude) - 1; Current.Position -= depth * Radius; collision = true; break; // ? Did you mean to include one of these?}To explain depth: the distance of penetration is 3-Radius.magnitude (although at some point the constants 3 and 9 shouldn't be 'magic numbers'), thus we need to move back by the vector -(3-Radius.magnitude).(normalised radius) = -((3-Radius.magnitude)/Radius.magnitude)*Radius. To avoid the double calculation of the magnitude we can cancel it out: (3-Radius.magnitude)/Radius.magnitude = (3/Radius.magnitude) - 1.Oh yes, I meant to say: if you 'head-on' an object, you are always likely to get stuck. You can either live with it or make a special case: if(Radius.normalise() == Target.normalise()) Target += //some special case.Also, you might want a directional test: is the object moving away from the collision, if so let it carry on. You could do that by changing the initial collision test:if((Radius.magSquared < 9) && (Radius.dot(Target) < 0));  Bob Janova,Thanks for your reply. Unfortunately I'm still having problems, but you've given me a few avenues to explore. I rigged up your correction code, but it tends to cause intersections when dealing with multiple objects (also, that's why I don't have a break command). It's possible (well, likely) I'm just implementing it wrong, though.Quote:It doesn't look right to me; a collision shouldn't depend on where the coordinate system is based! Are you sure you didn't mean Target.cross(Radius)? (I don't understand what this step is for, though – please enlighten me!)That step's just there to tell which direction I'm moving in (ie: left or right). The cross product probably isn't necessary -- I could probably just check FacingAngle somehow -- but it does work (to an extent).Quote:A couple of code tidiness points (minor): Radius would be better called deltaPosition, or Difference, or something like that (perhaps not ds as mine tend to be!), as radii are generally scalars; and it would be a nice addition to your Vector class to have a MagSquared method (then the check would simply be if(deltaPosition.magSquared < 9)).I didn't even consider a magSquared function. Thanks!Quote:Oh yes, I meant to say: if you 'head-on' an object, you are always likely to get stuck. You can either live with it or make a special case: if(Radius.normalise() == Target.normalise()) Target += //some special case.Can you elaborate upon this? I think this might solve my problem, but right now I'm not sure how to implement it. My "special case" is a printf diagnostic that never runs.Quote:Also, you might want a directional test: is the object moving away from the collision, if so let it carry on. You could do that by changing the initial collision test:if((Radius.magSquared < 9) && (Radius.dot(Target) < 0))Also a good idea.Thanks again for the help!Also, the reason my correction code works as it does is because I'd rather the objects keep moving on their path than have to keep changing direction when hitting obstacles. I'm nowhere near the level of implementing a proper collision-detection system (with rebound and all those frills) so avoiding that issue under the guise of "artistic intent" sounds like a good idea ;)   ;Quote:Can you elaborate upon [the head-on problem]? I think this might solve my problem, but right now I'm not sure how to implement it.If you run straight into an obstacle (i.e. along its normal), it is not clear which way around it the player should be pushed. Thus a naive 'push me away from the centre' implementation (which is what I suggested) will get stuck, as it's pushing you away in exactly the opposite direction to that in which you're trying to move, and you go nowhere.A suitable fudge would beif((Radius.normalise()) == Target){ // i.e. trying to go towards the centre of the obstacle Current.Position += 0.1 * new Vector(Target.z, 0, -Target.y);}... i.e. a little nudge to one side. The next frame you won't be pushing straight towards the middle any more and will begin to slide around the obstacle.Quote:That step's just there to tell which direction I'm moving in (ie: left or right).In that case I think you did mean Target.Cross(Radius); that tells you whether you're going clockwise or anti-clockwise around the obstacle ('left' and 'right' don't mean much on a circle!).Quote:Also, the reason my correction code works as it does is because I'd rather the objects keep moving on their path than have to keep changing direction when hitting obstacles.Well, if your object continues on its path then it is ignoring the collision! You have to make the object go around the obstacle in some way ;). I didn't include any 'response' code, just that to move the object back to its last legal position.I looked at your code again and it seems that the parameter Dir is being used as a speed. Is that what it's meant to do?Perhaps it would help if you posted a couple of simple diagrams showing collision scenarios and what you would like the object to do, as I'm not sure I'm answering the question you asked!   ;  Ah, yes, it does seem communication's the main issue here!Quote:... i.e. a little nudge to one side. The next frame you won't be pushing straight towards the middle any more and will begin to slide around the obstacle.This is the implementation I've got now. The only problem is that "one side" is precisely that -- right now every object goes clockwise around a given obstacle (to use the proper parlance). I just can't work out how to get it to decide which direction offers a shorter route.I'm not logged in to my linux partition right now, so I can't provide screenshots, but here's a rough description:If I comment out the cross stuff entirely, the code works perfectly. Any given object (either the player, or an object controlled by AI) can work its way around all obstacles -- it just goes clockwise around every one until it's no longer in collision with any.The problem is that I can't seem to make the objects change from clockwise to anti-clockwise, and vice versa. And even if I could, I'd run into issues when approaching two objects right next to each other. Suppose I go clockwise around one, and enter the radius of a second, which deems I go anti-clockwise -- thus entering the radius of the first obstacle -- and thus I get stuck between, well, a rock and a hard place. I think your Target.cross(Radius) code would fix the first problem, but the latter requires some further thought. My latest approach is using an Object->inCollision variable to check that we're not changing the direction immediately after a collision; I'll try that in tandem with your suggestion and see how it works.Thanks for the help -- I've never really shared my code before, and can only imagine how much sense it makes to anyone else.Also, Dir just changes between -1 and +1, to accommodate objects travelling forwards and backwards. I'll likely remove that functionality, though, because I've given some serious thought to the actual gameplay in the interim and decided I only really need my objects to travel in one direction.   ;  If the problem is to find the shorter way, then the following thoughts may help.The movement of the avatar before collision was into one direction from the current position on. This describes a ray. This ray hits the circle at 0, 1, or 2 points. If it hits twice then select those with the shorter travel distance. Then compute the normal of the circle at the hit point (simple, since the obstacle is circular).You can use the normal in two ways. First, you can use it to reflect the original movement vector, or you can compute the cross product with the original movement vector. If the reflected vector points to the left (right) of the original, or the cross product points upwards (downwards) then you use the CW (CCW) way around the obstacle. I assume the method using the cross product being simpler, although you have to take care on the correct order; above I've chosen "motion cross normal"). However, you have to handle the case where the reflected vector points totally back or the cross product becomes 0, in what case the one way is as good as the other (so you can chose one arbitrarily or even randomly).[Edited by - haegarr on September 24, 2006 11:40:49 AM];  An with connected obstacles: Well, as long as the count of connections isn't high (say they don't form the Chinese Wall ;) then you may compute the shorter way only if the avatar comes from a free motion. If, on the other hand, the motion is already caused from a previous collision, then skip the route computation but remain with the direction you've chosen earlier. You may try the other direction after colliding with N connected obstacles in a row. But obviously the behaviour becomes to look stupid if there are really many connected obstacles.   