astar.h

来自「2002年」· C头文件 代码 · 共 143 行

#ifndef _ASTAR_H
#define _ASTAR_H

#ifdef WIN32
	#pragma warning( disable : 4786)
#endif

#include <vector>
#include <list>
#include <functional>
#include <algorithm>

#ifndef NULL
#define NULL 0
#endif

template <class T> class priority_list : public std::list<T>{
public:
	class T_less : public std::unary_function<T, bool>{
		T d;
	public:
		explicit T_less(const T& data) : d(data) {}
		bool operator() (const T& data) const { return data < d; }
	};

	std::list<T>::iterator oinsert(const T& d){
		std::list<T>::iterator iter;
		iter = std::find_if(begin(), end(), T_less(d));
		return insert(iter, d);
	}
};

/***********A* Algorithm*********************/
template <class T> class Astar{
protected:
	struct Node{
		T d;
		int p_idx;	
		int c_idx;

		Node(const T& data, const int p = -1) : d(data), p_idx(p) {}
		inline bool operator == (const Node& n) const { return bool(d == n.d) ; }
		inline bool operator < (const Node& n) const { return bool(d < n.d) ; }
		inline bool IsRoot() const { return bool(p_idx < 0); }
	};
	typedef priority_list<Node> o_list;
	typedef std::vector<Node> c_list;

	o_list openlist;
	c_list closelist;

	inline const Node& GetPnode(const Node& node) const { return closelist[node.p_idx]; }
	inline Node& GetPnode(const Node& node) { return closelist[node.p_idx]; }

	Node* p_sel;
	int maxscounts;					//max search steps.	Abort if reached
	int scounts;

	bool IsValidSel(){ return bool(p_sel != NULL); }	

	void Reset(){
		openlist.clear(); closelist.clear();
		p_sel = NULL;
	}
	
	virtual void ExtendSel(){};

	/*return value::
		replaced : 2, aborted : 0, normal : 1
	*/
	int TryNode(const Node& d){
		o_list::iterator iter =  std::find(openlist.begin(), openlist.end(), d);
		if(iter != openlist.end()){
			if(iter->d < d.d){
				openlist.erase(iter);
				openlist.oinsert(d);
				return 2;
			}else{
				return 0;
			}
		}
		openlist.oinsert(d);
		return 1;
	}

	bool IsVisited(const Node& d) const{
		c_list::const_iterator t = std::find(closelist.begin(), closelist.end(), d);
		return bool(t != closelist.end());
	}

private:
	void SelToClose(const Node& d){
		closelist.push_back(d);
		p_sel = & closelist.back();
		p_sel->c_idx = closelist.size() - 1;
	}

	bool Select(){			//select top node from openlist for next step
		if(openlist.empty())	return false;

		o_list::iterator sel = openlist.begin();
		Node data = *sel;
		openlist.erase(sel);

		SelToClose(data);
		return true;
	}

public:
	Astar(){
		SetMaxScounts(100);
	}

	inline void SetMaxScounts(int value){
		maxscounts = value;
		closelist.reserve(maxscounts);
	}

	virtual void SetInitial(T& data){
		Reset();

		Node d(data);
		SelToClose(d);
	}

	virtual bool IsTarget(){return false;}

	bool FindOptimalway(){
		if(p_sel == NULL) return false;

		scounts = 0;
		while(scounts++ < maxscounts){
			ExtendSel();
			if(!Select()) return false;
			if(IsTarget()) return true;
		}

		return false;
	}
};

#endif //_ASTAR_H