2D angled collisions

(RY-TY)/(RX-TX) is the tangent so no it isn''t correct to take the tangent of the tangent to find the angle, but the arc-tangent would be. If RX equal to TX you will of course have a problem as you divide by zero. I think all you really need is the distance and direction between the centers. The distance tells you if the circles are close enough to collide. The sign on the direction will get you down to a quadrant and the ratio of the components will get you to a subdivision of that quadrant. As an example if dx = (rx - tx) and dy = (ry - ty) then if dx and dy are greater then zero then the bullet collided in the southwest quadrant. If dx > dy then is collided in the west by southwest section and if dx < dy then it was the south by southwest section.

With polygons is is going to be a little harder because a corner could strike a side which gives one point of contact like the circles or a side could strike a side which means you have many points of contact. If they are rectangles and the sides a parallel to the axis then it is pretty simple. If they are not then the only thing I know of is finding the intersection of the lines that define the side and testing them, i.e. y=m1*x+b1, y=m2*x+b2, y=y, m1*x+b1=m2*x+b2, x=(b2-b1)/(m1-m2), y=m1((b2-b1)/(m1-m2))+b1. You can then use the start and end points of the line segment that is the side as a bounding box and test whether the point is inside. If the slopes are equal then you will have a problem, but then all that is needed is checking for when their x or y intercepts are equal. You also have to do a bounding box test on both end points of the other line.

I doubt this is the best way, but at least it is a way that works and since there wasn''t any other replies...

thank you for your reply LilBudyWizer.

i like the idea with the collision of circles, distance between centers would tell me if they collided or not, and i can find where at with the slope.
is this a quick way to find distance?
we have CenterX1, CenterY1, radius1, CenterX2, CenterY2, radius2.
they have collided if...
(radius1 + radius2)squared <
(CenterX1 - CenterX2)squared + (CenterY1 - CenterY2)squared
is this correct?

also, the robots are just rectangles (but they can be rotated).
since i know that all rectangles are the same size, and that they are actually rectangles, and the angle they are rotated, is there anyway to simplify the collision test since we have this information?

That would be >= not <. If the centers are the same then the right side is zero, not infinity. As for the rest, I have to run, but I''ll get back to it later.

You can simplfy it by using a bounding box that is aligned with the axis to do a preliminary test. Simplfy depends upon your point of view. It could mean reducing instructions/calculations or it could mean making it easier to follow which are really opposing goals. Either way I would say code it and then work towards whichever goal you want from there.

speed is what i am after, memory or ease of programming dont concern me as much as how fast the collision detection is.

because of the game, i need it to be as accurate and fast as possible.

i might just give each robot a circle that completely surrounds it, and then use the distance check to see if i need to do further more accurate collision detection, whatcha think?

I didn''t ignore this post, but rather my math is a bit weak so my ability to reduce it is a bit limited. Checking a bounding box would take fewer calculations. Rather than (r1+r2)^2 >= (x1-x2)^2 + (y1-y2)^2 you can just use (r1+r2) >= abs(x1-x2) + abs(y1-y2). The abs should be faster than the multiply. That isn''t necessarily the smallest bounding box, but it at least shows the relationship between the two calculations. In practice it would make more sense to just compare the sides, i.e.

