HOG2
NBS.h
Go to the documentation of this file.
1 //
2 // NBS.h
3 // This file derived from MM.h by Nathan Sturtevant
4 // The following is the original claim
5 //
6 // MM.h
7 // hog2 glut
8 //
9 // Created by Nathan Sturtevant on 10/27/15.
10 // Copyright © 2015 University of Denver. All rights reserved.
11 //
12 
13 #ifndef NBS_H
14 #define NBS_H
15 
16 #include "BDOpenClosed.h"
17 #include "BDIndexOpenClosed.h"
18 #include "FPUtil.h"
19 #include <unordered_map>
20 #include "NBSQueue.h"
21 //#include "NBSQueueGF.h"
22 #include "Graphics.h"
23 //#define EPSILON 1
24 
25 // ADMISSIBLE is defined at "BDOpenClosed.h"
26 
27 
28 using std::cout;
29 
30 
31 template <class state, class action, class environment, class dataStructure = NBSQueue<state, 1>, class priorityQueue = BDOpenClosed<state, NBSCompareOpenReady<state, BDOpenClosedData<state>>, NBSCompareOpenWaiting<state, BDOpenClosedData<state>>>>
32 class NBS {
33 public:
34  NBS()
35  {
36  forwardHeuristic = 0; backwardHeuristic = 0; env = 0; ResetNodeCount();
37  }
38  virtual ~NBS() {}
39  void GetPath(environment *env, const state& from, const state& to,
40  Heuristic<state> *forward, Heuristic<state> *backward, std::vector<state> &thePath);
41  bool InitializeSearch(environment *env, const state& from, const state& to,
42  Heuristic<state> *forward, Heuristic<state> *backward, std::vector<state> &thePath);
43  bool ExpandAPair(std::vector<state> &thePath);
44  bool DoSingleSearchStep(std::vector<state> &thePath);
45 
46 
47 
48 
49  virtual const char *GetName() { return "NBS"; }
50 
51  void ResetNodeCount() { nodesExpanded = nodesTouched = 0; counts.clear(); }
52 
53  inline const int GetNumForwardItems() { return queue.forwardQueue.size(); }
54  inline const BDOpenClosedData<state> &GetForwardItem(unsigned int which) { return queue.forwardQueue.Lookat(which); }
55  inline const int GetNumBackwardItems() { return queue.backwardQueue.size(); }
56  inline const BDOpenClosedData<state> &GetBackwardItem(unsigned int which) { return queue.backwardQueue.Lookat(which); }
57 
58  void SetForwardHeuristic(Heuristic<state> *h) { forwardHeuristic = h; }
59  void SetBackwardHeuristic(Heuristic<state> *h) { backwardHeuristic = h; }
60  stateLocation GetNodeForwardLocation(const state &s)
61  {
62  uint64_t childID;
63  auto l = queue.forwardQueue.Lookup(env->GetStateHash(s), childID);
64  return l;
65  }
66  stateLocation GetNodeBackwardLocation(const state &s)
67  {
68  uint64_t childID;
69  return queue.backwardQueue.Lookup(env->GetStateHash(s), childID);
70  }
71  double GetNodeForwardG(const state& s)
72  {
73  uint64_t childID;
74  auto l = queue.forwardQueue.Lookup(env->GetStateHash(s), childID);
75  if (l != kUnseen)
76  return queue.forwardQueue.Lookat(childID).g;
77  return -1;
78  }
79  double GetNodeBackwardG(const state& s)
80  {
81  uint64_t childID;
82  auto l = queue.backwardQueue.Lookup(env->GetStateHash(s), childID);
83  if (l != kUnseen)
84  return queue.backwardQueue.Lookat(childID).g;
85  return -1;
86  }
87  uint64_t GetNodesExpanded() const { return nodesExpanded; }
88  uint64_t GetNodesTouched() const { return nodesTouched; }
89  uint64_t GetDoubleExpansions() const;
90  uint64_t GetNecessaryExpansions() const
91  {
92  uint64_t necessary = 0;
93  for (const auto &i : counts)
94  {
95  if (i.first < currentCost)
96  necessary+=i.second;
97  }
98  return necessary;
99  }
100  // returns 0...1 for the percentage of the optimal path length on each frontier
101  float GetMeetingPoint()
102  {
103  uint64_t fID, bID;
104  queue.backwardQueue.Lookup(env->GetStateHash(middleNode), bID);
105  queue.forwardQueue.Lookup(env->GetStateHash(middleNode), fID);
106  assert (fequal(queue.backwardQueue.Lookup(bID).g+queue.forwardQueue.Lookup(fID).g, currentCost));
107  return queue.backwardQueue.Lookup(bID).g/currentCost;
108  }
109  double GetSolutionCost() const { return currentCost; }
110 
111  void OpenGLDraw() const;
112  void Draw(Graphics::Display &d) const;
113  void DrawBipartiteGraph(Graphics::Display &d) const;
114 
115  // void SetWeight(double w) {weight = w;}
116 private:
117  void ExtractFromMiddle(std::vector<state> &thePath);
118  void ExtractPathToGoal(state &node, std::vector<state> &thePath)
119  {
120  uint64_t theID;
121  queue.backwardQueue.Lookup(env->GetStateHash(node), theID);
122  ExtractPathToGoalFromID(theID, thePath);
123  }
124  void ExtractPathToGoalFromID(uint64_t node, std::vector<state> &thePath)
125  {
126  do {
127  thePath.push_back(queue.backwardQueue.Lookup(node).data);
128  node = queue.backwardQueue.Lookup(node).parentID;
129  } while (queue.backwardQueue.Lookup(node).parentID != node);
130  thePath.push_back(queue.backwardQueue.Lookup(node).data);
131  }
132 
133  void ExtractPathToStart(state &node, std::vector<state> &thePath)
134  {
135  uint64_t theID;
136  queue.forwardQueue.Lookup(env->GetStateHash(node), theID);
137  ExtractPathToStartFromID(theID, thePath);
138  }
139 
140  void ExtractPathToStartFromID(uint64_t node, std::vector<state> &thePath)
141  {
142  do {
143  thePath.push_back(queue.forwardQueue.Lookup(node).data);
144  node = queue.forwardQueue.Lookup(node).parentID;
145  } while (queue.forwardQueue.Lookup(node).parentID != node);
146  thePath.push_back(queue.forwardQueue.Lookup(node).data);
147  }
148 
149  void OpenGLDraw(const priorityQueue &queue) const;
150  void Draw(Graphics::Display &d, const priorityQueue &queue) const;
151 
152  void Expand(uint64_t nextID,
153  priorityQueue &current,
154  priorityQueue &opposite,
155  Heuristic<state> *heuristic, const state &target);
156  //direction ==0 forward; 1 backward
157  //void Expand(int direction);
158  uint64_t nodesTouched, nodesExpanded;
159  state middleNode;
160  double currentCost;
161  double currentSolutionEstimate;
162  std::vector<state> neighbors;
163  environment *env;
164  std::unordered_map<double, int> counts;
165 
166  dataStructure queue;
167  // priorityQueue queue.forwardQueue, queue.backwardQueue;
168  //priorityQueue2 queue.forwardQueue, queue.backwardQueue;
169 
170  state goal, start;
171 
172  Heuristic<state> *forwardHeuristic;
173  Heuristic<state> *backwardHeuristic;
174 
175  //keep track of whether we expand a node or put it back to open
176  bool expand;
177 
178  double currentPr;
179 
180 
181 };
182 
183 template <class state, class action, class environment, class dataStructure, class priorityQueue>
184 void NBS<state, action, environment, dataStructure, priorityQueue>::GetPath(environment *env, const state& from, const state& to,
185  Heuristic<state> *forward, Heuristic<state> *backward, std::vector<state> &thePath)
186 {
187  if (InitializeSearch(env, from, to, forward, backward, thePath) == false)
188  return;
189 
190  while (!ExpandAPair(thePath))
191  { }
192 }
193 
194 template <class state, class action, class environment, class dataStructure, class priorityQueue>
195 bool NBS<state, action, environment, dataStructure, priorityQueue>::InitializeSearch(environment *env, const state& from, const state& to,
196  Heuristic<state> *forward, Heuristic<state> *backward,
197  std::vector<state> &thePath)
198 {
199  this->env = env;
200  forwardHeuristic = forward;
201  backwardHeuristic = backward;
202  currentSolutionEstimate = 0;
203  currentCost = DBL_MAX;
204  queue.Reset(env->GetMaxHash());
205  // queue.forwardQueue.Reset();
206  // queue.backwardQueue.Reset();
207  ResetNodeCount();
208  thePath.resize(0);
209  start = from;
210  goal = to;
211  if (start == goal)
212  return false;
213 
214  queue.forwardQueue.AddOpenNode(start, env->GetStateHash(start), 0, forwardHeuristic->HCost(start, goal));
215  queue.backwardQueue.AddOpenNode(goal, env->GetStateHash(goal), 0, backwardHeuristic->HCost(goal, start));
216 
217  return true;
218 }
219 
220 template <class state, class action, class environment, class dataStructure, class priorityQueue>
221 bool NBS<state, action, environment, dataStructure, priorityQueue>::ExpandAPair(std::vector<state> &thePath)
222 {
223  uint64_t nForward, nBackward;
224  bool result = queue.GetNextPair(nForward, nBackward);
225  // if failed, see if we have optimal path (but return)
226  if (result == false)
227  {
228  if (currentCost == DBL_MAX)
229  {
230  thePath.resize(0);
231  return true;
232  }
233  ExtractFromMiddle(thePath);
234  return true;
235  }
236  else if (queue.forwardQueue.Lookup(nForward).data == queue.backwardQueue.Lookup(nBackward).data) // if success, see if nodes are the same (return path)
237  {
238 // if (queue.TerminateOnG())
239 // printf("NBS: Lower Bound on C* from g+g (gsum)\n");
240  ExtractFromMiddle(thePath);
241  return true;
242  }
243  else if (!fless(queue.GetLowerBound(), currentCost))
244  {
245  ExtractFromMiddle(thePath);
246  return true;
247  }
248 
249  counts[queue.GetLowerBound()]+=2;
250  Expand(nForward, queue.forwardQueue, queue.backwardQueue, forwardHeuristic, goal);
251  Expand(nBackward, queue.backwardQueue, queue.forwardQueue, backwardHeuristic, start);
252  return false;
253 }
254 
255 template <class state, class action, class environment, class dataStructure, class priorityQueue>
256 void NBS<state, action, environment, dataStructure, priorityQueue>::ExtractFromMiddle(std::vector<state> &thePath)
257 {
258  std::vector<state> pFor, pBack;
259  // std::cout << "Extracting from " << middleNode << "\n";
260  ExtractPathToGoal(middleNode, pBack);
261  // std::cout << "And from: Extracting from " << middleNode << "\n";
262  ExtractPathToStart(middleNode, pFor);
263  reverse(pFor.begin(), pFor.end());
264  thePath = pFor;
265  thePath.insert( thePath.end(), pBack.begin()+1, pBack.end() );
266 }
267 
268 
269 template <class state, class action, class environment, class dataStructure, class priorityQueue>
270 bool NBS<state, action, environment, dataStructure, priorityQueue>::DoSingleSearchStep(std::vector<state> &thePath)
271 {
272  return ExpandAPair(thePath);
273 }
274 
275 
276 template <class state, class action, class environment, class dataStructure, class priorityQueue>
277 void NBS<state, action, environment, dataStructure, priorityQueue>::Expand(uint64_t nextID,
278  priorityQueue &current,
279  priorityQueue &opposite,
280  Heuristic<state> *heuristic, const state &target)
281 {
282 
283  // uint64_t nextID = current.Peek(kOpenReady);
284  //
285  uint64_t tmp = current.Close();
286  assert(tmp == nextID);
287  //if (currentCost != DBL_MAX)
288  //std::cout << "Expanding " << current.Lookup(nextID).data << "\n";
289 
290  //this can happen when we expand a single node instead of a pair
291  if (fgreatereq(current.Lookup(nextID).g + current.Lookup(nextID).h, currentCost))
292  return;
293 
294  nodesExpanded++;
295  env->GetSuccessors(current.Lookup(nextID).data, neighbors);
296  for (auto &succ : neighbors)
297  {
298  //std::cout << "--Child " << succ << "\n";
299  nodesTouched++;
300  uint64_t childID;
301  auto loc = current.Lookup(env->GetStateHash(succ), childID);
302 
303  // screening
304  double edgeCost = env->GCost(current.Lookup(nextID).data, succ);
305  if (fgreatereq(current.Lookup(nextID).g+edgeCost, currentCost))
306  continue;
307 
308  switch (loc)
309  {
310  case kClosed: // ignore
311  // break;
312 #ifdef ADMISSIBLE
313  if (fless(current.Lookup(nextID).g + edgeCost, current.Lookup(childID).g))
314  {
315  // std::cout << "Re-opening node from closed " << current.Lookup(nextID).data << "\n";
316  double oldGCost = current.Lookup(childID).g;
317  current.Lookup(childID).parentID = nextID;
318  current.Lookup(childID).g = current.Lookup(nextID).g + edgeCost;
319  current.Reopen(childID);
320 
321  // TODO: check if we improved the current solution?
322  uint64_t reverseLoc;
323  auto loc = opposite.Lookup(env->GetStateHash(succ), reverseLoc);
324  if (loc == kOpenReady || loc == kOpenWaiting)
325  {
326  if (fless(current.Lookup(nextID).g + edgeCost + opposite.Lookup(reverseLoc).g, currentCost))
327  {
328  if (currentCost == DBL_MAX)
329  {
330  // printf("NBS: first solution %" PRId64 "\n", nodesExpanded);
331  // std::cout << "Through " << succ << " (not here)\n";
332  }
333  // TODO: store current solution
334  // printf("NBS Potential updated solution found, cost: %1.2f + %1.2f = %1.2f (%" PRId64 " nodes)\n",
335  // current.Lookup(nextID).g+edgeCost,
336  // opposite.Lookup(reverseLoc).g,
337  // current.Lookup(nextID).g+edgeCost+opposite.Lookup(reverseLoc).g,
338  // nodesExpanded);
339  currentCost = current.Lookup(nextID).g + edgeCost + opposite.Lookup(reverseLoc).g;
340 
341  middleNode = succ;
342  }
343  }
344  }
345 #endif
346  break;
347  case kOpenReady: // update cost if needed
348  case kOpenWaiting:
349  {
350  if (fless(current.Lookup(nextID).g+edgeCost, current.Lookup(childID).g))
351  {
352  current.Lookup(childID).parentID = nextID;
353  current.Lookup(childID).g = current.Lookup(nextID).g+edgeCost;
354  current.KeyChanged(childID);
355 
356  // TODO: check if we improved the current solution?
357  uint64_t reverseLoc;
358  auto loc = opposite.Lookup(env->GetStateHash(succ), reverseLoc);
359  if (loc == kOpenReady || loc == kOpenWaiting)
360  {
361  if (fless(current.Lookup(nextID).g+edgeCost + opposite.Lookup(reverseLoc).g, currentCost))
362  {
363  // if (currentCost == DBL_MAX)
364  // {
365  // printf("NBS: first solution %" PRId64 "\n", nodesExpanded);
366  // std::cout << "Through " << succ << " (better)\n";
367  // }
368  // TODO: store current solution
369  // printf("NBS Potential updated solution found, cost: %1.2f + %1.2f = %1.2f (%" PRId64 " nodes)\n",
370  // current.Lookup(nextID).g+edgeCost,
371  // opposite.Lookup(reverseLoc).g,
372  // current.Lookup(nextID).g+edgeCost+opposite.Lookup(reverseLoc).g,
373  // nodesExpanded);
374  currentCost = current.Lookup(nextID).g+edgeCost + opposite.Lookup(reverseLoc).g;
375 
376  middleNode = succ;
377  }
378  }
379 #ifdef ADMISSIBLE
380 
381 #else
382  else if (loc == kClosed)
383  {
384  current.Remove(childID);
385  }
386 #endif // !ADMISSIBLE
387  }
388  }
389  break;
390  case kUnseen:
391  {
392  uint64_t reverseLoc;
393  auto locReverse = opposite.Lookup(env->GetStateHash(succ), reverseLoc);
394 #ifdef ADMISSIBLE
395 
396 #else
397  if (locReverse == kClosed)// then
398  {
399  break; //do nothing. do not put this node to open
400  }
401  else//loc == kUnseen or kOpen
402 #endif // ADMISSIBLE
403  {
404  //double edgeCost = env->GCost(current.Lookup(nextID).data, succ);
405  //if(fless(current.Lookup(nextID).g + edgeCost + heuristic->HCost(succ, target),currentPr))
406  // current.AddOpenNode(succ,
407  // env->GetStateHash(succ),
408  // current.Lookup(nextID).g + edgeCost,
409  // heuristic->HCost(succ, target),
410  // nextID,0);
411  //else
412  double newNodeF = current.Lookup(nextID).g + edgeCost + heuristic->HCost(succ, target);
413  if (fless(newNodeF, currentCost))
414  {
415  if (fless(newNodeF, queue.GetLowerBound()))
416  current.AddOpenNode(succ,
417  env->GetStateHash(succ),
418  current.Lookup(nextID).g + edgeCost,
419  heuristic->HCost(succ, target),
420  nextID, kOpenReady);
421  else
422  current.AddOpenNode(succ,
423  env->GetStateHash(succ),
424  current.Lookup(nextID).g + edgeCost,
425  heuristic->HCost(succ, target),
426  nextID, kOpenWaiting);
427 
428  if (locReverse == kOpenReady || locReverse == kOpenWaiting)
429  {
430  //double edgeCost = env->GCost(current.Lookup(nextID).data, succ);
431  if (fless(current.Lookup(nextID).g + edgeCost + opposite.Lookup(reverseLoc).g, currentCost))
432  {
433  if (currentCost == DBL_MAX)
434  {
435  // if (&current == &queue.forwardQueue)
436  // std::cout << "Searching forward\n";
437  // else
438  // std::cout << "Searching backward\n";
439  // printf("NBS: first solution %" PRId64 " ", nodesExpanded);
440  //
441  // std::cout << "Through " << succ << " (first) \n";
442  //
443  // uint64_t theID;
444  // auto loc = queue.forwardQueue.Lookup(env->GetStateHash(succ), theID);
445  // std::cout << "Forward:\n";
446  // switch (loc)
447  // {
448  // case kOpenReady: std::cout << "Initially in open ready\n"; break;
449  // case kOpenWaiting: std::cout << "Initially in open waiting\n"; break;
450  // case kClosed: std::cout << "Initially in closed\n"; break;
451  // case kUnseen: std::cout << "Initially in UNSEEN\n"; break;
452  // }
453  // loc = queue.backwardQueue.Lookup(env->GetStateHash(succ), theID);
454  // std::cout << "Backward:\n";
455  // switch (loc)
456  // {
457  // case kOpenReady: std::cout << "Initially in open ready\n"; break;
458  // case kOpenWaiting: std::cout << "Initially in open waiting\n"; break;
459  // case kClosed: std::cout << "Initially in closed\n"; break;
460  // case kUnseen: std::cout << "Initially in UNSEEN\n"; break;
461  // }
462 
463  }
464  // TODO: store current solution
465  // printf("NBS Potential solution found, cost: %1.2f + %1.2f = %1.2f (%" PRId64 " nodes)\n",
466  // current.Lookup(nextID).g + edgeCost,
467  // opposite.Lookup(reverseLoc).g,
468  // current.Lookup(nextID).g + edgeCost + opposite.Lookup(reverseLoc).g,
469  // nodesExpanded);
470  currentCost = current.Lookup(nextID).g + edgeCost + opposite.Lookup(reverseLoc).g;
471 
472  middleNode = succ;
473  // std::cout << "One more time, solution passes through " << middleNode << " (first) \n";
474 
475  }
476 
477  }
478 
479  }
480  else {
481  //std::cout << "***Not adding " << succ << " to open because cost is worse than current of " << currentCost << "\n";
482  }
483  }
484 
485  }
486  break;
487  }
488  }
489 }
490 
491 
492 template <class state, class action, class environment, class dataStructure, class priorityQueue>
493 uint64_t NBS<state, action, environment, dataStructure, priorityQueue>::GetDoubleExpansions() const
494 {
495  uint64_t doubles = 0;
496  for (unsigned int x = 0; x < queue.forwardQueue.size(); x++)
497  {
498  uint64_t key;
499  const auto &data = queue.forwardQueue.Lookat(x);
500  if (data.where == kClosed)
501  {
502  auto loc = queue.backwardQueue.Lookup(env->GetStateHash(data.data), key);
503  if (loc == kClosed)
504  doubles++;
505  }
506 
507  }
508  return doubles;
509 }
510 
511 template <class state, class action, class environment, class dataStructure, class priorityQueue>
512 void NBS<state, action, environment, dataStructure, priorityQueue>::OpenGLDraw() const
513 {
514  OpenGLDraw(queue.forwardQueue);
515  OpenGLDraw(queue.backwardQueue);
516 }
517 
518 template <class state, class action, class environment, class dataStructure, class priorityQueue>
519 void NBS<state, action, environment, dataStructure, priorityQueue>::OpenGLDraw(const priorityQueue &q) const
520 {
521  double transparency = 0.9;
522  if (q.size() == 0)
523  return;
524  uint64_t top = -1;
525  // double minf = 1e9, maxf = 0;
526  if (q.OpenReadySize() > 0)
527  {
528  top = q.Peek(kOpenReady);
529  }
530  for (unsigned int x = 0; x < q.size(); x++)
531  {
532  const auto &data = q.Lookat(x);
533  if (x == top)
534  {
535  env->SetColor(1.0, 1.0, 0.0, transparency);
536  env->OpenGLDraw(data.data);
537  }
538  if (data.where == kOpenWaiting)
539  {
540  env->SetColor(0.0, 0.5, 0.5, transparency);
541  env->OpenGLDraw(data.data);
542  }
543  else if (data.where == kOpenReady)
544  {
545  env->SetColor(0.0, 1.0, 0.0, transparency);
546  env->OpenGLDraw(data.data);
547  }
548  else if (data.where == kClosed)
549  {
550  if (&q == &queue.backwardQueue)
551  env->SetColor(1.0, 0.0, 1.0, transparency);
552  else
553  env->SetColor(1.0, 0.0, 0.0, transparency);
554  env->OpenGLDraw(data.data);
555  }
556  }
557 }
558 
559 template <class state, class action, class environment, class dataStructure, class priorityQueue>
560 void NBS<state, action, environment, dataStructure, priorityQueue>::Draw(Graphics::Display &d) const
561 {
562  Draw(d, queue.forwardQueue);
563  Draw(d, queue.backwardQueue);
564 }
565 
566 template <class state, class action, class environment, class dataStructure, class priorityQueue>
567 void NBS<state, action, environment, dataStructure, priorityQueue>::Draw(Graphics::Display &d, const priorityQueue &q) const
568 {
569  double transparency = 0.9;
570  if (q.size() == 0)
571  return;
572  uint64_t top = -1;
573  // double minf = 1e9, maxf = 0;
574  if (q.OpenReadySize() > 0)
575  {
576  top = q.Peek(kOpenReady);
577  }
578  for (unsigned int x = 0; x < q.size(); x++)
579  {
580  const auto &data = q.Lookat(x);
581  if (x == top)
582  {
583  env->SetColor(1.0, 1.0, 0.0, transparency);
584  env->Draw(d, data.data);
585  }
586  else if (data.where == kOpenWaiting)
587  {
588  env->SetColor(1.0, 0.50, 0.25, transparency);
589  env->Draw(d, data.data);
590  }
591  else if (data.where == kOpenReady)
592  {
593  env->SetColor(1.0, 0.75, 0.25, transparency);
594  env->Draw(d, data.data);
595  }
596  else if (data.where == kClosed)
597  {
598  if (&q == &queue.backwardQueue)
599  env->SetColor(0.25, 0.5, 1.0, transparency);
600  else
601  env->SetColor(1.0, 0.0, 0.0, transparency);
602  env->Draw(d, data.data);
603  }
604  }
605 }
606 
607 template <class state, class action, class environment, class dataStructure, class priorityQueue>
608 void NBS<state, action, environment, dataStructure, priorityQueue>::DrawBipartiteGraph(Graphics::Display &d) const
609 {
610  double val = queue.GetLowerBound();
611  //currentCost
612  assert(!"Implementaion incomplete");
613  // Draw(d, queue.forwardQueue);
614  // Draw(d, queue.backwardQueue);
615 }
616 //void DrawBipartiteGraph(Graphics::Display &d);
617 
618 
619 #endif /* NBS_h */
NBS::GetBackwardItem
const BDOpenClosedData< state > & GetBackwardItem(unsigned int which)
Definition: NBS.h:56
kOpenWaiting
@ kOpenWaiting
Definition: BDOpenClosed.h:24
NBS::~NBS
virtual ~NBS()
Definition: NBS.h:38
NBS::SetBackwardHeuristic
void SetBackwardHeuristic(Heuristic< state > *h)
Definition: NBS.h:59
BDIndexOpenClosed.h
NBS::OpenGLDraw
void OpenGLDraw() const
Definition: NBS.h:512
fgreatereq
bool fgreatereq(double a, double b)
Definition: FPUtil.h:31
Heuristic
Definition: Heuristic.h:30
NBS::currentCost
double currentCost
Definition: NBS.h:160
NBS::currentPr
double currentPr
Definition: NBS.h:178
kOpenReady
@ kOpenReady
Definition: BDOpenClosed.h:23
NBS::env
environment * env
Definition: NBS.h:163
d
mcData d[]
Definition: MotionCaptureMovement.cpp:21
NBS::ExtractPathToStartFromID
void ExtractPathToStartFromID(uint64_t node, std::vector< state > &thePath)
Definition: NBS.h:140
NBS::queue
dataStructure queue
Definition: NBS.h:166
kClosed
@ kClosed
Definition: BDOpenClosed.h:25
NBS::goal
state goal
Definition: NBS.h:170
NBS::GetNodeForwardG
double GetNodeForwardG(const state &s)
Definition: NBS.h:71
FPUtil.h
NBS::GetNodesExpanded
uint64_t GetNodesExpanded() const
Definition: NBS.h:87
NBS::middleNode
state middleNode
Definition: NBS.h:159
NBS
Definition: NBS.h:32
NBS::ExtractPathToStart
void ExtractPathToStart(state &node, std::vector< state > &thePath)
Definition: NBS.h:133
NBS::start
state start
Definition: NBS.h:170
kUnseen
@ kUnseen
Definition: BDOpenClosed.h:26
NBS::GetNodesTouched
uint64_t GetNodesTouched() const
Definition: NBS.h:88
loc
Definition: MapGenerators.cpp:296
NBS::GetSolutionCost
double GetSolutionCost() const
Definition: NBS.h:109
NBS::ExpandAPair
bool ExpandAPair(std::vector< state > &thePath)
Definition: NBS.h:221
stateLocation
stateLocation
Definition: BDOpenClosed.h:22
Graphics::Display
Definition: Graphics.h:146
NBS::DrawBipartiteGraph
void DrawBipartiteGraph(Graphics::Display &d) const
Definition: NBS.h:608
fless
bool fless(double a, double b)
Definition: FPUtil.h:28
NBS::neighbors
std::vector< state > neighbors
Definition: NBS.h:162
BDOpenClosed.h
NBS::forwardHeuristic
Heuristic< state > * forwardHeuristic
Definition: NBS.h:172
Heuristic::HCost
virtual double HCost(const state &a, const state &b) const
Definition: Heuristic.h:73
NBS::GetNecessaryExpansions
uint64_t GetNecessaryExpansions() const
Definition: NBS.h:90
NBS::ExtractPathToGoalFromID
void ExtractPathToGoalFromID(uint64_t node, std::vector< state > &thePath)
Definition: NBS.h:124
NBS::expand
bool expand
Definition: NBS.h:176
NBS::GetNumBackwardItems
const int GetNumBackwardItems()
Definition: NBS.h:55
NBS::GetNodeBackwardLocation
stateLocation GetNodeBackwardLocation(const state &s)
Definition: NBS.h:66
NBS::GetName
virtual const char * GetName()
Definition: NBS.h:49
Graphics.h
BDOpenClosedData
Definition: BDOpenClosed.h:33
NBS::GetMeetingPoint
float GetMeetingPoint()
Definition: NBS.h:101
NBS::GetPath
void GetPath(environment *env, const state &from, const state &to, Heuristic< state > *forward, Heuristic< state > *backward, std::vector< state > &thePath)
Definition: NBS.h:184
NBS::GetNodeForwardLocation
stateLocation GetNodeForwardLocation(const state &s)
Definition: NBS.h:60
NBS::InitializeSearch
bool InitializeSearch(environment *env, const state &from, const state &to, Heuristic< state > *forward, Heuristic< state > *backward, std::vector< state > &thePath)
Definition: NBS.h:195
NBS::GetNumForwardItems
const int GetNumForwardItems()
Definition: NBS.h:53
NBS::DoSingleSearchStep
bool DoSingleSearchStep(std::vector< state > &thePath)
Definition: NBS.h:270
NBS::counts
std::unordered_map< double, int > counts
Definition: NBS.h:164
NBS::backwardHeuristic
Heuristic< state > * backwardHeuristic
Definition: NBS.h:173
NBS::GetDoubleExpansions
uint64_t GetDoubleExpansions() const
Definition: NBS.h:493
NBSQueue.h
NBS::ExtractFromMiddle
void ExtractFromMiddle(std::vector< state > &thePath)
Definition: NBS.h:256
NBS::nodesTouched
uint64_t nodesTouched
Definition: NBS.h:158
NBS::GetNodeBackwardG
double GetNodeBackwardG(const state &s)
Definition: NBS.h:79
NBS::Draw
void Draw(Graphics::Display &d) const
Definition: NBS.h:560
fequal
bool fequal(double a, double b, double tolerance=TOLERANCE)
Definition: FPUtil.h:32
NBS::ResetNodeCount
void ResetNodeCount()
Definition: NBS.h:51
NBS::ExtractPathToGoal
void ExtractPathToGoal(state &node, std::vector< state > &thePath)
Definition: NBS.h:118
NBS::NBS
NBS()
Definition: NBS.h:34
NBS::Expand
void Expand(uint64_t nextID, priorityQueue &current, priorityQueue &opposite, Heuristic< state > *heuristic, const state &target)
Definition: NBS.h:277
NBS::currentSolutionEstimate
double currentSolutionEstimate
Definition: NBS.h:161
NBS::nodesExpanded
uint64_t nodesExpanded
Definition: NBS.h:158
NBS::GetForwardItem
const BDOpenClosedData< state > & GetForwardItem(unsigned int which)
Definition: NBS.h:54
node
Nodes to be stored within a Graph.
Definition: Graph.h:170
NBS::SetForwardHeuristic
void SetForwardHeuristic(Heuristic< state > *h)
Definition: NBS.h:58
Generated by   doxygen 1.8.17