9
\$\begingroup\$

I'm making a game based on a 2D grid, with some cells passable and some not. Dynamic objects can move continuously, independent of the grid, but need to collide with impassable cells.

I wrote an algorithm to trace a ray against the grid, that gives me all cells that ray intersects. However, actual object are not point-sized; I'm currently representing them as circles. But I can't figure out an effective algorithm to trace a moving circle. Here's a picture of what I need: enter image description here

The numbers show in what order the circle collides with grid cells. Does anybody know the algorithm to find these collisions? Preferably in C#.

Update The circle can be bigger than a single grid cell.

Improve this question
\$\endgroup\$
2
  • \$\begingroup\$ mmh why 3 collide BEFORE 4? \$\endgroup\$
    – FxIII
    Jun 23, 2011 at 10:27
  • \$\begingroup\$ @FxIII I actually moved the circle in the picture, and it hit 3 before 4. Only barely, but still before. \$\endgroup\$
    – Nevermind
    Jun 23, 2011 at 12:01

3 Answers 3

Reset to default
6
\$\begingroup\$

I think your drawing is a little misleading because you choose to draw strokes from the point on the circle tangent to your moving direction. I can see that the collisions to your grid edges happends when the TOP and LEFT points of your circle touch an edge.

Let C be your center and r the radius so P' = C + (r,0) and P" = C + (0,r).

If D is your direction vector (the versor) you have two lines :

R' = D · t + P',

R" = D · t + P"

You simple have to find the intersection of those lines with the lines of equation:

y = i and y = i that are the edges of your grid!

The solution are easy because you have to simply consider the x or the y component of R' and R". You will find the ts value for each insersection, and the points for thoose ts, simply sort those point by t and you are done.

I believe you can easily say what cell is hit if you know the intersection point.

This works if r < 1 (the cell width and height).

It works also for the other cases simply doing some consideration about P' and P". We choose TOP and LEFT because of direction, BOTTOM and RIGHT should be considered for opposite direction, you understand why.

Now look at this image: big circle

The circle is bigger then a single cell and we suppose it is going the same direction as your drawing. P1 is the first point that will touch, P2 is the second, P3 is useless because is in the bottom half. What you need to do is to cast rays from P1 and P2 as we seen before and do the same for the vertical lines.

In general you will have other starting points along with the TOP and the LEFT ones from where shoot your rays, bigger your circle is, the more rays to cast.

To be honest some you can avoid to shoot all that rays doing some geometrical consideration, but that can make the things harder to understand.

Improve this answer
\$\endgroup\$
6
  • \$\begingroup\$ Yeah, I thought up the P' and P" points myself, but couldn't figure out what to do when circle is larger than a single cell. Additional points really make sense (and I obviously only need to add rays between P' and P") \$\endgroup\$
    – Nevermind
    Jun 23, 2011 at 11:59
  • \$\begingroup\$ Geometrical considerations can be done that simplifies the computations but using the implementation can lead you to the same results by experience. \$\endgroup\$
    – FxIII
    Jun 23, 2011 at 12:17
  • \$\begingroup\$ Is it clear that you have to test for horizontal and vertical grid lines separately? \$\endgroup\$
    – FxIII
    Jun 23, 2011 at 13:14
  • \$\begingroup\$ I think you must also check when the circle covers a grid vertex, because the circle will collide with the diagonally-adjacent cell at its corner but it will not necessarily be the top/left/bottom/rightmost point on the circle that touches it first (and you will detect the collision too early.) Example: squares 3,4,5 in the example diagram in the question. They are hit in order (3 then 4 then 5) but your algorithm would detect 4 & 5 simultaneously. \$\endgroup\$
    – finnw
    Jun 30, 2011 at 18:28
  • \$\begingroup\$ @finnw they touch simultaneously only if the cicle travels exactly in the direction of the bisector. \$\endgroup\$
    – FxIII
    Jun 30, 2011 at 19:46
1
\$\begingroup\$

If you want to use your ray-collision algorithm, you can choose eight points on each circle (at 45-degree increments, aligned with your square grid), and use the ray-collision between corresponding points (i.e., from the top of one circle to the top of the other). The union of all these ray-collisions is the entire set of cells intersected.

You could probably improve on this a little--for example by using the line segment from the center of one circle to the center of the other, but extended on either side by the radius of the circle, as well as the parallel line segments on either side at the extremities of the circles.

Improve this answer
\$\endgroup\$
8
  • \$\begingroup\$ 8 rays will probably guarantee all intersections, but they won't give them in the right order. And for collisions I need order, not just a list of cells. \$\endgroup\$
    – Nevermind
    Jun 22, 2011 at 15:28
  • \$\begingroup\$ Augment your ray-collision algorithm to retain a t-value for each collision. When you get the union of cells, you can sort on the t-value to get the correct order. \$\endgroup\$
    – TreDubZedd
    Jun 22, 2011 at 16:02
  • \$\begingroup\$ But how can I compare t-value of different rays? \$\endgroup\$
    – Nevermind
    Jun 22, 2011 at 16:06
  • \$\begingroup\$ If you're always originating from the same circle, your intersection points will be distances from that circle. When you come to a cell you've already seen, if the t-value of the current collision is smaller than the previous one, use it...otherwise, discard the intersection (keeping the original). \$\endgroup\$
    – TreDubZedd
    Jun 22, 2011 at 16:13
  • 1
    \$\begingroup\$ You might be able to get away with just two rays on the sides of the circle perpendicular to the movement, then you can see which tiles get hit by the rays and you can check the rest to see if their centers fall between the two rays. The only stuff that should miss would be things colliding at the beginning or end circle but that's just two circles and can be handled easily. It may be a bit slower than eight rays, I'm not certain; but you wouldn't need to scale the number based on the size of the circle. \$\endgroup\$
    – Lunin
    Jun 22, 2011 at 17:25
1
\$\begingroup\$

I'm not saying this is a perfect analogy, but you might think about Bresenham's line algorithm. A modification of this algorithm or one of its extensions might be helpful, especially if you couple it with some of the other posts and comments. Typically, this algorithm isn't concerned with ordering, but I would think that you'd be able to add that fairly trivially.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ I was thinking about this too, but it in my opinion, this is not the right algorithm. Bresenham chooses only one pixel, he needs all. And it would be dificult to adapt bresenham to circle insted of just one pixel. \$\endgroup\$
    – zacharmarz
    Jun 22, 2011 at 21:37
  • \$\begingroup\$ The ray tracer I use is actually kinda-sorta based on Bresenham algorithm. I have trouble generalizing it from a thin line to "fat" one, specifically circle-swept. \$\endgroup\$
    – Nevermind
    Jun 23, 2011 at 5:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .