How to find 2D grid cells swept by a moving circle?
- by Nevermind
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:
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.