HOG2
CRAStar.cpp
Go to the documentation of this file.
1 /*
2  * $Id: craStar.cpp
3  * hog2
4  *
5  * Created by Nathan Sturtevant on 6/23/05.
6  * Modified by Nathan Sturtevant on 02/29/20.
7  *
8  * This file is part of HOG2. See https://github.com/nathansttt/hog2 for licensing information.
9  *
10  */
11 
12 #include "CRAStar.h"
13 #include "FPUtil.h"
14 #include "AStar3.h"
15 #include <cfloat>
16 #include <limits.h>
17 
18 using namespace GraphAbstractionConstants;
19 const int MAX_INT = 2147483647;
20 static const int verbose = 0;
21 
22 craStar::craStar()
23 :SearchAlgorithm()
24 {
25  partialLimit = -1;
26  expandSearchRadius = true;
27  sprintf(algName,"CRA*(%d)", partialLimit);
28 
29  absLevel = -1;
30  smoothing = true;
31  smType = BEGIN;
32 }
33 
34 path *craStar::GetPath(GraphAbstraction *aMap, node *from, node *to, reservationProvider *rp)
35 {
36  // std::cout<<"find path from "<<*from<<"\nto "<<*to<<std::endl;
37 
38  std::vector<node *> fromChain;
39  std::vector<node *> toChain;
40  path *lastPath = 0;
41 
42 
43  if (aMap->GetAbstractGraph(from->GetLabelL(kAbstractionLevel))->FindEdge(from->GetNum(), to->GetNum()))
44  return new path(from, new path(to));
45 
46  setupSearch(aMap, fromChain, from, toChain, to);
47  if (fromChain.size() == 0)
48  return 0;
49 
50 
51 
52  // do {
53  // // lastPath = buildNextAbstractPath(aMap, lastPath, fromChain, toChain, rp);
54  // // lastPath = buildNextAbstractPathQuick(aMap,lastPath,fromChain,toChain,rp);
55  // } while (lastPath->n->GetLabelL(kAbstractionLevel) > 0);
56 
57  path* abs = buildAbstractPath(aMap, fromChain, toChain, rp);
58 
59  if (partialLimit > 0)
60  {
61 
62  path *trav = abs;
63  path *thisPart = new path(trav->n);
64  for (int x = 0; x < partialLimit-1; x++)
65  {
66 
67  if (trav->next) {
68  trav = trav->next;
69  thisPart->tail()->next = new path(trav->n);
70  }
71  else
72  break;
73  }
74 
75  toChain.clear();
76  findGoalNode(aMap,trav->n,toChain);
77 
78  lastPath = doRefinement(aMap, thisPart, fromChain,toChain);
79  //delete thisPart;
80  }
81  else
82  lastPath = doRefinement(aMap, abs, fromChain, toChain);
83 
84  // if (verbose){
85  // std::cout<<"before smoothing :";
86  // lastPath->Print();
87  // std::cout<<std::endl;
88  //}
89 
90 
91 if (smoothing)
92 {
93 
94  path* p = lastPath;
95  lastPath = smoothPath(aMap,lastPath);
96  delete p;
97 }
98 return lastPath;
99 //return trimPath(lastPath, to);
100 }
101 
106 void craStar::findGoalNode(GraphAbstraction* aMap, node* n, std::vector<node *> &toChain)
107 {
108  int currLevel = n->GetLabelL(kAbstractionLevel);
109  if (currLevel==0)
110  {
111 
112  toChain.push_back(n);
113  }
114  else{
115  findGoalNode(aMap,aMap->GetAbstractGraph(currLevel-1)->GetNode(n->GetLabelL(kFirstData)), toChain);
116  toChain.push_back(n);
117  }
118 }
119 
120 void craStar::setupSearch(GraphAbstraction *aMap,
121  std::vector<node *> &fromChain, node *from,
122  std::vector<node *> &toChain, node *to)
123 {
124  nodesExpanded = 0;
125  nodesTouched = 0;
126 
127  if ((from == 0) || (to == 0) || (!aMap->Pathable(from, to)) || (from == to))
128  {
129  if (verbose) {
130  if (!from)
131  printf("craStar: from == 0\n");
132  if (!to)
133  printf("craStar: to == 0\n");
134  if (from == to)
135  printf("craStar: from == to\n");
136  if (from && to && (!aMap->Pathable(from, to)))
137  printf("craStar: no path from %p to %p\n", (void*)from, (void*)to);
138  //cout << "praStar: no path from " << *from << " to " << *to << endl;
139  }
140  return;
141  }
142 
143  if (verbose)
144  printf("At nodes #%d and %d\n", from->GetNum(), to->GetNum());
145 
146  aMap->GetNumAbstractGraphs(from, to, fromChain, toChain);
147 
148  unsigned int previousSize = fromChain.size();
149  int minNode = (int)(2*sqrt(aMap->GetAbstractGraph(0)->GetNumNodes()));
150 
151  if (absLevel > 0)
152  {
153 
154  while((int)fromChain.size()-1 > absLevel)
155  {
156 
157  toChain.pop_back();
158  fromChain.pop_back();
159  }
160  }
161  else{ // dynamic level selection
162  while ((fromChain.size() > 2) && ((fromChain.size() > (previousSize)/2) ||
163  (aMap->GetAbstractGraph(fromChain.size())->GetNumNodes() < minNode)))
164  {
165  toChain.pop_back();
166  fromChain.pop_back();
167  }
168  }
169 }
170 
174 path* craStar::buildAbstractPath(GraphAbstraction *aMap,
175  std::vector<node *> &fromChain,
176  std::vector<node *> &toChain,
177  reservationProvider *rp)
178 {
179  path *result;
180  aStarOld* astar = new aStarOld();
181 
182  node *to = 0;
183  node *from = 0;
184 
185  to = toChain.back();
186  from = fromChain.back();
187 
188  result = astar->GetPath(aMap, from, to, rp);
189 
190  nodesExpanded += astar->GetNodesExpanded();
191  nodesTouched += astar->GetNodesTouched();
192 
193  delete astar;
194 
195  return result;
196 }
197 
198 
199 
204 path *craStar::doRefinement(GraphAbstraction *aMap, path* absPath, std::vector<node*> &fromChain, std::vector<node*> &toChain)
205 {
206  assert((fromChain.size() == toChain.size()) && (toChain.back()->GetLabelL(kAbstractionLevel) == fromChain.back()->GetLabelL(kAbstractionLevel))
207  && (fromChain.back() == absPath->n));
208 
209  path* lastPath = absPath;
210 
211  while(fromChain.size() > 1)
212  {
213 
214  // Reset from & to
215  fromChain.pop_back();
216  node* from = fromChain.back();
217 
218  if (verbose) std::cout<<"Finding path at level "<<from->GetLabelL(kAbstractionLevel)<<std::endl;
219 
220  toChain.pop_back();
221  node* to = toChain.back();
222 
223  if (verbose) std::cout<<"From: "<<*from<<"\nto: "<<*to<<std::endl;
224 
225  path* apath = lastPath;
226 
227  int abstractLevel = apath->n->GetLabelL(kAbstractionLevel);
228 
229  if (verbose)
230  {
231 
232  std::cout<<"abstract path\n";
233  while(apath->next)
234  {
235 
236  std::cout<<*(apath->n)<<std::endl;
237  apath = apath->next;
238  }
239  std::cout<<*(apath->n)<<std::endl;
240  apath = lastPath;
241  }
242  node* currentLow = from;
243 
244  assert(aMap->GetNthParent(currentLow,abstractLevel) == apath->n);
245 
246  apath = apath->next;
247  path* returnPath = new path(currentLow);
248 
249  Graph* g = aMap->GetAbstractGraph(currentLow->GetLabelL(kAbstractionLevel));
250 
251  // check if the first node is an orphan
252  if (currentLow->GetNumEdges()==1)
253  {
254 
255  neighbor_iterator niter = currentLow->getNeighborIter();
256  int neighborNode = currentLow->nodeNeighborNext(niter);
257  nodesTouched++;
258  node* neigh = g->GetNode(neighborNode);
259  returnPath->tail()->next = new path(neigh);
260 
261  currentLow = neigh;
262  }
263 
264  while(apath->next)
265  {
266 
267  currentLow = getNextNode(aMap, currentLow, returnPath, apath, g, abstractLevel);
268  apath = apath->next;
269  }
270 
271  // do the last one
272  currentLow = getNextNode(aMap, currentLow, returnPath, apath, g, abstractLevel);
273 
274  // Fix up the end; make sure we get to "to"
275 
276  node* lastnode = currentLow;
277 
278  if (returnPath->tail()->n != to)
279  {
280 
281  if (!g->FindEdge(currentLow->GetNum(),to->GetNum()))
282  {
283 
284  // check if goal is an orphan
285  if (to->GetNumEdges() == 1)
286  {
287 
288  neighbor_iterator niter = to->getNeighborIter();
289  int neighborNode = to->nodeNeighborNext(niter);
290  nodesTouched++;
291  node* neigh = g->GetNode(neighborNode);
292  returnPath->tail()->next = new path(neigh);
293  g->FindEdge(currentLow->GetNum(), neigh->GetNum())->setMarked(true);
294  lastnode = neigh;
295  }
296  }
297 
298  g->FindEdge(lastnode->GetNum(), to->GetNum())->setMarked(true);
299  returnPath->tail()->next = new path(to);
300  }
301  delete lastPath;
302  lastPath = returnPath;
303 
304  }
305  return lastPath;
306 }
307 
311 node* craStar::getNextNode(GraphAbstraction *aMap, node* currentLow, path* returnPath, path* apath, Graph* g, int abstractLevel)
312 {
313  nodesExpanded++;
314 
315  std::vector<node*> neighbors(currentLow->GetNumEdges());
316  int numInArray = 0;
317  double minHeur = DBL_MAX;
318  int minIndex = -1;
319 
320  // Try to find a neighbor which has the next node in the abstract path as a parent
321  neighbor_iterator niter = currentLow->getNeighborIter();
322  int neighborNode = currentLow->nodeNeighborNext(niter);
323 
324  while(neighborNode != -1)
325  {
326  nodesTouched++;
327  node* neigh = g->GetNode(neighborNode);
328  if (aMap->GetNthParent(neigh,abstractLevel) == apath->n)
329  {
330 
331  returnPath->tail()->next = new path(neigh);
332  currentLow = neigh;
333  break;
334  }
335  else if (aMap->GetNthParent(neigh,abstractLevel) == aMap->GetNthParent(currentLow,abstractLevel))
336  {
337 
338  // same parent as current node --> add to array
339  neighbors[numInArray] = neigh;
340  double hdist = aMap->h(neigh,apath->n);
341  if (minHeur > hdist)
342  {
343 
344  minHeur = hdist;
345  minIndex = numInArray;
346  }
347 
348  numInArray++;
349 
350  }
351  neighborNode = currentLow->nodeNeighborNext(niter);
352  }
353 
354  if (neighborNode == -1)
355  {
356  // no direct neighbor with next abs node as parent
357  // try neighbors of the neighbor node with min heuristic distance to next abstract node
358  node* neigh = neighbors[minIndex];
359  neighbor_iterator niter2 = neigh->getNeighborIter();
360  int n2num = neigh->nodeNeighborNext(niter2);
361  nodesExpanded++;
362  while(n2num != -1)
363  {
364 
365  nodesTouched++;
366  node* n2 = g->GetNode(n2num);
367 
368  if (aMap->GetNthParent(n2,abstractLevel) == apath->n)
369  {
370 
371  g->FindEdge(currentLow->GetNum(),neigh->GetNum())->setMarked(true);
372  g->FindEdge(neigh->GetNum(), n2->GetNum())->setMarked(true);
373 
374  returnPath->tail()->next = new path(neigh, new path(n2));
375  currentLow = n2;
376 
377  break;
378  }
379  n2num = neigh->nodeNeighborNext(niter2);
380  }
381 
382  if (n2num == -1)
383  {
384 
385  // not min heuristic node - try the rest of the list
386  neighbors[minIndex] = neighbors[numInArray-1];
387 
388  for (int i=0; i<numInArray-1; i++)
389  {
390 
391  nodesExpanded++;
392  /*node*/ neigh = neighbors[i];
393  neighbor_iterator niter3 = neigh->getNeighborIter();
394  int nnum = neigh->nodeNeighborNext(niter3);
395 
396  // double check this code
397  while(nnum != -1)
398  {
399 
400  nodesTouched++;
401  node* n2 = g->GetNode(nnum);
402  if (aMap->GetNthParent(n2,abstractLevel) == apath->n)
403  {
404 
405  g->FindEdge(currentLow->GetNum(),neigh->GetNum())->setMarked(true);
406  g->FindEdge(neigh->GetNum(), n2->GetNum())->setMarked(true);
407 
408  returnPath->tail()->next = new path(neigh, new path(n2));
409  currentLow = n2;
410  break;
411  }
412  nnum = neigh->nodeNeighborNext(niter3);
413  }
414  }
415  }
416  }
417  return currentLow;
418 }
419 
420 
421 path *craStar::buildNextAbstractPath(GraphAbstraction *aMap, path *lastPath,
422  std::vector<node *> &fromChain,
423  std::vector<node *> &toChain,
424  reservationProvider *rp)
425 {
426  node *to, *from, *hTarget = 0;
427  to = toChain.back();
428  toChain.pop_back();
429  from = fromChain.back();
430  fromChain.pop_back();
431 
432  if (verbose)
433  printf("Expanded %d nodes before doing level %d\n", nodesExpanded, (int)from->GetLabelL(kAbstractionLevel));
434 
435  if (verbose)
436  printf("Building path from %d to %d (%ld/%ld)\n",
437  from->GetNum(), to->GetNum(), from->GetLabelL(kParent), to->GetLabelL(kParent));
438 
439  std::vector<node *> eligibleNodeParents;
440 
441  if (lastPath)
442  {
443  // cut path down to size of partial path limit
444  if (partialLimit > 0)
445  {
446  path *trav = lastPath;
447 
448  for (int x = 0; x < partialLimit; x++)
449  if (trav->next)
450  trav = trav->next;
451  // we don't need to reset the target if we have a complete path
452  // but we do if our complete path doesn't end in our target node
453  if ((trav->next != 0) || ((trav->next == 0) && ((int)trav->n->GetNum() != to->GetLabelL(kParent))))
454  {
455  to = trav->n;
456  if (trav->next)
457  hTarget = trav->next->n;
458  else
459  hTarget = to;
460  delete trav->next;
461  trav->next = 0;
462  if (verbose) printf("Setting target parent to %d\n", to->GetNum());
463  }
464  }
465 
466  Graph *g = aMap->GetAbstractGraph(lastPath->n->GetLabelL(kAbstractionLevel));
467  // find eligible nodes for lower level expansions
468  for (path *trav = lastPath; trav; trav = trav->next)
469  {
470  if (expandSearchRadius)
471  {
472  edge_iterator ei = trav->n->getEdgeIter();
473  for (edge *e = trav->n->edgeIterNext(ei); e; e = trav->n->edgeIterNext(ei)) {
474  if (e->getFrom() == trav->n->GetNum())
475  eligibleNodeParents.push_back(g->GetNode(e->getTo()));
476  else
477  eligibleNodeParents.push_back(g->GetNode(e->getFrom()));
478  }
479  }
480  eligibleNodeParents.push_back(trav->n);
481  }
482  }
483 
484  cAStar.setCorridor(&eligibleNodeParents);
485  delete lastPath;
486  path *result;
487  if (hTarget != 0)
488  {
489  result = cAStar.getBestPath(aMap, from, to, hTarget, rp);
490  }
491  else {
492  result = cAStar.GetPath(aMap, from, to, rp);
493  }
494  nodesExpanded += cAStar.GetNodesExpanded();
495  nodesTouched += cAStar.GetNodesTouched();
496  return result;
497 }
498 
499 path *craStar::trimPath(path *lastPath, node *origDest)
500 {
501  if (partialLimit != -1)
502  {
503  int parent = -1;
504  path *change = 0, *last = 0;
505  for (path *trav = lastPath; trav; trav = trav->next)
506  {
507  if (trav->n == origDest)
508  return lastPath;
509  if (trav->n->GetLabelL(kParent) != parent)
510  {
511  parent = trav->n->GetLabelL(kParent);
512  change = last;
513  }
514  last = trav;
515  }
516  if (change)
517  {
518  delete change->next;
519  change->next = 0;
520  }
521  }
522  return lastPath;
523 }
524 
525 
532 path* craStar::smoothPath(GraphAbstraction *m,path* p)
533 {
534  findMinMax(p);
535 
536  if (verbose) std::cout<<"Smoothing the path\n";
537 
538  // put the path nodes in a vector
539  lookup.clear();
540 // path* pcopy = p->Clone();
541 // path* ptr = pcopy;
542  int tempLabel=0;
543 
544  for (path *tmp = p; tmp != 0; tmp = tmp->next)
545  {
546  lookup.push_back(tmp->n);
547  // set key = index in lookup
548  tmp->n->SetLabelL(kTemporaryLabel,tempLabel);
549  tempLabel++;
550  }
551  unsigned int n = 0;
552  path* smooth = 0;
553 
554  while(true)
555  {
556 
557  //Skip blanks
558  while(lookup[n]==0 && n<lookup.size()-1)
559  n++;
560 
561  if (n>=lookup.size()-1)
562  {
563 
564  break;
565  }
566 
567  unsigned int last = lookup[n]->GetLabelL(kTemporaryLabel);
568 
569  if (last!=n)
570  {
571 
572  for (unsigned int i=n; i<last && i<lookup.size(); i++)
573  {
574 
575  lookup[i]=0;
576  }
577  n = last;
578  continue;
579  }
580 
581  int dir;
582  for (dir = NORTH; dir <= NW; dir++)
583  {
584 
585  // get a shortcut if it exists
586  path* pathToNode = nextPathNode(m,lookup[n],dir);
587 
588  // paste the shortcut into our current path
589  if (pathToNode)
590  {
591  int lastNode = pathToNode->tail()->n->GetLabelL(kTemporaryLabel);
592  int curr = pathToNode->n->GetLabelL(kTemporaryLabel);
593 
594  if (lastNode > curr && !nextInLookup(lastNode, curr,lookup))
595  {
596  // make sure it's not the next one
597 
598  unsigned int index = n;
599  path* pathCopy = pathToNode;
600  //path* backup = pathCopy;
601  unsigned int end = pathToNode->tail()->n->GetLabelL(kTemporaryLabel);
602 
603  while(pathCopy->next)
604  {
605 
606  //make sure we're not overwriting anything
607  assert(index <= end);
608 
609  lookup[index]=pathCopy->n;
610  pathCopy->n->SetLabelL(kTemporaryLabel,index);
611  pathCopy = pathCopy->next;
612  index++;
613  }
614  assert(index <= end);
615 
616  lookup[index]=pathCopy->n;
617  pathCopy->n->SetLabelL(kTemporaryLabel,index);
618 
619  index++;
620 
621  while(index<=end)
622  {
623 
624  lookup[index]= 0;
625  index++;
626  }
627 
628  if (smType==END)
629  {
630 
631  n = end;
632  }
633  else if (smType==TWO_BACK)
634  n = backTwoNodes(end,lookup);
635  else
636  n++;
637 
638  delete pathToNode; pathToNode = 0;
639  //delete backup;
640  break;
641 
642  }
643  else if (dir==NW)
644  {
645 
646  n++;
647  }
648 
649  delete pathToNode;
650  }
651  else if (dir==NW)
652  {
653 
654  n++;
655  }
656  } //end for every direction
657 
658 
659  }
660 
661  //Create smoothed path from lookup table
662  for (unsigned int i=0; i<lookup.size(); i++)
663  {
664 
665  if (lookup[i]!=0)
666  {
667 
668  if (!smooth)
669  smooth = new path(lookup[i],0);
670  else
671  smooth->tail()->next = new path(lookup[i],0);
672  }
673  }
674  return smooth;
675 }
676 
680 int craStar::backTwoNodes(int i, std::vector<node*> lookupVal)
681 {
682  i--;
683  while(lookupVal[i]==NULL)
684  {
685 
686  i--;
687  }
688  i--;
689  while(lookupVal[i]==NULL)
690  {
691 
692  i--;
693  }
694  return i;
695 }
696 
697 
703 bool craStar::nextInLookup(int last, int curr, std::vector<node*> lookupVal)
704 {
705  if (last<curr)
706  return false;
707 
708  for (int i=curr+1; i<=last; i++) //
709  {
710  if (i==last)
711  return true;
712  if (lookupVal[i]!=NULL)
713  return false;
714  }
715  return true;
716 }
717 
723 path* craStar::nextPathNode(GraphAbstraction *m,node* n, int dir)
724 {
725  Graph *g = m->GetAbstractGraph(0);
726 
727  int px = n->GetLabelL(kFirstData);
728  int py = n->GetLabelL(kFirstData+1);
729 
730  node* next = getNextNode(static_cast<MapAbstraction*>(m),px,py,dir);
731 
732  if (next)
733  {
734 
735  nodesTouched++;
736  int nextKey = next->GetLabelL(kTemporaryLabel);
737  edge* e = g->FindEdge(n->GetNum(), next->GetNum());
738 
739  if (e && (nextKey >= 0) && (nextKey < static_cast<int>(lookup.size())) && (lookup[nextKey]==next))
740  {
741 
742  //we're done - we found the path
743  return new path(n,new path(next));
744  }
745  else{ // look further for a path node
746  if (e)
747  {
748 
749  path * p = nextPathNode(m,next,dir);
750  if (p)
751  {
752 
753  return new path(n,p);
754  }
755  else // haven't found a path node
756  return 0;
757  }
758  else // no edge here
759  return 0;
760  }
761  }
762  else{ // we won't hit the path
763  return 0;
764  }
765 }
766 
771 node* craStar::getNextNode(MapAbstraction *m,int x, int y, int dir)
772 {
773  if ((x < minx) || (x > maxx) || (y < miny) || (y>maxy))
774  return 0;
775 
776  switch(dir)
777  {
778  case NORTH:
779  return m->GetNodeFromMap(x,y+1);
780  break;
781  case EAST:
782  return m->GetNodeFromMap(x+1,y);
783  break;
784  case SOUTH:
785  return m->GetNodeFromMap(x, y-1);
786  break;
787  case WEST:
788  return m->GetNodeFromMap(x-1, y);
789  break;
790  case NE:
791  return m->GetNodeFromMap(x+1, y+1);
792  break;
793  case SE:
794  return m->GetNodeFromMap(x+1, y-1);
795  break;
796  case SW:
797  return m->GetNodeFromMap(x-1, y-1);
798  break;
799  case NW:
800  return m->GetNodeFromMap(x-1, y+1);
801  break;
802  default:
803  return 0;
804  }
805 }
806 
810 void craStar::findMinMax(path* p)
811 {
812  minx = MAX_INT;
813  miny = MAX_INT;
814  maxx = -1;
815  maxy = -1;
816 
817  path* pcopy = p;
818 
819  while(pcopy->next)
820  {
821  int x = pcopy->n->GetLabelL(kFirstData);
822  int y = pcopy->n->GetLabelL(kFirstData+1);
823 
824  if (x < minx) minx = x;
825  if (x > maxx) maxx = x;
826 
827  if (y < miny) miny = y;
828  if (y > maxy) maxy = y;
829 
830  pcopy = pcopy->next;
831  }
832 
833  int x = pcopy->n->GetLabelL(kFirstData);
834  int y = pcopy->n->GetLabelL(kFirstData+1);
835 
836  if (x < minx) minx = x;
837  if (x > maxx) maxx = x;
838 
839  if (y < miny) miny = y;
840  if (y > maxy) maxy = y;
841 
842  assert((minx != MAX_INT)&&(miny != MAX_INT)&&(maxx != -1)&&(maxy != -1));
843 
844 }
craStar::TWO_BACK
@ TWO_BACK
Definition: CRAStar.h:40
craStar::SOUTH
@ SOUTH
Definition: CRAStar.h:30
GraphAbstraction
A generic class for basic operations on Graph abstractions.
Definition: GraphAbstraction.h:63
GraphAbstractionConstants
Definition: GraphAbstraction.h:22
node::SetLabelL
void SetLabelL(unsigned int index, long val) const
Definition: Graph.cpp:702
craStar::craStar
craStar()
Definition: CRAStar.cpp:22
craStar::trimPath
path * trimPath(path *lastPath, node *origDest)
Definition: CRAStar.cpp:499
aStarOld::GetPath
path * GetPath(GraphAbstraction *aMap, node *from, node *to, reservationProvider *rp=0)
Definition: AStar3.cpp:35
Graph::FindEdge
edge * FindEdge(unsigned int from, unsigned int to)
Finds an edge between nodes with ids from and to, no matter which direction.
Definition: Graph.cpp:230
neighbor_iterator
unsigned int neighbor_iterator
Definition: Graph.h:34
SearchAlgorithm::GetNodesTouched
uint64_t GetNodesTouched()
Definition: SearchAlgorithm.h:32
GraphAbstraction::GetAbstractGraph
Graph * GetAbstractGraph(int level)
return the abstract Graph at the given level
Definition: GraphAbstraction.h:74
craStar::minx
int minx
Definition: CRAStar.h:117
craStar::doRefinement
path * doRefinement(GraphAbstraction *aMap, path *absPath, std::vector< node * > &fromChain, std::vector< node * > &toChain)
Do a quick refinement of an abstract path.
Definition: CRAStar.cpp:204
edge::setMarked
void setMarked(bool marked)
Definition: Graph.h:149
craStar::algName
char algName[30]
Definition: CRAStar.h:101
path::n
node * n
Definition: Path.h:22
craStar::smType
SmoothType smType
Definition: CRAStar.h:113
edge_iterator
std::vector< edge * >::const_iterator edge_iterator
Definition: Graph.h:30
craStar::NORTH
@ NORTH
Definition: CRAStar.h:28
FPUtil.h
SearchAlgorithm::GetNodesExpanded
uint64_t GetNodesExpanded()
Definition: SearchAlgorithm.h:31
SearchAlgorithm::nodesTouched
uint32_t nodesTouched
Definition: SearchAlgorithm.h:37
craStar::BEGIN
@ BEGIN
Definition: CRAStar.h:38
AStar3.h
craStar::cAStar
corridorAStar cAStar
Definition: CRAStar.h:100
aStarOld
A sample A* implementation.
Definition: AStar3.h:26
MAX_INT
const int MAX_INT
Definition: CRAStar.cpp:19
craStar::smoothing
bool smoothing
Definition: CRAStar.h:114
Graph
A generic Graph class.
Definition: Graph.h:66
Graph::GetNode
node * GetNode(unsigned long num)
Definition: Graph.cpp:152
craStar::miny
int miny
Definition: CRAStar.h:119
craStar::expandSearchRadius
bool expandSearchRadius
Definition: CRAStar.h:99
craStar::setupSearch
void setupSearch(GraphAbstraction *aMap, std::vector< node * > &fromChain, node *from, std::vector< node * > &toChain, node *to)
Definition: CRAStar.cpp:120
CRAStar.h
craStar::WEST
@ WEST
Definition: CRAStar.h:31
craStar::buildNextAbstractPath
path * buildNextAbstractPath(GraphAbstraction *, path *lastPath, std::vector< node * > &fromChain, std::vector< node * > &toChain, reservationProvider *)
Definition: CRAStar.cpp:421
GraphAbstraction::h
virtual double h(node *a, node *b)=0
heuristic cost between any two nodes
craStar::maxy
int maxy
Definition: CRAStar.h:120
GraphAbstraction::Pathable
virtual bool Pathable(node *from, node *to)=0
is there a legal path between these 2 nodes?
Graph::getEdgeIter
edge_iterator getEdgeIter() const
Definition: Graph.cpp:315
GraphAbstractionConstants::kFirstData
@ kFirstData
Definition: GraphAbstraction.h:34
craStar::maxx
int maxx
Definition: CRAStar.h:118
craStar::absLevel
int absLevel
Definition: CRAStar.h:115
craStar::buildAbstractPath
path * buildAbstractPath(GraphAbstraction *aMap, std::vector< node * > &fromChain, std::vector< node * > &toChain, reservationProvider *rp)
Build an abstract path for quick refinement.
Definition: CRAStar.cpp:174
SearchAlgorithm::nodesExpanded
uint32_t nodesExpanded
Definition: SearchAlgorithm.h:36
craStar::NW
@ NW
Definition: CRAStar.h:35
GraphAbstractionConstants::kAbstractionLevel
@ kAbstractionLevel
Definition: GraphAbstraction.h:25
craStar::lookup
std::vector< node * > lookup
Definition: CRAStar.h:105
craStar::backTwoNodes
int backTwoNodes(int i, std::vector< node * > lookup)
Find the index of the node two nodes back in the path.
Definition: CRAStar.cpp:680
craStar::partialLimit
int partialLimit
Definition: CRAStar.h:98
Graph::GetNumNodes
int GetNumNodes()
Definition: Graph.cpp:403
craStar::findMinMax
void findMinMax(path *p)
Find the box that bounds the path for more efficient path smoothing.
Definition: CRAStar.cpp:810
node::nodeNeighborNext
int nodeNeighborNext(neighbor_iterator &) const
Definition: Graph.cpp:807
craStar::smoothPath
path * smoothPath(GraphAbstraction *m, path *p)
copied from hpaStar.cpp
Definition: CRAStar.cpp:532
path
std::vector< xyLoc > path
Definition: Sample.cpp:43
craStar::findGoalNode
void findGoalNode(GraphAbstraction *aMap, node *n, std::vector< node * > &toChain)
GIven an abstract level parent node n, find a new goal that is a 0-level child of n as well as the pa...
Definition: CRAStar.cpp:106
craStar::SW
@ SW
Definition: CRAStar.h:34
GraphAbstraction::GetNumAbstractGraphs
void GetNumAbstractGraphs(node *from, node *to, std::vector< node * > &fromChain, std::vector< node * > &toChain)
given 2 nodes, find as much of their hierarchy that exists in the Graph
Definition: GraphAbstraction.cpp:39
path::tail
path * tail()
Definition: Path.h:28
corridorAStar::GetPath
path * GetPath(GraphAbstraction *aMap, node *from, node *to, reservationProvider *rp=0)
Definition: CorridorAStar.cpp:28
craStar::nextInLookup
bool nextInLookup(int last, int curr, std::vector< node * > lookup)
find out whether last is the next 'real' index in the lookup table after curr.
Definition: CRAStar.cpp:703
craStar::nextPathNode
path * nextPathNode(GraphAbstraction *m, node *n, int dir)
shoot a ray in direction dir and see if you hit the path Return the better path if you find it; 0 if ...
Definition: CRAStar.cpp:723
node::GetNum
unsigned int GetNum() const
Definition: Graph.h:176
corridorAStar::getBestPath
path * getBestPath(GraphAbstraction *aMap, node *from, node *to, node *hGoal, reservationProvider *rp=0)
get the best path from FROM to TO.
Definition: CorridorAStar.cpp:33
GraphAbstractionConstants::kTemporaryLabel
@ kTemporaryLabel
Definition: GraphAbstraction.h:29
reservationProvider
Definition: ReservationProvider.h:33
SearchAlgorithm
A generic algorithm which can be used for pathfinding.
Definition: SearchAlgorithm.h:25
corridorAStar::setCorridor
void setCorridor(const std::vector< node * > *)
Definition: CorridorAStar.cpp:23
verbose
static const int verbose
Definition: CRAStar.cpp:20
craStar::NE
@ NE
Definition: CRAStar.h:32
craStar::EAST
@ EAST
Definition: CRAStar.h:29
GraphAbstractionConstants::kParent
@ kParent
Definition: GraphAbstraction.h:27
path::next
path * next
Definition: Path.h:23
node::GetLabelL
long GetLabelL(unsigned int index) const
Definition: Graph.h:220
craStar::GetPath
virtual path * GetPath(GraphAbstraction *aMap, node *from, node *to, reservationProvider *rp=0)
Definition: CRAStar.cpp:34
path
A linked list of nodes which form a continuous path.
Definition: Path.h:20
node::getNeighborIter
neighbor_iterator getNeighborIter() const
Definition: Graph.cpp:802
craStar::END
@ END
Definition: CRAStar.h:39
craStar::SE
@ SE
Definition: CRAStar.h:33
GraphAbstraction::GetNthParent
node * GetNthParent(node *which, int n)
return nth level parent of which or null if it doesn't exist
Definition: GraphAbstraction.cpp:67
node::GetNumEdges
int GetNumEdges()
Definition: Graph.h:204
node
Nodes to be stored within a Graph.
Definition: Graph.h:170
craStar::getNextNode
node * getNextNode(GraphAbstraction *aMap, node *currentLow, path *returnPath, path *apath, Graph *g, int abstractLevel)
Find the next node of the refined path.
Definition: CRAStar.cpp:311
edge
Edge class for connections between node in a Graph.
Definition: Graph.h:129
Generated by   doxygen 1.8.17