How to represent shortcut nodes in Java?

Question

How would I implement a shortcut finder into an A* path-finding algorithm? Assume that every tile is represented by an (x,y) coordinate, and I know where every "good" tile and every "non-walkable" tile is on the grid. How could I best find the solution to this problem on a large scale where the starting and ending spots are always different with many different shortcuts and obstacles in the way of each starting point and ending point. What is the most optimal way of finding the shortest path between grid points miles away (assuming each tile represents 1 foot)?

I don't know of any optimizations beyond breadth-first search, but if your grid is small enough, that shuldn't be an issue. I would make a `TraversableNode` interface, which can provide a `adjacentNodes` method which returns a list of adjacent nodes. Then, you could make two clases, `RegularTile`, whose adjacent nodes are its immediate neighbors, and `TeleportTile`, whose adjacent nodes are its immediate neighbors, PLUS all the adjacent neighbors of its "partner". — Alexander, Jun 19 '18 at 16:48

score 2 · Answer 1 · answered Jun 19 '18 at 09:14

A* cannot generally be used with shortcut/jump nodes. This is because A* uses a heuristic, roughly: “walking into the direction of the target is the optimal route, barring any obstacles”. Or more formally: the triangle inequality must hold. The triangle inequality guarantees that taking a detour will result in a longer path. The A* algorithm relies on a heuristic that never underestimates the minimum distance.

However, jump nodes violate this assumption. It is possible to construct a scenario where the shortest path is to run away from your target in order to find a jump node. So the A* heuristic can be misleading. In your example the jump nodes would happen to work fine because they are in line with the direction suggested by the heuristic, but this is not generally the case.

If you want to use A* with jump nodes, you need to adapt the path-finding algorithm to not only search a path towards the target, but also to all jump nodes that are closer than the target (as informed by your heuristic). This is complicated (because you have to update the list of possible jump nodes after a jump) but efficient. Alternatively, you can use a different path finding algorithm, e.g. Dijkstra (which is A* without a heuristic, so a breadth-first search).

Representing the jump nodes is not difficult if you write your A* algorithm in terms of nodes rather than in terms of grid coordinates. Given a node, you will have a neighbours(node) operation that gives its neighbours. These neighbours are typically neighbouring grid points. However, the function can take into account jump nodes, and return the jump target's neighbours instead.

Caleth · Answer 2 · 2018-06-19T17:39:42.377

0

A* is applicable wider than squared grids.

Rather than defining the neighbours of a tile to be only those that differ by one in the X or Y direction, you include any shortcuts and exclude any obstacles.

Start from the pseudocode on Wikipedia

function neighbours(node)
    result := []
    for displacement in [(1,0), (-1,0), (0,1), (0,-1)]
        neighbour := node + displacement
        if passable(neighbour)
            result.Add(neighbour)
    for shortcut in shortcuts[node]
        result.Add(shortcut)
    return result

Then you need to make sure that your distance heuristic never overestimates.

function prepare_heuristic(shortcuts, goal)
    result := Infinity
    for node in shortcuts.values
        result := min(result, displacement(node, goal))
    return result

function distance_heuristic(node, goal)
    return min(shortcut_distance, displacement(node, goal))

This is still an improvement over pure Dijkstra, especially when shortcuts are rare

edited Jun 19 '18 at 17:39

answered Jun 19 '18 at 08:34

Caleth

10,519
2
23
35

You can do this, but the heuristic that distinguishes A* from Dijkstra's algorithm (breath-first search) wouldn't work. – Alexander Jun 19 '18 at 16:43
@Alexander a naive heuristic is inadmissable, but you can still make some improvement over Dijkstra – Caleth Jun 19 '18 at 17:40
From what I can tell, your `prepare_heuristic` function is itself doing a breadth-first search, completely defeating its purpose as being a lightweight approximation that can better inform a breadth-first search. – Alexander Jun 19 '18 at 17:52
`displacement` is the naive `abs(left.X - right.X) - abs(left.Y - right.Y)` calculation – Caleth Jun 19 '18 at 17:55
Ah whoops, I skimmed and thought that was a recursive call – Alexander Jun 19 '18 at 18:03

How to represent shortcut nodes in Java?

2 Answers2