How to limit path length in A*?

Question

I have a limited number of movement points and the ability to teleport in a maze and would like to find the most optimal path. The only problem is that A* doesn't allow for path limit, which means it could be too long to navigate in this example.

The most optimal path would be the one that tries to get to the target while using the most movement points and the least teleportation actions.

Maze

['o', 'S', 'o']
['o', 'o', 'o']
['o', 'o', 'o']
['o', 'o', 'o']
['o', 'o', 'o']
['o', 'o', 'o']
['o', 'T', 'o']
['o', 'o', 'o']
['o', 'o', 'o']

• o -- empty cell
• S -- start
• T -- target

^{Obstacles not included for brevity.}

Rules

• agent only has 5 movement points
• teleportation is allowed which advances by exactly 2 squares

Graph

• each adjacent cell is connected with cost 10 (for walking)
• each cell that is 2 cells away from the current one is set to 22 (11 cost per cell when teleporting)

Current behavior

The algorithm will try to use 6 movement points, as it is the cheapest path.

Optimal path

• jump south by 2 cells
• go 4 cells south

^{the reverse works too}

Code

The code for heuristic doesn't expose the entire path which means I cannot stop it before it goes too far.

astar(
    from_position,
    |point| get_connections_for_point(point),
    |point| point.distance_to(to_position),
    |point| point == to_position,
);

I tried setting the teleportation cost lower, but it results in the algorithm using that over regular walk, which isn't right, as teleportation is more costly.

I tried setting the teleportation cost to be the same as the walking cost, but the algorithm also prefers teleportation as it produces fewer cells in the returned Vec.

Answer 1

One potential solution I found is to set both costs to the same value, and iterate over all paths returned by the A* algorithm and find the one that has the fewest teleportations and the one that reaches the target based on the movement points available and used.

// get a collection of paths
astar_bag(
    from_position,
    |point| get_connections_for_point(point),
    |point| point.distance_to(to_position),
    |point| point == to_position,
);