Details
A* A-star is a path-finding algorithm similar to Dijkstra's algorithm.
A* uses a heuristic to improve the efficiency of path finding.
A path found using A* is not guaranteed to be the shortest path,
but it usually runs much faster than a pure Dijkstra's algorithm.
1. Look for the function named aStarSearch()
You might start by copying code from dfSearch().
2. Your search will start at the starting position.
Assign a value, or cost, to each neighbor.
Diagonal neighbors have a slightly higher cost. (how much?)
Each node's cost is its parent's cost plus the new cost.
Update each neighbor's parent field.
3. After neighbors have been updated, search the entire grid of Nodes
for the lowest-cost node (that has not yet been visited).
Make this the current Node.
More details will be added as the lab progresses.
Homework
Improvement of A* algorithm.
The image below was produced with pathfind.cpp
An improvement was made to the A* algorithm to produce the path below.
Look at the way the hueristic is being used.
It is a hint, but sometimes a hint can be made too strongly
and have too much effect on the outcome.
See if you can adjust the way the hueristic is being used so that the
A* path looks more intelligent.
Notice how the path above turns before reaching the wall to optimize the
path more than the image above it.
Your lab assignment is to figure this out.
