HOG2
MapAbstraction.cpp
Go to the documentation of this file.
1 /*
2  * $Id: MapAbstraction.cpp
3  * hog2
4  *
5  * Created by Nathan Sturtevant on 6/3/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 "MapAbstraction.h"
13 
14 using namespace GraphAbstractionConstants;
15 
16 MapAbstraction::~MapAbstraction()
17 {
18  delete m;
19 }
20 
21 void MapAbstraction::GetRandomTileFromNode(node *n, int &x, int &y)
22 {
23  while (GetAbstractionLevel(n) != 0)
24  n = GetNthChild(n, random()%GetNumChildren(n));
25  x = n->GetLabelL(kFirstData);
26  y = n->GetLabelL(kFirstData+1);
27 }
28 
29 void MapAbstraction::GetTileFromNode(node *n, int &x, int &y)
30 {
31  if (GetAbstractionLevel(n) != 0)
32  {
33  GetTileUnderLoc(x, y, GetNodeLoc(n));
34  node *t = GetNodeFromMap(x, y);
35  if (GetNthParent(t, GetAbstractionLevel(n)) == n)
36  {
37  // printf("Nth parent is %d (%d), not %d (%d)\n",
38  // t->GetNum(), GetAbstractionLevel(t),
39  // n->GetNum(), GetAbstractionLevel(n));
40  return;
41  }
42  while (GetAbstractionLevel(n) != 0)
43  n = GetNthChild(n, 0);
44  }
45  x = n->GetLabelL(kFirstData);
46  y = n->GetLabelL(kFirstData+1);
47  //printf("(%d, %d) in x/y\n", x, y);
48 }
49 
50 void MapAbstraction::ToggleDrawAbstraction(int which)
51 {
52  bool drawThis = ((levelDraw>>which)&0x1);
53  if (!drawThis)
54  levelDraw |= (1<<which);
55  else
56  levelDraw = levelDraw&(~(1<<which));
57 }
58 
59 void MapAbstraction::OpenGLDraw() const
60 {
61  for (unsigned int x = 0; x < abstractions.size(); x++)
62  {
63  if ((levelDraw >> x) & 1)
64  DrawGraph(abstractions[x], (x>1)&&((levelDraw>>(x-1))&1));
65  //glCallList(displayLists[x]);
66  }
67 }
68 
69 
70 void MapAbstraction::DrawGraph(Graph *g, bool drawLevel) const
71 {
72  if ((g == 0) || (g->GetNumNodes() == 0)) return;
73 
74  int abLevel = g->GetNode(0)->GetLabelL(kAbstractionLevel);
75 
76  // if (verbose&kBuildGraph) printf("Drawing Graph abstraction %d!\n", abLevel);
77  glBegin(GL_LINES);
78  glNormal3f(0, 1, 0);
79 
80  // glColor4f(1-((GLfloat)(abLevel%15)/15.0), ((GLfloat)(abLevel%15)/15.0), .25+((GLfloat)(abLevel%15-8)/30.0), 1);
81  // switch (g->GetNode(0)->GetLabelL(kAbstractionLevel)%3)
82  // {
83  // case 0: glColor4f(1, 0, 0, 1); break;
84  // case 1: glColor4f(0, 1, 0, 1); break;
85  // case 2: glColor4f(1, 1, 0, 1); break;
86  // case 3: glColor4f(0, 0, 1, .5); break;
87  // case 4: glColor4f(1, 0, 1, .5); break;
88  // case 5: glColor4f(1, 1, 0, .5); break;
89  // case 6: glColor4f(0, 1, 0, .5); break;
90  // case 7: glColor4f(0, 1, 0, .5); break;
91  // default:glColor4f(0, 0, 1, .5); break;
92  // }
93  node_iterator ni;
94  // ni = g->getNodeIter();
95  // for (node *n = g->nodeIterNext(ni); n; n = g->nodeIterNext(ni))
96  // {
97  // if (n->GetLabelL(kNodeBlocked) > 0)
98  // {
99  // glColor3f(1, 1, 1);
100  // recVec rv = GetNodeLoc(n);
101  // glVertex3f(rv.x, 0, rv.z);
102  // glVertex3f(rv.x, rv.y, rv.z);
103  // }
104  // }
105  edge_iterator ei = g->getEdgeIter();
106  for (edge *e = g->edgeIterNext(ei); e; e = g->edgeIterNext(ei))
107  {
108  //int x, y;
109  //double offsetx, offsety;
110  node *n;
111  n = g->GetNode(e->getFrom());
112 
113  if (e->GetLabelL(kEdgeCapacity) == 0) glColor4f(.5, .5, .5, 1);
114  else if (e->GetLabelL(kEdgeCapacity) <= 0) glColor4f(.2, .2, .2, 1);
115  else if (e->getMarked()) glColor4f(1, 1, 1, 1);
116  else if (abLevel%2)
117  glColor4f(1-((GLfloat)(abLevel%15)/15.0), ((GLfloat)(abLevel%15)/15.0), 0, 1);
118  else glColor4f(1-((GLfloat)(abLevel%15)/15.0), ((GLfloat)(abLevel%15)/15.0), 0, 1);
119  //glColor4f(1-((GLfloat)(abLevel%15)/15.0), ((GLfloat)(abLevel%15)/15.0), .5+((GLfloat)(abLevel%15-8)/30.0), 1);
120 
121  // Color the edge widths
122  // else if (e->getWidth() <= 0.0)
123  // glColor4f(1, 0, 0, 1);
124  // else if (e->getWidth() <= 0.8)
125  // glColor4f(1, 0, 1, 1);
126  // else if (e->getWidth() <= 1.1)
127  // glColor4f(1, 1, 0, 1);
128  // else if (e->getWidth() <= 1.5)
129  // glColor4f(0, 1, 1, 1);
130  // else if (e->getWidth() <= 2.1)
131  // glColor4f(0, 1, 0, 1);
132  //if (e->getMarked()) {
133  recVec rv = GetNodeLoc(n);
134  glVertex3f(rv.x, rv.y, rv.z);
135 
136  n = g->GetNode(e->getTo());
137  rv = GetNodeLoc(n);
138 
139  glVertex3f(rv.x, rv.y, rv.z);
140  //}
141  }
142  //node_iterator
143  ni = g->getNodeIter();
144 
145  if (drawLevel)
146  {
147  for (node *n = g->nodeIterNext(ni); n; n = g->nodeIterNext(ni))
148  DrawLevelConnections(n);
149  }
150  glEnd();
151  // if (verbose&kBuildGraph) printf("Done\n");
152 }
153 
154 void MapAbstraction::DrawLevelConnections(node *n) const
155 {
156  // int x, y;
157  // double offsetx, offsety;
158  // recVec ans;
159  //if (n->getNumOutgoingEdges()+n->getNumIncomingEdges() == 0) return;
160 
161  if (n->GetLabelL(kAbstractionLevel) == 0) return;
162  else {
163  glColor4f(.6, .6, .6, .6);
164  recVec v = GetNodeLoc(n);
165  for (int cnt = 0; cnt < n->GetLabelL(kNumAbstractedNodes); cnt++)
166  {
167  recVec v1 = GetNodeLoc(abstractions[n->GetLabelL(kAbstractionLevel)-1]->GetNode(n->GetLabelL(kFirstData+cnt)));
168  glVertex3f(v.x, v.y, v.z);
169  glVertex3f(v1.x, v1.y, v1.z);
170  }
171  }
172  //return ans;
173 }
174 
175 void MapAbstraction::GetTileUnderLoc(int &x, int &y, const recVec &v)
176 {
177  double width = (GetMap()->GetMapWidth()+1)/2.0;
178  double height = (GetMap()->GetMapHeight()+1)/2.0;
179  //double offsetx, offsety;
180  //offsetx = offsety = .5;
181  x = (int)(width*(v.x+1.0));
182  y = (int)(height*(v.y+1.0));
183  // printf("(%1.2f, %1.2f) in openGL converted to (%d, %d) in x/y\n",
184  // v.x, v.y, x, y);
185 }
186 
187 recVec MapAbstraction::GetNodeLoc(node *n) const
188 {
189  int x, y;
190  // double offsetx, offsety;
191  recVec ans;
192 
193  if (n->GetLabelF(kXCoordinate) != kUnknownPosition)
194  {
195  ans.x = n->GetLabelF(kXCoordinate);
196  ans.y = n->GetLabelF(kYCoordinate);
197  ans.z = n->GetLabelF(kZCoordinate);
198  return ans;
199  }
200 
201  // double width = GetMap()->GetMapWidth();
202  // double height = GetMap()->GetMapHeight();
203 
204  if (n->GetLabelL(kAbstractionLevel) == 0)
205  {
206  x = n->GetLabelL(kFirstData);
207  y = n->GetLabelL(kFirstData+1);
208 
209  Map *mp = GetMap();
210  double r;
211  mp->GetOpenGLCoord(x,y,ans.x,ans.y,ans.z,r);
212  // switch (n->GetLabelL(kFirstData+2)) {
213  // case kTopLeft: offsetx = .3; offsety = .3; break;
214  // case kTopRight: offsetx = .6; offsety = .3; break;
215  // case kBottomLeft: offsetx = .3; offsety = .6; break;
216  // case kBottomRight: offsetx = .6; offsety = .6; break;
217  // case kNone:
218  // default: offsetx = .5; offsety = .5; break;
219  // }
220  // ans.x = (double)x/width+offsetx/width-.5;
221  // ans.z = (double)y/height+offsety/width-.5;
222  }
223  else {
224  int totNodes = 0;
225  ans.x = ans.y = ans.z = 0;
226  for (int cnt = 0; cnt < n->GetLabelL(kNumAbstractedNodes); cnt++)
227  {
228  int absLevel = n->GetLabelL(kAbstractionLevel)-1;
229  node *nextChild = abstractions[absLevel]->GetNode(n->GetLabelL(kFirstData+cnt));
230  recVec tmp = GetNodeLoc(nextChild);
231  int weight = nextChild->GetLabelL(kNumAbstractedNodes);
232  totNodes += weight;
233  ans.x += weight*tmp.x;
234  ans.y += weight*tmp.y;
235  ans.z += weight*tmp.z;
236  }
237  ans.x /= totNodes;//n->GetLabelL(kNumAbstractedNodes);
238  ans.y /= totNodes;//n->GetLabelL(kNumAbstractedNodes);
239  ans.z /= totNodes;//n->GetLabelL(kNumAbstractedNodes);
240  }
241  Map *mp = GetMap();
242  double r, a, b, c;
243  mp->GetOpenGLCoord(0,0,a,b,c,r);
244  // height
245  ans.z -= 5.0*r;
246  //ans.z = -(double)5.0*r*(n->GetLabelL(kAbstractionLevel)+1.1);
247 
248  n->SetLabelF(kXCoordinate, ans.x);
249  n->SetLabelF(kYCoordinate, ans.y);
250  n->SetLabelF(kZCoordinate, ans.z);
251  return ans;
252 }
253 
254 void MapAbstraction::ClearMarkedNodes()
255 {
256  for (unsigned int x = 0; x < abstractions.size(); x++)
257  {
258  edge_iterator ei = abstractions[x]->getEdgeIter();
259  for (edge *e = abstractions[x]->edgeIterNext(ei); e; e = abstractions[x]->edgeIterNext(ei))
260  e->setMarked(false);
261  }
262 }
263 
264 // estimate the cost from a to b
265 double MapAbstraction::h(node *a, node *b)
266 {
267  if ((a == 0) || (b == 0))
268  return 999999999.99;
269 
270  recVec rv1 = GetNodeLoc(a);
271  recVec rv2 = GetNodeLoc(b);
272  double answer = OctileDistance((double)rv1.x,(double)rv1.y,(double)rv2.x,(double)rv2.y);
273  // if (fabs(rv1.x-rv2.x) < fabs(rv1.y-rv2.y)) {
274  // answer = root2m1*fabs(rv1.x-rv2.x)+fabs(rv1.y-rv2.y);
275  // } else {
276  // answer = root2m1*fabs(rv1.y-rv2.y)+fabs(rv1.x-rv2.x);
277  // }
278  answer *= GetMap()->GetCoordinateScale();
279 // if (a->GetNumEdges() < 4)
280 // return 9999999;
281 // if (b->GetNumEdges() < 4)
282 // return 9999999;
283  //answer+=(8-a->GetNumEdges()+8-b->GetNumEdges())*5;
284  //if (answer > 1)
285  return answer;
286  //return 1;
287 }
288 
290 double MapAbstraction::OctileDistance(double x1, double y1, double x2, double y2)
291 {
292  double answer = 0.0;
293  const double root2m1 = ROOT_TWO-1;//sqrt(2.0)-1;
294  if (fabs(x1-x2) < fabs(y1-y2))
295  answer = root2m1*fabs(x1-x2)+fabs(y1-y2);
296  else
297  answer = root2m1*fabs(y1-y2)+fabs(x1-x2);
298  return answer;
299 }
300 
301 
302 
303 
312 Graph *GetMapGraph(Map *m)
313 {
314 // return GraphSearchConstants::GetGraph(m);
315  // printf("Getting Graph representation of world\n");
316  char name[32];
317  Graph *g = new Graph();
318  node *n;
319  for (int y = 0; y < m->GetMapHeight(); y++)
320  {
321  for (int x = 0; x < m->GetMapWidth(); x++)
322  {
323  Tile &currTile = m->GetTile(x, y);
324  currTile.tile1.node = kNoGraphNode;
325  currTile.tile2.node = kNoGraphNode;
326 
327  if (m->AdjacentEdges(x, y, kInternalEdge))
328  {
329  if (m->GetTerrainType(x, y) == kOutOfBounds)
330  continue;
331  sprintf(name, "(%d, %d)", x, y);
332  currTile.tile1.node = g->AddNode(n = new node(name));
333  n->SetLabelL(kAbstractionLevel, 0); // level in abstraction tree
334  n->SetLabelL(kNumAbstractedNodes, 1); // number of abstracted nodes
335  n->SetLabelL(kParent, -1); // parent of this node in abstraction hierarchy
336  n->SetLabelF(kXCoordinate, kUnknownPosition);
337  n->SetLabelL(kNodeBlocked, 0);
338  n->SetLabelL(kFirstData, x);
339  n->SetLabelL(kFirstData+1, y);
340  n->SetLabelL(kFirstData+2, kNone);
341  }
342  else {
343  if (m->GetTerrainType(x, y, kLeftEdge) != kOutOfBounds)
344  {
345  sprintf(name, "(%d/%d)", x, y);
346  currTile.tile1.node = g->AddNode(n = new node(name));
347  n->SetLabelL(kAbstractionLevel, 0); // level in abstraction tree
348  n->SetLabelL(kNumAbstractedNodes, 1); // number of abstracted nodes
349  n->SetLabelL(kParent, -1); // parent of this node in abstraction hierarchy
350  n->SetLabelF(kXCoordinate, kUnknownPosition);
351  n->SetLabelL(kNodeBlocked, 0);
352  n->SetLabelL(kFirstData, x);
353  n->SetLabelL(kFirstData+1, y);
354  if (currTile.split == kForwardSplit)
355  n->SetLabelL(kFirstData+2, kTopLeft);
356  else
357  n->SetLabelL(kFirstData+2, kBottomLeft);
358  }
359 
360  if (m->GetTerrainType(x, y, kRightEdge) != kOutOfBounds)
361  {
362  sprintf(name, "(%d\\%d)", x, y);
363  currTile.tile2.node = g->AddNode(n = new node(name));
364  n->SetLabelL(kAbstractionLevel, 0); // level in abstraction tree
365  n->SetLabelL(kNumAbstractedNodes, 1); // number of abstracted nodes
366  n->SetLabelL(kParent, -1); // parent of this node in abstraction hierarchy
367  n->SetLabelF(kXCoordinate, kUnknownPosition);
368  n->SetLabelL(kNodeBlocked, 0);
369  n->SetLabelL(kFirstData, x);
370  n->SetLabelL(kFirstData+1, y);
371  if (currTile.split == kForwardSplit)
372  n->SetLabelL(kFirstData+2, kBottomRight);
373  else
374  n->SetLabelL(kFirstData+2, kTopRight);
375  }
376  }
377  }
378  }
379  for (int y = 0; y < m->GetMapHeight(); y++)
380  {
381  for (int x = 0; x < m->GetMapWidth(); x++)
382  {
383  //cout << "Trying (x, y) = (" << x << ", " << y << ")" << endl;
384  AddMapEdges(m, g, x, y);
385  // if (!g->verifyGraph())
386  // {
387  // cerr << "Broken at (x, y) = (" << x << ", " << y << ")" << endl;
388  // }
389  }
390  }
391  // printf("Done\n");
392 
393  // verify Graph is correct
394 #if 0
395  {
396  node_iterator ni = g->getNodeIter();
397  for (n = g->nodeIterNext(ni); n; n = g->nodeIterNext(ni))
398  {
399  int numEdges = n->getNumOutgoingEdges() + n->getNumIncomingEdges();
400 
401  edge *ee;
402  edge_iterator eie = n->getEdgeIter();
403  for (int x = 0; x < numEdges; x++)
404  {
405  ee = n->edgeIterNext(eie);
406  if (ee == 0)
407  { cout << "**That's impossible; we were told we had " << numEdges << ":(" << n->getNumOutgoingEdges() << "+" << n->getNumIncomingEdges() <<
408  ") edges, we're on #" << x << " and we got nil!";
409  cout << "(node " << n->GetNum() << ")" << endl;
410  break;
411  }
412  }
413  }
414  }
415 #endif
416 
417  return g;
418 }
419 
427 static const int gEdgeProb = 100;
428 static const int gStraightEdgeProb = 100;
429 
430 void AddMapEdges(Map *m, Graph *g, int x, int y)
431 {
432  // check 4 surrounding edges
433  // when we get two of them, we add the corresponding diagonal edge(?)...not yet
434  // make sure the edge we add isn't there already!
435  // make sure we get the right node # when we add the edge
436  edge *e = 0;
437 
438  // left edge is always tile1, right edge is always tile 2
439  if ((x >= 1) && (m->AdjacentEdges(x, y, kLeftEdge)) && (m->GetTile(x, y).tile1.node != kNoGraphNode))
440  {
441  if (m->AdjacentEdges(x-1, y, kInternalEdge) && (m->GetTile(x-1, y).tile1.node != kNoGraphNode))
442  {
443  if ((random()%100) < gStraightEdgeProb)
444  {
445  e = new edge(m->GetTile(x, y).tile1.node, m->GetTile(x-1, y).tile1.node, 1);
446  g->AddEdge(e);
447  }
448  }
449  else if (m->GetTile(x-1, y).tile2.node != kNoGraphNode)
450  {
451  if ((random()%100) < gStraightEdgeProb)
452  {
453  e = new edge(m->GetTile(x, y).tile1.node, m->GetTile(x-1, y).tile2.node, 1);
454  g->AddEdge(e);
455  }
456  }
457  if (e)
458  e->SetLabelL(kEdgeCapacity, 1);
459  }
460  e = 0;
461  // top edge (may be tile 1 or tile 2)
462  if ((y >= 1) && (m->AdjacentEdges(x, y, kTopEdge)))
463  {
464  if ((m->AdjacentEdges(x, y, kInternalEdge)) || (m->GetSplit(x, y) == kForwardSplit))
465  {
466  if (m->GetTile(x, y).tile1.node != kNoGraphNode)
467  {
468  if (m->AdjacentEdges(x, y-1, kInternalEdge) || (m->GetSplit(x, y-1) == kBackwardSplit))
469  {
470  if (m->GetTile(x, y-1).tile1.node != kNoGraphNode)
471  {
472  if ((random()%100) < gStraightEdgeProb)
473  {
474  e = new edge(m->GetTile(x, y).tile1.node, m->GetTile(x, y-1).tile1.node, 1);
475  g->AddEdge(e);
476  }
477  }
478  }
479  else if (m->GetTile(x, y-1).tile2.node != kNoGraphNode)
480  {
481  if ((random()%100) < gStraightEdgeProb)
482  {
483  e = new edge(m->GetTile(x, y).tile1.node, m->GetTile(x, y-1).tile2.node, 1);
484  g->AddEdge(e);
485  }
486  }
487  }
488  }
489  else {
490  if (m->AdjacentEdges(x, y-1, kInternalEdge) || (m->GetSplit(x, y-1) == kBackwardSplit))
491  {
492  if ((m->GetTile(x, y).tile2.node != kNoGraphNode) && (m->GetTile(x, y-1).tile1.node != kNoGraphNode))
493  {
494  if ((random()%100) < gStraightEdgeProb)
495  {
496  e = new edge(m->GetTile(x, y).tile2.node, m->GetTile(x, y-1).tile1.node, 1);
497  g->AddEdge(e);
498  }
499  }
500  }
501  else if ((m->GetTile(x, y).tile2.node != kNoGraphNode) && (m->GetTile(x, y-1).tile2.node != kNoGraphNode))
502  {
503  if ((random()%100) < gStraightEdgeProb)
504  {
505  e = new edge(m->GetTile(x, y).tile2.node, m->GetTile(x, y-1).tile2.node, 1);
506  g->AddEdge(e);
507  }
508  }
509  }
510  if (e)
511  e->SetLabelL(kEdgeCapacity, 1);
512  }
513  e = 0;
514  // diagonal UpperLeft edge, always node 1...
515  // (1) we can cross each of the boundaries between tiles
516  if ((x >= 1) && (y >= 1) && (m->AdjacentEdges(x, y, kLeftEdge)) && (m->AdjacentEdges(x, y, kTopEdge)) &&
517  (m->AdjacentEdges(x, y-1, kLeftEdge)) && (m->AdjacentEdges(x-1, y, kTopEdge)) &&
518  (m->GetTile(x, y).tile1.node != kNoGraphNode))
519  {
520  // (2) we can cross the inner tile boundaries
521  if (((m->AdjacentEdges(x-1, y, kInternalEdge)) || (m->GetSplit(x-1, y) == kBackwardSplit)) &&
522  ((m->AdjacentEdges(x, y-1, kInternalEdge)) || (m->GetSplit(x, y-1) == kBackwardSplit)) &&
523  ((m->AdjacentEdges(x-1, y-1, kInternalEdge)) || (m->GetSplit(x-1, y-1) == kForwardSplit)) &&
524  ((m->AdjacentEdges(x, y, kInternalEdge)) || (m->GetSplit(x, y) == kForwardSplit)))
525  {
526  // (3) find what tiles to connect
527  if (m->AdjacentEdges(x-1, y-1, kInternalEdge))
528  {
529  if (m->GetTile(x-1, y-1).tile1.node != kNoGraphNode)
530  {
531  if ((random()%100) < gEdgeProb)
532  {
533  e = new edge(m->GetTile(x, y).tile1.node, m->GetTile(x-1, y-1).tile1.node, ROOT_TWO);
534  g->AddEdge(e);
535  }
536  }
537  }
538  else if (m->GetTile(x-1, y-1).tile2.node != kNoGraphNode)
539  {
540  if ((random()%100) < gEdgeProb)
541  {
542  e = new edge(m->GetTile(x, y).tile1.node, m->GetTile(x-1, y-1).tile2.node, ROOT_TWO);
543  g->AddEdge(e);
544  }
545  }
546  if (e)
547  e->SetLabelL(kEdgeCapacity, 1);
548  }
549  }
550  e = 0;
551  // diagonal UpperRight edge
552  // (1) we can cross each of the boundaries between tiles
553  if ((y >= 1) && (x < m->GetMapWidth()-1) && (m->AdjacentEdges(x, y, kRightEdge)) && (m->AdjacentEdges(x, y, kTopEdge)) &&
554  (m->AdjacentEdges(x, y-1, kRightEdge)) && (m->AdjacentEdges(x+1, y, kTopEdge)) &&
555  (m->GetTile(x+1, y-1).tile1.node != kNoGraphNode))
556  {
557  // (2) we can cross the inner tile boundaries
558  if (((m->AdjacentEdges(x+1, y, kInternalEdge)) || (m->GetSplit(x+1, y) == kForwardSplit)) &&
559  ((m->AdjacentEdges(x, y-1, kInternalEdge)) || (m->GetSplit(x, y-1) == kForwardSplit)) &&
560  ((m->AdjacentEdges(x+1, y-1, kInternalEdge)) || (m->GetSplit(x+1, y-1) == kBackwardSplit)) &&
561  ((m->AdjacentEdges(x, y, kInternalEdge)) || (m->GetSplit(x, y) == kBackwardSplit)))
562  {
563  // (3) connect
564  if (m->AdjacentEdges(x, y, kInternalEdge))
565  {
566  if (m->GetTile(x, y).tile1.node != kNoGraphNode)
567  {
568  if ((random()%100) < gEdgeProb)
569  {
570  e = new edge(m->GetTile(x, y).tile1.node, m->GetTile(x+1, y-1).tile1.node, ROOT_TWO);
571  g->AddEdge(e);
572  }
573  }
574  }
575  else if (m->GetTile(x, y).tile2.node != kNoGraphNode)
576  {
577  if ((random()%100) < gEdgeProb)
578  {
579  e = new edge(m->GetTile(x, y).tile2.node, m->GetTile(x+1, y-1).tile1.node, ROOT_TWO);
580  g->AddEdge(e);
581  }
582  }
583  if (e)
584  e->SetLabelL(kEdgeCapacity, 1);
585  }
586  }
587 }
Graph::AddNode
int AddNode(node *)
Definition: Graph.cpp:136
GraphAbstractionConstants
Definition: GraphAbstraction.h:22
node::SetLabelL
void SetLabelL(unsigned int index, long val) const
Definition: Graph.cpp:702
node::SetLabelF
void SetLabelF(unsigned int index, double val) const
Definition: Graph.cpp:687
kRightEdge
@ kRightEdge
Definition: Map.h:83
recVec
A generic vector (essentially the same as a point, but offers normalization)
Definition: GLUtil.h:78
recVec::z
GLdouble z
Definition: GLUtil.h:98
kOutOfBounds
@ kOutOfBounds
Definition: Map.h:52
gStraightEdgeProb
static const int gStraightEdgeProb
Definition: MapAbstraction.cpp:428
Graph::AddEdge
void AddEdge(edge *)
Definition: Graph.cpp:170
kTopRight
@ kTopRight
Definition: Map.h:99
Graph::nodeIterNext
node * nodeIterNext(node_iterator &) const
Definition: Graph.cpp:303
edge_iterator
std::vector< edge * >::const_iterator edge_iterator
Definition: Graph.h:30
width
int width
Definition: SFML_HOG.cpp:54
Map::GetTile
Tile & GetTile(long x, long y)
Return the tile at location x, y.
Definition: Map.cpp:994
GraphAbstractionConstants::kEdgeCapacity
@ kEdgeCapacity
Definition: GraphAbstraction.h:53
Tile::tile1
halfTile tile1
Definition: Map.h:116
kTopLeft
@ kTopLeft
Definition: Map.h:98
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
Tile::split
tSplit split
Definition: Map.h:117
GraphAbstractionConstants::kZCoordinate
@ kZCoordinate
Definition: GraphAbstraction.h:32
node_iterator
std::vector< node * >::const_iterator node_iterator
Definition: Graph.h:33
GraphAbstractionConstants::kNumAbstractedNodes
@ kNumAbstractedNodes
Definition: GraphAbstraction.h:26
node::getEdgeIter
edge_iterator getEdgeIter() const
Definition: Graph.cpp:749
kBottomLeft
@ kBottomLeft
Definition: Map.h:100
Tile::tile2
halfTile tile2
Definition: Map.h:116
kNoGraphNode
const int kNoGraphNode
Definition: Map.h:93
GetMapGraph
Graph * GetMapGraph(Map *m)
GetMapGraph(map)
Definition: MapAbstraction.cpp:312
Graph::getEdgeIter
edge_iterator getEdgeIter() const
Definition: Graph.cpp:315
GraphAbstractionConstants::kFirstData
@ kFirstData
Definition: GraphAbstraction.h:34
kForwardSplit
@ kForwardSplit
Definition: Map.h:69
kBackwardSplit
@ kBackwardSplit
Definition: Map.h:70
edge::SetLabelL
void SetLabelL(unsigned int index, long val)
Definition: Graph.cpp:598
ROOT_TWO
static const double ROOT_TWO
Definition: GLUtil.h:61
Map::GetMapWidth
long GetMapWidth() const
return the width of the map
Definition: Map.h:163
GraphAbstractionConstants::kAbstractionLevel
@ kAbstractionLevel
Definition: GraphAbstraction.h:25
AddMapEdges
void AddMapEdges(Map *m, Graph *g, int x, int y)
Definition: MapAbstraction.cpp:430
kInternalEdge
@ kInternalEdge
Definition: Map.h:81
Map::GetTerrainType
long GetTerrainType(long x, long y, tSplitSide split=kWholeTile) const
Get the terrain type of the (split) tile at x, y.
Definition: Map.cpp:1028
height
int height
Definition: SFML_HOG.cpp:54
GraphAbstractionConstants::kYCoordinate
@ kYCoordinate
Definition: GraphAbstraction.h:31
Graph::GetNumNodes
int GetNumNodes()
Definition: Graph.cpp:403
Graph::getNodeIter
node_iterator getNodeIter() const
Definition: Graph.cpp:298
halfTile::node
long node
Definition: Map.h:110
GraphAbstractionConstants::kXCoordinate
@ kXCoordinate
Definition: GraphAbstraction.h:30
node::GetLabelF
double GetLabelF(unsigned int index) const
Definition: Graph.h:215
GraphAbstractionConstants::kNodeBlocked
@ kNodeBlocked
Definition: GraphAbstraction.h:33
MapAbstraction.h
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
gEdgeProb
static const int gEdgeProb
AddMapEdges(map, Graph, x, y)
Definition: MapAbstraction.cpp:427
Tile
Definition: Map.h:113
kBottomRight
@ kBottomRight
Definition: Map.h:101
Map::GetSplit
tSplit GetSplit(long x, long y) const
Return the split of the tile at x, y.
Definition: Map.cpp:1004
kTopEdge
@ kTopEdge
Definition: Map.h:84
Map::AdjacentEdges
bool AdjacentEdges(long x, long y, tEdge edge) const
Is the tile at x, y adjacent across the edge?
Definition: Map.cpp:1602
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
kLeftEdge
@ kLeftEdge
Definition: Map.h:82
node::GetLabelL
long GetLabelL(unsigned int index) const
Definition: Graph.h:220
GraphAbstractionConstants::kUnknownPosition
const double kUnknownPosition
Definition: GraphAbstraction.h:56
recVec::y
GLdouble y
Definition: GLUtil.h:98
node::edgeIterNext
edge * edgeIterNext(edge_iterator &) const
Definition: Graph.cpp:754
recVec::x
GLdouble x
Definition: GLUtil.h:98
node::getNumIncomingEdges
int getNumIncomingEdges()
Definition: Graph.cpp:789
node
Nodes to be stored within a Graph.
Definition: Graph.h:170
Map
A tile-based representation of the world.
Definition: Map.h:142
node::getNumOutgoingEdges
int getNumOutgoingEdges()
Definition: Graph.cpp:784
kNone
@ kNone
Definition: Map.h:97
edge
Edge class for connections between node in a Graph.
Definition: Graph.h:129
Generated by   doxygen 1.8.17