Detecting collision on a grid with a fast-moving object

Question

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.

Answer 1

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

Answer 2

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.