Pathfinding

2017/04/20 code

Advent of Code 2016 #13 poses a really fun problem: traversing a maze. This happens to be deeply tied to the Project Euler puzzle that got me hooked on programming.

The goal is to get from the green point to the red point in the fewest number of steps.

You can see the process step-by-step, or just automate the entire process to see the end result.

This algorithm is completely naive. At every step, it just explores every possible possibility for each member at the boundary. The most obvious way to improve this is by using a heuristic.

Pathfinding algorithms are obviously useful for stuff like videogame AI or logistics software, but the graphs traversed can also be abstract. Consider a CPU that is waiting for user input. Knowing its immediate state at some point in time, one could explore all the possible outcomes of user input, and pre-compute the next outcome. Then, whether the user presses this or that button, the next dialog would load instantly.