Welcome, Guest. Please Login or Register.  • Help
SMF Underground
+ SHMUP-DEV » SHMUP DEV FORUMS » Assistance » Tutorials
|-+ Art Of Collision [part 2] : Circles, Dynamic Testing, and Time Filtering

Pages: [1]   Go Down
0 Members and 1 Guest are viewing this topic. Topic Tools  
Read August 13, 2008, 04:19:05 PM #0
motorherp

Art Of Collision [part 2] : Circles, Dynamic Testing, and Time Filtering

Welcome back. This is the second article in the 'art of collision' series (the first can be found lower down) and this time the focus is going to be on circles. This tutorial is going cover static and dynamic circle collision testing during which I'll give a comparison of the techniques and how this applies to shooter games in particular. Hopefully this will give you a good understanding of the advantages of dynamic testing over static testing in general as well as the sacrifices which must be made. I apologise now if you took part in the rather long and detailed thread a while back which covered this area since a lot will be repeated, but I'll do so in a more formalised way so hopefully it makes more sense. Donít worry though; there will be something good for you here too. As a bonus, since we're talking about circles, I'm also going to let you in on a technique you can apply, which shmups tend to be well suited for, which will be like adding a nitrous tank to your collision engines. They're really going to fly after this.

So why use circles? For a start they're an accurate shape for many of the objects we'll encounter in shooters such as bullets or the cockpit of the player ship which defines their hit area. Also just as with the aabb's in the last tutorial they're extremely cheap and easy to collide together. In the case of circles this comes down to the fact that they are isotropic shapes, i.e. the same in all directions. This means our collision test boils down to just measuring the distance between the circles' centres and if this is less than the sum of the circles' radii then they must be intersecting. This distance calculation would usually involve a square root but if instead we work with the sum of the square of the circles radii then we can use the square distance saving us this expensive calculation. Therefore our test looks like so:

Code:
struct Circle
{
    float x;                     // x position
    float y;                     // y position
    float sqRadius;     // square radius
}


bool Collide(Circle A, Circle B)
{
    // calculate separation on each axis
    float x = A.x - B.x;
    float y = A.y - B.y;

    // calculate square distance
    float sqDistance = x*x + y*y;

    // test for collision
    return (sqDistance < A.sqRadius + B.sqRadius);
}

Imagine a scene with lots of circles in it were we are testing for collisions between the circles using the above test. Each frame becomes like a snap-shot in time and the collisions we detect will be an accurate representation of what the scene appears to be doing in that snap-shot. Next frame all our circles move a bit and we get another snap-shot. What happens between the frames though? Imagine two circles moving quickly enough towards each other that during one snap-shot they appear separated and then in the next snap-shot they have swapped positions but still appear separated. The above test will tell us in both frames that these circles aren't colliding but in reality we know that they must have passed through each other between the frames and hence we should really trigger the collision resolution code for the two objects these circles represent. So how do we detect these situations? Well this is were dynamic collision tests come in, i.e. collision tests which account for the motion of the objects between the frames. So how do we do this dynamic test. Well we know we can find the position of a circle at any time (t) between the frames using, position(t) = position(t=0) + t*velocity, where t=0 is the time of the previous frame. What we need to find though is whether the distance between two circles ever becomes less than the sum of the radii for any time between the frames. I'll not go into the derivation of the algorithm since although itís simple itís quite long and is far better described in many other places on the internet. Instead I'll just give you a code dump of a robust implementation taken from http://www.gamedev.net/reference/articles/article1234.asp which you should read if you're interested in the maths.

Code:
struct DynamicCircle
{
    float x;                         // x position in the current frame
    float y;                         // y position in the current frame
    float px;                     // x position in the previous frame
    float py;                     // y position in the previous frame
    float sqRadius;         // square radius
}


bool Collide(DynamicCircle A, DynamicCircle B)
{
    // calculate relative velocity and position
    float dvx = (B.x - B.px) - (A.x - A.px);
    float dvy = (B.y - B.py) - (A.y - A.py);
    float dx = B.px - A.px;
    float dy = B.py - A.py;

    // check if circles are already colliding
    float sqRadiiSum = A.sqRadius + B.sqRadius;
    float pp = dx*dx + dy*dy - sqRadiiSum;
    if(pp < 0) { return true; }

    // check if the circles are moving away from each other and hence canít collide
    float pv = dx*dvx + dy*dvy;
    if(pv >= 0) { return false; }

    // check if the circles can reach each other between the frames
    float vv = dvx*dvx + dvy*dvy;
    if((pv + vv) <= 0 && (vv + 2*pv + pp) >= 0) { return false; }

    // if we've gotten this far then itís possible for intersection if the distance between
    // the circles is less than the radii sum when itís at a minimum. Therefore find the time
    // when the distance is at a minimum and test this
    float tmin = -pv / vv;
    return (pp + pv*tmin > 0);
}

As you can see the dynamic test is quite a bit more complex than the static test and this will be reflected in our performance. So is this efficiency loss worth the benefit of having 100% accurate collision? Well this really depends on many game dependant factors and is something you'll have to decide for yourself based on your project. I'll give you a rundown of the various implications though so that you are better equipped to make this decision. First of all we should think about what it means to the player to have a static system and let our engine miss collisions:

* The player is trying to shoot down a barrage of missiles before they hit him and destroy his ship. He has them perfectly lined up in his sights and lets the hot lead fly from his guns. In a dynamic system all the missiles will be destroyed and the player is saved thanks to his quick reactions and accurate aiming. In a static system some missiles might miraculously escape the defensive fire and wipe him out regardless of the fact that the player did everything right.

* The player lunges through a gap in the bullet fire to quickly collect a stream of medals left from his defeated foes. In a dynamic system the player successfully collects all the medals and then continues to focus his energies on the next wave. In a static system, to the playerís dismay he fails to pick up some of the medals in the stream even though he passed directly through them all and now has to make a second pass as the next wave descends upon him.

* The player his navigating his way through a dense bullet cloud but has miscalculated and surrounded himself by an inescapable wall of death. He grimaces waiting for the end knowing he's made a mistake. In a dynamic system he dies as expected whereas in a static system the player finds that he can sometimes escape by diving head first into the wall of death and if he's lucky come out unharmed.

As you can see from the first two examples, a static system can create a frustrating and unfair game play experience for the player which will directly impact on the games playability which obviously we want to avoid. Although the third scenario might seem to work in the players favour at first, the static system has introduced an uncontrollable element of random chance into the core game mechanics. This will weaken the players trust in the game mechanics and implants the belief that doing well in the game is just as much due to random chance as skill. This will also harm the game play experience, especially over the longer term when people want to fight it out over the top spots on the score board. This mistrust is actually what is fundamentally wrong with all the examples but with different consequences in each case. The dynamic system in comparison will always give us the results we expect for all situations which creates a very solid trust in the game mechanics for the player and as a result increases their enjoyment of the game.

Note however that the aim is to create the illusion of accurate collision and if this is done well enough the player will know no different. Therefore although a static system will unavoidably miss some collisions the question you have to try and answer is 'will this happen often enough to be noticeable by the player?'. So how can we try and limit the number of missed collisions in a static system? Before I can answer this first of all we'll need an understanding of what effects our collision accuracy. When two circles pass through each other try and imagine them moving in very small steps and think about how many of those steps they are in contact (this is easier if you consider the relative motion so one circle is stationary relative to the other). The ratio of this number of colliding steps compared to the total number of steps is correlated to the chance a static system will correctly detect this collision. The following diagram shows the red circle moving through the green circle, the elongated red area being the total area swept out by the red circle during its motion and the yellow area is the area during which both circles are in contact. The top black line shows the total time for the motion and the bottom one the amount of time during which the circles are in contact. Itís the ratio of these two lines we're interested in which I'll refer to as the collision ratio.





Therefore whether a static system will be suitable for you or not is dependant on the typical collision ratio for your game's objects, which is in itself dependant on the objects' size, speed, and also the time between frames. As your objects get smaller, their speeds get faster, or your frame rate gets lower, the viability of a static system becomes less and less. Hence if small and fast objects are required for your game and you canít raise the frame rate sufficiently to compensate then you should consider using a dynamic system. Keep in mind that if you go for a static system you will be constantly bound by these size, speed, and frame rate restrictions in order to keep it viable where as with a dynamic system you wonít have to worry about these issues. Any restrictions we can lift of our design process are always a good thing. There's one more implication of static systems I want to mention which is demonstrated in this diagram:





