|
|
 
1 #ifndef __ASTAR_SERACH_ALGO_H__
2#define __ASTAR_SERACH_ALGO_H__
3
4#include <Algorithm>
5
6namespace fredazsq
7 {
8 namespace linghuye
9  {
10
11/**//*************************************************
12** 寻路节点
13 *************************************************/
14template<typename TNodeLocation>
15struct TAXNode
16{
17 float G, F;
18 TNodeLocation pos;
19 TAXNode* pParentNode;
20 bool bClosed; // 使用状态表明节点处于开放或关闭列表.
21
22 bool operator<(const TAXNode& node) const
23 {
24 return pos < node.pos;
25 }
26};
27
28/**//******************************************************************************
29** 封装A*寻路算法
30*******************************************************************************
31** 作为棋盘信息提供类TField必须实现下列函数:
32** 1. bool IsFieldThrough(TNodeLocation pos) const; 在 pos 位置是否为空,可通行.
33** 2. float EvaluateStepCost(TNodeLocation posFrom, TNodeLocation posTo, TNodeLocation posLastStep) const; 计算pos1,pos2到单步代价.
34** 3. float EvaluateProbableCost(TNodeLocation posFrom, TNodeLocation posTo) const; 计算pos1,pos2到估算代价.
35** 4. TNodeLocation* QueryNeiborLocations(TNodeLocation pos, int& nNodeCount); const 询问pos的相邻可通节点集
36*******************************************************************************
37** TNodeLocation,节点位置
38** 1.支持<,==,=操作符,如int.
39*******************************************************************************
40** 0. 初始化时传入棋盘信息提供类的实例引用.
41** 1. 使用主函数SearchPath进行搜索,使用QueryResultPath取得结果.
42******************************************************************************/
43template<class TField, class TNodeLocation>
44struct CAStar2DAlgo
45{
46public:
47 typedef std::vector<TNodeLocation> CResultPath;
48 typedef TAXNode<TNodeLocation> CAXNode;
49 typedef std::set<CAXNode> CAXNodeSet;
50
51 struct CAXNodePriorityQueue // 优先队列
52 {
53 std::vector<CAXNode*> m_heap;
54
55 static bool AXNodeCostSortPred(CAXNode* n1, CAXNode* n2)
56 {
57 return (n1->G + n1->F) > (n2->G + n2->F);
58 }
59
60 void push(CAXNode* pNode)
61 {
62 m_heap.push_back(pNode);
63 std::push_heap(m_heap.begin(), m_heap.end(), &CAXNodePriorityQueue::AXNodeCostSortPred);
64 }
65
66 CAXNode* pop()
67 {
68 CAXNode* pNode = m_heap.front();
69 std::pop_heap(m_heap.begin(), m_heap.end(), &CAXNodePriorityQueue::AXNodeCostSortPred);
70 m_heap.pop_back();
71 return pNode;
72 }
73
74 bool empty()
75 {
76 return m_heap.empty();
77 }
78
79 void resort(CAXNode* pNode)
80 {
81 std::vector<CAXNode*>::iterator it = std::find(m_heap.begin(), m_heap.end(), pNode);
82 std::push_heap(m_heap.begin(), it, &CAXNodePriorityQueue::AXNodeCostSortPred);
83 }
84
85 void clear()
86 {
87 m_heap.clear();
88 }
89 };
90
91public:
92 const TField& m_field;
93 TNodeLocation m_posTarget;
94 CAXNode* m_ptrTargetNode; // Result Node
95
96 CAXNodeSet m_setNodes; // All nodes in use
97 CAXNodePriorityQueue m_queOpenNodes; // Cost sorted open list
98
99public:
100 CAStar2DAlgo(const TField& field) : m_field(field), m_ptrTargetNode(NULL)
101 {
102 }
103
104 ~CAStar2DAlgo()
105 {
106 }
107
108 void Reset()
109 {
110 m_setNodes.clear();
111 m_queOpenNodes.clear();
112 m_ptrTargetNode = NULL;
113 }
114
115public:
116 inline CAXNode* ClaimNode(TNodeLocation pos, CAXNode* pParentNode = NULL)
117 {
118 CAXNode node;
119 node.pos = pos;
120 node.F = node.G = 0;
121 node.bClosed = false; // Default is open
122 node.pParentNode = pParentNode;
123 return &(*m_setNodes.insert(node).first);
124 }
125
126 bool SearchPath(TNodeLocation posStart, TNodeLocation posTarget)
127 {
128 CAXNode* pCurNode;
129 m_posTarget = posTarget;
130
131 // Add start node into open list
132 CAXNode* pStartNode = ClaimNode(posStart);
133 m_queOpenNodes.push(pStartNode);
134
135 while(!m_queOpenNodes.empty())
136 {
137 // Pick lowest cost node
138 pCurNode = m_queOpenNodes.pop();
139
140 // Check search target
141 if(pCurNode->pos == m_posTarget)
142 {
143 m_ptrTargetNode = pCurNode;
144 return true;
145 }
146
147 // Switch node from OpenList to CloseList
148 pCurNode->bClosed = true;
149 ProcessNeighborNodes(pCurNode);
150 }
151
152 return false;
153 }
154
155 void ProcessNeighborNodes(CAXNode* pCurNode)
156 {
157 CAXNode tempNode;
158 int nNodeCount = 0;
159 TNodeLocation* pLocs = m_field.QueryNeiborLocations(pCurNode->pos, nNodeCount);
160 TNodeLocation posLastStep = pCurNode->pParentNode? pCurNode->pParentNode->pos : pCurNode->pos;
161
162 // For each neibors
163 for(int i = 0; i < nNodeCount; ++i)
164 {
165 tempNode.pos = pLocs[i];
166 if(m_field.IsFieldThrough(tempNode.pos))
167 {
168 CAXNodeSet::iterator it = m_setNodes.find(tempNode);
169 if(it == m_setNodes.end())
170 {
171 CAXNode* pNewNode = ClaimNode(tempNode.pos, pCurNode);
172 pNewNode->G = pCurNode->G + m_field.EvaluateStepCost(pCurNode->pos, pNewNode->pos, posLastStep);
173 pNewNode->F = m_field.EvaluateProbableCost(pNewNode->pos, m_posTarget);
174 m_queOpenNodes.push(pNewNode);
175 }
176 else if(!it->bClosed)
177 {
178 CAXNode& node = *it;
179 float G = pCurNode->G + m_field.EvaluateStepCost(pCurNode->pos, node.pos, posLastStep);
180 if(G < node.G)
181 {
182 node.G = G;
183 node.pParentNode = pCurNode;
184 m_queOpenNodes.resort(&node);
185 }
186 }
187 }
188 }
189 }
190
191 /**//******************************************************************
192 ** 取回最终结果
193 ******************************************************************/
194 bool QueryResultPath(CResultPath& path)
195 {
196 if(!m_ptrTargetNode) return false;
197
198 CAXNode* pNode = m_ptrTargetNode;
199 while(pNode)
200 {
201 path.push_back(pNode->pos);
202 pNode = pNode->pParentNode;
203 }
204 return true;
205 }
206};
207
208/**//*******************************************************************************
209** TNodeLocation,节点位置
210** 1.支持<,== 操作符号.
211********************************************************************************/
212template<typename TNodeLocation>
213struct CShisenFieldImpl
214{
215 TNodeLocation* QueryNeiborLocations(TNodeLocation pos, int& nRetCount) const
216 {
217 static const int dy[4] = { 1, 0, 0, -1 };
218 static TNodeLocation posNeibors[4]; // Single thread
219
220 nRetCount = 4;
221 for(int i = 0; i < 4; i++)
222 {
223 posNeibors[i].x = pos.x + dx[i];
224 posNeibors[i].y = pos.y + dy[i];
225 }
226 return posNeibors;
227 }
228
229 float EvaluateStepCost(TNodeLocation posFrom, TNodeLocation posTo, TNodeLocation posLast) const
230 {
231 if(((posFrom.x-posTo.x) && (posLast.y-posFrom.y)) ||
232 ((posFrom.y-posTo.y) && (posLast.x-posFrom.x)))
233 {
234 return 100;
235 }
236 else return 1;
237 }
238
239 float EvaluateProbableCost(TNodeLocation pos1, TNodeLocation pos2) const
240 {
241 return 0;
242 }
243
244/**//* 平滑优化
245 float EvaluateStepCost(MY_POSITION posFrom, MY_POSITION posTo, MY_POSITION posLast) const
246 {
247 int cx1 = posTo.x - posFrom.x;
248 int cy1 = posTo.y - posFrom.y;
249 int cx2 = posFrom.x - posLast.x;
250 int cy2 = posFrom.y - posLast.y;
251 return ((cx1 == cx2 && cy1 == cy2)? 0 : 10) + ((cx1 && cy1)? 14 : 10);
252 }
253*/
254};
255
256/**//*******************************************************************************
257** 最小路径
258*******************************************************************************/
259template<typename TNodeLocation>
260struct CShortestPathFieldImpl
261{
262 TNodeLocation* QueryNeiborLocations(TNodeLocation pos, int& nRetCount) const
263 {
264 static const int dx[4] = { 0, -1, 1, 0 };
265 static const int dy[4] = { 1, 0, 0, -1 };
266 static TNodeLocation posNeibors[4]; // Single thread
267
268 nRetCount = 4;
269 for(int i = 0; i < 4; i++)
270 {
271 posNeibors[i].x = pos.x + dx[i];
272 posNeibors[i].y = pos.y + dy[i];
273 }
274 return posNeibors;
275 }
276
277 float EvaluateStepCost(TNodeLocation posFrom, TNodeLocation posTo, TNodeLocation posLast) const
278 {
279 return 1;
280 }
281
282 float EvaluateProbableCost(TNodeLocation pos1, TNodeLocation pos2) const
283 {
284 return 0;
285 }
286};
287
288/**//*******************************************************************************
289** 最小路径
290*******************************************************************************/
291template<typename TNodeLocation>
292struct CGamePathFieldImpl
293{
294 TNodeLocation* QueryNeiborLocations(TNodeLocation pos, int& nRetCount) const
295 {
296 static const int dx[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };
297 static const int dy[8] = { 1, 1, 1, 0, 0, -1, -1, -1 };
298 static MY_POSITION posNeibors[8];
299
300 nRetCount = 8;
301 for(int i = 0; i < 8; i++)
302 {
303 posNeibors[i].x = pos.x + dx[i];
304 posNeibors[i].y = pos.y + dy[i];
305 }
306 return posNeibors;
307 }
308
309 float EvaluateStepCost(TNodeLocation posFrom, TNodeLocation posTo, TNodeLocation posLast) const
310 {
311 if(posFrom.x-posTo.x && posFrom.y-posTo.y)
312 {
313 return 14;
314 }
315 else return 10;
316 }
317
318 float EvaluateProbableCost(TNodeLocation posFrom, TNodeLocation posTo) const
319 {
320 return (abs(posFrom.x-posTo.x) + abs(posFrom.y-posTo.y)) * 10;
321 }
322};
323
324}// namespace linghuye
325 }// namespace fredazsq
326
327#endif//__FIELD_SERACH_ALGO_H__
|