1
\$\begingroup\$

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.

traditional jump point search

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?

\$\endgroup\$
  • \$\begingroup\$ Okay I've read the question but never come across the search. It's very easy to prove that shortest path algorithms work, please state in pseudo-code what your proposed algorithm will do and I'll see if I can prove or disprove its fitness tonight. \$\endgroup\$ – Alec Teal Sep 22 '15 at 15:33
  • \$\begingroup\$ @AlecTeal I'm proposing a modification to Jump Point Search that would allow it to work with weighted grids. For more information about Jump Point Search look here and here. \$\endgroup\$ – TheNumberOne Sep 22 '15 at 15:57
  • \$\begingroup\$ By weighted grids you mean ones of non-uniform "gaps"? \$\endgroup\$ – Alec Teal Sep 22 '15 at 15:59
  • \$\begingroup\$ Okay this is good! Sorry to not know of it (A* and navmeshes have been my bread and butter for years) - if you don't hear from me (nor get an answer) please do drop me a comment tomorrow. \$\endgroup\$ – Alec Teal Sep 22 '15 at 16:01
  • \$\begingroup\$ I wasn't sure if I had heard of the jump-point algorithm, but now I actually remember reading the first page you linked to. Your proposal sounds like it should work; may I ask what went wrong? \$\endgroup\$ – ETHproductions Sep 24 '15 at 18:41
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.