Here we see the collision ratios of two circles as they pass each other more and more off their centre line. As you can see, as the collision becomes more and more glancing our collision ratio drops and hence our static collision accuracy also drops. In fact with a static system our collision accuracy will always converge to zero as the collision becomes more glancing and hence no matter how big and slow our objects are and how high our frame rate is, total collision accuracy can never be achieved. In effect itís like our collision shapes have become 'fuzzy' around the edges instead of being sharply defined. A dynamic system on the other hand is not effected by glancing collision and responds exactly the same as the head on collision case. Therefore a dynamic system gives total collision accuracy all the time regardless, well at least for isotropic shapes like circles. Most dynamic collision techniques donít account for rotation and hence non isotropic shapes suffer from similar fuzzy edges but not quite to the same extent.

The advantages of using a dynamic system are quite extensive and can be very important, and the decision on whether a static system is viable or not isn't very clear cut. Therefore as a general rule I tend to say that if you can spare the cycles to run a dynamic system then do so. It is however horses for courses and if you really need the extra performance to extend your target market to lower spec machines for example, then maybe you will have to make the sacrifices and go with a static system. This isn't the end of the world though and if managed well enough will go un-noticed by the player.


Offline  
Read August 13, 2008, 04:19:19 PM #1
motorherp

Re: Art Of Collision [part 2] : Circles, Dynamic Testing, and Time Filtering

Ok so now the part you've likely been waiting for. How do we take advantage of circles to turbo charge our collision engines? Well we can take advantage of their isotropic nature to severely reduce the number of collision checks we need to perform each frame under certain conditions. I call this process 'time filtering'. So how does this work? If we have an object which is represented by a circle of radius 'r' and has a maximum possible speed 'v', then the area of possible locations that object can touch after a time 't' is also a circle cantered on the objects location and with radius 'R = r + t*v'. If we have two circles we can calculate the 't' value when their two circles of possible location begin to intersect and then we know we no longer have to run collision tests on these two circles until the time 't' has passed since they cant possibly intersect until that time.

Imagine a very manic shooter with a large number of enemy bullets we wish to collide against the player's circle were we're only interested in bullet to player collisions and aren't interested in detecting intersections between bullets and bullets. If we store a list of potential collision bullet id's along with their corresponding times of first intersections with the player (stored in game time, not relative time) and keep that list sorted in time order, then each frame the player only need look up the list and test for collisions with bullets that have a time less than the current game time. Therefore each frame we will only need to perform collision tests with a small fraction of our total number of bullets. In fact this time calculation is also capable of detecting when two circles are actually colliding and hence we can do something quite cool. Each frame, for any bullet that has a time less than the game time we re-perform our time of first possible contact calculation. If this detects a collision then we respond to this, else we set this bullets time to the time returned by the calculation meaning we can put off having to test it again for a while. This is because our calculation is the time of very first possible contact given the current conditions and its unlikely this will be the actual time of first contact. So how do we implement this? As usual I'll give you a simplified code dump with the important bits filled out and commented since this can explain it for more efficiently than I can with words:


Code:
struct Circle
{
    float x, y;             // position
    float radius;
    float speed;         // current speed for constant speed objects, or max possible speed for variable speed objects
    int objId;             // the id of the owner obj of this circle
};


struct TPC             // Time of Possible Contact
{
    float time;         // measured in game time (not relative time)
    int circleId;          // Id of the circle this corresponds to
};



struct TimeFilter
{
    float gameTime;
    Circle subjectCircle;         // circle of the subject (in our example the player)
    Circle collideeCircles[MAX_OBJECTS];         // circles of our collidees (in our example the bullets)
    TPC tpcs[MAX_OBJECTS];
    int numCollidees;

    void Initialise(Circle subject);

    int AddCollidee(Circle collidee);
    void RemoveCollidee(int circleId);

    void UpdateSubject(float posX, float posY);
    void UpdateCollidee(int circleId, float posX, float posY);

    void Update(float dt);         // dt = time passed since last frame
    void UpdateTPC(int tpcId); // generates new time of first contact and detects intersecting circle;

    void SortTPCs();

    void ResolveCollision(int circleId);
};


void TimeFilter::Initialise(Circle subject)
{
    // call once at start
    gameTime = 0.0f;
    numCollidees = 0;
    subjectCircle = subject;
}


int TimeFilter::AddCollidee(Circle collidee)
{
    // add collidee circle and generate tpc for this collidee.
    collideeCircles[numCollidees] = collidee;
    tpcs[numCollidees].circleId = numCollidees;
    UpdateTPC(numCollidees);
    numCollidees += 1;

    // return circle Id for use by external objects
    return numCollidees - 1;
}


