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\$ – ratchet freak Nov 18 '13 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 '13 at 11:10
  • \$\begingroup\$ A* doesn't impose limitations on the graph; only on the heuristic \$\endgroup\$ – ratchet freak Nov 18 '13 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\$ – MichaelHouse Nov 18 '13 at 15:17
  • 1
    \$\begingroup\$ possible duplicate of Pathfinding with 2D, non-grid based movement over uniform terrain \$\endgroup\$ – BlueRaja - Danny Pflughoeft Nov 18 '13 at 17:24

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.