# Overlaying grid for pathfinding

My game is not grid-based, so units can be at any arbitrary coordinate and move at different speeds. My obstacles are all rectangular and axis-aligned, so naturally it makes sense for me to overlay a grid over the map for pathfinding. Each unit will take up a grid cell (floor(unit.x / CELL_SIZE), floor(unit.y / CELL_SIZE)). I will then run standard A* grid-based pathfinding on the grid.

The problem is that although the path is grid-aligned, the unit movement is not. Thus, in the midst of moving, the unit might end up colliding with a cell that is blocked, and get stucked. Here's a picture to illustrate:

I'm trying to get from point A to point B. B is the center of the grid cell, since it is a waypoint from the found path. A is the point the unit is currently at. The pathfinder thinks A to B is valid movement, since it takes the grid cell of A as the start point and the diagonal neighbour B is not blocked. But moving from A to B might result in position C, which is blocked.

I thought of using a soft collision radius for pathfinding, but it has its problems. The pathfinder will not return any paths where there's a soft collision. So if the current location of the unit already has a soft collision, the unit cannot move! It seems that it is necessary to keep the pathfinding collision and physics collision identical...

How do I resolve this problem, and what is the standard way to overlay a grid for pathfinding?

• don't allow diagonal movement... Nov 18, 2013 at 11:00
• @ratchetfreak But diagonals reduce the number of grid cells that need to be searched, and I'm trying to make pathfinding as speedy as possible. Also, I believe A* on grid is usually done using 8 octants, so I'm sure there's a standard solution out there! Thanks for the suggestion though. Nov 18, 2013 at 11:10
• A* doesn't impose limitations on the graph; only on the heuristic Nov 18, 2013 at 11:13
• It's common to do a ray cast or a sphere sweep to ensure the path is clear. You can save processing time by only doing those checks on diagonal movements.
– House
Nov 18, 2013 at 15:17
• possible duplicate of Pathfinding with 2D, non-grid based movement over uniform terrain Nov 18, 2013 at 17:24