Now that we have all the support classes, structures, and functions we need for the A* algorithm, it's time to get our hands dirty
bool AStarSearch(string StartName, string GoalName)
if(StartName=="" || GoalName=="") return false;
//Search for Start Location Match
if(StartCityFound==false) return false;
cout<<"\nRecording Exploratory Process:\n"<<"Start Location: "<<
StartName<<"\t Ending Location: "<<GoalName<<endl;
//Get Next Location on the Frontier
while(!Frontier.empty() && (GoalDistance>MinPossibleDistance || GoalFound==false))
if(GoalDistance>MinPossibleDistance || GoalFound==false)
cout<<"Child City not found - Terminating\n";
" - " + ChildCity.Name;
cout<<"Current Expanded Path: "<<ChildCity.AccumulatedPath<<
" Distance: "<<ChildCity.AccumulatedDistance<<endl;
cout<<"Goal Path: "<<GoalPath<<" Distance: "<<
cout<<"\n\nBest Goal Path:\n";
cout<<GoalPath<<" Distance: "<<GoalDistance<<endl;
Figure ISS-12: C++ A* Search Code
It doesn't look too terribly complex. But does it really work? Let's go through the code and check to see if we don't see
any missing steps requiring
and then some magic happens in order to finish the job:
C++ Code for A* Search.
bool AStarSearch(string StartName, string GoalName):
bool returns true on successful goal completion or false on failure.
AStarSearch Yup, that's what we're calling it.
string StartName Ascii string for starting location. Case Sensitive.
string GoalName Academic for A* since all straight line distances are to Budapest.
Everything else will fail.
vector<City>::iterator CityNumber: Index pointer to step through Cities vector.
City CurrentCity: City data structure to extract elements from Cities vector.
City StartCity: City data structure used to match StartName parameter sent by calling routine.
City ChildCity: City data structure used to give possible expansion paths.
Neighbor CurrentNeighbor: Temporary data structure used to extract data from Neighbors structure.
bool StartCityFound=false: Flag indicating success or failure of finding a match for the start location.
bool GoalFound=false: Flag indicating success or failure on finding a match for the goal location.
int MinPossibleDistance=0: Comparison value used to find Best Cost route.
int GoalDistance=0: The current best goal distance value found.
string GoalPath: string used to record most recent goal path found. if(StartName=="" || GoalName==""): If they sent an empty string, we might as well pack it up and call it a day.
Search Cities vector for Start Location Match
CityNumber=Cities.begin(): Place index at first element of Cities vector.
CityNumber<Cities.end(): Check against last entry of Cities vector.
CityNumber++: Increment index by one to access each element.
CurrentCity=*CityNumber: Transfer data from vector into Current City object.
if(CurrentCity.Name==StartName): Test for match.
StartCity=CurrentCity: Make a copy once the match is found.
StartCityFound=true: Set flag indicating match was found.
StartCity.AccumulatedPath=StartName: This is where the path starts.
if(StartCityFound==false) return false: No match found - No point in searching for the goal. Frontier.push_back(StartCity): Place Start City in the Frontier so we can begin the expansion process.
Process elements in Frontier Priority Queue according to A* rules.
while(!Frontier.empty() && (GoalDistance>MinPossibleDistance || GoalFound==false)):
while (!Frontier.empty(): If the frontier becomes empty - a match was not found. GoalDistance>MinPossibleDistance: Keep search all lower distance paths even after a goal is found.
GoalFound==false): Keep expanding at least until a goal is found.
CurrentCity=FindShortestPath(&MinPossibleDistance): Get the Top Priority Element out of Frontier. if(GoalDistance>MinPossibleDistance || GoalFound==false): Prevents overrun after final goal is found.
Expand all destination possibilities from the current location:
CurrentNeighbor=CurrentCity.NeighborNumber: Transfer data out of Neighbors vector into CurrentNeighbor
if(GetChildCity(CurrentNeighbor, &ChildCity)==false): Get the City that matches the Neighbor.
ChildCity.AccumulatedPath=CurrentCity.AccumualatedPath + "-" + ChildCity.Name:
Keep a record of the path taken to get here.
The distance traveled to get to the new location is located in the Neighbor structure.
if(ChildCity.Name==GoalName): Have we found a possible path yet?
GoalPath=ChildCity.AccumulatedPath: Child City contains a record of Path taken and distance to get there. Frontier.push_back(ChildCity): Save the city in the Frontier for possible expansion.
Print out the results and exit.
Seems like it should work. Only having 1 destination keeps things simple, multiple destinations could get a little ugly with A*.
Before we compile and run, C/C++ is a little picky about prototypes and headers, so we better run a quick checklist to make sure they are all there:
C++ A* Search Headers & Prototypes
using namespace std;
bool GetChildCity(Neighbor, City*);
City FindShortestPath(int *LowestPathDistance);
bool AStarSearch(string, string);
Figure ISS-13: C++ Headers & prototypes for A* Search
If one of your prototypes is missing the compiler will complain and ask you to fix it. Let's put in
main() which should give
us a complete program:
Figure ISS-14: C++ main function for A* Search
All right then, let's run it as a
console application in windows or linux and see if the output matches diagram
Figure ISS-15: Output of C++ A* Search algorithm for Romanian Map Problem
The results are entirely from cut and pasted code on this webpage. If the results don't work for you, it is probably something
trivial like a character didn't get copied over or something. I didn't try it on Windows, I ran it on the Linux server that is my webhost, and I used the
Well, that completes AI topics for now. The current push is going to
be some game programming using C#. If you wish to try your hand @
and the corresponding C# code: Microsoft XNA Game programming