A* Visualizer
An application built with the Qt framework that allows users to build custom 2d environments. The user can click on the environment to build obstacles themselves or click a button to generate obstacle blocks at random. The user can select between a Uniform Cost (brute force) or A* (heuristic best first) search. The optimization that results by using an A* search over the brute force Uniform Cost search is visible in that the algorithm expands nodes that show the most promise. The visualization shows that nodes expanded under A* seem to move “towards” the solution.
Below is a brief demo of the app, and the code is availible on my GitHub here
This application uses the A* algorithm to plan a path within a 2 dimensional environment where the agent can move up, down, left, or right. A* can be used, however, in any searching algorithm that can be modeled as a graph of expandable nodes.
The Uniform Cost algorithm can be considered a brute-force approach, as it checks all possible paths from start to finish without discrimination and finishes as soon as it finds any result
A* check all possible paths as well, but checkes the paths that look the best first, using a heuristic. The specific hueristic used is the meaure of Euclidean distance to the goal node. Becuase this hueristic is will never overestimate its length, A* gaurentees giving the shortest path possible.