# Detecting collision on a grid with a fast-moving object

I am working in a 2D collision system where I need to detect a collision of a rectangle on a grid, but since the rectangle may be fast enough to jump more than one of the grid squares (sometimes several) I need to check collision of everything in the middle of point A to B.

Does anyone know a way to achieve that?

In the image below, I am starting at point A and in one update it's at point B. I would need to check collision on the whole gray area. As you can see in the image, the rectangle don't need to be on a fixed position on the grid.

The grid squares in my case have 30x30 pixels and the rectangle has 35x65. My grid is also on a list, but this can change if needed.

Thank you in advance for any help.

-

After some more research I decided against box2dxna or Farseer.

What I am (still) building is a solution using Bresenham's line algorithm and ray casting.

I will consider each square on the grid as a pixel, and this should be pretty fast.

So I will actually do more than one ray cast. One for each of the squares on position A facing position B.

So in the image above I will do 4 calls to ray cast. Each ray will hit something like 10 squares, giving me 40 to 50 checks in total.

I hope this help someone else in the future.

Ray casting

Bresenham's line algorithm

-

You could move the rectangle in discrete steps and check collision for every step. For example, instead of moving 10 units, move it 5 times 2 units and check every time. More steps you have, more demanding the processing is but is more precise. In order to reduce processing you could do this only for fast moving objects because slower ones won't produce tunneling (one object passing through other).

Another approach would be to construct a rectangle that would be around the entire movement. In your example, construct the rectangle around the gray area and check collision against it.

-
Yes thank you, I will have a simpler collision system for slower sprites. About the rectangle around the gray area, I was trying that last night...without much success...I think I was tired. I got some code to do the angled rectangles, but couldn't make it work properly. – Danfus May 23 '12 at 12:55
You should also consider using existing physics systems, usually there is no need to reinvent the wheel :-). For example Box2D.XNA (box2dxna.codeplex.com). – loodakrawa May 23 '12 at 13:02
I am doing this project for learning purposes, so I like to deal with those problems, but sure I will give it a look. This may allow me to keep moving if i get stuck on something. Thank you again. – Danfus May 23 '12 at 13:07
I decided to give Farseer Physics a try. Thank you for you suggestion. – Danfus May 23 '12 at 13:30