Hot-Link Menu in Right-Side Column

Last Updated 6-29-2010


C++ A* Search Function Code

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 with the Real McCoy:

bool	AStarSearch(string StartName, string GoalName)
{
	vector<City>::iterator	CityNumber;

	City		CurrentCity;
	City		StartCity;
	City		ChildCity;

	Neighbor	CurrentNeighbor;
	
	bool		StartCityFound=false;
	bool		GoalFound=false;

	int		MinPossibleDistance=0;
	int		GoalDistance=0;

	string		GoalPath;

	if(StartName=="" || GoalName=="") return false;

//Search for Start Location Match

	for(CityNumber=Cities.begin();CityNumber<Cities.end();CityNumber++)
	{
		CurrentCity=*CityNumber;
		if(CurrentCity.Name==StartName)
		{
			StartCity=CurrentCity;
			StartCityFound=true;
			StartCity.AccumulatedPath=StartName;
		}
	}

	if(StartCityFound==false) return false;

	Frontier.push_back(StartCity);

	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))
	{
		CurrentCity=FindShortestPath(&MinPossibleDistance);
		if(GoalDistance>MinPossibleDistance || GoalFound==false)
		{
			for(	CurrentCity.NeighborNumber=CurrentCity.Neighbors.begin();
				CurrentCity.NeighborNumber<CurrentCity.Neighbors.end();
				CurrentCity.NeighborNumber++)
			{
				CurrentNeighbor=*CurrentCity.NeighborNumber;
				if(GetChildCity(CurrentNeighbor, &ChildCity)==false)
				{
					cout<<"Child City not found - Terminating\n";
					return false;
				}

				ChildCity.AccumulatedPath=CurrentCity.AccumulatedPath +
					" - " + ChildCity.Name;
				ChildCity.AccumulatedDistance=CurrentCity.AccumulatedDistance +
					CurrentNeighbor.Distance;
				cout<<"Current Expanded Path: "<<ChildCity.AccumulatedPath<<
					" Distance: "<<ChildCity.AccumulatedDistance<<endl;

				if(ChildCity.Name==GoalName)
				{
					GoalDistance=ChildCity.AccumulatedDistance;
					GoalPath=ChildCity.AccumulatedPath;
					cout<<"Goal Path: "<<GoalPath<<" Distance: "<<
						GoalDistance<<endl;
					GoalFound=true;
				}
				Frontier.push_back(ChildCity);
			}
		}
	}

	cout<<"\n\nBest Goal Path:\n";
	cout<<GoalPath<<" Distance: "<<GoalDistance<<endl;
	cout<<"Evaluation Complete\n";
	return true;
}
						

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

  • for(CityNumber=Cities.begin();CityNumber<Cities.end();CityNumber++):
    • 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:
    • for( CurrentCity.NeighborNumber=CurrentCity.Neighbors.begin():
    • CurrentCity.NeighborNumber<CurrentCity.Neighbors.end():
    • CurrentCity.NeighborNumber++):

  • 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.
  • ChildCity.AccumulatedDistance=CurrentCity.AccumulatedDistance+CurrentNeighbor.Distance:
    • 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?
  • GoalDistance=ChildCity.AccumulatedDistance:
  • 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
#include <stdio.h>
#include <string>
#include <iostream>
#include <vector>

using namespace std;

bool	GetChildCity(Neighbor, City*);

void	MakeMap();

City	FindShortestPath(int *LowestPathDistance);

bool 	AStarSearch(string, string);
						

Figure ISS-13: C++ Headers & prototypes for A* Search


C++ A* Search Main()

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:

int	main()
{
	MakeMap();
	AStarSearch("Arad", "Bucharest");
	return 0;
}
						

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 ISS4:

A* Output

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 g++ compiler.

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 @ Microsoft XNA Game programming and the corresponding C# code:

Press the Button below:


Home


Artificial Intelligence

Big O Notation

NP Completeness

Intelligent Agents


Problem Definition

Formulating Problems

Toy Problems

Vacuum World


8-Puzzle

8 Queens

The Knuth Sequence

Real World Problems

Route Finding Problems

Touring Problems

Traveling Salesperson Problem

VLSI Layout

Robot Navigation

Automatic Assembly Sequencing


Searching For Solutions


Frontier Node Expansion

Search Algorithm Infrastructure

Child Node Creation

Measuring Algorithm Performance


Uninformed Search Strategies

Breadth-First Search

Breadth-First Characteristics

C++ Breadth-First Search Code

Breadth-First Data Structure


Breadth-First Main Program

Breadth-First Make Map

Breadth-First Make Neighbor

Breadth-First Point of Origin


Breadth-First Print Cities

Breadth-First Initial Listing


Breadth-First Path Record

Breadth-First Get Child City

C++ Breadth-First Search Code


Breadth-First Print Goal Path

Uniform-Cost Search


Depth-First Search

Depth-First C++ Solution

Depth-First Data Structure


Depth-First MakeMap()

Depth-First Display Data

Depth-First Initial Listing


Depth-First GetChildCity()

Depth-First Path Record


Depth-First Search Function


Depth-First PrintGoalPath()

Depth-First Main()

Depth-Limited Search


Iterative Depth Search

Bidirectional Search

Comparing Strategies


Informed Search Strategies

Greedy Best-First

A* Search


Conditions For Optimality

Optimality of A*


C++ A* Search Code

A* Search Data Structure

A* Search Data Entry


A* Search GetChildCity()

C++ Min Priority Queue


C++ A* Search Code Function

C++ A* Headers & Prototypes

C++ A* Search Main()


Normalized Information Distance