void TimeFilter::RemoveCollidee(int circleId)
{
    // remove the circle with this id and the corresponding tpc.
}


void TimeFilter::UpdateSubject(float posX, float posY)
{
    // update the subjects position
}


void TimeFilter::UpdateCollidee(int circleId, float posX, float posY)
{
    // update the collidee with the corresponding id's position
}


void TimeFilter::Update(float dt)
{
    // update game time
    gameTime += dt;

    // sort tpc list
    SortTPCs();

    // check for and test possible contacts
    for(int i = 0; i < numCollidees; ++i)
    {
        // if the game time has passed the tpc then recalculate
        if(tpcs[i].time <= gameTime)
        {
            UpdateTPC(i);
        }
        else
        {
            // if we dont have to recalculate this tpc yet then we know the rest beyond this dont need
            // recalculating since they're in time order, thus break out of the loop
            break;
        }
    }
}


bool TimeFilter::UpdateTPC(int tpcId)
{
    // calculate gap between circles
    float diffX = subjectCircle.x - collideeCircles[tpcs[tpcId].circleId].x;
    float diffY = subjectCircle.y - collideeCircles[tpcs[tpcId].circleId].y;
    float distance = sqrtf(diffX*diffX + diffY*diffY);
    float gap = distance - (subjectCircle.radius + collideeCircles[tpcs[tpcId].circleId].radius);

    // if the gap is less than zero then these circles must be intersecting
    if(gap < 0.0f)
    {
        ResolveCollision(tpcs[i].circleId);
    }
    else
    {
        // else we're not yet intersecting so calculate new time of contact
        tpcs[tpcId].time = gameTime +  (gap / (subjectCircle.speed + collideeCircles[tpcs[tpcId].circleId].speed));
    }
}


void TimeFilter::SortTPCs()
{
    // sort array in time ascending order
    // I'll not go into details since I gave an in depth look at a sorting method in my last 'art of collision' tutorial.
    // You can use any sorting method you want however, but an insertion sort like that mentioned above
    // would be fastest
}


void TimeFilter::ResolveCollision(int circleId)
{
    // trigger your collision resolution code here
}

(*disclaimer* - the above code might contain errors since itís not been compiled and run. Its intended to be a guide rather than to give fuel to copy-paste monkeys ;p. The important thing here is that you take away an understanding of the technique so you can implement it yourselves to fit your needs. If you do spot errors though then please let me know so I can correct them.)

So the idea here is that you call the Initialise function once at the beginning of your level, then each frame you update all your objects and have them update their circles using UpdateCollidee. Once this has been done you then call Update passing in the time passed between this and the last frame and this will then collide everything for you. The above is the simplest implementation I could give so you can focus on the key elements and is missing the bells and whistles. So how can we go about improving this technique? Here are some ideas:

In the UpdateTPC method you'll see that the function doesn't take into account bullet direction but assumes it can move in any direction, which is obviously the case for the player but maybe not for bullets. Therefore for bullets which dont change their travel direction ever we can take this into consideration to give us a better estimate of our time of first possible contact. In the line of code where we add the speeds together we are assuming the relative velocity is the worst case scenario of when the objects are moving directly towards each other. However taking the bullet direction into consideration we can project its travel vector onto the vector between the objects to get a more accurate relative velocity between the objects. Note for this to work we will also need to store the objects direction in the circles which I'll represent with dx and dy (these are normalised directions so when multiplied with the speed give us our travelled distance), and the code in the else bracket would look something like:

Code:
float invDistance = 1.0f / distance;
float projSpeed = collideeCircles[tpcs[tpcId].circleId].speed * invDistance * (collideeCircles[tpcs[tpcId].circleId].dx*diffX + collideeCircles[tpcs[tpcId].circleId].dy*diffY);
tpcs[tpcId].time = gameTime + gap / (subjectCircle.speed - projSpeed);

Note that the sign in the time equation has changed to a minus.  This is because we wish to know the relative velocity between the circles, ie: the velocity difference.  The reason we've used a plus sign previously is because we've been assuming the worst case where the circles are moving directly towards each other.  Therefore one circles velocity vector is directly negative to the others so the equation became "speedA - (-speedB)" = "speedA + speedB".

