CODEWITHSUNDEEP
algorithmpath-findinga-star
PEC
PEC

Reputation: 603

Pathfinding - Jump Point Search - open and closed lists

I wanted to make an efficient pathfinding algorithm so I got into jump point search. I read the publication about it as well as online material. It explains the process very well, however, I couldn't find material on how it should be merged with A*. For example, I am not sure if the algorithm ever tries to add the same node to the open list multiple times, since the algorithm is supposed to eliminate same-length symmetric paths. Should I do a check for that every time before I add a new node or should I add every jump point I find to the open list?

So in a nutshell, I would like to know how to handle the open and closed lists in a jump point search algorithm.

Upvotes: 1

Views: 1306

Answers (1)

BlueRaja - Danny Pflughoeft
BlueRaja - Danny Pflughoeft

Reputation: 86126

Since JPS only works on 8-connected grid-graphs, and 8-connected grid graphs have a consistent heuristic (the Chebyshev or Euclidean distance, depending on your graph), you do not need to add any node to the OPEN list more than once.

Upvotes: 1

Related Questions