bool BoundingCheck(rect bb1, rect bb2) { bool rc = true; if (bb1.right < bb2.left) rc = false; else if (bb2.left > bb2.right) rc = false; else if (bb1.top > bb2.bottom) rc = false; else if (bb1.bottom < bb2.top) rc = false; return(rc); } [/source] As for setting the bounding box... [source] void GetBounding(point *ptPoints, rect &rc) { rc.left = rc.right = ptPoints->x; rc.top = rc.bottom = ptPoints->y; for (int i = 1, ptPoints++; i < 4; i++) { if (rc.left > ptPoints->x) rc.left = ptPoints->x; else if (rc.right < ptPoints->x) rc.right = ptPoints->x; if (rc.top > ptPoints->y) rc.top = ptPoints->y; else if (rc.bottom < ptPoints->y; rc.bottom = ptPoints->y; } }

If the boxes are relatively large you could get elaborate and track which points set which side and then check midpoints between that point and the corner. If the overlap is within the rectangle defined by the corner and the two midpoints then there wasn''t a collision. If you wanted simple programming you could use the region functions from windows.

Overall I would say the most important thing is limiting the number of collision checks you do. As an example checking for collision between two static objects would be a complete waste since they don''t move. Checking collision between projectiles may be accurate, but is the ability to shoot down projectiles a feature of the game. Even if it is then they still can''t shoot their own projectile unless the speed/acceleration of the projectiles varies or they can move faster than the projectile. If they can move faster than the projectile then they can shoot themselves, but otherwise checking for collision against the person that fired it is a waste. That is assuming the projectiles move in a straight line.

Beyond that is performing only the calculations at the point they actually changed. As an example with the bounding circles (r1+r2) may not change. If you are finding the intersection of the sides the slopes only change when the objects rotates. Assuming two sides are parallel to the direction of travel then two y intercepts also only change when the object rotates and the other two change by the y component of the velocity vector. Also as long as the velocities and directions do not change then if the objects are closing then they are closing at a fixed rate. i.e. the distance between the objects can be calculated by adding a fixed quanity to their previous distances apart.

This is where my weakness in math hurts. I would have to struggle to come up with the exact calculation. Also beyond that I believe the critical points on the derivative would tell you when they are closest which if they don''t collide at that point then they don''t collide. Which brings up the issues of accuracy. If you want to be accurate then you have to calculate the point of collision when it changes and then check the direction to that point after each update of the positions. If the x or y component of the direction vector reversed then you went past the point of collision in the last update.

The biggest issue with performance tuning something is whether it is needed. The basic check against a bounding box makes four compares when there is a collision between the bounding box. Otherwise on average there will be two compares. You only go on to the more complex collision check when the bounding boxes collide. Realistically how many objects will have their bounding boxes collide in a single frame? I would be somewhat surprised if it was more than ten. It would have to be an extremely complex calculation for ten of them per frame to slow you down.

Generally with optimizations I assume 10% of my code will take 90% of my processing. So with the vast majority of the code optimization plays a relatively small part. I try not to do anything wasteful, but I don''t try to get every single operation to maximimum efficency. A fast program is better than a slow one, but a slow one is better than none at all. If I''m concerned about a particular routine I measure it first. I execute it in a loop enough times for it to be a few seconds. I then calculate how long it takes per execution. I then make a best guess on how many I reasonably have to do and calculate how long I will spend doing that number. With real-time you have basically a fixed timeslice you have to fit into so I check what percentage of that time I will spend doing that operation. If it is a small percentage then I''m not going to waste my time optimizing it.

This does risk adding up all the parts and finding you don''t fit in the timeslice, but the assumption that 10% of the code takes 90% of the processing is generally true. Without a sampling profiler it can be very difficult to find that 10% after the fact. You can view your program as a tree though. At each node you measure how long each of the sub-nodes took. If a small section of your program is using 90% of your processing then one of those sub-node took at least 90%. Then you repeat the process for that sub-node.

With a game you are dealing with a very small quantity of time. 0.05 of a second can make the differance between 30 and 12 fps, but it is difficult to measure 0.05 seconds without affecting the measurement. So you have to modify the program to loop enough to get the time being measured up into something you can reasonably trust like a few seconds. You can get just as carried away trying to get a 100% accurate measurement as you can optimizing every last instruction. 90% accurate is good enough though. You are most productive optimizing the routine that takes the largest portion of time. Sometimes this routine cannot be further optimized, but that is pretty rare and usually when people believe that it is because they looked at the routine outside the context of the entire program. An example is an optimized line drawing routine. Perhaps that is the fastest way to draw a line, but is calling it four times the fastest way to draw a rectangle.

You want to spend your time optimizing the routines that consume the largest percentage of your time. If you draw a lot of lines then optimizing a line drawing routine may make sense, but if you only draw one line per frame then it is questionable what the benefit of optimizing it is. Making 10% of your processing 10 times faster saves you less than 10%, but making 90% of your processing 25% faster saves you over 20%. Also if all of your processing already fits into the time you have to do it then the benefit of further optimization is questionable with a game. You don''t want to be wasteful, but you don''t want to spend an excessive amount of time optimizing something that has a relatively small impact on overall performance.