Something to beware of here though is that its now possible for the relative speed to become negative which means the objects will never collide, however when we sort our lists they'll be pushed to the start since they end up with a negative time and we'll be recalculating their tpc every frame. We can cope with this by doing a test for negative time straight after this calculation and if this is the case set the time to a very high number that we wont reach during the span of a game level (eg 1e22f). This way the tpc will be pushed to the end of the list and wonít interfere with the algorithm.

You might be worried about the square root slowing things down but in general I wouldn't worry about it. The reason being that this bit of code wonít get executed very often, with one exception which is when bullets start getting very close the player. To stop many square roots being called though you could add in a distance threshold to the system. What this would do is, if the object is calculated to be within the distance threshold during the tpc update then we flag this tpc and set its time low (0). This would make it crop up for tpc updating each frame, but in the tpc update we first check for this flag and if it's set we dont calculate a new tpc but just revert to static circle collision testing as described at the start of this article. Note however that this will trap us into forever using explicit testing each frame for this object after it has approached to within the threshold even if it then leaves the threshold again. All we need to do to fix this is in the static circle collision test, test to see if the square distance calculated is above the square of the threshold distance and if so unset the flag.

You've probably noticed that I've been talking about static testing all this time where as I just had a discussion earlier about the advantages of dynamic testing. Indeed this method can be updated to be dynamic, we just need to include a call to the dynamic collision test in the else brackets of the UpdateTPC method and that will take care of it for us (and also replacing the explicit test mentioned in the last paragraph for a dynamic one of cause). Easy as that. In fact if we directly implement the test into the UpdateTPC method many of our variables for the collision test will have already been calculated and we can get rid of the first section of that test which checks if the circles are already colliding since this has already been done.

One last quick upgrade I want to mention is that this method can easily be extended to support other shapes by associating a radius with those shapes, were the radius is the length from their centre to their maximum extent. When a collision is detected between the circles you'd then have to explicitly call the collision method for the corresponding shapes to see if an actual collision has occurred.

Rightio, hopefully you can see the power of the time filter for certain Cave shooter style scenarios were you have an obscene number of bullets to collide against the player. How does this cope with non linear collision though, for example colliding a bunch of asteroids with each other? Well sadly this is were we run into troubles. This method can only focus on one object at a time, the subject object, and hence each asteroid would also have to have its own time filter for collision with the other asteroids. This isn't a problem performance wise, it'll do the same thing for these cases as it does for the player vs enemy bullets, ie give us a serious boost. It does mean however that our memory consumption starts to rocket. Whether your game can cope with this or not depends on the type of scenarios you'll be throwing at it, but if you're using memory raw (without a memory manager) then be cautious of this. The alternative is to use the time filter only where itís needed most and resort to other methods for everything else.

Ok thatís your lot. I hoped you enjoyed this article, feel free to give me feedback and ask questions. I'll do my best to reply to them all.


Dan.
« Last Edit: August 15, 2008, 09:13:57 AM by motorherp »

Offline  
Read August 14, 2008, 07:12:58 PM #2
motorherp

Re: Art Of Collision [part 2] : Circles, Dynamic Testing, and Time Filtering

[reserved]


Offline  
Read August 14, 2008, 07:34:00 PM #3
motorherp

Re: Art Of Collision [part 2] : Circles, Dynamic Testing, and Time Filtering

You can find previous replies to this tutorial posted in the following thread:

http://www.shmup-dev.com/forum/index.php?topic=1084.0

That topic has now been locked.  Please continue any discussions or add any further questions in this thread.  Many thanks.


Offline  
Read August 15, 2008, 03:04:11 AM #4
Yumil

Re: Art Of Collision [part 2] : Circles, Dynamic Testing, and Time Filtering

I've been working on the directional optimization and have found that it's not worth the work. The one in you have in your tutorial wont work as it just adds the two velocities together... If Im right, the x and the y will have to be squared then added and rooted to get a value we can use...doing that kills the sign, which kills finding ones that will never collide with the current direction. It can be fixed, but I dont know if it is worth it. Anywho, I've tweaked it to do a standard test within a certain threshold of distance and now have 2100-2300 bullets on screen with no slowdown under the right conditions(8-9 enemy bullets a frame, going 2 pixels a frame in a 1280x720 screen). It's more than enough for my game, so I'll go on to the next component that needs work. I might rework on the directional optimization later as I wanted to push 2500-3000 bullets before slowdown, but right now it's not worth the effort.
Offline  
Read August 15, 2008, 08:02:49 AM #5
motorherp

