Watch algorithms find the shortest path through obstacles. Draw walls, generate mazes, and compare how A*, Dijkstra, BFS, DFS, and Greedy Best-First explore differently.
Pathfinding is the problem of finding the shortest (or any) route between two points while avoiding obstacles. It is one of the most fundamental problems in computer science and appears everywhere from GPS navigation to video game AI.
BFS explores all neighbors at the current depth before moving deeper. It uses a queue (FIFO) and guarantees the shortest path in an unweighted grid. You will see it expand in concentric rings outward from the start node. Time complexity: O(V + E).
DFS dives as deep as possible before backtracking. It uses a stack (LIFO) and does not guarantee the shortest path. You will see it snake through the grid in long corridors. Useful for maze generation and topological sorting. Time complexity: O(V + E).
Dijkstra's is the gold standard for shortest path in weighted graphs. It uses a priority queue and always expands the node with the lowest cumulative cost. On an unweighted grid like this, it behaves identically to BFS. Its power shines when edges have different costs (terrain, traffic). Time complexity: O((V + E) log V) with a binary heap.
A* combines Dijkstra's actual cost with a heuristic estimate of remaining distance. Here we use the Manhattan distance heuristic. This guides the search toward the goal, often exploring far fewer nodes than Dijkstra while still guaranteeing the shortest path (when the heuristic is admissible). A* is the most widely used pathfinding algorithm in games and robotics. Time complexity: O((V + E) log V) but with much better average-case performance.
Greedy Best-First uses only the heuristic, ignoring actual cost. It races toward the goal but can be fooled by obstacles, producing longer paths or exploring many nodes when the direct route is blocked. It does not guarantee the shortest path, but can be very fast when the path is relatively unobstructed.
A* beats Dijkstra in most practical scenarios because the heuristic prunes the search space. Dijkstra wins when you need shortest paths to all nodes (not just one destination) or when no good heuristic exists. In game development, A* is almost always the right choice for point-to-point pathfinding.
A heuristic is an educated guess of the remaining cost to the goal. For grid pathfinding, common heuristics include: Manhattan distance (sum of horizontal + vertical distance, used here), Euclidean distance (straight line), and Chebyshev distance (allows diagonal movement). An admissible heuristic never overestimates the true cost, which guarantees A* finds the optimal path.
Pathfinding algorithms are at the heart of game AI. In Tactiko, players make tactical moves on a grid — just like the algorithms finding optimal routes above. Simple rules, deep strategy.
Play Tactiko