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.
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.
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.