4 ms·

JPS assumes a very particular geometric structure, i.e., a grid with uniform weights, while A* is much more general and works on any graph with arbitrary edge w

by davmre 13y ago

JPS assumes a very particular geometric structure, i.e., a grid with uniform weights, while A* is much more general and works on any graph with arbitrary edge weights. So there are lots of problems where the JPS tricks don't apply, but you can still use A*.

goldfeld 13y ago
What if each tile had a different attrition score (not necessarily making movement slower but e.g. consuming more resources in a game)? Would that conceptually be the be same as edge weights and thus more fit for A*?
- davmre 13y ago
  Yes, you could represent the score of a tile as the cost of an edge leading into (or out of) that tile. I don't know if it's possible to generalize any of the JPS ideas to this setting (my guess is that it'd be tricky), but basic A* would definitely work.
philsnow 13y ago
I haven't looked at the paper. JPS might be generalizable to graphs with non-uniform weights, by considering adjacent nodes with _lower_ cost than the current node as a "forced neighbor" (to use the term from the link).
- 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 ago
    I'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.

by davmre 13y ago

goldfeld 13y ago

What if each tile had a different attrition score (not necessarily making movement slower but e.g. consuming more resources in a game)? Would that conceptually be the be same as edge weights and thus more fit for A*?

davmre 13y ago
Yes, you could represent the score of a tile as the cost of an edge leading into (or out of) that tile. I don't know if it's possible to generalize any of the JPS ideas to this setting (my guess is that it'd be tricky), but basic A* would definitely work.

philsnow 13y ago

I haven't looked at the paper. JPS might be generalizable to graphs with non-uniform weights, by considering adjacent nodes with _lower_ cost than the current node as a "forced neighbor" (to use the term from the link).

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 ago
  I'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.