Find path on grid limited by distance

General Grid graph
1
  • A* version: 5.3.8
  • Unity version: 6000.0.58f2

I have a Grid graph with custom diagonal traversal cost (straight cost 1, diagonal cost 2). The costs are defined in a custom GridGraph.

Now, this is a turn based game and I want the enemies to be able to find the path to their targets considering their current movement points, which translate directly to the traversal cost.

Right now I have two ways of interacting the with the graph:

  • ABPath: allows me to find a path to the target, but doesn’t take into account traversal costs.
  • ConstantPath: allows me to find all nodes within the traversable distance.

What I want is a mix of both, an ABPath that provides the best path to the position, up to a specific movement cost.

I’m able to filter the results of the ABPath so that the movement cost is respected, but in some occasions I’m not able to fully utilize all movement points as the path is unaware of the maximum cost, so it sometimes picks diagonals when it’s not possible to move diagonally.

Is there any built in way of doing this? What’s the recommended approach?

2

Hi

What I would suggest is using ABPath, and then post-procesing the path to cut off the part that is outside the agent’s movement capabilities this turn. This avoids the problem of the agent not knowing how to move at all if the target is out of range for 1 turn. But it does mean you need to calculate the movement costs yourself, I’m afraid.

3

Hi, thanks for the swift reply!

My main issue is the last step, if it’s a diagonal step and I only have one movement point remaining, then I cannot complete the path but I can still move.

I would need to treat this case individually, calculating a ConstantPath with distance 1 and checking which which of the resulting points is closer to the target. But I wonder if that’s going to result in the shortest path.

Is that correct or is there any easier way?

4

I you also need to visualize which nodes that the agent can move to… no, I’m not sure if there’s a better way at the moment.