Re: Art Of Collision [part 2] : Circles, Dynamic Testing, and Time Filtering

I've been working on the directional optimization and have found that it's not worth the work. The one in you have in your tutorial wont work as it just adds the two velocities together... If Im right, the x and the y will have to be squared then added and rooted to get a value we can use...doing that kills the sign, which kills finding ones that will never collide with the current direction.

Ah yes there is a problem, but not what you think it is, although good job for spotting the error.  What's happened is that I haven't taken into account that the diff vector isn't normalised, so the bullet velocity vector projection is becoming scaled.  You dont need to go through all the hastle you mention though since we can re-use the distance calculation we've already done.  Therefore the code should look like:

Code:
float invDistance = 1.0f / distance;
float projSpeed = collideeCircles[tpcs[tpcId].circleId].speed * invDistance * (collideeCircles[tpcs[tpcId].circleId].dx*diffX + collideeCircles[tpcs[tpcId].circleId].dy*diffY);
tpcs[tpcId].time = gap / (subjectCircle.speed + projSpeed);

Thanks for that, it's good to have some people actualy checking what I'm putting up there since a lot of it just spills out of my head onto the page Grin.  Another karma boost coming your way for that and I'll make the corrections in the tutorial.
.
« Last Edit: August 15, 2008, 08:14:14 AM by motorherp »

Offline  
Read August 15, 2008, 08:25:09 AM #6
motorherp

Re: Art Of Collision [part 2] : Circles, Dynamic Testing, and Time Filtering

