A* Search

Instruction

A* algorithm is a complete search algorithm, if a solution exists it will find it.

A* algorithm prioritize its search using a cost function c(n) = g(n) + h(n), where g(n) is known path cost to node n and h(n) is the estimated cost from node n to target. In this simulation, h(n) is simply the Manhattan distance scaled by factor of 2 to have impose stronger guidance.

A* is said to be admissible, therefore optimal, if and only if the heuristic function h(n) never overestimate the true cost.

Instructions

1. Select source and destination coordinates
2. (Optional) To introduce obstacles, click on any tile. Obstacle tiles are black
3. Click the Start button run simulation

Color code

■ : Obstacles tile

■ : Source tile

■ : Visited tiles

■ : Target tile & path to target

■ : Unvisited tiles

Logs