Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I have a simple problem. 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:

picture

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?

share|improve this question
1  
don't allow diagonal movement... –  ratchet freak Nov 18 '13 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. –  Wakaka Nov 18 '13 at 11:10
    
A* doesn't impose limitations on the graph; only on the heuristic –  ratchet freak Nov 18 '13 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. –  Byte56 Nov 18 '13 at 15:17
1  

1 Answer 1

up vote 0 down vote accepted

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.

share|improve this answer
    
Nice and simple solution! It works very well for my purposes :) –  Wakaka Nov 20 '13 at 6:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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