3 ms·
Sure, but then you have to visit all the adjacent node to deduce whether or not they're lower cost - and that uses equivalent CPU time to A* anyway. A* has been
by Schwolop 13y ago
Sure, but then you have to visit all the adjacent node to deduce whether or not they're lower cost - and that uses equivalent CPU time to A* anyway. A* has been formally proven to be faster than any other graph algorithm using the same heuristic. I do wish people would stop trying to beat it by constraining the rules of the game!
- philsnow 13y agoI'm confused. JPS checks whether an adjacent node is a "wall" (or otherwise-arbitrarily-high cost node), and uses that information to either keep going in the same direction or add more "open" nodes. It seems that it assumes each node has "local" information about local nodes. I think JPS's main contribution is that there are fewer "open" nodes added over the life of the algorithm than A*, right ? The number of open nodes is roughly the "branching factor", and reducing that reduces the total amount of work done.