Skip to main content
gamedev.net
🔒 Locked 🤖 Godot

Problems with policy classes

Started by JimPrice Apr 8, 2005 at 7:37 PM 3 replies 550+ views
Original Post
JimPrice
JimPrice
Hi, For my first real foray into the magical, wonderful world of Templates, I'm trying to create a policy-driven A* pathfinding class, and have hit a problem. Wonder if anyone can help. I have the following definition: 

template 
<
	class EndEvaluator,
	class Heuristic,
	class Map,
	class NodeType
> 
class AStarPathFinder : public EndEvaluator, public Heuristic, public Map
{
public:
	// Actually runs the pathfinding
	void FindPath(const Vector2& start, std::vector<Vector2>& actionStack);

private:
	// A wrapper class used to store the pathfinding information
	struct PathFindNode
	{
		PathFindNode(const NodeType* const node, PathFindNode* parent, float G, float H) :
			node_(node), parent_(parent), F_(G + H), G_(G), H_(H) {}
		const NodeType* const node_;
		PathFindNode* parent_;
		float F_;
		float G_;
		float H_;
		bool operator==(const PathFindNode& other)
			{return node_ == other.node_;}
		bool operator==(const NodeType* const other)
			{return node_ == other;}
	};
};
I was using a dummy EndEvaluator class, but have just added a constructor and variable, as follows: 

class SingleEndNode
{
public:
	SingleEndNode(const MapNode* const destination) : destination_(destination) {}
protected:
	bool AtEnd(const MapNode* const test);
private:
	const MapNode* const destination_;
};
The class is called by: 

MapNode* mapNode = new MapNode;
std::vector<Vector2> actions;

// Create the pathfinder
AStarPathFinder<SingleEndNode(mapNode), ManhattanDistance, Map, MapNode> pathFinder;

// Run the pathfinder
pathFinder.FindPath(Vector2(0, 0), actions);
Before I added the parameterised constructor to the template call, everything worked fine. Now I have SingleEndNode taking a parameter, it's all gone pear-shaped - I get the following error messages: c:\Documents and Settings\Owner\My Documents\Visual Studio Projects\Templated PathFinding\Main.cpp(15): error C2974: 'AStarPathFinder' : invalid template argument for 'EndEvaluator', type expected c:\Documents and Settings\Owner\My Documents\Visual Studio Projects\Templated PathFinding\Main.cpp(15): error C2955: 'AStarPathFinder' : use of class template requires template argument list c:\Documents and Settings\Owner\My Documents\Visual Studio Projects\Templated PathFinding\Main.cpp(15): error C2133: 'pathFinder' : unknown size What am I doing wrong? Do I need to construct a SingleEndPoint instance prior to calling the template? Is there any way to get around this? What's going on? I assume this is happening because I'm now trying to derive from an instance instead of from a class - if so, how do I get around this? Thanks in advance for any help, Jim. Edit : OK - so the issue is that I'm trying to inherit from an instance, not a class. But if I want to have the option of 2 different EndEvaluators - the SingleEndNode as above and a MultipleEndNode which contains a vector of MapNode pointers - how do I write the ctor for the PathFinder class? In one case it needs a ctor with a MapNode*, in the other it needs a ctor with a vector of MapNode*'s. [Edited by - JimPrice on April 8, 2005 7:55:22 PM]
snk_kid
snk_kid
Quote:
Original post by JimPrice
But if I want to have the option of 2 different EndEvaluators - the SingleEndNode as above and a MultipleEndNode which contains a vector of MapNode pointers - how do I write the ctor for the PathFinder class? In one case it needs a ctor with a MapNode*, in the other it needs a ctor with a vector of MapNode*'s.


Typically class policies are class templates and in general they should only handle one responbility/aspect/behaviour (for e.g. one policy that deals with memory allocation) and it should be completely isolated from other policies, if they need to know about each then there probably is something wrong with the design. They also don't generally have state they normally encapsulate behaviour.

Anyways what you can do is make your policies class templates and use template template parameters for them instead of type parameters, also it seems to me (for what i understand from your code) that a node is logically part of or goes with or trait of a map so you can have a *map traits* type that provides needed nested types (maybe some static member functions) including the node type for a map e.g.: 

