Shortest Path Algorithms – How to Find the Shortest Path with Wormhole Nodes

a staralgorithmsgraphgraph-traversal

example

This is an example of what I want to do via code. I know you can use jump point search to easily get from the green node to the red node with no problems, or even A*. But how do you calculate this with warps.

In the image, you can see that it only takes 8 moves to get from the green node to the red node when taking the blue path. The blue path instantly moves your position from one purple node to the next. The space in the middle that costs 2 moves is a point between two warp zones that you must move to get to.

It is clearly faster to take the blue path, since you only need to move half (roughly) as far as the yellow path, but how do I do this programatically?

For the purpose of solving this problem, let's assume that there are multiple purple "warps" around the graph that you are able to use, AND we know exactly where each purple point will warp to, and where they are on the graph.

Some purple warps are bi-directional, and some are not, meaning, sometimes you can only enter a warp from one side, but not go back after warping.

I've thought about the solution, and only concluded that I would be able to calculate the problem by checking the distance to each warp point (minus the uni-directional points), and the difference between those points, and the points close to them.

The program would have to figure out somehow that it is more beneficial to take the second warp, instead of walking from the first jump. So, instead of moving 6 spots, then warping, then moving the remaining 8 steps by foot (which is also faster than not using warps at all), it would take the 6 moves, then the two moves to the second warp.

EDIT: I realized the blue path will actually take 12 moves, instead of 8, but the question remains the same.

Best Answer

Most path finding algorithms are defined in terms of graphs, not in terms of grids. In a graph, a connection between two otherwise distant nodes is not really a problem.

However, you have to take care with your heuristics. With wormholes, the minimum distance between two nodes is no longer the euclidean distance and the distance does not satisfy the triangle inequality. Such heuristics are inadmissible for A*. You therefore cannot use A* easily.

Of course path finding algorithms like Dijkstra that do not use a heuristic will still work. This is more like a breadth-first search and will select your wormholes without extra effort. However, Dijkstra will visit more nodes that A* with a good heuristic. (Dijkstra is equivalent to A* with heuristic(x) = 0.)

I think A* will work if you use a heuristic that treats all outgoing wormholes as a wormhole directly to the target: the heuristic may underestimate the distance, but must never overestimate it. I.e. the heuristic would be:

def wormhole_heuristic(x):
  return min(euclidean_distance(x, g) for g in [goal, wormholes...])

For a very accurate heuristic, you can (recursively) add the distance from the wormhole endpoint to the goal or next wormhole. I.e. as a pre-calculation you could perform path finding on the (totally connected) subgraph containing all wormholes and the goal, where the distance between two nodes is their euclidean distance. This may be beneficial if the number of wormholes is far less than the number of reachable cells on your grid. The new heuristic would be:

def wormhole_heuristic(x):
  direct = euclidean_distance(x, goal)
  via_wormhole = min(euclidean_distance(x, w) + wormhole_path_distance(w, goal) for w in wormholes)
  return min(direct, via_wormhole)

As @Caleth points out in the comments, this is all very tunable and we can improve the first wormhole heuristic without doing a full path finding through the wormhole network, by adding the distance between last wormhole exit and the goal. Because we don't know which wormhole exit will be used last and we must not overestimate, we have to assume the exit closest to the goal:

def wormhole_heuristic(x):
  direct = euclidean_distance(x, goal)
  to_next_wormhole = min(euclidean_distance(x, w) for w in wormholes)
  from_last_wormhole = min(euclidean_distance(w.exit, goal) for w in wormholes)
  via_wormhole = to_next_wormhole + from_last_wormhole
  return min(direct, via_wormhole)
Related Topic