Hacker News new | past | comments | ask | show | jobs | submit login

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.




Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: