At the risk of being either laughed or flamed off the planet...

I wrote what I hope to be a very generic A* implementation using templates. I had wrestled with tyring to do this same sort of thing using a class hierarchy, but it became very unweildy very quickly. I haven't had much experience with templates, so I thought this might be a good place to start. All that being said, below are the two clases that seem to be serving me very well right now. Any comments and constructive criticisms are welcome.

Here's the GraphSearch class which does the actual search.
[source lang="cpp"]/**
@author Robert Kirk DeLisle rkdelisle@gmail.com
@version 0.1
@section LICENSE
@section DESCRIPTION
GraphSearch Template Class
Provides different graph search/pathfinding algorithms.
Currently:
Dijkstra
A*
IDA*
Fringe Search
Usage: GraphSearch<Searchable, Heuristic>
Searchable class:
Any class intended to serve as a node within a graph for the search.
Must implement:
std::string GetUID() - retrieve a globally unique ID for the node
vector< Searchable * > GetNeighbors() - get all valid neighbors of this node from the graph
float G() - retrieve the G value (cost thus far) for this node
void G(float value) - set the G value for this node
float GetCostToExpand() - how much did it cost to expand this node from the parent
Searchable * GetParentNode() - retrieve a pointer to the parent node. If null, assumed to be the start location of the search
std::string GetGeneratingTransform() - what is the parsable transform that led to generation of this node from the parent
a vector of these will be stored as the solution/path from Start to Goal
void ReplaceNode( Searchable * ) - used to replace one node (the caller) with another (the parameter) in the search
this will maintain the order of the nodes in the list and apply the correct costs
if we find a shorter path to a node after first evaluating it
These functions need to be defined to operate on the Searchable class:
bool NodeSort( Searchable &left, Searchable &right ) - sorting algorithm used by GraphSearch to maintain search priority returns (left.F() > right.F())
bool IsGoal( Searchable * ) - is this node the goal?
Heuristic Template Class:
A class providing a function to calculate the appropriate heuristic for the search.
Implements:
float ComputeH( Searchable & ) - compute and store the heuristic for the passed node
Note: for Dijkstra, ComputeH() returns 0.0
*/

#ifndef GRAPHSEARCH_12Oct12_RKD
#define GRAPHSEARCH_12Oct12_RKD
#include <vector>
#include <map>
#include <string>
#include <algorithm>
#include <iostream>
template<class Searchable, class H>
class GraphSearch
{
private:
/** The priority queue will be a vector managed by std::algorithm::make_heap(), ::push_heap() and ::pop_heap(). */
std::vector<Searchable *> vpq_open_list;
/** To facilitate searching the priority queue, a std::map will be maintained in parallel. */
std::map<std::string, Searchable *> map_open_list; //
/** Closed list will be a std::map to facilitate easy searching */
std::map<std::string, Searchable *> map_closed_list;
/** Vector to hold the solution.
Each entry correponds to the results of Searchable::GetGeneratingTransform() moving from
node to node in the search space.
Each transformation is a string that comes from Searchable::GetGeneratingTransform() and correcponds
to a transormation applied to the object represented by the node.
*/
std::vector<std::string> m_Solution;
bool m_SolutionFound;
/** Store the transformations necessary to move from the Start node to the Goal node.
Each transformation is a string that comes from Searchable::GetGeneratingTransform() and correcponds
to a transormation applied to the object represented by the node.
*/
std::vector<std::string> StorePathToGoal(Searchable *);
//capture the path to the goal once it is found
//return the length of that path
/** Delete dynamic objects stored in open and closed lists */
void FreeLists();
public:
/** Default constructor. Initialize necessary variables. */
GraphSearch() { Init(); };
/** Initialize object variables. */
void Init()
{
m_SolutionFound = false;
m_Solution.clear();
vpq_open_list.clear();
map_open_list.clear();
map_closed_list.clear();
};
/** The A* Search Algorithm
\param *Start - Pointer to the start node as a Searchable object.
\param *heu - Heuristic object to be used by the algorithm.
\return true if a solution is found
false if the search space is fully evaluated and no solution is found
*/
bool AStar(Searchable *Start, H heu);
/** Retrieve the solution/path from Start to Goal */
std::vector<std::string> GetSolution()
{
return m_Solution;
};
/** Default destructor */
~GraphSearch() {};
};

template<class Searchable, class H>
bool GraphSearch<Searchable, H>::AStar(Searchable *Start, H heu)
{
//run A* from the start node to the goal node
//if a solution is found, store it in the m_Solution variable
//and return "true", otherwise, return "false"
Searchable *current;
std::vector<Searchable *> neighbor_list;
Init();
vpq_open_list.push_back(Start);
std::make_heap(vpq_open_list.begin(), vpq_open_list.end(), NodeSort);
map_open_list[ Start->GetUID() ] = Start;
Start->G(0.0);
while (!vpq_open_list.empty())
{
std::pop_heap(vpq_open_list.begin(), vpq_open_list.end(), NodeSort);
current = vpq_open_list.back();
if ( IsGoal(current) )
{
m_SolutionFound = true;
StorePathToGoal( current );
//take the Start out of the lists so that it doesn't get deleted
map_open_list.erase(Start->GetUID());
map_closed_list.erase(Start->GetUID());
FreeLists();
return true;
}
vpq_open_list.pop_back();
map_open_list.erase( current->GetUID() );
map_closed_list[ current->GetUID() ] = current;
neighbor_list = current->GetNeighbors();
for( typename std::vector<Searchable *>::iterator it=neighbor_list.begin(); it != neighbor_list.end(); it++ )
{
if ( map_closed_list.find( (*it)->GetUID() ) != map_closed_list.end() )
{
delete *it;
continue;
}
if ( map_open_list.find( (*it)->GetUID() ) != map_open_list.end() )
{
typename std::map<std::string, Searchable *>::iterator ol_it = map_open_list.find( (*it)->GetUID() );
if ( (*ol_it).second->G() > current->G() + (*it)->GetCostToExpand() )
{
(*ol_it).second->ReplaceNode( (*it) );
(*ol_it).second->G( current->G() + (*it)->GetCostToExpand() );
(*ol_it).second->H( heu.ComputeH( (*ol_it).second ));
std::make_heap(vpq_open_list.begin(), vpq_open_list.end(), NodeSort);
}
delete *it;
}
else
{
(*it)->G( current->G() + (*it)->GetCostToExpand() );
(*it)->H( heu.ComputeH( (*it) ));
map_open_list[ (*it)->GetUID() ] = (*it);
vpq_open_list.push_back( (*it) );
std::push_heap(vpq_open_list.begin(), vpq_open_list.end(), NodeSort);
}
}
}
m_SolutionFound = false;
return false; //if we get here, we've exhaused the entire search space
}
template<class Searchable, class H>
std::vector<std::string> GraphSearch<Searchable, H>::StorePathToGoal(Searchable *current)
{
//capture the path to the goal once it is found
//return the length of that path
m_Solution.clear();
if ( !m_SolutionFound )
return m_Solution;
while( current->GetParentNode() != 0 )
{
m_Solution.push_back( current->GetGeneratingTransform() );
current = current->GetParentNode();
};
std::reverse(m_Solution.begin(), m_Solution.end());
return m_Solution;
}
template<class Searchable, class H>
void GraphSearch<Searchable, H>::FreeLists()
{
for ( typename std::map<std::string, Searchable *>::iterator it=map_open_list.begin(); it!=map_open_list.end(); it++)
delete (*it).second;
map_open_list.clear();
for ( typename std::map<std::string, Searchable *>::iterator it=map_closed_list.begin(); it!=map_closed_list.end(); it++)
delete (*it).second;
map_closed_list.clear();
}
#endif
[/source]


This is an example of a Heuristic Class that is used by GraphSearch. The only necessary function is ComputeH but I put in the option to pick from multiple heuristics before it is passed to GraphSearch.

[source lang="cpp"]/**
@author Robert Kirk DeLisle rkdelisle@gmail.com
@version 0.1
@section LICENSE
@section DESCRIPTION
Heuristic Template Class example
For use with GraphSearch Template Class
Provides a heuristic for the 2x2x2 Rubik's Cube
Usage: GraphSearch<Searchable>
Searchable class:
Any class intended to serve as a node within a graph for the search and for which a heuristic is calculated.
Must implement:
ComputeH( Searchable & ) - returns a heuristic estimate of distance to the goal from the passed Searchable node
*/

#include <map>
#include <fstream>
#include <string>
#include <sstream>
#include <iostream>
#ifndef CUBE2HEURISTIC_2012OCT09_RKD
#define CUBE2HEURISTIC_2012OCT09_RKD
template<class Searchable>
class Cube2Heuristic
{
public:
/** For this example, two possible heuristics are available:
DIJKSTRA returns 0.0 as Dijkstra search uses no heuristic
UPDOWNFACE returns the max of the number of turn necessary to properly position (NOT orient) the top corners or the bottom corners.
*/
enum Heuristics
{
DIJKSTRA,
UPDOWNFACE
};
/** Compute the heuristic value
\param *node - Pointer to the node of interest.
\return the computed value
*/
float ComputeH(Searchable *node);
/** For this example, I have set up the ability to pre-select which heuristic you want to use.
\param h - Value from the Cube2Heuristic::Heuristics enumeration
*/
void SetHeuristic( Heuristics h ) { m_SelectedHeuristic = h; };
/** Default constructor. Initialize any heuristics and set a default one to be used. */
Cube2Heuristic()
{
InitUpDownFace();
m_SelectedHeuristic = UPDOWNFACE;
};
/** Default destructor. */
~Cube2Heuristic() {};
private:
/** Holds the pre-computed heuristic.
\param .first - A UID for the 2x2x2 Cube
\param .second - The maximum of the number of turns to properly position (NOT orient) the upper corners or the lower corners.
*/
std::map<unsigned int, int> UpDownFaceHeuristic;
/** Initialize the heuristic */
void InitUpDownFace();
/** Retrieve the precomputed UPDONWFACEHEURISTIC - used by ComputeH()
\param *node - pointer to the node/2x2x2 cube of interest
*/
float GetUpDownFaceHeuristic(Searchable *node);
Heuristics m_SelectedHeuristic;
};
template<class Searchable>
float Cube2Heuristic<Searchable>::GetUpDownFaceHeuristic(Searchable *node)
{
return std::max( UpDownFaceHeuristic[node->GetTopID()], UpDownFaceHeuristic[node->GetBottomID()] );
};
template<class Searchable>
float Cube2Heuristic<Searchable>::ComputeH(Searchable *node)
{
switch ( m_SelectedHeuristic )
{
case DIJKSTRA:
return 0.0;
case UPDOWNFACE:
return GetUpDownFaceHeuristic(node);
default:
return 0.0;
}
}
template<class Searchable>
void Cube2Heuristic<Searchable>::InitUpDownFace()
{
std::fstream HFile;
std::string incomingLine;
int pos, moves;
unsigned int ID;
HFile.open("UpDownFace.heu", std::ios::in);
while ( !HFile.eof() )
{
std::getline(HFile, incomingLine);
pos = incomingLine.find(",");
std::istringstream( incomingLine.substr(0,pos) ) >> ID;
std::istringstream( incomingLine.substr(pos+1) ) >> moves;
UpDownFaceHeuristic[ID] = moves;
}
HFile.close();
};
#endif[/source]