[mopierotti]

I've spent a lot of time thinking about fast pathfinding in order to speed up my Scala Quoridor AI*[0], and here are some tips/tricks I've learned:

- MPAA (multipath adaptive A*) is great if you need to re-search the same area multiple times as obstacles are introduced. It allows you to feed in the results of previous searches in order to speed up pathfinding.

- JPS (jump point search) looks very appealing in theory because it allows you to significantly reduce the number of "nodes" considered, but I found that the increased overhead in identifying jump points meant it didn't provide a speedup. There might be a way to marry the ideas of MPAA and JPS, but it is very easy to conceptually shoot yourself in the foot with minor conceptual details when getting creative with the algorithms. (As a contrived example, using a ">" when you needed a ">=" might mean you are no longer guaranteed to output the real shortest path in certain situations)

- Instead of using a proper heap for storing open nodes, consider using a bucketed priority queue if your max priority value is a relatively low integer. This means there's an underlying array indexed by priority, which makes push'ing and pop'ing quite fast.

[0] Quoridor takes place on a 9x9 grid, and repeated pathfinding is essential in order to determine how close a player is to their goal, and more broadly whether the goal is even reachable. (In order to even determine the valid moves from a given position, all moves must be checked to see if they make a goal unreachable). I plan to release this within the next few months, including at least 3 decision making "engines": mtdf (a min-max variant), MCTS (parallel with some tricks), and a hybrid involving catboost.

[GuB-42]

9x9 is a really small grid. 81 tiles. Storing all the distances from every tile to every other tile would take 6561 bytes. Fits in a typical L1 cache.

The nice thing about that is that you can use it as a lookup table for your heuristic function instead of the usual straight line. This table can be initialized at the start of each turn, for example using the Floyd-Warshall algorithm with the already placed walls. I managed to significantly speed up my A* on a similar problem using this technique, plus, it is really simple, it was straight A* though, no MPAA or JPS.

[mopierotti]

Interesting idea, thanks! I will probably try this. I had stopped tweaking things too much after implementing MPAA, because most of the searches end up "short circuit"-ing relatively quickly.

With MPAA you preserve all previous shortest paths that have been found (in the form of an Array where array(nodeIndex) points to the nodeIndex of the next node on the path). When attempting to optimistically follow one of these paths, if the algorithm hits a new wall, it will null out the path it took up until the wall. However a future search (or iteration in the same search) may still reuse the part of the shortest path that still exists after the wall.

That said, you're right that it's a tiny grid, and cache behavior can dominate any abstract theoretical properties in surprising ways.

[bigbillheck]

> would take 6561 bytes

3240 if you're nasty.

[gerjo]

JPS is fun; though I struggled to interpret the suggested performance gains by the authors indeed due to the calculation of the jump nodes.

Many years ago I added a visualisation to the JPS implementation of PathFinding.js to visualise this recursive search to find jump nodes - here's an online demo: https://qiao.github.io/PathFinding.js/visual/

[keriati1]

+1 for the bucket queue. I learned about that trick a few weeks ago and in my use cases it cut the time to run A* by around 60-70%.