• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
kirkd

A* implementation with templates - feedback?

0 posts in this topic

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] Edited by kirkd
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0