template < typename NodeType >struct evaluator { /*... */ };	// default evalutor policytemplate < typename NodeType >struct heuristic { /* ... */ };	// default heurisitc policytemplate < typename MapType >struct map_traits {	        // traits of a map, default traits can                             // just forward nested types of most map types   typedef MapType	map_type;   typedef typename map_type::node_type node_type;   //...};struct Vector2;template <   typename Map,   typename Traits = map_traits<Map>,   template < typename > class Heuristic  =  heuristic,   template < typename > class Evaluator  =  evaluator> struct AStarPathFinder :	public Map,	public Evaluator< typename Traits::node_type >,	public Heuristic< typename Traits::node_type > {   typedef Traits traits_type;   typedef typename traits_type::node_type node_type;   typedef Heuristic< typename traits_type::node_type > heurisitc_type;   typedef Evaluator< typename traits_type::node_type > evalutator_type;   // Actually runs the pathfinding   template < typename InputIterator >   void FindPath(InputIterator first, InputIterator last, const Vector2& start) const {	for(; first != last; ++first) {	   ///.....    	}   }private:   // A wrapper class used to store the pathfinding information   struct PathFindNode {	typedef const node_type		const_node_type;	typedef node_type*		node_ptr;	typedef const const_node_type*	const_node_ptr;	const_node_ptr node_;	PathFindNode* parent_;	float F_;	float G_;	float H_;	PathFindNode(const_node_ptr node,		     PathFindNode* parent,		     float G, float H)	: node_(node), parent_(parent), F_(G + H), G_(G), H_(H) {}			bool operator==(const PathFindNode& other) const { return node_ == other.node_; }	bool operator==(const_node_ptr other) const { return node_ == other; }    };};///......struct my_map {   struct map_node { /* .... */ };   typedef map_node node_type;};int main() {   AStarPathFinder< my_map > a_star;}


Sorry i can't help that much as i don't know exactly what your trying to do and i don't know the A* algorithm to give anything more useful although the above might give you some ideas, if you maybe described what exactly you want to do i might be able to help more.

[Edited by - snk_kid on April 9, 2005 4:14:57 AM]
JimPrice
JimPrice
Thanks for the reply snk_kid. As I said, this is the first time I've played with something like this, so at this stage I need all the help I can get. I did make a couple of changes last night, but they feel a little hacky and, after reading your response, I think there may be a better way.

First things first though - it's probably best if I explain what I'm trying to do in a little more detail. A* is basically just a node-search over a graph, designed to find the 'shortest' route from one node to another. For the purposes of this exercise , I think most of the mechanics are unimportant, but here are the key points I was trying to separate out:

There's a single start node
There may be a single end node, or there may be several end nodes any of which is suitable for an endpoint. For example, when I run my hide behaviour a list of map-nodes that the enemy can't see is created and a path to the closest one is generated.
Finding the best path is dependent upon the currently travelled distance and a heuristic function that predicts the remaining distance to the target


The classes I had in my original post were:
Map : because you start (or end) at a location that may not be directly situated on a node, Map has to provide a FindNearestNode function that finds the nearest node to the requested location.
MapNode : this is just the mapnode type that is used to represent the graph within the Map class. It also has to provide a typedef to show how it's descendants are stored
EndEvaluator : this has to provide a function with signature bool AtEnd(MapNode*) that evaluates whether the search is over at the current mapnode
Heuristic : has to provide a function with signature float GetHeuristic(MapNOde*) that evaluates the heuristic to the target

Unfortunately there's some problems with this. EndEvaluator contains the target node(s) - but heuristic needs to know about them in order to calculate it's stuff. Oh, and deriving from Map didn't work either, for some reason that now escapes me. So here's what I currently have, as of this morning:

