Jump Point Search with Weights

Question

Everywhere I've searched on the internet, people seem to assume that jump point search would not work with weighted grids. So why wouldn't it work with this simple modification to the algorithm:

This diagram here illustrates the circumstances that the traditional jump point search algorithm would add the node x to the open set.

_{Please note that the black squares are numbered 2 and 4 respectively.}

In these two images, the reason x is added to the open set is because the optimal paths to the circled squares from the parent of x must go through x. I propose, that if any path going through x from the parent of x to a node around x is lighter than the corresponding path going around x, x should be expanded.

Example psuedocode:

Please note that weightOfPath should return infinity if any of the nodes are impassable.

Horizontal case:

if weightOfPath(4,x,3) < weightOfPath(4,2,3) or weightOfPath(4,x,8) < weightOfPath(4,7,8):
    addToOpenNodes(x);

Diagonal case:

if weightOfPath(6,x,1) < weightOfPath(6,4,1) or weightOfPath(6,x,8) < weightOfPath(6,7,8):
    addToOpenNodes(x);

Why wouldn't this work?

Answer 1

My thought is that JPS makes the assumption of things being symmetrical. Meaning two possible paths can give you the same path.

The problem when you add weights, some behavior becomes really undefined.

When an expansion hits a wall, it just stops. Period. It doesn't even create a new point.

But when it passes by a wall, and detects a space is open after the wall that a previous expansion couldn't get to it stops and creates a jump point.

My best guess is that you'd need to treat any areas with additional weights as just that. An area with an additional weight, and not create a new jump point when you enter, leave, or pass by.

This would mean that logically we'd be saying that we're just slowing down. But the route can get to the same place.

This is best seen as, "What can get me there faster" than "what is the shortest path". The shortest path could obviously lead you through quick sand that's only two feet deep. But the fastest is likely around it.