Built with: Java
Demo
I made an maze solver/navigator that searches the shortest path to a random goal point (marked as a yellow dot, called Thing). The semi-transparent blue robots are dummy robots used to visualize'searched' paths.
Implementing A* search, I dealt with graph and heuristic cost calculation. A* search is a path-finding, graph-traversal algorithm.
To find the shortest path, the algorithm estimates the costs for all possible paths (that are not blocked by walls) to the goal point. Then, the robot takes the path with least cost. A cost refers to the unit distance from the robot's position to the goal position.
The calculation of an estimated cost is expressed as follows:
f(x) = g(x) + h(x)
where
- f: the total estimated cost of path from the start point to the goal point
- g: the actual cost of the path
- h: herustic. the estimated cost of the path
The robot can turn only in four directions (West, South, East, and North). Therefore, the algorith initially calculates the estimated costs for all possible paths to the goal point, always in these directions. During the path finding, if a dummy robot is blocked by a wall, the searching process stops.
My project can be improved by making this process multi-threaded so as to diminish the searching time (by starting a new thread for each direction).
The heuristic value added to the G cost is the line distance between a point to the goal point. So, the heuristic function exactly looks like the distance between two points formula.