The A* search algorithm is to find a path to the given goal node with the smallest cost.
At each iteration of the algorithm, A* determines which of its paths to extend. It does so based on the cost of the path and an estimate of the cost required to extend the path all the way to the goal. Specifically, A* selects the path that minimizes
f(n) = g(n) + h(n)
wheren
is the next node on the path,g(n)
is the cost of the path from the starting node ton
, andh(n)
is a heuristic function that estimates the cost of the cheapest path fromn
to the goal. (wikipedia)
.
|--- src/AStarSearchAlgorithm.hpp: the A* search header file
|--- src/AStarSearchAlgorithm.cpp: the A* search algorithm
|--- src/test.cpp: algorithm testing examples
|--- src/main.cpp: main function to run the algorithm
|--- src/makefile: compile scripts
|--- data/1.board: text file of a rectangle grid
-
One should provide a text file with a fixed format for each line, which is a number followed by a comma where the number are
0
or1
. For example,1,0,0,0,0,
. See1.board
for more details. -
Enter the starting and goal point: row and column (index starts from 0)
Note: the starting point can be empty
0
or obstacle1
.
$ make build && ./a.out
Note:
i
is the initial point,0
is empty,x
is obstacle,*
is path, andG
is goal.
I set up auto-testing for the algorithm itself which will run every time when pushing to the repo (see Action
tab for more details). You can also test the algorithm locally with the following scripts:
$ make test && ./a.out
To delete the object file, run make clean
.