harada

Two equivalent paths share the same endpoints and have the same length. Two symmetric paths also have these properties but they can also be shown to be permutations of each other.

Seeing the permutation property isn't straightforward until you change your definition of a path: from an ordered sequence of edges to an ordered sequence of vectors.

Take the following two paths as examples:

p1 = {up, up, up, right, right, right} p2 = {up, right, up, right, up, right}

Not only are they equivalent but I can derive one from the other by just changing the order of the moves.

Such symmetries are plentiful on grid maps: as soon as you have a large open area, you introduce lots of possible ways to cross it.

In the paper we make an apples-to-apples comparison with a recent optimality-preserving state-space reduction method called Swamps and an apples-to-oranges comparison with an approximate pathfinding algorithm, HPA*.

Swamps is a nice technique for narrowing the scope of the current search; it achieves ~5x maximum speedup and could be combined with Jump Point Search to go faster still.

The comparison to HPA is summarised in the article. Additional evaluations are the subject of further work :)

I can see how defining symmetry for a pathfinding domain might be non-intuitive. What the quoted definition is trying to communicate is that paths sharing such a relation are permutations of one another and thus, symmetric.

This behaviour exists because A*'s heuristic function assumes there are no obstacles when estimating the remaining distance to reach the goal. As the difference between the heuristic estimate to the goal and the actual distance increases, some nodes "behind" the start location will appear more promising than other nodes which are eventually proven to be on the optimal path.

This is such a great idea. I donate to charity regularly anyway and I'm a sucker for games. Now I can have both!

I ended up paying $100. Most of the money went to Child's Play but the devs still got $20 and the EFF $10.