游戏服务端中的A*寻路算法
#ifndef __ASTAR_SERACH_ALGO_H__
?#define __ASTAR_SERACH_ALGO_H__
?#include <Algorithm>
???
? namespace fredazsq
? {???
? namespace linghuye
? {???
????
?/**//*************************************************
?** 寻路节点
?*************************************************/
?template<typename TNodeLocation>
?struct TAXNode
?{???
???? float?????? G, F;
???? TNodeLocation? pos;
???? TAXNode*?? pParentNode;
???? bool?????? bClosed;??????? // 使用状态表明节点处于开放或关闭列表.
???
???? bool operator<(const TAXNode& node) const
???? {???
???????? return pos < node.pos;
???? }???
?};???
??
?/**//******************************************************************************
?**? 封装A*寻路算法
?*******************************************************************************
?**? 作为棋盘信息提供类TField必须实现下列函数:
?**? 1. bool IsFieldThrough(TNodeLocation pos) const;??????????????????????????????????? 在 pos 位置是否为空,可通行.
?**? 2. float EvaluateStepCost(TNodeLocation posFrom, TNodeLocation posTo, TNodeLocation posLastStep) const;??????? 计算pos1,pos2到单步代价.
?**? 3. float EvaluateProbableCost(TNodeLocation posFrom, TNodeLocation posTo) const;??? 计算pos1,pos2到估算代价.
?**? 4. TNodeLocation* QueryNeiborLocations(TNodeLocation pos, int& nNodeCount); const??? 询问pos的相邻可通节点集
?*******************************************************************************
?**? TNodeLocation,节点位置
?**? 1.支持<,==,=操作符,如int.
?*******************************************************************************
?**? 0. 初始化时传入棋盘信息提供类的实例引用.
?**? 1. 使用主函数SearchPath进行搜索,使用QueryResultPath取得结果.
?******************************************************************************/
?template<class TField, class TNodeLocation>
?struct CAStar2DAlgo
?{???
?public:
???? typedef std::vector<TNodeLocation>??? CResultPath;
???? typedef TAXNode<TNodeLocation>??????? CAXNode;
???? typedef std::set<CAXNode>??????????? CAXNodeSet;
????
???? struct CAXNodePriorityQueue??????????? // 优先队列
???? {???
???????? std::vector<CAXNode*> m_heap;
????????
???????? static bool AXNodeCostSortPred(CAXNode* n1, CAXNode* n2)
???????? {???
???????????? return (n1->G + n1->F) > (n2->G + n2->F);
???????? }
????????
???????? void push(CAXNode* pNode)
???????? {
???????????? m_heap.push_back(pNode);
??????????? std::push_heap(m_heap.begin(), m_heap.end(), &CAXNodePriorityQueue::AXNodeCostSortPred);
???????? }
????????
??????? CAXNode* pop()
??????? {???
???????????? CAXNode* pNode = m_heap.front();
??????????? std::pop_heap(m_heap.begin(), m_heap.end(), &CAXNodePriorityQueue::AXNodeCostSortPred);
???????????? m_heap.pop_back();
???????????? return pNode;
???????? }
???????
??????? bool empty()
??????? {
??????????? return m_heap.empty();
???????? }
????????
??????? void resort(CAXNode* pNode)
??????? {???
???????????? std::vector<CAXNode*>::iterator it = std::find(m_heap.begin(), m_heap.end(), pNode);
?????????? std::push_heap(m_heap.begin(), it, &CAXNodePriorityQueue::AXNodeCostSortPred);
???????? }
????????
??????? void clear()
?????? {
???????????? m_heap.clear();
???????? }
???? };???
??????
?public:???
?? const TField& m_field;
???? TNodeLocation? m_posTarget;
???? CAXNode* m_ptrTargetNode;??????????????????? // Result Node
???????
??? CAXNodeSet m_setNodes;??????????????????????? // All nodes in use
??? CAXNodePriorityQueue m_queOpenNodes;??????? // Cost sorted open list
???????
public:???
??? CAStar2DAlgo(const TField& field) : m_field(field), m_ptrTargetNode(NULL)
??? {???????
??? }???
???????
??? ~CAStar2DAlgo()
?? {???
??? }???
???????
??? void Reset()
??? {???
?????? m_setNodes.clear();
??????? m_queOpenNodes.clear();
??????? m_ptrTargetNode = NULL;
??? }???
???????
public:???
?? inline CAXNode* ClaimNode(TNodeLocation pos, CAXNode* pParentNode = NULL)
??? {???
??????? CAXNode node;
??????? node.pos = pos;
?????? node.F = node.G = 0;
??????? node.bClosed = false;??? // Default is open
??????? node.pParentNode = pParentNode;
??????? return &(*m_setNodes.insert(node).first);
??? }???
???????
??? bool SearchPath(TNodeLocation posStart, TNodeLocation posTarget)
??? {???
?????? CAXNode* pCurNode;
??????? m_posTarget = posTarget;
???????
??????? // Add start node into open list
??????? CAXNode* pStartNode = ClaimNode(posStart);
??????? m_queOpenNodes.push(pStartNode);
???????
?????? while(!m_queOpenNodes.empty())
??????? {???
?????????? // Pick lowest cost node
?????????? pCurNode = m_queOpenNodes.pop();
???????????
??????????? // Check search target
??????????? if(pCurNode->pos == m_posTarget)
??????????? {
??????????????? m_ptrTargetNode = pCurNode;
??????????????? return true;
??????????? }
???????????
??????????? // Switch node from OpenList to CloseList
?????????? pCurNode->bClosed = true;
?????????? ProcessNeighborNodes(pCurNode);
??????? }
??????
??????? return false;
??? }
???????
?? void ProcessNeighborNodes(CAXNode* pCurNode)
??? {???
??????? CAXNode tempNode;
??????? int nNodeCount = 0;
?????? TNodeLocation* pLocs = m_field.QueryNeiborLocations(pCurNode->pos, nNodeCount);
?????? TNodeLocation posLastStep = pCurNode->pParentNode? pCurNode->pParentNode->pos : pCurNode->pos;
??????
??????? // For each neibors
??????? for(int i = 0; i < nNodeCount; ++i)
??????? {???
??????????? tempNode.pos = pLocs[i];
??????????? if(m_field.IsFieldThrough(tempNode.pos))
??????????? {???
??????????????? CAXNodeSet::iterator it = m_setNodes.find(tempNode);
?????????????? if(it == m_setNodes.end())
??????????????? {???
??????????????????? CAXNode* pNewNode = ClaimNode(tempNode.pos, pCurNode);
?????????????????? pNewNode->G = pCurNode->G + m_field.EvaluateStepCost(pCurNode->pos, pNewNode->pos, posLastStep);
??????????????????? pNewNode->F = m_field.EvaluateProbableCost(pNewNode->pos, m_posTarget);
?????????????????? m_queOpenNodes.push(pNewNode);
?????????????? }???
??????????????? else if(!it->bClosed)
??????????????? {???
??????????????????? CAXNode& node = *it;
??????????????????? float G = pCurNode->G + m_field.EvaluateStepCost(pCurNode->pos, node.pos, posLastStep);
??????????????????? if(G < node.G)
??????????????????? {???
?????????????????????? node.G = G;
??????????????????????? node.pParentNode = pCurNode;
??????????????????????? m_queOpenNodes.resort(&node);
??????????????????? }
??????????????? }
??????????? }
??????? }
??? }
???
?? /**//******************************************************************
??? **? 取回最终结果
??? ******************************************************************/
??? bool QueryResultPath(CResultPath& path)
??? {???
?????? if(!m_ptrTargetNode) return false;
???????
??????? CAXNode* pNode = m_ptrTargetNode;
??????? while(pNode)
??????? {???
??????????? path.push_back(pNode->pos);
??????????? pNode = pNode->pParentNode;
?????? }
??????? return true;
?? }
};
/**//*******************************************************************************
**? TNodeLocation,节点位置
**? 1.支持<,== 操作符号.
********************************************************************************/
template<typename TNodeLocation>
struct CShisenFieldImpl
{???
??? TNodeLocation* QueryNeiborLocations(TNodeLocation pos, int& nRetCount) const
?? {???
????? static const int dy[4] = { 1, 0, 0, -1 };
??????? static TNodeLocation posNeibors[4];??? // Single thread
???????????????
??????? nRetCount = 4;
?????? for(int i = 0; i < 4; i++)
?????? {
??????????? posNeibors[i].x = pos.x + dx[i];
??????????? posNeibors[i].y = pos.y + dy[i];
??????? }
?????? return posNeibors;
??? }
???
??? float EvaluateStepCost(TNodeLocation posFrom, TNodeLocation posTo, TNodeLocation posLast) const
?? {???
??????? if(((posFrom.x-posTo.x)? &&? (posLast.y-posFrom.y))? ||?
?????????? ((posFrom.y-posTo.y)? &&? (posLast.x-posFrom.x)))
??????? {???
??????????? return 100;
??????? }
??????? else return 1;
??? }
???
??? float EvaluateProbableCost(TNodeLocation pos1, TNodeLocation pos2) const
??? {
??????? return 0;
??? }
???
/**//*??? 平滑优化
??? float EvaluateStepCost(MY_POSITION posFrom, MY_POSITION posTo, MY_POSITION posLast) const
??? {???
??????? int cx1 = posTo.x - posFrom.x;
??????? int cy1 = posTo.y - posFrom.y;
??????? int cx2 = posFrom.x - posLast.x;
??????? int cy2 = posFrom.y - posLast.y;
??????? return ((cx1 == cx2? &&? cy1 == cy2)? 0 : 10) + ((cx1? &&? cy1)? 14 : 10);
??? }
*/???
};???
???
/**//*******************************************************************************
**? 最小路径
*******************************************************************************/
template<typename TNodeLocation>
struct CShortestPathFieldImpl
{???
??? TNodeLocation* QueryNeiborLocations(TNodeLocation pos, int& nRetCount) const
??? {???
??????? static const int dx[4] = { 0, -1, 1,? 0 };
??????? static const int dy[4] = { 1,? 0, 0, -1 };
??????? static TNodeLocation posNeibors[4];??? // Single thread
???????????????
??????? nRetCount = 4;
??????? for(int i = 0; i < 4; i++)
??????? {
??????????? posNeibors[i].x = pos.x + dx[i];
??????????? posNeibors[i].y = pos.y + dy[i];
??????? }
??????? return posNeibors;
??? }
???
??? float EvaluateStepCost(TNodeLocation posFrom, TNodeLocation posTo, TNodeLocation posLast) const
??? {???
??????? return 1;
??? }
???
??? float EvaluateProbableCost(TNodeLocation pos1, TNodeLocation pos2) const
??? {
??????? return 0;
??? }
};
/**//*******************************************************************************
**? 最小路径
*******************************************************************************/
template<typename TNodeLocation>
struct CGamePathFieldImpl
{???
??? TNodeLocation* QueryNeiborLocations(TNodeLocation pos, int& nRetCount) const
??? {???
??????? static const int dx[8] = { -1, 0, 1, -1, 1, -1,? 0,? 1 };
??????? static const int dy[8] = {? 1, 1, 1,? 0, 0, -1, -1, -1 };
??????? static MY_POSITION posNeibors[8];
???????
??????? nRetCount = 8;
??????? for(int i = 0; i < 8; i++)
??????? {
??????????? posNeibors[i].x = pos.x + dx[i];
??????????? posNeibors[i].y = pos.y + dy[i];
??????? }
??????? return posNeibors;
??? }
???
??? float EvaluateStepCost(TNodeLocation posFrom, TNodeLocation posTo, TNodeLocation posLast) const
??? {???
??????? if(posFrom.x-posTo.x? &&? posFrom.y-posTo.y)
??????? {
??????????? return 14;
??????? }
??????? else return 10;
??? }
???
??? float EvaluateProbableCost(TNodeLocation posFrom, TNodeLocation posTo) const
??? {
??????? return (abs(posFrom.x-posTo.x) + abs(posFrom.y-posTo.y)) * 10;
??? }
};
}// namespace linghuye
}// namespace fredazsq
#endif//__FIELD_SERACH_ALGO_H__
