The Shape of Search

Algorithm:   Heuristic Weight:   

This is a visualization of the A* search and breadth-first search algorithms on a grid world. Obstacles in the gridworld are represented by black pixels. The A* search algorithm tries to a find a shortest path between the starting location and the goal location. The goal location is centered vertically at the far right edge and the starting location is centered vertically about 50 pixels from the far left. The colors represent the order in which locations were explored by the search. Yellow locations were explored earlier and dark red locations were explored toward the end of the search. Despite the animations, this visualization is not meant to show the speed of the search.

You can choose between A* and Breadth-First search. Try setting a weight on the heuristic (between 1.1 and 1.5) for A*. Increasing the weight causes A* to behave more like a greedy search; finding solutions quickly by pruning much more of the search space at the cost of solution quality. A* is only guaranteed to return the shortest path to the goal with a weight of 1. Increasing the weight leads to longer solution paths.

This visualization was implemented using processing.js.