My Project: dynamics.mod/NewtonDynamics/source/core/dgPathFinder.h Source File

My Project

dgPathFinder.h
Go to the documentation of this file.
1 /* Copyright (c) <2003-2011> <Julio Jerez, Newton Game Dynamics>
2 *
3 * This software is provided 'as-is', without any express or implied
4 * warranty. In no event will the authors be held liable for any damages
5 * arising from the use of this software.
6 *
7 * Permission is granted to anyone to use this software for any purpose,
8 * including commercial applications, and to alter it and redistribute it
9 * freely, subject to the following restrictions:
10 *
11 * 1. The origin of this software must not be misrepresented; you must not
12 * claim that you wrote the original software. If you use this software
13 * in a product, an acknowledgment in the product documentation would be
14 * appreciated but is not required.
15 *
16 * 2. Altered source versions must be plainly marked as such, and must not be
17 * misrepresented as being the original software.
18 *
19 * 3. This notice may not be removed or altered from any source distribution.
20 */
21
22 #ifndef __dgPathFinder__
23 #define __dgPathFinder__
24
25 #include "dgStdafx.h"
26 #include "dgTree.h"
27 #include "dgHeap.h"
28
29 template<class NODEID, class COST> class dgPathFinder;
30
31
32 #define DG_MAX_PATH_ENUMERATION_CHILDREN 128
33
34 template<class NODEID, class COST>
35 class dgPathNode
36 {
37 friend class dgPathFinder<NODEID, COST>;
38 NODEID m_Id;
39 COST m_NodeCostToGoal;
40 COST m_NodeCostFromSource;
41 dgPathNode* m_Next;
42
43 public:
44 dgPathNode();
45 NODEID GetId() const;
46 const dgPathNode* GetNext() const;
47 const dgPathNode* GetParent() const;
48 };
49
50 template<class NODEID, class COST>
51 class dgPathCloseList: public dgTree<dgPathNode<NODEID, COST>, NODEID>
52 {
53 protected:
54 dgPathCloseList(): dgTree<dgPathNode<NODEID, COST>, NODEID>() {}
55 };
56
57
58 template<class NODEID, class COST>
59 class dgPathOpenHeap: public dgUpHeap<typename dgPathCloseList<NODEID, COST>::dgTreeNode*, COST>
60 {
61 protected:
62 dgPathOpenHeap(dgInt32 maxElements)
63 :dgUpHeap<typename dgPathCloseList<NODEID, COST>::dgTreeNode*, COST>(maxElements)
64 {
65 }
66
67 friend class dgPathFinder<NODEID, COST>;
68 };
69
70
71 template<class NODEID, class COST>
72 class dgPathFinder: public dgPathCloseList<NODEID, COST>
73 {
74 dgInt32 maxChildren;
75
76 public:
77 dgPathFinder(dgInt32 maxElementsInOpenList, dgInt32 nodeMaxChildren);
78 virtual ~dgPathFinder();
79
80 virtual const dgPathNode<NODEID, COST>* CalCulatePath (NODEID source, NODEID goal);
81
82 // this funtions must be overloaded by the user
83 virtual COST GetCostFromParent(const dgPathNode<NODEID, COST>& node) const;
84 virtual COST GetEstimatedCostToGoal(NODEID id) const;
85 virtual dgInt32 EnumerateChildren(NODEID parent, NODEID array[]) const;
86
87 dgPathOpenHeap<NODEID, COST> m_openList;
88 };
89
90
91 template<class NODEID, class COST>
92 dgPathNode<NODEID, COST>::dgPathNode ()
93 {
94 }
95
96 template<class NODEID, class COST>
97 NODEID dgPathNode<NODEID, COST>::GetId () const
98 {
99 return m_Id;
100 }
101
102
103 template<class NODEID, class COST>
104 const dgPathNode<NODEID, COST>* dgPathNode<NODEID, COST>::GetNext() const
105 {
106 return m_Next;
107 }
108
109
110 template<class NODEID, class COST>
111 const dgPathNode<NODEID, COST>* dgPathNode<NODEID, COST>::GetParent() const
112 {
113 return m_Next;
114 }
115
116
117 template<class NODEID, class COST>
118 dgPathFinder<NODEID, COST>::dgPathFinder(
119 dgInt32 maxElementsInOpenList,
120 dgInt32 nodeMaxChildren)
121 :dgPathCloseList<NODEID, COST>(),
122 m_openList(maxElementsInOpenList)
123 {
124 maxChildren = nodeMaxChildren;
125 }
126
127
128 template<class NODEID, class COST>
129 dgPathFinder<NODEID, COST>::~dgPathFinder()
130 {
131 }
132
133 template<class NODEID, class COST>
134 const dgPathNode<NODEID, COST>* dgPathFinder<NODEID, COST>::CalCulatePath (NODEID source, NODEID goal)
135 {
136 dgInt32 count;
137 dgInt32 heapMaxCount;
138 dgPathNode<NODEID, COST> cell;
139 dgPathNode<NODEID, COST>* next;
140 dgPathNode<NODEID, COST>* prev;
141 dgPathNode<NODEID, COST>* link;
142 typename dgPathCloseList<NODEID, COST>::dgTreeNode* node;
143 NODEID idArray[DG_MAX_PATH_ENUMERATION_CHILDREN];
144
145 dgPathCloseList<NODEID, COST>& close = *this;
146
147 m_openList.Flush();
148 close.RemoveAll();
149
150 cell.m_Id = source;
151 cell.m_Next = NULL;
152 cell.m_NodeCostFromSource = COST (0);
153 cell.m_NodeCostToGoal = GetEstimatedCostToGoal(cell.m_Id);
154
155 node = close.Insert (cell, source);
156
157 heapMaxCount = m_openList.GetMaxCount();
158 m_openList.Push (node, cell.m_NodeCostFromSource + cell.m_NodeCostToGoal);
159 while (m_openList.GetCount()) {
160 node = m_openList[0];
161 dgPathNode<NODEID, COST>& parent = node->GetInfo();
162 if (parent.m_Id == goal) {
163 link = &parent;
164 next = NULL;
165 do {
166 prev = link->m_Next;
167 link->m_Next = next;
168 next = link;
169 link = prev;
170 } while (link);
171 return next;
172 }
173
174 m_openList.Pop();
175 count = EnumerateChildren(node->GetKey(), idArray);
176 cell.m_Next = &parent;
177 for (int i = 0; i < count; i ++) {
178 bool state;
179 cell.m_Id = idArray[i];
180
181 COST newCostFromSource (GetCostFromParent(cell) + parent.m_NodeCostFromSource);
182 node = close.Insert (cell, cell.m_Id, state);
183 dgPathNode<NODEID, COST>& newCell = node->GetInfo();
184 if (state) {
185 if (newCell.m_NodeCostFromSource <= newCostFromSource) {
186 continue;
187 }
188 //newCell.m_Next = cell.m_Next;
189 }
190
191 newCell.m_NodeCostFromSource = newCostFromSource;
192 newCell.m_NodeCostToGoal = GetEstimatedCostToGoal(newCell.m_Id);
193 if (m_openList.GetCount() >= heapMaxCount) {
194 m_openList.Remove (heapMaxCount);
195 }
196 m_openList.Push (node, newCell.m_NodeCostFromSource + newCell.m_NodeCostToGoal);
197 }
198 }
199 return NULL;
200 }
201
202 template<class NODEID, class COST>
203 COST dgPathFinder<NODEID, COST>::GetCostFromParent(const dgPathNode<NODEID, COST>& node) const
204 {
205 return COST (1);
206 }
207
208 template<class NODEID, class COST>
209 COST dgPathFinder<NODEID, COST>::GetEstimatedCostToGoal(NODEID id) const
210 {
211 return COST (1);
212 }
213
214 template<class NODEID, class COST>
215 dgInt32 dgPathFinder<NODEID, COST>::EnumerateChildren(NODEID parent, NODEID array[]) const
216 {
217 return 0;
218 }
219
220
221
222
223 #endif
224
225
226
dgTree< dgPathNode< NODEID, COST >, NODEID >::Insert
dgTreeNode * Insert(const dgPathNode< NODEID, COST > &element, NODEID key, bool &elementWasInTree)
Definition: dgTree.h:555
dgPathNode::dgPathNode
dgPathNode()
Definition: dgPathFinder.h:92
dgPathNode::GetParent
const dgPathNode * GetParent() const
Definition: dgPathFinder.h:111
dgHeap.h
dgTree.h
dgPathFinder
Definition: dgPathFinder.h:29
dgInt32
int dgInt32
Definition: dgTypes.h:218
dgPathOpenHeap
Definition: dgPathFinder.h:59
dgPathFinder::~dgPathFinder
virtual ~dgPathFinder()
Definition: dgPathFinder.h:129
dgPathFinder::GetCostFromParent
virtual COST GetCostFromParent(const dgPathNode< NODEID, COST > &node) const
Definition: dgPathFinder.h:203
dgPathNode
Definition: dgPathFinder.h:35
dgTree
Definition: dgTree.h:88
dgPathFinder::GetEstimatedCostToGoal
virtual COST GetEstimatedCostToGoal(NODEID id) const
Definition: dgPathFinder.h:209
dgPathFinder::dgPathFinder
dgPathFinder(dgInt32 maxElementsInOpenList, dgInt32 nodeMaxChildren)
Definition: dgPathFinder.h:118
dgStdafx.h
dgPathCloseList
Definition: dgPathFinder.h:51
dgPathNode::GetId
NODEID GetId() const
Definition: dgPathFinder.h:97
dgUpHeap
Definition: dgHeap.h:91
dgPathOpenHeap::dgPathOpenHeap
dgPathOpenHeap(dgInt32 maxElements)
Definition: dgPathFinder.h:62
DG_MAX_PATH_ENUMERATION_CHILDREN
#define DG_MAX_PATH_ENUMERATION_CHILDREN
Definition: dgPathFinder.h:32
dgPathFinder::EnumerateChildren
virtual dgInt32 EnumerateChildren(NODEID parent, NODEID array[]) const
Definition: dgPathFinder.h:215
dgPathFinder::m_openList
dgPathOpenHeap< NODEID, COST > m_openList
Definition: dgPathFinder.h:87
dgPathNode::GetNext
const dgPathNode * GetNext() const
Definition: dgPathFinder.h:104
dgPathCloseList::dgPathCloseList
dgPathCloseList()
Definition: dgPathFinder.h:54
dgTree< dgPathNode< NODEID, COST >, NODEID >::RemoveAll
void RemoveAll()
Definition: dgTree.h:754
dgPathFinder::CalCulatePath
virtual const dgPathNode< NODEID, COST > * CalCulatePath(NODEID source, NODEID goal)
Definition: dgPathFinder.h:134