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?

  • 1
    \$\begingroup\$ don't allow diagonal movement... \$\endgroup\$ Nov 18, 2013 at 11:00
  • \$\begingroup\$ @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. \$\endgroup\$
    – Wakaka
    Nov 18, 2013 at 11:10
  • \$\begingroup\$ A* doesn't impose limitations on the graph; only on the heuristic \$\endgroup\$ Nov 18, 2013 at 11:13
  • \$\begingroup\$ 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. \$\endgroup\$
    – House
    Nov 18, 2013 at 15:17
  • 1
    \$\begingroup\$ possible duplicate of Pathfinding with 2D, non-grid based movement over uniform terrain \$\endgroup\$ Nov 18, 2013 at 17:24

1 Answer 1


A simple solution would be to only allows a diagonal movement in the graph you use for pathfinding if both of the corresponding vertical and horizontal cell are clear.

In your case, since C is not clear, you should no be autorized to go from A to B directly.


You must log in to answer this question.

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