// The MapNode classstruct MapNode{	int index_;	Vector2 location_;	typedef std::vector<std::pair<MapNode*, float> > Connections;	Connections connections_;};// Our EndEvaluatorclass SingleEndNode{public:	SingleEndNode() : destination_(0) {}	void SetEndNode(MapNode* destination) {destination_ = destination;}protected:	bool AtEnd(MapNode* test);	float GetHeuristic(const MapNode* const location, float (*fp)(const MapNode* const, const MapNode* const));private:	MapNode* destination_;};// Some implementationbool SingleEndNode::AtEnd(MapNode* test){	return (test == destination_);}float SingleEndNode::GetHeuristic(const MapNode* const location, float (*fp)(const MapNode* const, const MapNode* const)){	return fp(location, destination_);}// Our Heuristic functionclass ManhattanDistance{public:	static float CalculateHeuristic(const MapNode* const start, const MapNode* const end);};// Some implementationfloat ManhattanDistance::CalculateHeuristic(const MapNode* const start, const MapNode* const end){	return fabs(start->location_.x_ - end->location_.x_) + abs(start->location_.y_ - end->location_.y_);}// Finally our templated master classtemplate <	class NodeType,	class EndEvaluator,	class Heuristic> class AStarPathFinder : public EndEvaluator{public:	// Actually runs the pathfinding	void FindPath(const Vector2& start, std::vector<Vector2>& actionStack, Map* map);private:	// A wrapper class used to store the pathfinding information	struct PathFindNode	{		PathFindNode(NodeType* node, PathFindNode* parent, float G, float H) :			node_(node), parent_(parent), F_(G + H), G_(G), H_(H) {}		NodeType* node_;		PathFindNode* parent_;		float F_;		float G_;		float H_;		bool operator==(const PathFindNode& other)			{return node_ == other.node_;}		bool operator==(NodeType* other)			{return node_ == other;}	};};// And some illustration of some of what's going ontemplate <class NodeType, class EndEvaluator, class Heuristic> void AStarPathFinder<NodeType, EndEvaluator, Heuristic>::FindPath(const Vector2& start, std::vector<Vector2>& actionStack, Map* map){	// Set up some storage - yes, there are much better structures than list, but it's early days!	typedef std::list<PathFindNode> ListType;	typedef ListType::iterator ListIterator;	ListType openList;	ListType closedList;	// Set up our first node on the path	PathFindNode newNode(		map->NearestMapNode(start), 		0, 		0, 		GetHeuristic(map->NearestMapNode(start), typename Heuristic::CalculateHeuristic)		);	openList.push_back(newNode);	ListIterator currentPathFindNode = openList.begin();		// Run the pathfinding section until we've hit the end	while(!AtEnd(currentPathFindNode->node_))	{		// Loop over nodes walkable from the current one		for(			NodeType::Connections::const_iterator walkableNode = currentPathFindNode->node_->connections_.begin(); 			walkableNode != currentPathFindNode->node_->connections_.end();			++walkableNode)		{                        // At this point, lots of exciting things happen                }        }};// And in order to usetypedef AStarPathFinder<MapNode, SingleEndNode, ManhattanDistance> SimplePathFinder;// Run from within the Map classSimplePathFinder pathFinder;pathFinder.SetEndNode(NearestMapNode(end));pathFinder.FindPath(start, actionStack, this);


So - on to your reply. Policies should be independent, huh? Well, let's see - I've got a Map full of MapNodes, and EndEvaluator that relies upon MapNodes to some degree, and a Heuristic function that relies upon the EndEvaluator class. Bugger.

Will have a look at your suggestions about template-template classes - I was thinking about that last night, but couldn't see how to fit it all together.

I'm going to see if I can use what you've written - hope the stuff I've put here gives you a better idea of what I'm trying to achieve!

Thanks,
Jim.

Edit : OK, so I've made EndEvaluator and Heuristic template classes, as they rely upon MapNode (something I hadn't spotted before). Will see whether I need to use the type-traits as well. Will keep on plugging away...

[Edited by - JimPrice on April 9, 2005 2:23:12 PM]
Jingo
Jingo
As a side note, the policy(strategy) pattern does not have to be implemented with templates. You can use an abstract class to define the policy interface, and create a pointer/reference to the abstract class, then use polymorphism to switch between policies. Though that does give you the overhead of at least an extra pointer dereference.

struct policy{virtual void interface() = 0;};struct EndEvaluator : policy{EndEvaluator(MapNode*);void interface();private:MapNode* Node;};struct AStarPathFinder{AStarPathFinder(policy* thepolicy);private:policy* pEndEvaluator_;}int main(){AStarPathFinder finder(new EndEvaluator(mapnode));}


That gives you an easy way to give the policy state information and a way of chaning policies dynamically. Though whether the extra overhead is worth it depends on how often the policy will be called.
JimPrice
JimPrice
Quote:

As a side note, the policy(strategy) pattern does not have to be implemented with templates. You can use an abstract class to define the policy interface, and create a pointer/reference to the abstract class, then use polymorphism to switch between policies.


Yeah, I'd considered that, or using function pointers. But - in all cases I'll know the type of pathfinding I want to run at compile time, so I thought it would be better to create it using templates. Plus it's a good learning experience!

Dynamically changing policies is interesting, and I can see some uses, but in most cases I don't think I'll need it. This is still early stages though (I want to add different distance measures as well at some point, as well as create functions for calculating partial paths, and then I've got to create a manager class that holds a priority queue of pathfind objects, etc etc), so things might change as I develop.

Thanks for the comments,
Jim.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.