Aha, looking into it more deeply there is another problem too.  In the time calculation I'm dividing the gap by the difference between the velocities.  In the non directional situation I've assumed worst case where the circles are heading directly towards each other which is why the difference become an addition (because we're subtracting a negative speed).  I've failed to take this into account in the directional situation though and have carried over the plus sign.  Infact the time equation for the directional case should look like:

tpcs[tpcId].time = gap / (subjectCircle.speed - projSpeed);

I've made those mods to the tutorial too along with a better explanation.
.
« Last Edit: August 15, 2008, 08:42:10 AM by motorherp »

Offline  
Read August 15, 2008, 09:04:01 AM #7
Yumil

Re: Art Of Collision [part 2] : Circles, Dynamic Testing, and Time Filtering

You may also want to add the gameTime to it, like you do normally, or well, it wont account for time passed and will start saying something collides every frame after x time.

Anywho, thats a much simpler solution than I was thinking Id need. I'll probably try that in the morning, but its time for me to go to bed now.
Offline  
Read August 15, 2008, 09:13:06 AM #8
motorherp

Re: Art Of Collision [part 2] : Circles, Dynamic Testing, and Time Filtering

Ah yes of course, sorry about that looks like I missed it out.  Hopefully it should have been obvious what I meant given the previous decleration of the equations but I'll correct it in the tutorial just so people dont get confused.


Offline  
Read August 15, 2008, 09:09:24 PM #9
Yumil

Re: Art Of Collision [part 2] : Circles, Dynamic Testing, and Time Filtering

There's one last thing to add. The original formula took the maximum speed the collidee would be going, and thats need for a worst case collision, but calculating it's distance with the max speed isn't going to work. You're going to have to use it's current velocity to do it, or it just wont end up right. Course, all you have to change is that its speed value is its speed, not its max speed and thats outside the code you have provided, just changing the meaning of a single variable.
Offline  
Read August 17, 2008, 10:13:20 AM #10
motorherp

Re: Art Of Collision [part 2] : Circles, Dynamic Testing, and Time Filtering

Well if the bullets can change speed, then using the max speed will give you the most conservative estimate you need to make sure the algorithm wont miss collisions.  Saying it wont work isn't right, infact using the max speed is necessary to make sure the algorithm does work.  For example say you use the current speed to do the calculation and then later on the bullets speed up.  What this would mean is that the TPC you calculated would be too long and the objects could potentialy collide before the algortithm reports that you need to retest these objects.


Offline  
Read August 17, 2008, 06:25:53 PM #11
Yumil

Re: Art Of Collision [part 2] : Circles, Dynamic Testing, and Time Filtering

Well if the bullets can change speed, then using the max speed will give you the most conservative estimate you need to make sure the algorithm wont miss collisions.  Saying it wont work isn't right, infact using the max speed is necessary to make sure the algorithm does work.  For example say you use the current speed to do the calculation and then later on the bullets speed up.  What this would mean is that the TPC you calculated would be too long and the objects could potentialy collide before the algortithm reports that you need to retest these objects.

The player is going same direction as the bullet. The bullet can go potentially as fast or faster than the player, but in reality is going slower. The player will never hit the bullet if you calculate with the max speed, even if he passes it.

Heck, even if the bullet max is slower, the algorithm will miss the collision if they are going the same direction and the max is higher than what it is going.

Worst case is needed for towards, best case would be needed for away...maybe the optimization isn't worth it, since you'd need to update the TPC everytime it changes speed or direction.

BTW, my last comment on this one and the last one were in regard to the one with the direction optimization. The one without needs the worst case scenario to stay fast.
« Last Edit: August 17, 2008, 06:37:24 PM by Yumil »
Offline  
Read August 17, 2008, 08:53:34 PM #12
motorherp

Re: Art Of Collision [part 2] : Circles, Dynamic Testing, and Time Filtering

Yes you're right, the directional optimisation is designed for the case where the bullets can't change direction as described in the tutorial.  For objects which can change direction you need to assume worst case at all times to prevent the algorithm from missing collisions.  This is why the for the situation described in the tutorial, the direction optimisation is applied to the bullet circles only, the ship circle continues to use worst case since the player can move freely.  If you go back a few posts in the other questions thread for this topic you'll see where I've described what you will need to do and test to see if the directional optimisation is worth it for situations where bullets can change direction periodically since you showed an interest in that.  In that situation you would keep bullets straight for 'x' frames allowing you to use the optimisation and then recalc the TPC's after each set of 'x' frames when the bullets change direction.

Edit:  Aha ok, I've re-read what you've written and I see what you're saying now.  In the tutorial I only talk about fixed direction for the bullets in order to use the optimisation.  The correct restriction should actualy be fixed velocity vectors.  Therefore your bullets cant only not change direction but also cant change speed.
« Last Edit: August 17, 2008, 09:06:44 PM by motorherp »

Offline  
Read August 18, 2008, 04:31:31 PM #13
Yumil

Re: Art Of Collision [part 2] : Circles, Dynamic Testing, and Time Filtering

Edit:  Aha ok, I've re-read what you've written and I see what you're saying now.  In the tutorial I only talk about fixed direction for the bullets in order to use the optimisation.  The correct restriction should actualy be fixed velocity vectors.  Therefore your bullets cant only not change direction but also cant change speed.
Yeah, thats basically what I meant. Sorry, I'm not the most articulate person in the bunch.
Offline  
Read March 23, 2009, 02:16:10 AM #14
hima

Re: Art Of Collision [part 2] : Circles, Dynamic Testing, and Time Filtering

I just realized there's something wrong with the sqRadius approach. You still need radius of the two collision circles. If I understand correctly, initially it has to be

Code:
sqrt(sqDistance) < A.radius + B.radius

But then we square both sides since we don't want to work with sqrt
So we have to square (A.radius + B.radius)as well
Code:
sqDistance < (A.radius + B.radius)^2 = A.sqRadius + B.sqRadius + 2*A.radius*B.radius

So in the end the code should be

Code:
sqDistance < A.sqRadius + B.sqRadius + 2*A.radius*B.radius
Offline  
Read March 24, 2009, 11:13:57 AM #15
Hornet600S

Re: Art Of Collision [part 2] : Circles, Dynamic Testing, and Time Filtering

Yeah, but why not use

Code:
float tmp=A.radius+B.radius;
sqDistance<(tmp*tmp)

Just 1 addition and 1 multiplication, instead of 2 adds and 2 muls. And only one attribute (radius) instead of 2 (radius, sqRadius).
« Last Edit: March 24, 2009, 11:15:52 AM by Hornet600S »

"When the Amiga came out, everyone at Apple was scared as hell."
(Jean-Louis Gassťe - Head of Macintosh development at Apple)
Offline  
Read March 24, 2009, 12:03:44 PM #16
hima

Re: Art Of Collision [part 2] : Circles, Dynamic Testing, and Time Filtering

Oh that's very clever! I've never thought about that Cheesy Now I have to go back and fix my circle collision code.

Though my original intention was not for the performance purpose. Just wanted to point out the mistake in calculation Smiley
Offline  
Pages: [1]   Go Up
Jump to:  

Page created in 0.137 seconds with 19 queries.