HOG2
MeroB.cpp
Go to the documentation of this file.
1 /*
2  * MeroB.cpp
3  * hog2
4  *
5  * by Zhifu Zhang
6  *
7  * This code is not optimized for speed, but rather emphasizing on correctness.
8  */
9 
10 #include "MeroB.h"
11 #include <cstring>
12 
13 const static bool verbose = false;
14 
15 void MeroB::GetPath(GraphEnvironment *_env, Graph* _g, graphState from, graphState to, std::vector<graphState> &thePath)
16 {
17  if (!InitializeSearch(_env,_g,from,to,thePath))
18  return;
19 
20  while(!DoSingleSearchStep(thePath))
21  {}
22 
23  if (thePath.size() > 0 && verbose)
24  printf("\nNodes expanded=%lld, Nodes touched=%lld.\n",GetNodesExpanded(),GetNodesTouched());
25 }
26 
27 bool MeroB::InitializeSearch(GraphEnvironment *_env, Graph* _g, graphState from, graphState to, std::vector<graphState> &thePath)
28 {
29  env = _env;
30  if (heuristic == 0)
31  heuristic = env;
32  g = _g;
33  nodesTouched = nodesExpanded = 0;
34  start = from;
35  goal = to;
36 
37  closedList.clear();
38  openQueue.reset();
39  FCache.reset();
40 
41  if ((from == UINT32_MAX) || (to == UINT32_MAX) || (from == to))
42  {
43  thePath.resize(0);
44  return false;
45  }
46 
47  // step (1)
48  MeroBUtil::SearchNode first(heuristic->HCost(start, goal), 0, start, start);
49  openQueue.Add(first);
50 
51  //if (verID == MB_B || verID == MB_BP)
52  F = 0;
53 
54  return true;
55 }
56 
57 bool MeroB::DoSingleSearchStep(std::vector<graphState> &thePath)
58 
59 {
60  if (verID == MB_BP)
61  return DoSingleStepBP(thePath);
62  else if (verID == MB_B)
63  return DoSingleStepB(thePath);
64  else
65  return DoSingleStepA(thePath);
66 }
67 
68 /* The steps refer to the pseudo codes of the corresponding algorithms */
69 
70 bool MeroB::DoSingleStepA(std::vector<graphState> &thePath)
71 {
72  // return false means the search is not finished, true otherwise
73 
74  /* step (2) */
75  if (openQueue.size() == 0)
76  {
77  thePath.resize(0); // no path found!
78  closedList.clear();
79  openQueue.reset();
80  env = 0;
81  return true;
82  }
83 
84  /* step (3) */
85  nodesExpanded++;
86  MeroBUtil::SearchNode topNode = openQueue.Remove();
87  graphState topNodeID = topNode.currNode;
88  closedList[topNodeID] = topNode;
89 
90  if (verbose)
91  {
92  printf("Expanding node %ld , gcost=%lf, h=%lf, f=%lf.\n",
93  topNodeID, topNode.gCost, topNode.fCost-topNode.gCost, topNode.fCost);
94  }
95 
96  /* step (4) */
97  if (env->GoalTest(topNodeID, goal))
98  {
99  ExtractPathToStart(topNodeID, thePath);
100  //closedList.clear();
101  //openQueue.reset();
102  //env = 0;
103 
104  // don't reset everything yet, since they are required by the rendering funciton
105  return true;
106  }
107 
108  /* step (5), computing gi is delayed */
109  neighbors.resize(0);
110  env->GetSuccessors(topNodeID, neighbors);
111 
112  for (unsigned int x = 0; x<neighbors.size(); x++)
113  {
114  nodesTouched++;
115 
116  /* step (5) */
117  graphState neighbor = neighbors[x];
118  double edgeWeight = env->GCost(topNodeID,neighbor);
119  double gcost = topNode.gCost + edgeWeight;
120  double h = heuristic->HCost(neighbor,goal);
121  double f = gcost + h;
122 
123  /* step (6), neither in OPEN nor CLOSED */
124  if (!openQueue.IsIn(MeroBUtil::SearchNode(neighbor)) && closedList.find(neighbor) == closedList.end())
125  {
126  MeroBUtil::SearchNode n(f, gcost, neighbor,topNodeID);
127  openQueue.Add(n);
128 
129  if (verbose)
130  {
131  printf("Adding node %ld to OPEN, gcost=%lf, h=%lf, f=%lf.\n",neighbor,gcost,f-gcost,f);
132  }
133  }
134 
135  /* step (7) */
136  else
137  {
138  MeroBUtil::SearchNode neighborNode;
139  if (openQueue.IsIn(MeroBUtil::SearchNode(neighbor)))
140  {
141  neighborNode = openQueue.find(MeroBUtil::SearchNode(neighbor));
142 
143  //if (neighborNode.gCost <= gcost)
144  if (!fgreater(neighborNode.gCost,gcost))
145  continue;
146 
147  if (verbose)
148  {
149  printf("Adjusting node %ld in OPEN, gcost=%lf, h=%lf, f=%lf; g_old=%lf.\n",neighbor,gcost,f-gcost,f, neighborNode.gCost);
150  }
151 
152  neighborNode.copy(f,gcost,neighbor,topNodeID); // parent is changed
153  openQueue.DecreaseKey(neighborNode); // adjust its position in OPEN
154  }
155  else if (closedList.find(neighbor) != closedList.end())
156  {
157  neighborNode = closedList.find(neighbor)->second;
158 
159  //if (neighborNode.gCost <= gcost)
160  if (!fgreater(neighborNode.gCost,gcost))
161  continue;
162 
163  if (verbose)
164  {
165  printf("Moving node %ld from CLOSED to OPEN, gcost=%lf, h=%lf, f=%lf; g_old=%lf.\n",neighbor,gcost,f-gcost,f, neighborNode.gCost);
166  }
167 
168  neighborNode.copy(f,gcost,neighbor,topNodeID); // parent is changed
169  closedList.erase(neighbor); // delete from CLOSED
170 
171  openQueue.Add(neighborNode); // add to OPEN
172  }
173  }
174  }
175 
176  return false;
177 }
178 
179 /* Algorithm B. step (3) is modified from algorithm A.*/
180 bool MeroB::DoSingleStepB(std::vector<graphState> &thePath)
181 {
182  /* step (2) */
183  if (openQueue.size() == 0)
184  {
185  thePath.resize(0); // no path found!
186  closedList.clear();
187  openQueue.reset();
188  FCache.reset();
189  env = 0;
190  return true;
191  }
192 
193  /* step (3) */
194  nodesExpanded++;
195 
196  // put those with f < F into cache
197  FCache.reset();
198  while(openQueue.size() > 0)
199 
200  {
201  MeroBUtil::SearchNode tmpNode = openQueue.top();
202  if (fless(tmpNode.fCost, F))
203  {
204  FCache.Add(openQueue.Remove());
205  }
206  else
207  break;
208  }
209 
210  // select the node to expand
211  MeroBUtil::SearchNode topNode;
212  if (FCache.size() > 0)
213  {
214  topNode = FCache.Remove();
215  }
216  else
217  {
218  topNode = openQueue.Remove();
219 
220  if (fgreater(topNode.fCost,F))
221  {
222  F = topNode.fCost; // update F
223  if (verbose)
224  {
225  printf("F updated to %lf.\n",F);
226  }
227  }
228  }
229 
230  // move remaining nodes from FCache back to openQueue
231  while (FCache.size() > 0)
232  {
233  openQueue.Add(FCache.Remove());
234  }
235 
236 
237  graphState topNodeID = topNode.currNode;
238  closedList[topNodeID] = topNode;
239 
240  if (verbose)
241  {
242  printf("Expanding node %ld , gcost=%lf, h=%lf, f=%lf.\n",topNodeID,topNode.gCost,topNode.fCost-topNode.gCost,topNode.fCost);
243  }
244 
245  /* step (4) */
246  if (env->GoalTest(topNodeID, goal))
247  {
248  ExtractPathToStart(topNodeID, thePath);
249  //closedList.clear();
250  //openQueue.reset();
251  FCache.reset();
252  //env = 0;
253 
254  // don't reset everything yet, since they are required by the rendering funciton
255  return true;
256  }
257 
258  /* step (5), computing gi is delayed */
259  neighbors.resize(0);
260  env->GetSuccessors(topNodeID, neighbors);
261 
262  for (unsigned int x = 0; x<neighbors.size(); x++)
263  {
264  nodesTouched++;
265 
266  /* step (5) */
267  graphState neighbor = neighbors[x];
268  double edgeWeight = env->GCost(topNodeID,neighbor);
269  double gcost = topNode.gCost + edgeWeight;
270  double h = heuristic->HCost(neighbor,goal);
271  double f = gcost + h;
272 
273  /* step (6), neither in OPEN nor CLOSED */
274  if (!openQueue.IsIn(MeroBUtil::SearchNode(neighbor)) && closedList.find(neighbor) == closedList.end() )
275 
276  {
277  MeroBUtil::SearchNode n(f,gcost,neighbor,topNodeID);
278  openQueue.Add(n);
279 
280  if (verbose)
281  {
282  printf("Adding node %ld to OPEN, gcost=%lf, h=%lf, f=%lf.\n",neighbor,gcost,f-gcost,f);
283  }
284  }
285  /* step (7) */
286  else {
287  MeroBUtil::SearchNode neighborNode;
288  if (openQueue.IsIn(MeroBUtil::SearchNode(neighbor)))
289  {
290  neighborNode = openQueue.find(MeroBUtil::SearchNode(neighbor));
291 
292  //if (neighborNode.gCost <= gcost)
293  if (!fgreater(neighborNode.gCost,gcost))
294  continue;
295 
296  if (verbose)
297  {
298  printf("Adjusting node %ld in OPEN, gcost=%lf, h=%lf, f=%lf; g_old=%lf.\n",neighbor,gcost,f-gcost,f, neighborNode.gCost);
299  }
300 
301  neighborNode.copy(f,gcost,neighbor,topNodeID); // parent is changed
302  openQueue.DecreaseKey(neighborNode); // adjust its position in OPEN
303  }
304  else if (closedList.find(neighbor) != closedList.end())
305  {
306  neighborNode = closedList.find(neighbor)->second;
307 
308  //if (neighborNode.gCost <= gcost)
309  if (!fgreater(neighborNode.gCost,gcost))
310  continue;
311 
312  if (verbose)
313  {
314  printf("Moving node %ld from CLOSED to OPEN, gcost=%lf, h=%lf, f=%lf; g_old=%lf.\n",
315  neighbor,gcost,f-gcost,f, neighborNode.gCost);
316  }
317 
318  neighborNode.copy(f,gcost,neighbor,topNodeID); // parent is changed
319  closedList.erase(neighbor); // delete from CLOSED
320 
321  openQueue.Add(neighborNode); // add to OPEN
322  }
323  }
324  }
325  return false;
326 }
327 
328 /* Algorithm B' . step (3a) (3b) are inserted into algorithm B. step (7) is also changed, since we need to store the updated h */
329 bool MeroB::DoSingleStepBP(std::vector<graphState> &thePath)
330 {
331  /* step (2) */
332  if (openQueue.size() == 0)
333 
334  {
335  thePath.resize(0); // no path found!
336  closedList.clear();
337  openQueue.reset();
338  FCache.reset();
339  env = 0;
340  return true;
341  }
342 
343  /* step (3) */
344  nodesExpanded++;
345 
346  // put those with f < F into cache
347  FCache.reset();
348  while(openQueue.size() > 0)
349  {
350  MeroBUtil::SearchNode tmpNode = openQueue.top();
351  if (fless(tmpNode.fCost , F))
352  {
353  FCache.Add(openQueue.Remove());
354  }
355  else
356  break;
357  }
358 
359  // select the node to expand
360  MeroBUtil::SearchNode topNode;
361  if (FCache.size() > 0)
362  {
363  topNode = FCache.Remove();
364  printf("Expanding a node below F.\n");
365  }
366  else
367  {
368  topNode = openQueue.Remove();
369 
370  if (fgreater(topNode.fCost,F))
371  {
372  F = topNode.fCost; // update F
373  if (verbose)
374  {
375  printf("F updated to %lf.\n",F);
376  }
377  }
378  }
379 
380  // move remaining nodes from FCache back to openQueue
381  while(FCache.size() > 0)
382  {
383  openQueue.Add(FCache.Remove());
384  }
385 
386  graphState topNodeID = topNode.currNode;
387  closedList[topNodeID] = topNode;
388 
389  if (verbose)
390  {
391  printf("Expanding node %ld , gcost=%lf, h=%lf, f=%lf.\n",topNodeID,topNode.gCost,topNode.fCost-topNode.gCost,topNode.fCost);
392  }
393 
394  /* step (4) */
395  if (env->GoalTest(topNodeID, goal))
396  {
397  ExtractPathToStart(topNodeID, thePath);
398  //closedList.clear();
399  //openQueue.reset();
400  FCache.reset();
401  //env = 0;
402 
403  // don't reset everything yet, since they are required by the rendering funciton
404  return true;
405  }
406 
407  /* step (5), computing gi is delayed */
408  neighbors.resize(0);
409  env->GetSuccessors(topNodeID, neighbors);
410 
411  double hTop = topNode.fCost - topNode.gCost;
412  double minH2 = DBL_MAX; // min ( edgeWeight(i) + h(neighbor(i)) )
413 
414  for (unsigned int x = 0; x<neighbors.size(); x++)
415  {
416  nodesTouched++;
417 
418  /* step (5) */
419  graphState neighbor = neighbors[x];
420  double edgeWeight = env->GCost(topNodeID,neighbor);
421  double gcost = topNode.gCost + edgeWeight;
422 
423  /* step Mero (3a) */
424  double h_tmp; // for printing reports only
425  double h;
426  // this is necessary because the modified h is stored in the node, not the environment
427  if (openQueue.IsIn(MeroBUtil::SearchNode(neighbor))) {
428  MeroBUtil::SearchNode nb = openQueue.find(MeroBUtil::SearchNode(neighbor));
429  h = max( nb.fCost - nb.gCost, hTop - edgeWeight);
430 
431  h_tmp = nb.fCost - nb.gCost;
432  }
433  else if (closedList.find(neighbor) != closedList.end())
434  {
435  MeroBUtil::SearchNode nb = closedList.find(neighbor)->second;
436  h = max( nb.fCost - nb.gCost, hTop - edgeWeight);
437 
438  h_tmp = nb.fCost - nb.gCost;
439  }
440  else
441  {
442  h = max( heuristic->HCost(neighbor,goal), hTop - edgeWeight);
443 
444  h_tmp = heuristic->HCost(neighbor,goal);
445  }
446 
447  if (verbose)
448  {
449  if (fgreater(h,h_tmp))
450  printf("Improving h of node %ld by Mero rule (a), %lf->%lf\n",neighbor,h_tmp,h);
451  }
452 
453  double f = gcost + h;
454 
455  /* step Mero (3b) */
456  minH2 = min(minH2, h + edgeWeight);
457 
458  /* step (6), neither in OPEN nor CLOSED */
459  if (!openQueue.IsIn(MeroBUtil::SearchNode(neighbor)) && closedList.find(neighbor) == closedList.end() )
460  {
461  MeroBUtil::SearchNode n(f,gcost,neighbor,topNodeID);
462  openQueue.Add(n);
463 
464  if (verbose)
465  {
466  printf("Adding node %ld to OPEN, gcost=%lf, h=%lf, f=%lf.\n",neighbor,gcost,f-gcost,f);
467  }
468  }
469  /* step (7) */
470  else
471  {
472  MeroBUtil::SearchNode neighborNode;
473  if (openQueue.IsIn(MeroBUtil::SearchNode(neighbor)))
474  {
475  neighborNode = openQueue.find(MeroBUtil::SearchNode(neighbor));
476 
477  //if (neighborNode.gCost <= gcost)
478  if (!fgreater(neighborNode.gCost,gcost))
479  {
480  if (fgreater(h , neighborNode.fCost - neighborNode.gCost))
481  {
482  // we may fail to update gcost, but still update h
483  f = h + neighborNode.gCost;
484  neighborNode.fCost = f;
485  openQueue.IncreaseKey(neighborNode);
486  }
487  continue;
488  }
489 
490  if (verbose)
491  {
492  printf("Adjusting node %ld in OPEN, gcost=%lf, h=%lf, f=%lf; g_old=%lf.\n",neighbor,gcost,f-gcost,f, neighborNode.gCost);
493  }
494 
495  if (fless(f , neighborNode.fCost))
496  {
497  neighborNode.copy(f,gcost,neighbor,topNodeID); // parent is changed
498  openQueue.DecreaseKey(neighborNode); // adjust its position in OPEN
499  }
500  else
501  {
502  neighborNode.copy(f,gcost,neighbor,topNodeID); // parent is changed
503  openQueue.IncreaseKey(neighborNode); // adjust its position in OPEN
504  }
505  }
506  else if (closedList.find(neighbor) != closedList.end())
507  {
508  neighborNode = closedList.find(neighbor)->second;
509 
510  //if (neighborNode.gCost <= gcost)
511  if (!fgreater(neighborNode.gCost,gcost))
512  {
513  if (fgreater(h , neighborNode.fCost - neighborNode.gCost))
514  {
515  // we may fail to update gcost, but still update h
516  f = h + neighborNode.gCost;
517  neighborNode.fCost = f;
518  closedList[neighbor] = neighborNode;
519  }
520  continue;
521  }
522 
523  if (verbose)
524  {
525  printf("Moving node %ld from CLOSED to OPEN, gcost=%lf, h=%lf, f=%lf; g_old=%lf.\n",neighbor,gcost,f-gcost,f, neighborNode.gCost);
526  }
527 
528  neighborNode.copy(f,gcost,neighbor,topNodeID); // parent is changed
529  closedList.erase(neighbor); // delete from CLOSED
530 
531  openQueue.Add(neighborNode); // add to OPEN
532  }
533  }
534  }
535  /* step Mero (3b), update h of parent */
536  if (fgreater(minH2 , hTop))
537  {
538  topNode.fCost = minH2 + topNode.gCost; // f = h + gcost
539  closedList[topNodeID] = topNode;
540 
541  if (verbose)
542  {
543  printf("Improving h of node %ld by Mero rule (b), %lf->%lf\n",topNodeID,hTop,minH2);
544  }
545  }
546 
547  return false;
548 }
549 
550 void MeroB::ExtractPathToStart(graphState goalNode, std::vector<graphState> &thePath)
551 {
552  MeroBUtil::SearchNode n;
553  if (closedList.find(goalNode) != closedList.end())
554  {
555  n = closedList[goalNode];
556  }
557  else {
558  n = openQueue.find(MeroBUtil::SearchNode(goalNode));
559  }
560 
561  do {
562  thePath.push_back(n.currNode);
563  n = closedList[n.prevNode];
564  } while (n.currNode != n.prevNode);
565  //thePath.push_back(n.currNode);
566 }
567 
568 
569 //void MeroB::OpenGLDraw(int) const
570 //{
571 // OpenGLDraw();
572 //}
573 
574 void MeroB::OpenGLDraw() const
575 {
576 // //float r,gcost,b;
577 // double x,y,z;
578 // const MeroBUtil::SearchNode sn;
579 // graphState nodeID;
580 // const MeroBUtil::SearchNode topn;
581 // char buf[100];
582 //
583 // // draw nodes
584 // node_iterator ni = g->getNodeIter();
585 // for (node* n = g->nodeIterNext(ni); n; n = g->nodeIterNext(ni))
586 // {
587 // MeroBUtil::graphGenerator::GetLoc(n,x,y,z);
588 //
589 // nodeID = (graphState) n->GetNum();
590 // // draw sphere first
591 //
592 // // if in closed
593 // MeroBUtil::NodeLookupTable::const_iterator hiter;
594 // if ((hiter = closedList.find(nodeID)) != closedList.end())
595 // {
596 // sn = hiter->second;
597 // glColor3f(1,0,0); // red
598 // DrawSphere(x,y,z,0.025);
599 //
600 // memset(buf,0,100);
601 // sprintf(buf,"%d [%d,%d,%d]",n->GetNum(), (int)sn.gCost, (int)(sn.fCost - sn.gCost), (int)sn.fCost);
602 // }
603 // // if in open
604 // else if (openQueue.IsIn(MeroBUtil::SearchNode(nodeID)))
605 // {
606 // sn = openQueue.find(MeroBUtil::SearchNode(nodeID));
607 //
608 // FCache.reset();
609 // while(openQueue.size() > 0)
610 // {
611 // MeroBUtil::SearchNode tmpNode = openQueue.top();
612 // if (fless(tmpNode.fCost , F))
613 // {
614 // FCache.Add(openQueue.Remove());
615 // }
616 // else
617 // break;
618 // }
619 //
620 // if (FCache.size() > 0)
621 // {
622 // topn = FCache.top();
623 // }
624 // else
625 // {
626 // topn = openQueue.top();
627 // }
628 //
629 // while(FCache.size() > 0)
630 // {
631 // openQueue.Add(FCache.Remove());
632 // }
633 //
634 // // if on top, blue
635 // if (topn.currNode == sn.currNode)
636 // {
637 // glColor3f(0,0,1);
638 // DrawSphere(x,y,z,0.025);
639 // }
640 // else // green
641 // {
642 // glColor3f(0,1,0);
643 // DrawSphere(x,y,z,0.025);
644 // }
645 //
646 // memset(buf,0,100);
647 // sprintf(buf,"%d [%ld,%ld,%ld]",n->GetNum(), (long)sn.gCost, (long)(sn.fCost - sn.gCost), (long)sn.fCost);
648 // }
649 // // neither in open nor closed, white
650 // else
651 // {
652 // continue;
653 //
654 // glColor3f(1,1,1); // white
655 // DrawSphere(x,y,z,0.025);
656 //
657 // memset(buf,0,100);
658 // sprintf(buf,"%d [?,%ld,?]",n->GetNum(), (long)h->HCost(nodeID,goal));
659 // }
660 //
661 // // draw the text info, in black
662 // DrawText(x,y,z+0.05,0,0,0,buf);
663 // }
664 //
665 // // draw edges
666 // edge_iterator ei = g->getEdgeIter();
667 // for (edge* e = g->edgeIterNext(ei); e; e = g->edgeIterNext(ei))
668 // {
669 // DrawEdge(e->getFrom(), e->getTo(), e->GetWeight());
670 // }
671 }
672 
673 void MeroB::DrawText(double x, double y, double z, float r, float gg, float b, char* str)
674 {
675  //glPushMatrix();
676  // rotate ?
677 
678  glPushMatrix();
679  glColor3f(r,gg,b);
680  glTranslatef(x,y,z);
681  glScalef(1.0/(20*120.0), 1.0/(20*120.0), 1);
682  glRotatef(180, 0.0, 0.0, 1.0);
683  glRotatef(180, 0.0, 1.0, 0.0);
684 
685  int i=0;
686  while(str[i])
687  {
688  //glutStrokeCharacter(GLUT_STROKE_ROMAN,str[i]);
689  i++;
690  }
691  glPopMatrix();
692 }
693 
694 void MeroB::DrawEdge(unsigned int from, unsigned int to, double weight)
695 {
696  double x1,y1,z1;
697  double x2,y2,z2;
698  char buf[100] = {0};
699 
700  node* nfrom = g->GetNode(from);
701  node* nto = g->GetNode(to);
702 
703  MeroBUtil::graphGenerator::GetLoc(nfrom,x1,y1,z1);
704  MeroBUtil::graphGenerator::GetLoc(nto,x2,y2,z2);
705 
706  // draw line segment
707  glBegin(GL_LINES);
708  glColor3f(1,1,0); // yellow
709  glVertex3f(x1,y1,z1);
710  glVertex3f(x2,y2,z2);
711  glEnd();
712 
713  // draw weight info
714  sprintf(buf,"%ld",(long)weight);
715  DrawText((x1+x2)/2, (y1+y2)/2, (z1+z2)/2 + 0.05, 1, 0, 0, buf); // in red
716 }
717 
MeroB::env
GraphEnvironment * env
Definition: MeroB.h:280
MeroBUtil::SearchNode::copy
void copy(double f, double g, graphState curr, graphState prev)
Definition: MeroB.h:42
graphMove
Definition: GraphEnvironment.h:34
min
double min(double a, double b)
Definition: FPUtil.h:35
graphState
unsigned long graphState
Definition: GraphEnvironment.h:32
MeroB::FCache
MeroBUtil::GQueue FCache
Definition: MeroB.h:283
OpenClosedList::DecreaseKey
void DecreaseKey(OBJ val)
Indicate that the key for a particular object has decreased.
Definition: OpenClosedList.h:96
MeroB::goal
graphState goal
Definition: MeroB.h:279
MeroB::DoSingleStepA
bool DoSingleStepA(std::vector< graphState > &thePath)
Definition: MeroB.cpp:70
GraphEnvironment::GetSuccessors
virtual void GetSuccessors(const graphState &stateID, std::vector< graphState > &neighbors) const
Definition: GraphEnvironment.cpp:75
MeroB::neighbors
std::vector< graphState > neighbors
Definition: MeroB.h:278
OpenClosedList::top
OBJ top()
Definition: OpenClosedList.h:39
neighbor
graphMove neighbor
Definition: RoadMap.h:17
MeroB::GetNodesExpanded
uint64_t GetNodesExpanded()
Definition: MeroB.h:258
MeroBUtil::SearchNode::currNode
graphState currNode
Definition: MeroB.h:52
OpenClosedList::IsIn
bool IsIn(const OBJ val) const
Returns true if the object is in the OpenClosedList.
Definition: OpenClosedList.h:121
Graph
A generic Graph class.
Definition: Graph.h:66
Graph::GetNode
node * GetNode(unsigned long num)
Definition: Graph.cpp:152
GraphEnvironment::GoalTest
virtual bool GoalTest(const graphState &state, const graphState &goal) const
Definition: GraphEnvironment.cpp:182
MeroB::InitializeSearch
bool InitializeSearch(GraphEnvironment *env, Graph *g, graphState from, graphState to, std::vector< graphState > &thePath)
Definition: MeroB.cpp:27
MeroB::DrawText
void DrawText(double x, double y, double z, float r, float g, float b, char *str)
Definition: MeroB.cpp:673
MeroB::nodesTouched
uint64_t nodesTouched
Definition: MeroB.h:277
MeroB::DoSingleStepB
bool DoSingleStepB(std::vector< graphState > &thePath)
Definition: MeroB.cpp:180
OpenClosedList::Add
void Add(OBJ val)
Add object into OpenClosedList.
Definition: OpenClosedList.h:77
fless
bool fless(double a, double b)
Definition: FPUtil.h:28
MeroB::verID
unsigned int verID
Definition: MeroB.h:275
MeroB::DoSingleStepBP
bool DoSingleStepBP(std::vector< graphState > &thePath)
Definition: MeroB.cpp:329
MeroB::OpenGLDraw
void OpenGLDraw() const
Definition: MeroB.cpp:574
MeroB::DoSingleSearchStep
bool DoSingleSearchStep(std::vector< graphState > &thePath)
Definition: MeroB.cpp:57
Heuristic::HCost
virtual double HCost(const state &a, const state &b) const
Definition: Heuristic.h:73
OpenClosedList::Remove
OBJ Remove()
Remove the item with the lowest key from the OpenClosedList & re-heapify.
Definition: OpenClosedList.h:143
GraphEnvironment::GCost
virtual double GCost(const graphState &state1, const graphState &state2) const
Definition: GraphEnvironment.cpp:173
MeroBUtil::SearchNode::fCost
double fCost
Definition: MeroB.h:50
MeroBUtil::SearchNode::prevNode
graphState prevNode
Definition: MeroB.h:53
MeroB::DrawEdge
void DrawEdge(unsigned int from, unsigned int to, double weight)
Definition: MeroB.cpp:694
MeroBUtil::SearchNode
Definition: MeroB.h:34
MeroB::start
graphState start
Definition: MeroB.h:279
MeroBUtil::graphGenerator::GetLoc
static void GetLoc(node *n, double &x, double &y, double &z)
Definition: MeroB.h:98
fgreater
bool fgreater(double a, double b)
Definition: FPUtil.h:29
max
#define max(a, b)
Definition: MinimalSectorAbstraction.cpp:40
MB_BP
#define MB_BP
Definition: MeroB.h:28
MeroB::g
Graph * g
Definition: MeroB.h:285
MeroB::GetPath
void GetPath(GraphEnvironment *env, Graph *_g, graphState from, graphState to, std::vector< graphState > &thePath)
Definition: MeroB.cpp:15
MeroB::closedList
MeroBUtil::NodeLookupTable closedList
Definition: MeroB.h:282
verbose
const static bool verbose
Definition: MeroB.cpp:13
MB_B
#define MB_B
Definition: MeroB.h:27
UINT32_MAX
#define UINT32_MAX
Definition: GenericAStar.h:22
MeroB::openQueue
MeroBUtil::PQueue openQueue
Definition: MeroB.h:281
MeroB::ExtractPathToStart
void ExtractPathToStart(graphState goalNode, std::vector< graphState > &thePath)
Definition: MeroB.cpp:550
OpenClosedList::find
OBJ find(OBJ val)
find this object in the Heap and return
Definition: OpenClosedList.h:163
MeroBUtil::SearchNode::gCost
double gCost
Definition: MeroB.h:51
MeroB.h
MeroB::F
double F
Definition: MeroB.h:276
MeroB::GetNodesTouched
uint64_t GetNodesTouched()
Definition: MeroB.h:259
OpenClosedList::IncreaseKey
void IncreaseKey(OBJ val)
Indicate that the key for a particular object has increased.
Definition: OpenClosedList.h:109
OpenClosedList::size
unsigned size()
Definition: OpenClosedList.h:42
MeroB::heuristic
Heuristic< graphState > * heuristic
Definition: MeroB.h:274
OpenClosedList::reset
void reset()
Remove all objects from queue.
Definition: OpenClosedList.h:67
GraphEnvironment
Definition: GraphEnvironment.h:291
MeroB::nodesExpanded
uint64_t nodesExpanded
Definition: MeroB.h:277
node
Nodes to be stored within a Graph.
Definition: Graph.h:170
Generated by   doxygen 1.8.17