HOG2
ClusterAbstraction.cpp
Go to the documentation of this file.
1 /*
2  * $Id: ClusterAbstraction.cpp
3  * hog2
4  *
5  * Created by Renee Jansen on 06/06/06.
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 "ClusterAbstraction.h"
13 #include "GenericAStar.h"
14 #include <cfloat>
15 #include <cmath>
16 #include <limits>
17 
18 using namespace GraphAbstractionConstants;
19 
20 class ClusterSearchEnvironment : public OldSearchCode::SearchEnvironment
21 {
22 public:
23  ClusterSearchEnvironment(GraphAbstraction *_aMap, int _level)
24  :aMap(_aMap), level(_level) {}
25 
26  void getNeighbors(uint32_t nodeID, std::vector<uint32_t> &neighbors)
27  {
28  node *n = aMap->GetAbstractGraph(level)->GetNode(nodeID);
29  neighbor_iterator ni = n->getNeighborIter();
30  for (long tmp = n->nodeNeighborNext(ni); tmp != -1; tmp = n->nodeNeighborNext(ni))
31  {
32  if (inCorridor(tmp))
33  neighbors.push_back(tmp);
34  }
35  }
36 
37  double heuristic(uint32_t node1, uint32_t node2)
38  {
39  return aMap->h(aMap->GetAbstractGraph(level)->GetNode(node1),
40  aMap->GetAbstractGraph(level)->GetNode(node2));
41  }
42 
43  double gcost(uint32_t node1, uint32_t node2)
44  {
45  return heuristic(node1, node2);
46  }
47 
48  void setCorridor(std::vector<node *> &corr)
49  {
50  corridor = corr;
51  if (corr.size() > 0)
52  {
53  corridorLevel = aMap->GetAbstractionLevel(corr[0]);
54  for (unsigned int x = 0; x < corridor.size(); x++)
55  corridor[x]->SetLabelL(kTemporaryLabel, x);
56  }
57  }
58 
59  bool inCorridor(uint32_t nodeID)
60  {
61  if (corridor.size() == 0)
62  return true;
63  node *n = aMap->GetAbstractGraph(level)->GetNode(nodeID);
64  node *parent = aMap->GetNthParent(n, corridorLevel);
65  if (parent)
66  {
67  unsigned int loc = parent->GetLabelL(kTemporaryLabel);
68  if ((loc < corridor.size()) && (corridor[loc] == parent))
69  return true;
70  }
71  return false;
72  }
73 private:
74  GraphAbstraction *aMap;
75  int level;
76  int corridorLevel;
77  std::vector<node *> corridor;
78 };
79 
80 
81 const static int verbose = 0;
82 
86 void Cluster::AddNode(int n)
87 {
88  nodes.push_back(n);
89 }
90 
95 ClusterAbstraction::ClusterAbstraction(Map *map, int _clusterSize)
96 :MapAbstraction(map),clusterSize(_clusterSize)
97 {
98  abstractions.push_back(GetMapGraph(map));
99  createClustersAndEntrances();
100  linkEntrancesAndClusters();
101  createAbstractGraph();
102 }
103 
104 ClusterAbstraction::~ClusterAbstraction()
105 {
106  Graph* g = abstractions[1];
107  edge_iterator ei = g->getEdgeIter();
108  edge* e = g->edgeIterNext(ei);
109  while(e)
110  {
111  path* p = temp[e];
112  temp.erase(e);
113  delete p;
114 
115  // ei = g->getEdgeIter();
116  e = g->edgeIterNext(ei);
117  }
118  paths.clear();
119 }
120 
125 void ClusterAbstraction::createClustersAndEntrances()
126 {
127  Map* map = MapAbstraction::GetMap();
128  int row=0, col=0, clusterId=0;
129  int horizSize,vertSize;
130 
131  if (verbose) std::cout<<"Creating clusters and entrances\n";
132 
133  for (int j = 0; j < map->GetMapHeight(); j+=clusterSize)
134  {
135  col=0;
136  for (int i = 0; i< map->GetMapWidth(); i+=clusterSize)
137  {
138  horizSize = min(clusterSize, map->GetMapWidth()-i);
139  vertSize = min(clusterSize, map->GetMapHeight()-j);
140  Cluster cluster(clusterId++,row,col,i,j,horizSize,vertSize);
141 
142  addCluster(cluster);
143  if (j > 0 && j < map->GetMapHeight())
144  {
145 
146  createHorizEntrances(i,i+horizSize-1,j-1,row-1,col);
147  }
148  if (i > 0 && i < map->GetMapWidth())
149  {
150 
151  createVertEntrances(j,j+vertSize-1,i-1,row,col-1);
152  }
153  col++;
154  }
155  row++;
156  }
157 
158  rows = row;
159  columns = col;
160 
161  if (verbose) std::cout<<"map is "<<map->GetMapHeight()<<" x "<<map->GetMapWidth()<<std::endl
162  <<"rows of clusters: "<<rows<<"\ncolumns of clusters: "<<columns<<std::endl;
163 }
164 
165 /*
166  * return the minimum of two integers (get from some library?)
167  */
168 int ClusterAbstraction::min(int i, int j)
169 {
170 
171  if (i<j) return i;
172  else return j;
173 }
174 
175 /*
176  * create the abstract Graph: create a node for each entrance and connect entrances with their
177  * "counterparts" in adjacent clusters, then set up the parent/child relationship between these
178  * abstract nodes in the map Graph, then create intra edges.
179  */
180 void ClusterAbstraction::createAbstractGraph()
181 {
182  abstractions.push_back(new Graph());
183  Graph *g = abstractions[1];
184 
185  addAbsNodes(g);
186  setUpParents(g);
187  computeClusterPaths(g);
188 
189  // std::cout<<"1st level of abstraction\n";
190  // g->Print(std::cout);
191  // std::cout<<"end of Graph\n\n";
192  createConnectivityGraph();
193  // abstractions[2]->Print(std::cout);
194 
195  if (verbose) std::cout<<"abstract Graph has "<<abstractions[1]->GetNumNodes()<<" nodes\n";
196  if (verbose) std::cout<<"abstract graphs has "<<abstractions[1]->GetNumEdges()<<" edges\n";
197 }
198 
199 /*
200 * add a cluster to the abstraction
201  */
202 void ClusterAbstraction::addCluster(Cluster c)
203 {
204  clusters.push_back(c);
205 }
206 
207 /*
208 * add an entrance to the abstraction
209  */
210 void ClusterAbstraction::addEntrance(Entrance e)
211 {
212  entrances.push_back(e);
213 }
214 
221 void ClusterAbstraction::createHorizEntrances(int start, int end, int latitude, int row, int col)
222 {
223  Map* map = MapAbstraction::GetMap();
224  Graph* g = abstractions[0];
225 
226  for (int i=start; i<=end; i++)
227  {
228 
229 
230  while((i<=end) && (!GetNodeFromMap(i,latitude) || !GetNodeFromMap(i,latitude+1)
231  ||!(g->FindEdge(GetNodeFromMap(i,latitude)->GetNum(), GetNodeFromMap(i,latitude+1)->GetNum()))))
232  {
233  i++;
234  }
235 
236  if (i>end)
237  return;
238 
239  int begin = i;
240  i++;
241  //int begin = i;
242  // std::cout<<GetNodeFromMap(i,latitude)<<" "<<GetNodeFromMap(i,latitude+1)<<std::endl;
243  while((i<=end)&&(GetNodeFromMap(i,latitude)) && (GetNodeFromMap(i,latitude+1))
244  && (g->FindEdge(GetNodeFromMap(i,latitude)->GetNum(), GetNodeFromMap(i,latitude+1)->GetNum()))
245  && ((i==start) || ((g->FindEdge(GetNodeFromMap(i-1,latitude)->GetNum(), GetNodeFromMap(i,latitude)->GetNum()))
246  && (g->FindEdge(GetNodeFromMap(i-1,latitude+1)->GetNum(), GetNodeFromMap(i,latitude+1)->GetNum())))))
247  {
248  i++;
249  }
250 
251  //add entrance(s)
252  if ((i - begin) >= MAX_ENTRANCE_WIDTH)
253  {
254  // create two new entrances, one for each end
255  Entrance entrance1(latitude, begin,-1,-1,
256  map->GetNodeNum(begin,latitude),
257  map->GetNodeNum(begin,latitude+1),
258  row, col, 1, HORIZONTAL);
259  addEntrance(entrance1);
260  Entrance entrance2(latitude, (i - 1),-1,-1,
261  map->GetNodeNum(i-1,latitude),
262  map->GetNodeNum(i-1,latitude+1),
263  row, col, 1, HORIZONTAL);
264  addEntrance(entrance2);
265  }
266  else
267  {
268  // create one entrance in the middle
269  Entrance entrance(latitude, ((i - 1) + begin)/2,-1,-1,
270  map->GetNodeNum(((i - 1) + begin)/2,latitude),
271  map->GetNodeNum(((i - 1) + begin)/2,latitude+1),
272  row, col, (i - begin), HORIZONTAL);
273  addEntrance(entrance);
274  }
275  i--;
276  }
277 }
278 
284 void ClusterAbstraction::createVertEntrances(int start, int end, int meridian, int row, int col)
285 {
286  Map* map = MapAbstraction::GetMap();
287 
288  Graph* g = abstractions[0];
289  for (int i=start; i<=end; i++)
290  {
291 
292 
293  while((i<=end)&& (!GetNodeFromMap(meridian,i) || !GetNodeFromMap(meridian+1,i)
294  || (!(g->FindEdge(GetNodeFromMap(meridian,i)->GetNum(), GetNodeFromMap(meridian+1,i)->GetNum())))))
295  {
296  i++;
297  }
298 
299 
300 
301  if (i>end)
302  return;
303 
304  int begin = i;
305 
306  i++;
307 
308  while((i<=end) && (GetNodeFromMap(meridian,i)) && (GetNodeFromMap(meridian+1,i))
309  && (g->FindEdge(GetNodeFromMap(meridian,i)->GetNum(), GetNodeFromMap(meridian+1,i)->GetNum()))
310  && ((i==start) || ((g->FindEdge(GetNodeFromMap(meridian,i-1)->GetNum(), GetNodeFromMap(meridian,i)->GetNum()))
311  && (g->FindEdge(GetNodeFromMap(meridian+1,i-1)->GetNum(), GetNodeFromMap(meridian+1,i)->GetNum())))))
312  {
313  i++;
314  }
315 
316  //add entrance(s)
317  if ((i - begin) >= MAX_ENTRANCE_WIDTH)
318  {
319  // create two entrances, one for each end
320  Entrance entrance1(begin, meridian,-1,-1,
321  map->GetNodeNum(meridian,begin),
322  map->GetNodeNum(meridian+1,begin),
323  row, col, 1, VERTICAL);
324  addEntrance(entrance1);
325  Entrance entrance2((i - 1), meridian,-1,-1,
326  map->GetNodeNum(meridian,i-1),
327  map->GetNodeNum(meridian+1,i-1),
328  row, col, 1, VERTICAL);
329  addEntrance(entrance2);
330  }
331  else
332  {
333  // create one entrance
334  Entrance entrance(((i - 1) + begin)/2, meridian,-1,-1,
335  map->GetNodeNum(meridian,((i - 1) + begin)/2),
336  map->GetNodeNum(meridian+1,((i - 1) + begin)/2),
337  row, col, (i - begin), VERTICAL);
338  addEntrance(entrance);
339  }
340 
341  i--;
342 
343  }
344 
345 
346 }
347 
351 void ClusterAbstraction::linkEntrancesAndClusters()
352 {
353  if (verbose) std::cout<<"linking entrances and clusters\n";
354 
355  int cluster1Id;
356  int cluster2Id;
357  for (unsigned int i = 0; i < entrances.size(); i++)
358  {
359 
360  Entrance &entrance = entrances[i];
361  // std::cout<<"entrance getrow: "<<entrance.getRow()<<" entrance.getcol: "<<entrance.getCol()<<std::endl;
362  switch (entrance.getOrientation())
363  {
364  case HORIZONTAL:
365  {
366  cluster1Id = getClusterId(entrance.getRow(), entrance.getCol());
367  cluster2Id = getClusterId(entrance.getRow() + 1, entrance.getCol());
368 
369  // update entrance
370  entrance.setCluster1Id(cluster1Id);
371  entrance.setCluster2Id(cluster2Id);
372  }
373  break;
374  case VERTICAL:
375  {
376  cluster1Id = getClusterId(entrance.getRow(), entrance.getCol());
377  cluster2Id = getClusterId(entrance.getRow(), entrance.getCol() + 1);
378  entrance.setCluster1Id(cluster1Id);
379  entrance.setCluster2Id(cluster2Id);
380  }
381  break;
382  default:
383  assert(false);
384  break;
385  }
386  }
387 }
388 
392 void ClusterAbstraction::addAbsNodes(Graph* g)
393 {
394  Map* map = MapAbstraction::GetMap();
395  if (verbose) std::cout<<"adding abstract nodes\n";
396  int newnode1=-1;
397  int newnode2=-1;
398 
399  recVec ans;
400  double r;
401  int num=-1;
402 
403  for (unsigned int i=0; i<entrances.size(); i++)
404  {
405 
406  Entrance &entrance = entrances[i];
407  int cluster1Id = entrance.getCluster1Id();
408  int cluster2Id = entrance.getCluster2Id();
409  switch (entrance.getOrientation())
410  {
411  case HORIZONTAL:
412  {
413  // create node for 1st cluster
414  map->GetOpenGLCoord(entrance.getCenter1Col(), entrance.getCenter1Row(), ans.x,ans.y,ans.z,r);
415 
416  Cluster& c1 = getCluster(entrance.getCluster1Id());
417  num = nodeExists(c1,ans.x,ans.y,g);
418 
419  if (num==-1)
420  {
421 
422  node* n1 = new node("");
423  newnode1 = g->AddNode(n1);
424  n1->SetLabelL(kParent,-1);
425  n1->SetLabelL(kAbstractionLevel,1);
426  n1->SetLabelF(kXCoordinate,ans.x);
427  n1->SetLabelF(kYCoordinate,ans.y);
428  n1->SetLabelF(kZCoordinate,-10*r);
429  n1->SetLabelL(kNumAbstractedNodes,0);
430  c1.AddNode(newnode1);
431  }
432  else{
433  newnode1 = num;
434  }
435 
436  map->GetOpenGLCoord(entrance.getCenter1Col(), entrance.getCenter1Row()+1, ans.x,ans.y,ans.z,r);
437  Cluster& c2 = getCluster(cluster2Id);
438 
439  num = nodeExists(c2,ans.x,ans.y,g);
440  if (num==-1)
441  {
442 
443  node* n2= new node("");
444  newnode2 = g->AddNode(n2);
445  n2->SetLabelL(kParent,-1);
446  n2->SetLabelL(kAbstractionLevel,1);
447  n2->SetLabelF(kXCoordinate,ans.x);
448  n2->SetLabelF(kYCoordinate,ans.y);
449  n2->SetLabelF(kZCoordinate,-10*r);
450  n2->SetLabelL(kNumAbstractedNodes,0);
451 
452  c2.AddNode(newnode2);
453  }
454  else{
455  newnode2=num;
456  }
457  //add inter-edge
458  g->AddEdge(new edge(newnode1,newnode2,1));
459 
460  }
461  break;
462  case VERTICAL:
463  {
464  map->GetOpenGLCoord(entrance.getCenter1Col(), entrance.getCenter1Row(), ans.x,ans.y,ans.z,r);
465 
466  Cluster& c1 = getCluster(cluster1Id);
467  num = nodeExists(c1,ans.x,ans.y,g);
468  if (num==-1)
469  {
470 
471  node* n1 = new node("");
472  newnode1 = g->AddNode(n1);
473  n1->SetLabelL(kParent,-1);
474  n1->SetLabelL(kAbstractionLevel,1);
475  n1->SetLabelF(kXCoordinate,ans.x);
476  n1->SetLabelF(kYCoordinate,ans.y);
477  n1->SetLabelF(kZCoordinate,-10*r);
478  n1->SetLabelL(kNumAbstractedNodes,0);
479 
480  c1.AddNode(newnode1);
481  }
482  else{
483  newnode1 = num;
484  }
485 
486 
487  map->GetOpenGLCoord(entrance.getCenter1Col()+1, entrance.getCenter1Row(),ans.x,ans.y,ans.z,r);
488 
489  Cluster& c2 = getCluster(cluster2Id);
490  num = nodeExists(c2,ans.x,ans.y,g);
491  if (num==-1)
492  {
493 
494  node* n2 = new node("");
495 
496  newnode2 = g->AddNode(n2);
497  n2->SetLabelL(kParent,-1);
498  n2->SetLabelL(kAbstractionLevel,1);
499  n2->SetLabelF(kXCoordinate,ans.x);
500  n2->SetLabelF(kYCoordinate,ans.y);
501  n2->SetLabelF(kZCoordinate,-10*r);
502  n2->SetLabelL(kNumAbstractedNodes,0);
503 
504  c2.AddNode(newnode2);
505  }
506  else{
507  newnode2=num;
508  }
509  //add inter-edge
510  g->AddEdge(new edge(newnode1, newnode2, 1));
511 
512  }
513  break;
514  default:
515  assert(false);
516  break;
517  }
518  }
519 }
520 
521 /*
522  * Compute the paths inside each cluster. For each pair of entrances inside a cluster, find out if
523  * there is a path that only uses nodes inside the cluster. If there is, add an edge to the abstract
524  * Graph with the path distance as its weight and cache the path in the hash map.
525  *
526  * can make this more efficient?
527  */
528 void ClusterAbstraction::computeClusterPaths(Graph* g)
529 {//int total=0;
530  Map* map = MapAbstraction::GetMap();
531  if (verbose) std::cout<<"computing cluster paths\n";
532  for (unsigned int i=0; i<clusters.size(); i++)
533  {
534  Cluster& c = clusters[i];
535 
536  std::vector<node*> corridor;
537  for (int l=0; l<c.GetNumNodes(); l++)
538  {
539  corridor.push_back(g->GetNode(c.getIthNodeNum(l)));
540  }
541  for (unsigned int j=0; j < c.parents.size(); j++)
542  corridor.push_back(c.parents[j]);
543 
544  //int num = 0;
545  for (int j=0; j<c.GetNumNodes(); j++)
546  {
547  for (int k=j+1; k<c.GetNumNodes();k++)
548  {
549 
550  // find bottom level nodes
551  node* absStart = g->GetNode(c.getIthNodeNum(j));
552  node* absGoal = g->GetNode(c.getIthNodeNum(k));
553 
554  // find start/end coordinates (same in abstract and bottom level)
555  double startx = absStart->GetLabelF(kXCoordinate);
556  double starty = absStart->GetLabelF(kYCoordinate);
557  double startz = absStart->GetLabelF(kZCoordinate);
558 
559  double goalx = absGoal->GetLabelF(kXCoordinate);
560  double goaly = absGoal->GetLabelF(kYCoordinate);
561  double goalz = absGoal->GetLabelF(kZCoordinate);
562 
563  point3d s(startx,starty,startz);
564  point3d gl(goalx,goaly,goalz);
565 
566  int px;
567  int py;
568 
569  map->GetPointFromCoordinate(s,px,py);
570 
571  node* start = GetNodeFromMap(px,py);
572 
573  map->GetPointFromCoordinate(gl,px,py);
574 
575  node* goal = GetNodeFromMap(px,py);
576 
577  int startnum = c.getIthNodeNum(j);
578  int goalnum = c.getIthNodeNum(k);
579 
580  //find path
581 // corridorAStar astar;
582 // astar.setCorridor(&corridor);
583 // path* p = astar.GetPath(static_cast<MapAbstraction*>(this), start, goal);
584 
585  GenericAStar astar;
586  ClusterSearchEnvironment cse(this, GetAbstractionLevel(start));
587  cse.setCorridor(corridor);
588  std::vector<uint32_t> resultPath;
589  astar.GetPath(&cse, start->GetNum(), goal->GetNum(),
590  resultPath);
591  path *p = 0;
592  for (unsigned int x = 0; x < resultPath.size(); x++)
593  p = new path(GetAbstractGraph(start)->GetNode(resultPath[x]), p);
594 
595  if (p!=0)
596  {
597  //get its length
598  double dist = distance(p);
599 
600  //create edge
601  edge* newedge = new edge(startnum, goalnum, dist);
602  g->AddEdge(newedge);
603 
604  //store path
605  paths[newedge] = p;
606  }
607  }
608  }
609  }
610 }
611 
615 int ClusterAbstraction::getClusterId(int row, int col) const
616 {
617  // assert?
618  return row * columns + col;
619 }
620 
624 int ClusterAbstraction::getClusterIdFromCoord(int row, int col) const
625 {
626  // put in assert?
627  int crow = row / clusterSize;
628  int ccol = col / clusterSize;
629  return getClusterId(crow, ccol);
630 }
631 
635 Cluster& ClusterAbstraction::getCluster(int id)
636 {
637  assert (0 <= id && id < (int)clusters.size());
638  return clusters[id];
639 }
640 
646 //this could probably be done more efficiently. Reference to the node in the cluster?
647 //(instead of node number) What about storing more efficiently ? hash map inside
648 //createabsnodes?
649 int ClusterAbstraction::nodeExists(const Cluster& c,double x,double y, Graph* g)
650 {
651  int n=-1;
652  for (int i=0; i< c.GetNumNodes(); i++)
653  {
654 
655  n = c.getIthNodeNum(i);
656  node* no = g->GetNode(n);
657  if ((no->GetLabelF(kXCoordinate)==x) && (no->GetLabelF(kYCoordinate)==y))
658  {
659 
660  return n;
661  }
662  }
663  return -1;
664 }
665 
671 int ClusterAbstraction::getClusterIdFromNode(node* n)
672 {
673 
674  Map* map = MapAbstraction::GetMap();
675  if (n->GetLabelL(kAbstractionLevel) == 0)
676  return getClusterIdFromCoord(n->GetLabelL(kFirstData+1),n->GetLabelL(kFirstData));
677  else{
678  point3d s(n->GetLabelF(kXCoordinate),n->GetLabelF(kYCoordinate),-1);
679  int px;
680  int py;
681 
682  map->GetPointFromCoordinate(s,px,py);
683  return getClusterIdFromCoord(py,px);
684  }
685 }
686 
687 
695 void ClusterAbstraction::setUpParents(Graph* g)
696 {
697 
698 
699  if (verbose) std::cout<<"Setting up parents\n";
700  Map* map = MapAbstraction::GetMap();
701 
702  std::vector<node*> dummies;
703  int numOrigNodes = g->GetNumNodes();
704 
705  // create ALL DUMMY PARENTS first
706  for (unsigned int i=0; i<clusters.size(); i++)
707  {
708 
709  Cluster& c = clusters[i];
710 
711  node* dummyParent = new node("");
712  dummyParent->SetLabelL(kAbstractionLevel, 1);
713  dummyParent->SetLabelL(kNumAbstractedNodes, 0); // number of abstracted nodes
714  dummyParent->SetLabelL(kParent, -1);
715  dummyParent->SetLabelF(kXCoordinate, kUnknownPosition);
716  dummyParent->SetLabelL(kNodeBlocked, 0);
717 
718 
719  g->AddNode(dummyParent);
720  dummies.push_back(dummyParent);
721 
722  for (int x=c.getHOrig(); x<c.getHOrig()+c.getWidth(); x++)
723  {
724 
725  for (int y=c.getVOrig(); y<c.getVOrig()+c.GetHeight(); y++)
726  {
727 
728  if (map->GetNodeNum(x,y) >= 0)
729  {
730  node* n = GetNodeFromMap(x,y);
731  buildNodeIntoParent(n, dummyParent);
732  }
733  }
734  }
735  }
736 
737  int numNodesAfter = g->GetNumNodes();
738 
739  for (unsigned int i=0; i<clusters.size(); i++)
740  {
741 
742  Cluster& c = clusters[i];
743  //Create the corridor
744  std::vector<node*> corridor;
745  corridor.push_back(dummies[i]);
746 
747  for (int l=0; l<c.GetNumNodes(); l++)
748  {
749  corridor.push_back(g->GetNode(c.getIthNodeNum(l)));
750  }
751 
752 // corridorAStar astar;
753 // astar.setCorridor(&corridor);
754 
755  // std::cout<<"corridor has: "<<std::endl;
756  // for (unsigned int bla = 0; bla<corridor.size(); bla++)
757  // std::cout<<corridor[bla]<<" ("<<corridor[bla]->GetLabelL(kNumAbstractedNodes)<<") ";
758  // std::cout<<std::endl;
759 
760  //Find parent for each node
761  for (int x=c.getHOrig(); x<c.getHOrig()+c.getWidth(); x++)
762  {
763  for (int y=c.getVOrig(); y<c.getVOrig()+c.GetHeight(); y++)
764  {
765  if (map->GetNodeNum(x,y) >= 0)
766  {
767  node* mnode = GetNodeFromMap(x,y);
768 
769  // reset minimum
770  double minDist = DBL_MAX;
771  node* entrance = 0;
772 
773  //for every abstract (entrance node) in this cluster
774  for (int k=0; k<c.GetNumNodes(); k++)
775  {
776  //get the entrance
777  int nodenum = c.getIthNodeNum(k);
778 
779  node* n = g->GetNode(nodenum);
780  node* low = getLowLevelNode(n);
781 
782  if (low==mnode)
783  {
784  entrance = n;
785  break;
786  }
787 
788  //See if there's a path within this cluster
789 // astar.setCorridor(&corridor);
790 // path* p = astar.GetPath(static_cast<MapAbstraction*>(this),low,mnode);
791  GenericAStar astar;
792  ClusterSearchEnvironment cse(this, GetAbstractionLevel(low));
793  cse.setCorridor(corridor);
794  std::vector<uint32_t> resultPath;
795  astar.GetPath(&cse, low->GetNum(), mnode->GetNum(),
796  resultPath);
797  path *p = 0;
798  for (unsigned int t = 0; t < resultPath.size(); t++)
799  p = new path(GetAbstractGraph(low)->GetNode(resultPath[t]), p);
800 
801  if (p!=0)
802  {
803  // std::cout<<"corridor has: "<<std::endl;
804  // for (unsigned int bla = 0; bla<corridor.size(); bla++)
805  // std::cout<<corridor[bla]<<" ("<<corridor[bla]->GetLabelL(kNumAbstractedNodes)<<") ";
806  // std::cout<<std::endl;
807  // }
808 
809  // find distance to this point
810  point3d s(n->GetLabelF(kXCoordinate),n->GetLabelF(kYCoordinate),-1);
811  int px;
812  int py;
813  map->GetPointFromCoordinate(s,px,py);
814 
815  // calculate the distance to this entrance
816 
817  double dist = distance(p);
818 
819  if (dist<minDist)
820  {
821 
822  minDist=dist;
823  entrance=n;
824 
825  }
826  delete p;
827  }
828  }
829 
830  //std::cout<<entrance<<std::endl;
831  if (entrance)
832  {
833 
834  point3d s(entrance->GetLabelF(kXCoordinate),entrance->GetLabelF(kYCoordinate),-1);
835  int px;
836  int py;
837  map->GetPointFromCoordinate(s,px,py);
838  buildNodeIntoParent(mnode, entrance);
839  }
840  // else
841  //std::cout<<" no parent\n";
842  }//end if (not out of bounds)
843  }
844  }
845 }
846 // for (unsigned int i=0;i<dummies.size(); i++){
847 // // make sure no node has a dummy for a parent
848 // for (int j=0; j<dummies[i]->GetLabelL(kNumAbstractedNodes); j++){
849 // node* child = abstractions[0]->GetNode(dummies[i]->GetLabelL(kFirstData+j));
850 // if (dummies[i]->GetNum()==5289)
851 // std::cout<<"going to check\n";
852 // if (child->GetLabelL(kParent) == dummies[i]->GetNum()){
853 // if (dummies[i]->GetNum()==5289)
854 // std::cout<<"removing "<<child->GetNum()<<std::endl;
855 // child->SetLabelL(kParent,-1);
856 // }
857 // }
858 
859 // g->RemoveNode(dummies[i]);
860 // delete dummies[i];
861 // }
862 
863 //finish by giving not-yet-abstracted nodes a parent
864 
865 node_iterator ni = abstractions[0]->getNodeIter();
866 for (node *next = abstractions[0]->nodeIterNext(ni); next;
867  next = abstractions[0]->nodeIterNext(ni))
868 {
869  // if it isn't abstracted, do a bfs according to the cluster and abstract these nodes together
870  if ((next->GetLabelL(kParent) == -1) || ((next->GetLabelL(kParent) >= numOrigNodes) && next->GetLabelL(kParent) < numNodesAfter))
871  {
872  node *parent;
873  g->AddNode(parent = new node("??"));
874  parent->SetLabelL(kAbstractionLevel, next->GetLabelL(kAbstractionLevel)+1); // level in abstraction tree
875  parent->SetLabelL(kNumAbstractedNodes, 0); // number of abstracted nodes
876  parent->SetLabelL(kParent, -1); // parent of this node in abstraction hierarchy
877  parent->SetLabelF(kXCoordinate, kUnknownPosition);
878  parent->SetLabelL(kNodeBlocked, 0);
879  abstractionBFS(next, parent, getClusterIdFromNode(next),numOrigNodes,numNodesAfter);
880  }
881 }
882 for (unsigned int i=dummies.size()-1;i>0; --i)
883 {
884 
885 
886  int num = dummies[i]->GetNum();
887 
888 
889  g->RemoveNode(dummies[i]);
890  node* n = g->GetNode(num);
891 
892  if (n)
893  {
894 
895  //update children
896  int numnodes = n->GetLabelL(kNumAbstractedNodes);
897  for (int j=0; j<numnodes; j++)
898  {
899 
900  (abstractions[0]->GetNode(n->GetLabelL(kFirstData+j)))->SetLabelL(kParent, num);
901  }
902  }
903 
904  delete dummies[i];
905 }
906 }
907 
911 void ClusterAbstraction::abstractionBFS(node *which, node *parent, int cluster, int numOrigNodes, int numNodesAfter)
912 {
913  if ((which == 0) || (getClusterIdFromNode(which) != cluster) ||
914  ((which->GetLabelL(kParent) < numOrigNodes) && (which->GetLabelL(kParent>=0))) ||
915  ((which->GetLabelL(kParent) >= numNodesAfter) && (which->GetLabelL(kParent)>=0)))
916  return;
917 
918  buildNodeIntoParent(which, parent);
919 
920  getCluster(cluster).addParent(parent);
921 
922  neighbor_iterator ni = which->getNeighborIter();
923  for (long tmp = which->nodeNeighborNext(ni); tmp != -1; tmp = which->nodeNeighborNext(ni))
924  {
925  abstractionBFS(abstractions[0]->GetNode(tmp), parent, cluster,numOrigNodes,numNodesAfter);
926  }
927 }
928 
933 void ClusterAbstraction::createConnectivityGraph()
934 {
935  // std::cout<<" begin\n";
936  // abstractions[1]->Print(std::cout);
937  // std::cout<<"end of this\n";
938  Graph* g = new Graph;
939  abstractions.push_back(g);
940 
941  node_iterator ni = abstractions[1]->getNodeIter();
942  for (node *next = abstractions[1]->nodeIterNext(ni); next;
943  next = abstractions[1]->nodeIterNext(ni))
944  {
945  // std::cout<<"looking at "<<next->GetNum()<<std::endl;
946  //std::cout<<"parent: "<<next->GetLabelL(kParent)<<std::endl;
947 
948  // if it isn't abstracted, do a bfs according to the cluster and abstract these nodes together
949  if (next->GetLabelL(kParent) == -1)
950  {
951  // std::cout<<"here inside if\n";
952  node *parent;
953  g->AddNode(parent = new node("??"));
954  parent->SetLabelL(kAbstractionLevel, next->GetLabelL(kAbstractionLevel)+1); // level in abstraction tree
955  parent->SetLabelL(kNumAbstractedNodes, 0); // number of abstracted nodes
956  parent->SetLabelL(kParent, -1); // parent of this node in abstraction hierarchy
957  parent->SetLabelF(kXCoordinate, kUnknownPosition);
958  parent->SetLabelL(kNodeBlocked, 0);
959  connectedBFS(next, parent);
960  }
961  }
962  // g->Print(std::cout);
963 }
964 
965 void ClusterAbstraction::connectedBFS(node *which, node *parent)
966 {
967  if ((which == 0) || (which->GetLabelL(kParent) != -1))
968  {
969 
970  return;
971  }
972  buildNodeIntoParent(which, parent);
973 
974  neighbor_iterator ni = which->getNeighborIter();
975  for (long tmp = which->nodeNeighborNext(ni); tmp != -1; tmp = which->nodeNeighborNext(ni))
976  {
977  connectedBFS(abstractions[1]->GetNode(tmp), parent);
978  }
979 }
980 
984 bool ClusterAbstraction::Pathable(node* from, node* to)
985 {
986  node* fParent = abstractions[1]->GetNode(from->GetLabelL(kParent));
987  node* tParent = abstractions[1]->GetNode(to->GetLabelL(kParent));
988 
989  if (fParent->GetLabelL(kParent) == tParent->GetLabelL(kParent))
990  return true;
991  else
992  return false;
993 }
994 
995 
996 /*
997  * 'borrowed' from SectorAbstraction.cpp
998  */
999 void ClusterAbstraction::buildNodeIntoParent(node *n, node *parent)
1000 {
1001  assert((n->GetLabelL(kAbstractionLevel)+1 == parent->GetLabelL(kAbstractionLevel))&& parent);
1002 
1003  n->SetLabelL(kParent, parent->GetNum());
1004  parent->SetLabelL(kFirstData+parent->GetLabelL(kNumAbstractedNodes), n->GetNum());
1005  parent->SetLabelL(kNumAbstractedNodes, parent->GetLabelL(kNumAbstractedNodes)+1);
1006 }
1007 
1015 node* ClusterAbstraction::insertNode(node* n, int& expanded, int& touched)
1016 {
1017 
1018  expanded = 0;
1019  touched = 0;
1020 
1021  if (verbose)std::cout<<"in insert node\n";
1022  Map* map = MapAbstraction::GetMap();
1023  Graph* g = abstractions[1];
1024 
1025  point3d s(n->GetLabelF(kXCoordinate),n->GetLabelF(kYCoordinate),-1);
1026  int px;
1027  int py;
1028 
1029  map->GetPointFromCoordinate(s,px,py);
1030 
1031  // Cluster& c = getCluster(getClusterIdFromCoord(py,px));
1032  Cluster& c = getCluster(getClusterIdFromCoord(n->GetLabelL(kFirstData+1), n->GetLabelL(kFirstData)));
1033  // std::cout<<"cluster: "<<&c<<std::endl;
1034  // std::cout<<"id: "<<getClusterIdFromCoord(py,px)<<std::endl;
1035  // for (int l=0; l<c.GetNumNodes(); l++){
1036  // std::cout<<g->GetNode(c.getIthNodeNum(l))<<std::endl;
1037  // // corridor.push_back(g->GetNode(c.getIthNodeNum(l)));
1038  // }
1039  recVec ans;
1040  double r;
1041  map->GetOpenGLCoord((int)n->GetLabelL(kFirstData),(int)n->GetLabelL(kFirstData+1) , ans.x,ans.y,ans.z,r);
1042 
1043  // std::cout<<"cluster num: "<<getClusterIdFromCoord(py,px)<<std::endl;
1044  // std::cout<<"level "<<n->GetLabelL(kAbstractionLevel)<<std::endl;
1045  // int nnum = nodeExists(c,n->GetLabelF(kXCoordinate),n->GetLabelF(kYCoordinate),g);
1046 
1047  int nnum = nodeExists(c,ans.x,ans.y,g);
1048 
1049  // std::cout<<"nnum is "<<nnum<<std::endl;
1050  if (nnum==-1)
1051  {
1052  node* newnode = new node("");
1053  int nodenum = g->AddNode(newnode);
1054  newnode->SetLabelF(kXCoordinate, n->GetLabelF(kXCoordinate));
1055  newnode->SetLabelF(kYCoordinate, n->GetLabelF(kYCoordinate));
1056  newnode->SetLabelF(kZCoordinate, n->GetLabelF(kZCoordinate)*2); //should never have to draw this so it doesn't matter
1057  newnode->SetLabelL(kParent,-1);
1058  newnode->SetLabelL(kNumAbstractedNodes,0);
1059  newnode->SetLabelL(kAbstractionLevel,1);
1060 
1061  // std::vector<node*> corridor;
1062  // for (int l=0; l<c.GetNumNodes(); l++){
1063  // std::cout<<g->GetNode(c.getIthNodeNum(l))<<std::endl;
1064  // corridor.push_back(g->GetNode(c.getIthNodeNum(l)));
1065  // }
1066 
1067  // std::cout<<"nodes: "<<c.GetNumNodes()<<std::endl;
1068  for (int k=0; k<c.GetNumNodes(); k++)
1069  {
1070  //get the entrance
1071  int num = c.getIthNodeNum(k);
1072 
1073  node* tempgoal = g->GetNode(num);
1074 
1075  double goalx = tempgoal->GetLabelF(kXCoordinate);
1076  double goaly = tempgoal->GetLabelF(kYCoordinate);
1077  double goalz = tempgoal->GetLabelF(kZCoordinate);
1078 
1079  point3d gl(goalx,goaly,goalz);
1080 
1081  map->GetPointFromCoordinate(gl,px,py);
1082  node* goal = GetNodeFromMap(px,py);
1083 
1084  // std::cout<<"corridor has: "<<std::endl;
1085  // for (unsigned int bla = 0; bla<corridor.size(); bla++){
1086  // printMapCoord(corridor[bla]);
1087  // std::cout<<" "<<corridor[bla]<<" ("<<corridor[bla]->GetLabelL(kNumAbstractedNodes)<<") ";
1088  // }
1089  // std::cout<<std::endl;
1090 
1091  std::vector<node*> corridor;
1092  for (unsigned int i=0; i<c.parents.size(); i++)
1093  corridor.push_back(c.parents[i]);
1094  for (int j=0; j<c.GetNumNodes(); j++)
1095  corridor.push_back(g->GetNode(c.getIthNodeNum(j)));
1096 
1097  //find path
1098 // corridorAStar astar;
1099 // astar.setCorridor(&corridor);
1100 // path* p = astar.GetPath(static_cast<MapAbstraction*>(this),n , goal);
1101  GenericAStar astar;
1102  ClusterSearchEnvironment cse(this, GetAbstractionLevel(n));
1103  cse.setCorridor(corridor);
1104  std::vector<uint32_t> resultPath;
1105  astar.GetPath(&cse, n->GetNum(), goal->GetNum(),
1106  resultPath);
1107  path *p = 0;
1108  for (unsigned int x = 0; x < resultPath.size(); x++)
1109  p = new path(GetAbstractGraph(n)->GetNode(resultPath[x]), p);
1110 
1111  expanded += astar.GetNodesExpanded();
1112  touched += astar.GetNodesTouched();
1113 
1114  if (p!=0)
1115  {
1116 
1117  //get its length
1118  double dist = distance(p);
1119  //create edge
1120  edge* newedge = new edge(nodenum,num,dist);
1121  if (newnode->GetLabelL(kParent)==-1)
1122  {
1123 
1124  newnode->SetLabelL(kParent,(g->GetNode(num))->GetLabelL(kParent));
1125  }
1126 
1127  g->AddEdge(newedge);
1128 
1129  //store path
1130  path* p2 = p;
1131  temp[newedge] = p;
1132 
1133  newPaths.push_back(p2);
1134  }
1135  }
1136 
1137  if (newnode->GetLabelL(kParent)==-1)
1138  {
1139 
1140  // This node has its own parent in the connectivity Graph
1141  node* par = new node("");
1142  abstractions[2]->AddNode(par);
1143  par->SetLabelF(kXCoordinate, kUnknownPosition);
1144  par->SetLabelL(kParent,-1);
1145  par->SetLabelL(kNumAbstractedNodes,0);
1146  par->SetLabelL(kAbstractionLevel,2);
1147 
1148  buildNodeIntoParent(newnode,par);
1149  }
1150 
1151 
1152  // std::cout<<"inserted\n";
1153  return newnode;
1154  }
1155  else{
1156  // std::cout<<"no need to insert\n";
1157  return g->GetNode(nnum);
1158  }
1159 
1160 }
1161 
1162 
1163 
1169 void ClusterAbstraction::removeNodes(node* start, node* goal)
1170 {
1171  if (verbose) std::cout<<"in remove node\n";
1172 
1173  Map* map = MapAbstraction::GetMap();
1174 
1175  // Check cluster if it's one of the original nodes
1176  // Only delete if the node is not part of the original abstraction
1177  point3d s(start->GetLabelF(kXCoordinate),start->GetLabelF(kYCoordinate),-1);
1178  int px;
1179  int py;
1180  map->GetPointFromCoordinate(s,px,py);
1181 
1182  Cluster& c = getCluster(getClusterIdFromCoord(py,px));
1183  Graph* g = abstractions[1];
1184  int num = nodeExists(c,start->GetLabelF(kXCoordinate),start->GetLabelF(kYCoordinate),g);
1185  if (num==-1)
1186  {
1187 
1188  if (start->GetNumEdges() == 0)
1189  {
1190 
1191  abstractions[2]->RemoveNode(start->GetLabelL(kParent));
1192  }
1193  edge_iterator ei = start->getEdgeIter();
1194  edge* e =start->edgeIterNext(ei);
1195 
1196  while(e)
1197  {
1198 
1199  temp.erase(e);
1200  g->RemoveEdge(e);
1201  delete e;
1202  ei = start->getEdgeIter();
1203  e = start->edgeIterNext(ei);
1204  }
1205  int snum = start->GetNum();
1206  assert((snum == g->GetNumNodes()-1) || (snum == g->GetNumNodes()-2));
1207  g->RemoveNode(start);
1208  delete start;
1209  // std::cout<<"removing node\n";
1210  }
1211  // else
1212  // std::cout<<"don't need to remove this\n";
1213 
1214  point3d gl(goal->GetLabelF(kXCoordinate),goal->GetLabelF(kYCoordinate),-1);
1215  int px2;
1216  int py2;
1217  map->GetPointFromCoordinate(gl,px2,py2);
1218 
1219  Cluster& c2 = getCluster(getClusterIdFromCoord(py2,px2));
1220  num = nodeExists(c2,goal->GetLabelF(kXCoordinate),goal->GetLabelF(kYCoordinate),g);
1221  if (num==-1)
1222  {
1223 
1224  if (goal->GetNumEdges() == 0)
1225  {
1226 
1227  abstractions[2]->RemoveNode(goal->GetLabelL(kParent));
1228 
1229  }
1230  edge_iterator ei = goal->getEdgeIter();
1231  // std::cout<<"goal->GetNumEdges "<<goal->GetNumEdges()<<std::endl;
1232  edge* e = goal->edgeIterNext(ei);
1233  while(e)
1234  {
1235 
1236  temp.erase(e);
1237  int gnum = goal->GetNum();
1238  assert((gnum == g->GetNumNodes()-1) || (gnum == g->GetNumNodes()-2));
1239  g->RemoveEdge(e);
1240  delete e;
1241  ei = goal->getEdgeIter();
1242  e = goal->edgeIterNext(ei);
1243  }
1244 
1245  g->RemoveNode(goal);
1246  delete goal;
1247  // std::cout<<"removing goal node\n";
1248  }
1249  // else std::cout<<"don't need to remove goal\n";
1250 
1251  temp.clear();
1252  for (unsigned int i=0; i<newPaths.size(); i++)
1253  {
1254 
1255  delete newPaths[i];
1256  }
1257  newPaths.clear();
1258 }
1259 
1263 path* ClusterAbstraction::getCachedPath(edge* e)
1264 {
1265  if (temp[e]) return temp[e]->Clone();
1266  else if (paths[e]) return paths[e]->Clone();
1267  else return 0;
1268 }
1269 
1274 node* ClusterAbstraction::getLowLevelNode(node* abstract)
1275 {
1276  Map* map = MapAbstraction::GetMap();
1277 
1278  point3d s(abstract->GetLabelF(kXCoordinate),abstract->GetLabelF(kYCoordinate),-1);
1279  int px;
1280  int py;
1281  map->GetPointFromCoordinate(s,px,py);
1282 
1283  return MapAbstraction::GetNodeFromMap(px,py);
1284 }
1285 
1286 void ClusterAbstraction::printMapCoord(node* n)
1287 {
1288 
1289  Map* map = MapAbstraction::GetMap();
1290  Graph* g = abstractions[1];
1291  point3d s(n->GetLabelF(kXCoordinate),n->GetLabelF(kYCoordinate),-1);
1292  int px;
1293  int py;
1294  map->GetPointFromCoordinate(s,px,py);
1295 
1296  node* parent = g->GetNode(n->GetLabelL(kParent));
1297 
1298  point3d s2(parent->GetLabelF(kXCoordinate),parent->GetLabelF(kYCoordinate),-1);
1299  int px2;
1300  int py2;
1301  map->GetPointFromCoordinate(s2,px2,py2);
1302 
1303  std::cout<<"("<<px<<","<<py<<")"; // parent "<<parent<<"\n";
1304  //("<<px2<<","<<py2<<")\n";
1305 }
1306 
1307 void ClusterAbstraction::printPathAsCoord(path* p)
1308 {
1309  if (p->n)
1310  {
1311 
1312  path* curr = p;
1313  printMapCoord(curr->n);
1314  while(curr->next)
1315  {
1316 
1317  curr = curr->next;
1318  printMapCoord(curr->n);
1319  }
1320  }
1321 }
1322 
1323 void ClusterAbstraction::OpenGLDraw() const
1324 {
1325  MapAbstraction::OpenGLDraw();
1326  GLdouble xx, yy, zz, rr;
1327  glColor3f(0.25, 0.0, 0.75);
1328  Map *map = GetMap();
1329  map->GetOpenGLCoord(0, 0, xx, yy, zz, rr);
1330  glBegin(GL_LINES);
1331  int numXSectors = (map->GetMapWidth()+clusterSize-1)/clusterSize;
1332  int numYSectors = (map->GetMapHeight()+clusterSize-1)/clusterSize;
1333  for (int y = 0; y <= numYSectors; y++)
1334  {
1335  glVertex3f(xx-rr, yy-rr+2*y*rr*clusterSize, zz-5*rr);
1336  glVertex3f(xx+2*numXSectors*rr*clusterSize, yy-rr+2*y*clusterSize*rr, zz-5*rr);
1337  }
1338  for (int x = 0; x <= numXSectors; x++)
1339  {
1340  glVertex3f(xx-rr+2*x*rr*clusterSize, yy-rr, zz-5*rr);
1341  glVertex3f(xx-rr+2*x*rr*clusterSize, yy-rr+2*numYSectors*rr*clusterSize, zz-5*rr);
1342  }
1343  glEnd();
1344 }
ClusterAbstraction::computeClusterPaths
void computeClusterPaths(Graph *g)
Definition: ClusterAbstraction.cpp:528
Graph::AddNode
int AddNode(node *)
Definition: Graph.cpp:136
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
Entrance::setCluster2Id
void setCluster2Id(int id)
Definition: ClusterAbstraction.h:96
Entrance::getCol
int getCol()
Definition: ClusterAbstraction.h:94
ClusterAbstraction::addCluster
void addCluster(Cluster c)
Definition: ClusterAbstraction.cpp:202
node::SetLabelF
void SetLabelF(unsigned int index, double val) const
Definition: Graph.cpp:687
Map::GetNodeNum
int GetNodeNum(int x, int y, tCorner c=kNone)
Gets the abstract Graph node number for this tile.
Definition: Map.cpp:2339
Entrance::getCluster1Id
int getCluster1Id()
Definition: ClusterAbstraction.h:99
Graph::RemoveNode
node * RemoveNode(node *, unsigned int &)
Definition: Graph.cpp:356
ClusterSearchEnvironment::level
int level
Definition: ClusterAbstraction.cpp:75
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
recVec
A generic vector (essentially the same as a point, but offers normalization)
Definition: GLUtil.h:78
neighbor_iterator
unsigned int neighbor_iterator
Definition: Graph.h:34
ClusterAbstraction::getClusterIdFromCoord
int getClusterIdFromCoord(int row, int col) const
given a node's coordinates, find the cluster it's in
Definition: ClusterAbstraction.cpp:624
ClusterAbstraction::getLowLevelNode
node * getLowLevelNode(node *abstract)
get the map-level node that is at the (x,y) coordinates of the abstract node
Definition: ClusterAbstraction.cpp:1274
ClusterAbstraction::nodeExists
int nodeExists(const Cluster &c, double x, double y, Graph *g)
check if a node already exists in a certain cluster with a particular set of coordinates
Definition: ClusterAbstraction.cpp:649
recVec::z
GLdouble z
Definition: GLUtil.h:98
ClusterAbstraction::getCluster
Cluster & getCluster(int id)
get the cluster from it's ID
Definition: ClusterAbstraction.cpp:635
ClusterAbstraction::setUpParents
void setUpParents(Graph *g)
Nodes are assigned the closest entrance node in the abstract Graph as their parent.
Definition: ClusterAbstraction.cpp:695
ClusterAbstraction::createClustersAndEntrances
void createClustersAndEntrances()
create clusters on the abstract level and create corresponding entrances.
Definition: ClusterAbstraction.cpp:125
Entrance::getCenter1Col
int getCenter1Col()
Definition: ClusterAbstraction.h:98
ClusterSearchEnvironment::aMap
GraphAbstraction * aMap
Definition: ClusterAbstraction.cpp:74
ClusterAbstraction::rows
int rows
Definition: ClusterAbstraction.h:166
ClusterAbstraction::Pathable
bool Pathable(node *start, node *goal)
Check if there is a path between two nodes.
Definition: ClusterAbstraction.cpp:984
ClusterSearchEnvironment
Definition: ClusterAbstraction.cpp:20
Graph::AddEdge
void AddEdge(edge *)
Definition: Graph.cpp:170
Map::GetPointFromCoordinate
void GetPointFromCoordinate(point3d loc, int &px, int &py) const
Definition: Map.cpp:1900
ClusterAbstraction::linkEntrancesAndClusters
void linkEntrancesAndClusters()
from original HPA* abstiling.cpp
Definition: ClusterAbstraction.cpp:351
Cluster::AddNode
void AddNode(int)
Add an abstract node corresponding to an entrance to the cluster.
Definition: ClusterAbstraction.cpp:86
Cluster::getHOrig
int getHOrig() const
Definition: ClusterAbstraction.h:58
path::n
node * n
Definition: Path.h:22
ClusterAbstraction::createConnectivityGraph
void createConnectivityGraph()
Add a 2nd level to the Graph.
Definition: ClusterAbstraction.cpp:933
edge_iterator
std::vector< edge * >::const_iterator edge_iterator
Definition: Graph.h:30
ClusterAbstraction::connectedBFS
void connectedBFS(node *which, node *parent)
Definition: ClusterAbstraction.cpp:965
Graph::RemoveEdge
void RemoveEdge(edge *)
Definition: Graph.cpp:331
GenericAStar::GetNodesTouched
uint64_t GetNodesTouched()
Definition: GenericAStar.h:94
ClusterAbstraction::clusterSize
int clusterSize
Definition: ClusterAbstraction.h:165
VERTICAL
@ VERTICAL
Definition: ClusterAbstraction.h:22
ClusterAbstraction::createAbstractGraph
void createAbstractGraph()
Definition: ClusterAbstraction.cpp:180
GenericAStar::GetPath
void GetPath(OldSearchCode::SearchEnvironment *env, uint32_t from, uint32_t to, std::vector< uint32_t > &thePath)
Definition: GenericAStar.cpp:28
Graph
A generic Graph class.
Definition: Graph.h:66
Graph::GetNode
node * GetNode(unsigned long num)
Definition: Graph.cpp:152
Graph::edgeIterNext
edge * edgeIterNext(edge_iterator &) const
Definition: Graph.cpp:320
ClusterSearchEnvironment::inCorridor
bool inCorridor(uint32_t nodeID)
Definition: ClusterAbstraction.cpp:59
OldSearchCode::SearchEnvironment
Definition: OldSearchEnvironment.h:18
Cluster::parents
std::vector< node * > parents
Definition: ClusterAbstraction.h:64
GraphAbstractionConstants::kZCoordinate
@ kZCoordinate
Definition: GraphAbstraction.h:32
node_iterator
std::vector< node * >::const_iterator node_iterator
Definition: Graph.h:33
ClusterAbstraction.h
GraphAbstractionConstants::kNumAbstractedNodes
@ kNumAbstractedNodes
Definition: GraphAbstraction.h:26
node::getEdgeIter
edge_iterator getEdgeIter() const
Definition: Graph.cpp:749
ClusterAbstraction::buildNodeIntoParent
void buildNodeIntoParent(node *n, node *parent)
Definition: ClusterAbstraction.cpp:999
ClusterAbstraction::columns
int columns
Definition: ClusterAbstraction.h:167
Cluster::getVOrig
int getVOrig() const
Definition: ClusterAbstraction.h:59
ClusterAbstraction::addEntrance
void addEntrance(Entrance e)
Definition: ClusterAbstraction.cpp:210
loc
Definition: MapGenerators.cpp:296
ClusterSearchEnvironment::heuristic
double heuristic(uint32_t node1, uint32_t node2)
Definition: ClusterAbstraction.cpp:37
GetMapGraph
Graph * GetMapGraph(Map *m)
GetMapGraph(map)
Definition: MapAbstraction.cpp:312
Graph::getEdgeIter
edge_iterator getEdgeIter() const
Definition: Graph.cpp:315
GenericAStar.h
GraphAbstractionConstants::kFirstData
@ kFirstData
Definition: GraphAbstraction.h:34
point3d
#define point3d
Definition: GLUtil.h:123
GenericAStar
Definition: GenericAStar.h:77
Entrance::getOrientation
int getOrientation()
Definition: ClusterAbstraction.h:92
verbose
const static int verbose
Definition: ClusterAbstraction.cpp:81
ClusterAbstraction::createHorizEntrances
void createHorizEntrances(int, int, int, int, int)
based on the function from HPA* abswizard.cpp with the same name
Definition: ClusterAbstraction.cpp:221
ClusterAbstraction::createVertEntrances
void createVertEntrances(int, int, int, int, int)
based on the function from HPA* abstiling.cpp with the same name
Definition: ClusterAbstraction.cpp:284
ClusterAbstraction::OpenGLDraw
virtual void OpenGLDraw() const
Definition: ClusterAbstraction.cpp:1323
py2
int py2
Definition: Sample.cpp:28
Cluster::addParent
void addParent(node *n)
Definition: ClusterAbstraction.h:62
ClusterAbstraction::newPaths
std::vector< path * > newPaths
Definition: ClusterAbstraction.h:173
Map::GetMapWidth
long GetMapWidth() const
return the width of the map
Definition: Map.h:163
GraphAbstractionConstants::kAbstractionLevel
@ kAbstractionLevel
Definition: GraphAbstraction.h:25
ClusterAbstraction::abstractionBFS
void abstractionBFS(node *which, node *parent, int cluster, int numOrigNodes, int numNodesAfter)
'borrowed' from MapSectorAbstraction.cpp
Definition: ClusterAbstraction.cpp:911
Entrance::setCluster1Id
void setCluster1Id(int id)
Definition: ClusterAbstraction.h:95
ClusterAbstraction::removeNodes
void removeNodes(node *start, node *goal)
remove a start or goal node after the search has been completed.
Definition: ClusterAbstraction.cpp:1169
GraphAbstractionConstants::kYCoordinate
@ kYCoordinate
Definition: GraphAbstraction.h:31
ClusterAbstraction::entrances
std::vector< Entrance > entrances
Definition: ClusterAbstraction.h:170
Graph::GetNumNodes
int GetNumNodes()
Definition: Graph.cpp:403
ClusterAbstraction::getClusterId
int getClusterId(int row, int col) const
given a cluster row and column (NOT map row/column), return the cluster's ID.
Definition: ClusterAbstraction.cpp:615
Graph::getNodeIter
node_iterator getNodeIter() const
Definition: Graph.cpp:298
node::nodeNeighborNext
int nodeNeighborNext(neighbor_iterator &) const
Definition: Graph.cpp:807
ClusterSearchEnvironment::corridor
std::vector< node * > corridor
Definition: ClusterAbstraction.cpp:77
ClusterAbstraction::ClusterAbstraction
ClusterAbstraction(Map *map, int _clusterSize)
create a cluster abstraction for the given map.
Definition: ClusterAbstraction.cpp:95
path
std::vector< xyLoc > path
Definition: Sample.cpp:43
ClusterAbstraction::temp
clusterUtil::PathLookupTable temp
Definition: ClusterAbstraction.h:172
Cluster::GetNumNodes
int GetNumNodes() const
Definition: ClusterAbstraction.h:57
ClusterSearchEnvironment::corridorLevel
int corridorLevel
Definition: ClusterAbstraction.cpp:76
GraphAbstractionConstants::kXCoordinate
@ kXCoordinate
Definition: GraphAbstraction.h:30
ClusterSearchEnvironment::ClusterSearchEnvironment
ClusterSearchEnvironment(GraphAbstraction *_aMap, int _level)
Definition: ClusterAbstraction.cpp:23
Cluster::getWidth
int getWidth() const
Definition: ClusterAbstraction.h:61
node::GetLabelF
double GetLabelF(unsigned int index) const
Definition: Graph.h:215
Entrance
Definition: ClusterAbstraction.h:79
MAX_ENTRANCE_WIDTH
const int MAX_ENTRANCE_WIDTH
Definition: ClusterAbstraction.h:24
Cluster::GetHeight
int GetHeight() const
Definition: ClusterAbstraction.h:60
GraphAbstractionConstants::kNodeBlocked
@ kNodeBlocked
Definition: GraphAbstraction.h:33
node::GetNum
unsigned int GetNum() const
Definition: Graph.h:176
Map::GetMapHeight
long GetMapHeight() const
return the height of the map
Definition: Map.h:165
GraphAbstractionConstants::kTemporaryLabel
@ kTemporaryLabel
Definition: GraphAbstraction.h:29
Entrance::getRow
int getRow()
Definition: ClusterAbstraction.h:93
ClusterAbstraction::~ClusterAbstraction
~ClusterAbstraction()
Definition: ClusterAbstraction.cpp:104
ClusterSearchEnvironment::setCorridor
void setCorridor(std::vector< node * > &corr)
Definition: ClusterAbstraction.cpp:48
ClusterSearchEnvironment::gcost
double gcost(uint32_t node1, uint32_t node2)
Definition: ClusterAbstraction.cpp:43
Entrance::getCluster2Id
int getCluster2Id()
Definition: ClusterAbstraction.h:100
Cluster::getIthNodeNum
int getIthNodeNum(int i) const
Definition: ClusterAbstraction.h:56
Cluster
Definition: ClusterAbstraction.h:47
ClusterAbstraction::printPathAsCoord
void printPathAsCoord(path *p)
Definition: ClusterAbstraction.cpp:1307
ClusterAbstraction::paths
clusterUtil::PathLookupTable paths
Definition: ClusterAbstraction.h:171
px2
int px2
Definition: Sample.cpp:28
ClusterAbstraction::getClusterIdFromNode
int getClusterIdFromNode(node *n)
Given a map node, return the ID of the cluster it's in.
Definition: ClusterAbstraction.cpp:671
Map::GetOpenGLCoord
bool GetOpenGLCoord(int _x, int _y, GLdouble &x, GLdouble &y, GLdouble &z, GLdouble &radius) const
Get the openGL coordinates of a given tile.
Definition: Map.cpp:1826
GraphAbstractionConstants::kParent
@ kParent
Definition: GraphAbstraction.h:27
path::next
path * next
Definition: Path.h:23
ClusterSearchEnvironment::getNeighbors
void getNeighbors(uint32_t nodeID, std::vector< uint32_t > &neighbors)
Definition: ClusterAbstraction.cpp:26
node::GetLabelL
long GetLabelL(unsigned int index) const
Definition: Graph.h:220
ClusterAbstraction::getCachedPath
path * getCachedPath(edge *e)
get the map-level path that corresponds to abstract edge e
Definition: ClusterAbstraction.cpp:1263
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
GraphAbstractionConstants::kUnknownPosition
const double kUnknownPosition
Definition: GraphAbstraction.h:56
ClusterAbstraction::printMapCoord
void printMapCoord(node *n)
Definition: ClusterAbstraction.cpp:1286
recVec::y
GLdouble y
Definition: GLUtil.h:98
GenericAStar::GetNodesExpanded
uint64_t GetNodesExpanded()
Definition: GenericAStar.h:93
node::edgeIterNext
edge * edgeIterNext(edge_iterator &) const
Definition: Graph.cpp:754
HORIZONTAL
@ HORIZONTAL
Definition: ClusterAbstraction.h:22
recVec::x
GLdouble x
Definition: GLUtil.h:98
ClusterAbstraction::min
int min(int, int)
Definition: ClusterAbstraction.cpp:168
Entrance::getCenter1Row
int getCenter1Row()
Definition: ClusterAbstraction.h:97
ClusterAbstraction::insertNode
node * insertNode(node *n, int &expanded, int &touched)
insert a start or goal node in to the abstract Graph (for searching purposes).
Definition: ClusterAbstraction.cpp:1015
node::GetNumEdges
int GetNumEdges()
Definition: Graph.h:204
ClusterAbstraction::addAbsNodes
void addAbsNodes(Graph *g)
Add a node for cluster for each entrance.
Definition: ClusterAbstraction.cpp:392
ClusterAbstraction::clusters
std::vector< Cluster > clusters
Definition: ClusterAbstraction.h:169
node
Nodes to be stored within a Graph.
Definition: Graph.h:170
Map
A tile-based representation of the world.
Definition: Map.h:142
edge
Edge class for connections between node in a Graph.
Definition: Graph.h:129
Generated by   doxygen 1.8.17