Astarguesser

In this game, you are given a map with obstacles, and your task is to guess how good the A* algorithm will be at finding the shortest path from the entrance to the exit.

What is A*?

Let us start with Breadth First Search (BFS). In this algorithm, we proceed in waves: find all locations next to the source, then next to these locations, etc., until we reach the target. It is obvious that we will find the shortest path to the target this way, and also easy to implement on the computer: all the locations we reach are simply put in a queue, the location we explore next is always the one which was reached the earliest.

In A*, instead, we instead try to more promising directions first. While in BFS, the order is generally based on (the number of steps), in A* it is (the number of steps so far + heuristics), where 'heuristics' is some approximation of the the number of steps we still need to take (for example, the number of steps to the exit, not taking obstacles into account). If the heuristics is 'admissible' (not greater than the actual length of path to the exit) it is also guaranteed to find the shortest path. (See Red Blob Games for more details.)

A* seems to be the goto algorithm used by game developers for pathfinding purposes. But it rarely seems that good (even if the heuristics and tiebreakers are chosen reasonably). Maybe BFS (with its simplicity and good performance tue to the avoidance of priority queues), or some algorithm that takes into account the fact that you are usually pathfinding many times, could be more appropriate for your game?

Source code: https://github.com/zenorogue/astarguesser