HOG2
GraphEnvironment.cpp
Go to the documentation of this file.
1 /*
2  * GraphEnvironment.cpp
3  * hog2
4  *
5  * Created by Nathan Sturtevant on 5/29/07.
6  * Copyright 2007 Nathan Sturtevant, University of Alberta. All rights reserved.
7  *
8  */
9 
10 #include "GraphEnvironment.h"
11 #include "GLUtil.h"
12 #include "Heap.h"
13 #include "FloydWarshall.h"
14 #include "SVGUtil.h"
15 
16 using namespace GraphSearchConstants;
17 
18 //int GraphMapInconsistentHeuristic::hmode=2;
19 //int GraphMapInconsistentHeuristic::HN=10;
20 //double GraphMapPerfectHeuristic::prob=0.5;
21 
22 GraphEnvironment::GraphEnvironment(Graph *_g, GraphHeuristic *gh)
23 :g(_g), h(gh)
24 {
25  m = 0;
26  directed = false;
27  drawEdgeCosts = false;
28  integerEdgeCosts = false;
29  drawNodeLabels = false;
30  nodeScale = 1.0;
31 }
32 
33 GraphEnvironment::GraphEnvironment(Map *_m, Graph *_g, GraphHeuristic *gh)
34 :g(_g), h(gh)
35 {
36  m = _m;
37  directed = false;
38  drawEdgeCosts = false;
39  integerEdgeCosts = false;
40  drawNodeLabels = false;
41  nodeScale = 1.0;
42 }
43 
44 //GraphEnvironment::GraphEnvironment(Map *m)
45 //{
46 // h = 0;
47 // directed = false;
48 // g = GetMapGraph(m);
49 // //BuildHeuristics(m, g);
50 //}
51 
52 GraphEnvironment::~GraphEnvironment()
53 {
54  // delete g; ??
55  // delete g;
56 // delete h;
57 }
58 
59 int GraphEnvironment::GetNumSuccessors(const graphState &stateID) const
60 {
61  node *n = g->GetNode(stateID);
62 
63  if (n == 0)
64  {
65  return 0;
66  }
67 
68  if (directed)
69  {
70  return n->getNumOutgoingEdges();
71  }
72  return n->GetNumEdges();
73 }
74 
75 void GraphEnvironment::GetSuccessors(const graphState &stateID, std::vector<graphState> &neighbors) const
76 {
77  neighbors.resize(0);
78  node *n = g->GetNode(stateID);
79 
80  if (n == 0)
81  {
82  return;
83  }
84 
85  if (directed)
86  {
87  edge_iterator ei = n->getOutgoingEdgeIter();
88  for (edge *e = n->edgeIterNextOutgoing(ei); e; e = n->edgeIterNextOutgoing(ei))
89  {
90  neighbors.push_back(e->getTo());
91  }
92  }
93  else {
94  edge_iterator ei = n->getEdgeIter();
95  for (edge *e = n->edgeIterNext(ei); e; e = n->edgeIterNext(ei))
96  {
97  if (stateID != e->getTo())
98  neighbors.push_back(e->getTo());
99  else
100  neighbors.push_back(e->getFrom());
101  }
102  }
103 }
104 
105 void GraphEnvironment::GetActions(const graphState &stateID, std::vector<graphMove> &actions) const
106 {
107  actions.resize(0);
108  node *n = g->GetNode(stateID);
109 
110  if (n == 0)
111  {
112  return;
113  }
114 
115  if (directed)
116  {
117  edge_iterator ei = n->getOutgoingEdgeIter();
118  for (edge *e = n->edgeIterNextOutgoing(ei); e; e = n->edgeIterNextOutgoing(ei))
119  {
120  actions.push_back(graphMove(e->getFrom(),e->getTo()));
121  }
122  }
123  else {
124  edge_iterator ei = n->getEdgeIter();
125  for (edge *e = n->edgeIterNext(ei); e; e = n->edgeIterNext(ei))
126  {
127  if (stateID != e->getTo())
128  actions.push_back(graphMove(e->getFrom(),e->getTo()));
129  else
130  actions.push_back(graphMove(e->getTo(),e->getFrom()));
131  }
132  }
133 
134 }
135 
136 graphMove GraphEnvironment::GetAction(const graphState &s1, const graphState &s2) const
137 {
138  return graphMove(s1, s2);
139 }
140 
141 void GraphEnvironment::ApplyAction(graphState &s, graphMove a) const
142 {
143  assert(s == a.from);
144  s = a.to;
145 }
146 
147 bool GraphEnvironment::InvertAction(graphMove &a) const
148 {
149  uint32_t tmp = a.from;
150  a.from = a.to;
151  a.to = tmp;
152  if (g->findDirectedEdge(a.from, a.to))
153  return true;
154  return false;
155 }
156 
157 double GraphEnvironment::HCost(const graphState &state1, const graphState &state2) const
158 {
159  if (h)
160  return h->HCost(state1, state2);
161  if (state1 == state2)
162  return 0;
163  return 1;// this should be the min edge cost in the graph...
164 }
165 
166 double GraphEnvironment::GCost(const graphState &, const graphMove &move) const
167 {
168  edge *e = g->FindEdge(move.from, move.to);
169  assert(e);
170  return e->GetWeight();
171 }
172 
173 double GraphEnvironment::GCost(const graphState &state1, const graphState &state2) const
174 {
175  edge *e = g->FindEdge(state1, state2);
176 // if (!e)
177 // return -1000.0;
178  assert(e);
179  return e->GetWeight();
180 }
181 
182 bool GraphEnvironment::GoalTest(const graphState &state, const graphState &goal) const
183 {
184  return state == goal;
185 }
186 
187 uint64_t GraphEnvironment::GetStateHash(const graphState &state) const
188 {
189  return g->GetNode(state)->getUniqueID();
190 }
191 
192 void GraphEnvironment::GetStateFromHash(uint64_t hash, graphState &s) const
193 {
194  s = hash;
195 }
196 
197 
198 uint64_t GraphEnvironment::GetActionHash(graphMove act) const
199 {
200  return (g->GetNode(act.from)->getUniqueID()<<16)|
201  (g->GetNode(act.to)->getUniqueID());
202 }
203 
204 
205 
206 void GraphEnvironment::OpenGLDraw() const
207 {
208  if ((g == 0) || (g->GetNumNodes() == 0)) return;
209 
210  if (m)
211  {
212  m->OpenGLDraw();
213  return;
214  }
215 
216  // Hittable background behind graph
217  glBegin(GL_TRIANGLE_FAN);
218  glColor4f(0, 0, 0, 0.01);
219  glVertex3f(-1, -1, 0.01);
220  glVertex3f(1, -1, 0.01);
221  glVertex3f(1, 1, 0.01);
222  glVertex3f(-1, 1, 0.01);
223  glEnd();
224  glBegin(GL_LINES);
225  glNormal3f(0, 1, 0);
226 
227  GLdouble off = 0;
228  edge_iterator ei = g->getEdgeIter();
229  for (edge *e = g->edgeIterNext(ei); e; e = g->edgeIterNext(ei))
230  {
231  //int x, y;
232  //double offsetx, offsety;
233  node *n;
234  n = g->GetNode(e->getFrom());
235  assert(n!=0);
236 
237  {
238  GLfloat r, g, b, t;
239  GetColor(r, g, b, t);
240  glColor4f(r, g, b, t);
241  }
242  if (e->getMarked())
243  {
244  glColor3f(1.0, 0.0, 0.0);
245  off = -0.01;
246  }
247  else {
248  off = 0;
249  }
250 
251  GLdouble x, y, z;
252  x = n->GetLabelF(GraphSearchConstants::kXCoordinate);
253  y = n->GetLabelF(GraphSearchConstants::kYCoordinate);
254  z = n->GetLabelF(GraphSearchConstants::kZCoordinate);
255  glVertex3f(x, y, z+off);
256 
257  n = g->GetNode(e->getTo());
258  assert(n!=0);
259  x = n->GetLabelF(GraphSearchConstants::kXCoordinate);
260  y = n->GetLabelF(GraphSearchConstants::kYCoordinate);
261  z = n->GetLabelF(GraphSearchConstants::kZCoordinate);
262 
263  glVertex3f(x, y, z+off);
264  }
265  glEnd();
266 
267  char label[5];
268  if (drawEdgeCosts)
269  {
270  glLineWidth(3.0);
271  glColor4f(0.0, 0.0, 0.0, 1.0);
272  edge_iterator ei = g->getEdgeIter();
273  for (edge *e = g->edgeIterNext(ei); e; e = g->edgeIterNext(ei))
274  {
275  if (integerEdgeCosts)
276  sprintf(label, "%d", int(e->GetWeight()));
277  else
278  sprintf(label, "%1.2f", e->GetWeight());
279  node *n;
280  n = g->GetNode(e->getFrom());
281 
282  GLdouble x, y, z;
283  x = n->GetLabelF(GraphSearchConstants::kXCoordinate);
284  y = n->GetLabelF(GraphSearchConstants::kYCoordinate);
285  z = n->GetLabelF(GraphSearchConstants::kZCoordinate);
286 
287  n = g->GetNode(e->getTo());
288  x += n->GetLabelF(GraphSearchConstants::kXCoordinate);
289  y += n->GetLabelF(GraphSearchConstants::kYCoordinate);
290  z += n->GetLabelF(GraphSearchConstants::kZCoordinate);
291 
292  DrawText(x/2, y/2, z/2-0.003, 0.2, label);
293  }
294  glLineWidth(1.0);
295  }
296  if (drawNodeLabels)
297  {
298  glLineWidth(3.0);
299  glColor4f(0.0, 0.0, 0.0, 1.0);
300  for (int x = 0; x < g->GetNumNodes(); x++)
301  {
302  node *n = g->GetNode(x);
303  DrawTextCentered(n->GetLabelF(GraphSearchConstants::kXCoordinate),
304  n->GetLabelF(GraphSearchConstants::kYCoordinate),
305  n->GetLabelF(GraphSearchConstants::kZCoordinate)-0.003,
306  0.2, n->GetName());
307  }
308  glLineWidth(1.0);
309  }
310 
311 }
312 
313 void GraphEnvironment::OpenGLDraw(const graphState &s) const
314 {
315  if (m)
316  {
317  GLdouble xx, yy, zz, rad;
318  int x1, y1;
319  node *n = g->GetNode(s);
320  x1 = n->GetLabelL(GraphSearchConstants::kMapX);
321  y1 = n->GetLabelL(GraphSearchConstants::kMapY);
322  m->GetOpenGLCoord(x1, y1, xx, yy, zz, rad);
323  GLfloat red, gre, blue, t;
324  GetColor(red, gre, blue, t);
325  glColor4f(red, gre, blue, t);
326  //glColor3f(0.5, 0.5, 0.5);
327  //DrawSphere(xx, yy, zz, rad);
328  glBegin(GL_QUADS);
329  glVertex3d(xx+rad, yy+rad, zz-rad);
330  glVertex3d(xx-rad, yy+rad, zz-rad);
331  glVertex3d(xx-rad, yy-rad, zz-rad);
332  glVertex3d(xx+rad, yy-rad, zz-rad);
333  glEnd();
334  }
335  else {
336 
337  if (drawNodeLabels)// draw states as boxes
338  {
339 
340  GLfloat r, gr, b, t;
341  GetColor(r, gr, b, t);
342  glColor4f(r, gr, b, t);
343 
344  node *n = g->GetNode(s);
345  GLdouble x, y, z, rad;
346  x = (GLdouble)n->GetLabelF(GraphSearchConstants::kXCoordinate);
347  y = (GLdouble)n->GetLabelF(GraphSearchConstants::kYCoordinate);
348  z = (GLdouble)n->GetLabelF(GraphSearchConstants::kZCoordinate);
349  //rad = 20*(GLdouble)0.4/(g->GetNumNodes());
350  rad = nodeScale*(GLdouble)0.4/(g->GetNumNodes());
351  DrawSquare(x, y, z-0.002, rad);
352  glLineWidth(2.0);
353 // if (r+gr+b < 1.5)
354 // glColor4f(1, 1, 1, t);
355 // else
356  glColor4f(0, 0, 0, t);
357  OutlineRect(x-rad, y-rad, x+rad, y+rad, z-0.0021);
358  glLineWidth(1.0);
359  }
360  //(GLdouble)2.0/(g->GetNumNodes()*g->GetNumNodes()));
361 
362 
363  if (1) // draw states by their edges
364  {
365  node *n = g->GetNode(s);
366  glLineWidth(2.0);
367  glBegin(GL_LINES);
368 
369  GLfloat r, gr, b, t;
370  GetColor(r, gr, b, t);
371  glColor4f(r, gr, b, t);
372 
373  edge_iterator ei = n->getEdgeIter();
374  for (edge *e = n->edgeIterNext(ei); e; e = n->edgeIterNext(ei))
375  {
376  node *n;
377  n = g->GetNode(e->getFrom());
378 
379  GLdouble x, y, z;
380  x = n->GetLabelF(GraphSearchConstants::kXCoordinate);
381  y = n->GetLabelF(GraphSearchConstants::kYCoordinate);
382  z = n->GetLabelF(GraphSearchConstants::kZCoordinate);
383  glVertex3f(x, y, z);
384 
385  n = g->GetNode(e->getTo());
386  x = n->GetLabelF(GraphSearchConstants::kXCoordinate);
387  y = n->GetLabelF(GraphSearchConstants::kYCoordinate);
388  z = n->GetLabelF(GraphSearchConstants::kZCoordinate);
389 
390  glVertex3f(x, y, z);
391  }
392  glEnd();
393  glLineWidth(1.0);
394  }
395  }
396 }
397 
398 void GraphEnvironment::GLLabelState(const graphState &s, const char *txt) const
399 {
400 // glLineWidth(3.0);
401  glColor4f(0.0, 0.0, 0.0, 1.0);
402  node *n = g->GetNode(s);
403  double rad = nodeScale*(GLdouble)0.4/(g->GetNumNodes());
404 // glPushMatrix();
405 // glTranslatef(rad, -rad, 0);
406  DrawText(n->GetLabelF(GraphSearchConstants::kXCoordinate)+rad,
407  n->GetLabelF(GraphSearchConstants::kYCoordinate)-rad,
408  n->GetLabelF(GraphSearchConstants::kZCoordinate)-0.003,
409  0.2, txt);
410 // glPopMatrix();
411 // glLineWidth(1.0);
412 }
413 
414 void GraphEnvironment::OpenGLDraw(const graphState &, const graphMove &) const
415 {
416  // if we want to draw a set of moves we use this to do so
417 }
418 
419 void GraphEnvironment::GLDrawLine(const graphState &from, const graphState &to) const
420 {
421  {
422  GLfloat r, g, b, t;
423  GetColor(r, g, b, t);
424  glColor4f(r, g, b, t);
425  }
426 
427 
428  glBegin(GL_LINES);
429 
430  GLdouble x, y, z;
431 
432  node *n = g->GetNode(from);
433  x = n->GetLabelF(GraphSearchConstants::kXCoordinate);
434  y = n->GetLabelF(GraphSearchConstants::kYCoordinate);
435  z = n->GetLabelF(GraphSearchConstants::kZCoordinate);
436  glVertex3f(x, y, z);
437 
438  n = g->GetNode(to);
439  x = n->GetLabelF(GraphSearchConstants::kXCoordinate);
440  y = n->GetLabelF(GraphSearchConstants::kYCoordinate);
441  z = n->GetLabelF(GraphSearchConstants::kZCoordinate);
442  glVertex3f(x, y, z);
443 
444  glEnd();
445 }
446 
447 std::string GraphEnvironment::SVGHeader() const
448 {
449  std::string s;
450  // 10% margin on all sides of image
451  s = "<svg xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\" width = \""+std::to_string(610)+"\" height = \""+std::to_string(610)+"\" ";
452  s += "viewBox=\""+std::to_string(-5)+" "+std::to_string(-5)+" ";
453  s += std::to_string(610)+" "+std::to_string(610)+"\" ";
454  s += "preserveAspectRatio = \"none\" ";
455  s += ">\n";
456  return s;
457 }
458 std::string GraphEnvironment::SVGLabelState(const graphState &s, const char *str) const
459 {
460  float x1, y1;
461  node *n = g->GetNode(s);
462  x1 = n->GetLabelF(GraphSearchConstants::kXCoordinate);
463  y1 = n->GetLabelF(GraphSearchConstants::kYCoordinate);
464 
465  x1 = int((x1+1.0)*300.0+12.0);
466  y1 = int((y1+1.0)*300.0+20.0);
467 
468  return SVGDrawText(x1, y1, str, Colors::blue, 24);
469 }
470 
471 std::string GraphEnvironment::SVGDraw(const graphState &s) const
472 {
473  float x1, y1;
474  node *n = g->GetNode(s);
475  x1 = n->GetLabelF(GraphSearchConstants::kXCoordinate);
476  y1 = n->GetLabelF(GraphSearchConstants::kYCoordinate);
477 
478  x1 = int((x1+1.0)*300.0);
479  y1 = int((y1+1.0)*300.0);
480 
481  return SVGDrawCircle(x1, y1, 6, Colors::black)+SVGDrawCircle(x1, y1, 2, GetColor());
482 }
483 
484 std::string GraphEnvironment::SVGDraw() const
485 {
486  std::string s = "<path d=\"";
487 
488  edge_iterator ei = g->getEdgeIter();
489  int count = 0;
490  int minx = 600, miny=600, maxx = 0, maxy= 0;
491  for (edge *e = g->edgeIterNext(ei); e; e = g->edgeIterNext(ei))
492  {
493  if (e->getFrom() >= e->getTo())
494  continue;
495  //int x, y;
496  //double offsetx, offsety;
497  node *n;
498  n = g->GetNode(e->getFrom());
499 
500  rgbColor c;
501  GLfloat t;
502  GetColor(c.r, c.g, c.b, t);
503 
504  if (e->getMarked())
505  {
506 // c.r = 1;
507 // c.g = c.b = 0;
508  }
509 
510  float x1, y1, x2, y2;
511  x1 = n->GetLabelF(GraphSearchConstants::kXCoordinate);
512  y1 = n->GetLabelF(GraphSearchConstants::kYCoordinate);
513 
514  n = g->GetNode(e->getTo());
515  x2 = n->GetLabelF(GraphSearchConstants::kXCoordinate);
516  y2 = n->GetLabelF(GraphSearchConstants::kYCoordinate);
517 // M 100 350 l 150 -300
518  int fx1, fx2, fy1, fy2;
519  fx1 = int((x1+1.0)*300.0);
520  fx2 = int((x2+1.0)*300.0);
521  fy1 = int((y1+1.0)*300.0);
522  fy2 = int((y2+1.0)*300.0);
523  if (fx1 == fx2 && fy1 == fy2)
524  continue;
525 
526  maxx = std::max(maxx, fx1);
527  maxx = std::max(maxx, fx2);
528  minx = std::min(minx, fx1);
529  minx = std::min(minx, fx2);
530 
531  maxy = std::max(maxy, fy1);
532  maxy = std::max(maxy, fy2);
533  miny = std::min(miny, fy1);
534  miny = std::min(miny, fy2);
535 
536 
537  s += "M "+std::to_string(fx1)+" "+std::to_string(fy1)+" ";
538  s += "L "+std::to_string(fx2)+" "+std::to_string(fy2)+" ";
539 
540  if (0 == ++count%200)
541  {
542  s += "\" stroke=\"black\" stroke-width=\"0.1\" fill=\"none\" />\n";
543  s += "<path d=\"";
544  }
545  }
546 // printf("Bounds: (%d, %d) to (%d, %d)\n", minx, miny, maxx, maxy);
547  s += "\" stroke=\"black\" stroke-width=\"0.1\" fill=\"none\" />\n";
548 // for (float x = minx; x <= maxx; x += (maxx-minx)/10.0)
549 // {
550 // s += SVGDrawLine((float)x, (float)miny, (float)x, (float)maxy, 2.0, Colors::darkblue);
551 // }
552 // for (float y = miny; y <= maxy; y += (maxy-miny)/10.0)
553 // {
554 // s += SVGDrawLine((float)minx, (float)y, (float)maxx, (float)y, 2.0, Colors::darkblue);
555 // }
556  return s;
557 }
558 
559 void GraphEnvironment::DrawLERP(Graphics::Display &disp, Graph *a, Graph *b, float mix) const
560 {
561  DrawLERP(disp, a, b, mix,
562 [](float a, float b, float mix) { return (1-mix)*a+mix*b;},
563 [](float a, float b, float mix) { return (1-mix)*a+mix*b;});
564 }
565 
566 void GraphEnvironment::DrawLERP(Graphics::Display &disp, Graph *a, Graph *b, float mix,
567  std::function<float(float, float, float)> l1,
568  std::function<float(float, float, float)> l2) const
569 {
570  if ((a == 0) || (a->GetNumNodes() == 0) || b == 0 || b->GetNumNodes() == 0 || b->GetNumNodes() != a->GetNumNodes())
571  return;
572 
573  rgbColor mainColor = GetColor();
574 // float mixX = (mix<0.6)?(5*mix/3):1;
575 // float mixY = (mix<0.4)?0:5*(mix-0.4)/3;
576 
577  edge_iterator ei = a->getEdgeIter();
578  for (edge *e = a->edgeIterNext(ei); e; e = a->edgeIterNext(ei))
579  {
580 // if (e->getFrom() > e->getTo())
581 // continue;
582  //int x, y;
583  //double offsetx, offsety;
584  node *n;
585  node *n2;
586  GLdouble x1, y1;
587  GLdouble x2, y2;
588 
589  n = a->GetNode(e->getFrom());
590  n2 = b->GetNode(e->getFrom());
591  x1 = l1(n->GetLabelF(GraphSearchConstants::kXCoordinate), n2->GetLabelF(GraphSearchConstants::kXCoordinate), mix);
592  y1 = l2(n->GetLabelF(GraphSearchConstants::kYCoordinate), n2->GetLabelF(GraphSearchConstants::kYCoordinate), mix);
593 // x1 = (1-mixX)*+mixX*n2->GetLabelF(GraphSearchConstants::kXCoordinate);
594 // y1 = (1-mixY)*n->GetLabelF(GraphSearchConstants::kYCoordinate)+mixY*n2->GetLabelF(GraphSearchConstants::kYCoordinate);
595 
596  n = a->GetNode(e->getTo());
597  n2 = b->GetNode(e->getTo());
598  x2 = l1(n->GetLabelF(GraphSearchConstants::kXCoordinate), n2->GetLabelF(GraphSearchConstants::kXCoordinate), mix);
599  y2 = l2(n->GetLabelF(GraphSearchConstants::kYCoordinate), n2->GetLabelF(GraphSearchConstants::kYCoordinate), mix);
600 // x2 = (1-mixX)*n->GetLabelF(GraphSearchConstants::kXCoordinate)+mixX*n2->GetLabelF(GraphSearchConstants::kXCoordinate);
601 // y2 = (1-mixY)*n->GetLabelF(GraphSearchConstants::kYCoordinate)+mixY*n2->GetLabelF(GraphSearchConstants::kYCoordinate);
602 
603 // auto i = g->GetNumNodes();
604 // auto rad = nodeScale*(GLdouble)0.4/(std::max(i, 8));
605  disp.DrawLine(Graphics::point(x1, y1), Graphics::point(x2, y2), 0.005, mainColor);
606  }
607 
608 }
609 
610 void GraphEnvironment::DrawLERP(Graphics::Display &disp, Graph *a, Graph *b, graphState sa, graphState sb, float mix,
611  std::function<float(float, float, float)> l1,
612  std::function<float(float, float, float)> l2) const
613 {
614  if ((a == 0) || (a->GetNumNodes() == 0) || b == 0 || b->GetNumNodes() == 0 || b->GetNumNodes() != a->GetNumNodes())
615  return;
616 
617  rgbColor mainColor = GetColor();
618 // float mixX = (mix<0.6)?(5*mix/3):1;
619 // float mixY = (mix<0.4)?0:5*(mix-0.4)/3;
620 
621  edge_iterator ei = a->getEdgeIter();
622  for (edge *e = a->edgeIterNext(ei); e; e = a->edgeIterNext(ei))
623  {
624 // if (e->getFrom() > e->getTo())
625 // continue;
626  //int x, y;
627  //double offsetx, offsety;
628  node *n;
629  node *n2;
630  GLdouble x1, y1;
631 
632  n = a->GetNode(sa);
633  n2 = b->GetNode(sb);
634  x1 = l1(n->GetLabelF(GraphSearchConstants::kXCoordinate), n2->GetLabelF(GraphSearchConstants::kXCoordinate), mix);
635  y1 = l2(n->GetLabelF(GraphSearchConstants::kYCoordinate), n2->GetLabelF(GraphSearchConstants::kYCoordinate), mix);
636 
637  disp.FillCircle(Graphics::point(x1, y1), 0.005f*7, mainColor);
638  }
639 
640 }
641 
642 
643 void GraphEnvironment::Draw(Graphics::Display &disp) const
644 {
645  if ((g == 0) || (g->GetNumNodes() == 0)) return;
646 
647  rgbColor mainColor = GetColor();
648 
649  edge_iterator ei = g->getEdgeIter();
650  for (edge *e = g->edgeIterNext(ei); e; e = g->edgeIterNext(ei))
651  {
652  //int x, y;
653  //double offsetx, offsety;
654  node *n;
655  n = g->GetNode(e->getFrom());
656 
657  GLdouble x1, y1;
658  GLdouble x2, y2;
659  x1 = n->GetLabelF(GraphSearchConstants::kXCoordinate);
660  y1 = n->GetLabelF(GraphSearchConstants::kYCoordinate);
661 
662  n = g->GetNode(e->getTo());
663  x2 = n->GetLabelF(GraphSearchConstants::kXCoordinate);
664  y2 = n->GetLabelF(GraphSearchConstants::kYCoordinate);
665 
666  auto i = g->GetNumNodes();
667  auto rad = nodeScale*(GLdouble)0.4/(std::max(i, 8));
668 // disp.DrawLine(Graphics::point(x1, y1), Graphics::point(x2, y2), 1.0, mainColor);
669 // DrawLine(disp, x1, y1, x2, y2, 1);
670  if (directed) // arrow goes to node
671  {
672  GLdouble len = sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
673  GLdouble ratio = (rad+0.1*rad)/len;
674  DrawLine(disp, x1, y1, (x2*(1-ratio)+ratio*x1), (y2*(1-ratio)+ratio*y1), 1);
675  }
676  else {
677  DrawLine(disp, x1, y1, x2, y2, 1);
678  }
679 // disp.DrawLine(Graphics::point(x1, y1), Graphics::point(x2, y2), 0.2*rad, mainColor);
680 // disp.DrawLine(Graphics::point(x1, y1), Graphics::point(x2, y2), 0.1*rad*width, SearchEnvironment::color);
681  }
682 
683  char label[5];
684  if (drawEdgeCosts)
685  {
686  glLineWidth(3.0);
687  glColor4f(0.0, 0.0, 0.0, 1.0);
688  edge_iterator ei = g->getEdgeIter();
689  for (edge *e = g->edgeIterNext(ei); e; e = g->edgeIterNext(ei))
690  {
691  if (integerEdgeCosts)
692  sprintf(label, "%d", int(e->GetWeight()));
693  else
694  sprintf(label, "%1.2f", e->GetWeight());
695  node *n;
696  n = g->GetNode(e->getFrom());
697  assert(n!=0);
698 
699  GLdouble x, y, z;
700  x = n->GetLabelF(GraphSearchConstants::kXCoordinate);
701  y = n->GetLabelF(GraphSearchConstants::kYCoordinate);
702  z = n->GetLabelF(GraphSearchConstants::kZCoordinate);
703 
704  n = g->GetNode(e->getTo());
705  assert(n!=0);
706  x += n->GetLabelF(GraphSearchConstants::kXCoordinate);
707  y += n->GetLabelF(GraphSearchConstants::kYCoordinate);
708  z += n->GetLabelF(GraphSearchConstants::kZCoordinate);
709 
710  //DrawText(x/2, y/2, z/2-0.003, 0.2, label);
711  auto i = g->GetNumNodes();
712  double rad = nodeScale*(GLdouble)0.4/(std::max(i, 8));
713  disp.DrawText(label, Graphics::point(x/2, y/2), Colors::black, rad, Graphics::textAlignCenter);
714  }
715  glLineWidth(1.0);
716  }
717  if (drawNodeLabels)
718  {
719 // glLineWidth(3.0);
720 // glColor4f(0.0, 0.0, 0.0, 1.0);
721  for (int x = 0; x < g->GetNumNodes(); x++)
722  {
723  node *n = g->GetNode(x);
724 // DrawTextCentered(n->GetLabelF(GraphSearchConstants::kXCoordinate),
725 // n->GetLabelF(GraphSearchConstants::kYCoordinate),
726 // n->GetLabelF(GraphSearchConstants::kZCoordinate)-0.003,
727 // 0.2, n->GetName());
728  auto i = g->GetNumNodes();
729  double rad = nodeScale*(GLdouble)0.4/(std::max(i, 8));
730  disp.DrawText(n->GetName(), Graphics::point(n->GetLabelF(GraphSearchConstants::kXCoordinate),
731  n->GetLabelF(GraphSearchConstants::kYCoordinate)),
732  Colors::black, rad, Graphics::textAlignCenter, Graphics::textBaselineMiddle);
733 // disp.DrawText(n->GetName(), Graphics::point(n->GetLabelF(GraphSearchConstants::kXCoordinate),
734 // n->GetLabelF(GraphSearchConstants::kYCoordinate)), mainColor, 0.05);
735  }
736 // glLineWidth(1.0);
737  }
738 
739 }
740 
741 void GraphEnvironment::Draw(Graphics::Display &disp, const graphState &l) const
742 {
743 // GLfloat r, gr, b, t;
744 // GetColor(r, gr, b, t);
745 // glColor4f(r, gr, b, t);
746  rgbColor c = GetColor();//{r, gr, b};
747  node *n = g->GetNode(l);
748  float x, y, z, rad;
749  x = (float)n->GetLabelF(GraphSearchConstants::kXCoordinate);
750  y = (float)n->GetLabelF(GraphSearchConstants::kYCoordinate);
751  z = (float)n->GetLabelF(GraphSearchConstants::kZCoordinate);
752  //rad = 20*(GLdouble)0.4/(g->GetNumNodes());
753  auto i = g->GetNumNodes();
754  rad = nodeScale*(GLdouble)0.4/(std::max(i, 8));
755  Graphics::rect rec;
756  rec.left= x-rad;
757  rec.top = y-rad;
758  rec.right = x+rad;
759  rec.bottom = y+rad;
760 // rgbColor tmp = c;
761 // tmp.mix(Colors::white, 0.5);
762  disp.FillCircle({x, y}, rad, c);
763  disp.FrameCircle({x, y}, rad, Colors::black, 0.1*rad);
764 // disp.FillCircle(rec, tmp);
765 // disp.FrameCircle(rec, c, 2.0);
766 
767 // disp.FillRect(rec, tmp);
768 // disp.FillRect(rec, Colors::lightgray);
769 // disp.FrameRect(rec, c, 2.0);
770 // DrawSquare(x, y, z-0.002, rad);
771 // glLineWidth(2.0);
772 // // if (r+gr+b < 1.5)
773 // // glColor4f(1, 1, 1, t);
774 // // else
775 // glColor4f(0, 0, 0, t);
776 // OutlineRect(x-rad, y-rad, x+rad, y+rad, z-0.0021);
777 // glLineWidth(1.0);
778 }
779 
780 void GraphEnvironment::DrawStateLabel(Graphics::Display &disp, const graphState &l1, const char *txt) const
781 {
782  node *n = g->GetNode(l1);
783  GLdouble x, y, z, rad;
784  x = (GLdouble)n->GetLabelF(GraphSearchConstants::kXCoordinate);
785  y = (GLdouble)n->GetLabelF(GraphSearchConstants::kYCoordinate);
786  z = (GLdouble)n->GetLabelF(GraphSearchConstants::kZCoordinate);
787 // rad = 1.5*nodeScale*(GLdouble)0.4/(g->GetNumNodes());
788  auto i = g->GetNumNodes();
789  rad = nodeScale*(GLdouble)0.4/(std::max(i, 8));
790 
791 // disp.DrawText(txt, Graphics::point(x+rad, y-rad), GetColor(), 0.05);
792 // disp.DrawText(txt, Graphics::point(x+rad, y-rad), GetColor(), rad);
793  disp.DrawText(txt, Graphics::point(x+rad*ONE_OVER_ROOT_TWO+0.15*rad, y-rad*ONE_OVER_ROOT_TWO-0.15*rad), GetColor(), rad,
794  Graphics::textAlignLeft, Graphics::textBaselineBottom);
795 }
796 
797 void GraphEnvironment::DrawLine(Graphics::Display &disp, const graphState &from, const graphState &to, double width) const
798 {
799  float x1, y1;
800  float x2, y2;
801 
802  node *n = g->GetNode(from);
803  x1 = (float)n->GetLabelF(GraphSearchConstants::kXCoordinate);
804  y1 = (float)n->GetLabelF(GraphSearchConstants::kYCoordinate);
805  //z = n->GetLabelF(GraphSearchConstants::kZCoordinate);
806  //glVertex3f(x, y, z);
807 
808  n = g->GetNode(to);
809  x2 = (float)n->GetLabelF(GraphSearchConstants::kXCoordinate);
810  y2 = (float)n->GetLabelF(GraphSearchConstants::kYCoordinate);
811  //z = n->GetLabelF(GraphSearchConstants::kZCoordinate);
812  //glVertex3f(x, y, z);
813  DrawLine(disp, x1, y1, x2, y2, width);
814 }
815 
816 void GraphEnvironment::DrawLine(Graphics::Display &disp, float x1, float y1, float x2, float y2, double width) const
817 {
818  auto i = g->GetNumNodes();
819  auto rad = nodeScale*(GLdouble)0.4/(std::max(i, 8));
820  if (directed)
821  disp.DrawArrow(Graphics::point(x1, y1), Graphics::point(x2, y2), 0.1f*rad*width, SearchEnvironment::color);
822  else
823  disp.DrawLine(Graphics::point(x1, y1), Graphics::point(x2, y2), 0.1f*rad*width, SearchEnvironment::color);
824 }
825 
826 Graphics::point GraphEnvironment::GetLocation(const graphState &s) const
827 {
828  float x1, y1;
829 
830  node *n = g->GetNode(s);
831  x1 = (float)n->GetLabelF(GraphSearchConstants::kXCoordinate);
832  y1 = (float)n->GetLabelF(GraphSearchConstants::kYCoordinate);
833  Graphics::point p(x1, y1, 0);
834  return p;
835 }
836 
837 
838 namespace GraphSearchConstants {
839 
848  Graph *GetUndirectedGraph(Map *m)
849  { return GetEightConnectedGraph(m, false); }
850 
851  Graph *GetGraph(Map *m)
852  { return GetEightConnectedGraph(m); }
853 
854  Graph *GetEightConnectedGraph(Map *m, bool directed)
855  {
856  Graph *g = new Graph();
857  AddNodesToGraph(m, g);
858  for (int y = 0; y < m->GetMapHeight(); y++)
859  {
860  for (int x = 0; x < m->GetMapWidth(); x++)
861  {
862  AddEdges(m, g, x, y, directed);//, 1.0, 1.5);
863  }
864  }
865  // printf("Done\n");
866  return g;
867  }
868 
869  Graph *GetFourConnectedGraph(Map *m, bool directed)
870  {
871  Graph *g = new Graph();
872  AddNodesToGraph(m, g);
873  for (int y = 0; y < m->GetMapHeight(); y++)
874  {
875  for (int x = 0; x < m->GetMapWidth(); x++)
876  {
877  AddEdges(m, g, x, y, directed, 1.0, 0.0, 100, 0);//, 1.0, 1.5);
878  }
879  }
880  // printf("Done\n");
881  return g;
882  }
883 
884  void AddNodesToGraph(Map *m, Graph *g)
885  {
886  char name[32];
887  node *n;
888  for (int y = 0; y < m->GetMapHeight(); y++)
889  {
890  for (int x = 0; x < m->GetMapWidth(); x++)
891  {
892  Tile &currTile = m->GetTile(x, y);
893  currTile.tile1.node = kNoGraphNode;
894  currTile.tile2.node = kNoGraphNode;
895 
896  if (m->AdjacentEdges(x, y, kInternalEdge))
897  {
898  GLdouble xx, yy, zz, rr;
899  m->GetOpenGLCoord(x, y,xx, yy, zz, rr);
900  if (2 != m->GetTerrainType(x, y)>>terrainBits)
901  continue;
902  sprintf(name, "(%d, %d)", x, y);
903  currTile.tile1.node = g->AddNode(n = new node(name));
904  n->SetLabelF(kXCoordinate, xx);
905  n->SetLabelF(kYCoordinate, yy);
906  n->SetLabelF(kZCoordinate, 00);
907  n->SetLabelL(kMapX, x);
908  n->SetLabelL(kMapY, y);
909  }
910  else {
911  if (m->GetTerrainType(x, y, kLeftEdge) == kGround)
912  {
913  GLdouble xx, yy, zz, rr;
914  m->GetOpenGLCoord(x, y,xx, yy, zz, rr);
915  if (2 != m->GetTerrainType(x, y)>>terrainBits)
916  continue;
917  sprintf(name, "(%d, %d)", x, y);
918  currTile.tile1.node = g->AddNode(n = new node(name));
919  n->SetLabelF(kXCoordinate, xx);
920  n->SetLabelF(kYCoordinate, yy);
921  n->SetLabelF(kZCoordinate, 00);
922  n->SetLabelL(kMapX, x);
923  n->SetLabelL(kMapY, y);
924  // if (currTile.split == kForwardSplit)
925  // n->SetLabelL(kFirstData+2, kTopLeft);
926  // else
927  // n->SetLabelL(kFirstData+2, kBottomLeft);
928  }
929 
930  if (m->GetTerrainType(x, y, kRightEdge) == kGround)
931  {
932  GLdouble xx, yy, zz, rr;
933  m->GetOpenGLCoord(x, y,xx, yy, zz, rr);
934  if (m->GetTerrainType(x, y) == kOutOfBounds)
935  continue;
936  sprintf(name, "(%d, %d)", x, y);
937  currTile.tile1.node = g->AddNode(n = new node(name));
938  n->SetLabelF(kXCoordinate, xx);
939  n->SetLabelF(kYCoordinate, yy);
940  n->SetLabelF(kZCoordinate, 00);
941  n->SetLabelL(kMapX, x);
942  n->SetLabelL(kMapY, y);
943  // if (currTile.split == kForwardSplit)
944  // n->SetLabelL(kFirstData+2, kBottomRight);
945  // else
946  // n->SetLabelL(kFirstData+2, kTopRight);
947  }
948  }
949  }
950  }
951  }
952 
960  void AddEdges(Map *m, Graph *g, int x, int y,
961  bool directed,
962  double straigtEdgeCost,
963  double diagEdgeCost,
964  int straightEdgeProb,
965  int diagEdgeProb)
966  {
967  // check 4 surrounding edges
968  // when we get two of them, we add the corresponding diagonal edge(?)...not yet
969  // make sure the edge we add isn't there already!
970  // make sure we get the right node # when we add the edge
971  edge *e = 0;
972 
973  // left edge is always tile1, right edge is always tile 2
974  if ((x >= 1) && (m->AdjacentEdges(x, y, kLeftEdge)) && (m->GetTile(x, y).tile1.node != kNoGraphNode))
975  {
976  if (m->AdjacentEdges(x-1, y, kInternalEdge) && (m->GetTile(x-1, y).tile1.node != kNoGraphNode))
977  {
978  if ((random()%100) < straightEdgeProb)
979  {
980  e = new edge(m->GetTile(x, y).tile1.node, m->GetTile(x-1, y).tile1.node, straigtEdgeCost);
981  g->AddEdge(e);
982  if (directed)
983  {
984  e = new edge(m->GetTile(x-1, y).tile1.node, m->GetTile(x, y).tile1.node, straigtEdgeCost);
985  g->AddEdge(e);
986  }
987  }
988  }
989  else if (m->GetTile(x-1, y).tile2.node != kNoGraphNode)
990  {
991  if ((random()%100) < straightEdgeProb)
992  {
993  e = new edge(m->GetTile(x, y).tile1.node, m->GetTile(x-1, y).tile2.node, straigtEdgeCost);
994  g->AddEdge(e);
995  if (directed)
996  {
997  e = new edge(m->GetTile(x-1, y).tile2.node, m->GetTile(x, y).tile1.node, straigtEdgeCost);
998  g->AddEdge(e);
999  }
1000  }
1001  }
1002  }
1003 
1004  // top edge (may be tile 1 or tile 2)
1005  if ((y >= 1) && (m->AdjacentEdges(x, y, kTopEdge)))
1006  {
1007  if ((m->AdjacentEdges(x, y, kInternalEdge)) || (m->GetSplit(x, y) == kForwardSplit))
1008  {
1009  if (m->GetTile(x, y).tile1.node != kNoGraphNode)
1010  {
1011  if (m->AdjacentEdges(x, y-1, kInternalEdge) || (m->GetSplit(x, y-1) == kBackwardSplit))
1012  {
1013  if (m->GetTile(x, y-1).tile1.node != kNoGraphNode)
1014  {
1015  if ((random()%100) < straightEdgeProb)
1016  {
1017  e = new edge(m->GetTile(x, y).tile1.node, m->GetTile(x, y-1).tile1.node, straigtEdgeCost);
1018  g->AddEdge(e);
1019  if (directed)
1020  {
1021  e = new edge(m->GetTile(x, y-1).tile1.node, m->GetTile(x, y).tile1.node, straigtEdgeCost);
1022  g->AddEdge(e);
1023  }
1024  }
1025  }
1026  }
1027  else if (m->GetTile(x, y-1).tile2.node != kNoGraphNode)
1028  {
1029  if ((random()%100) < straightEdgeProb)
1030  {
1031  e = new edge(m->GetTile(x, y).tile1.node, m->GetTile(x, y-1).tile2.node, straigtEdgeCost);
1032  g->AddEdge(e);
1033  if (directed)
1034  {
1035  e = new edge(m->GetTile(x, y-1).tile2.node, m->GetTile(x, y).tile1.node, straigtEdgeCost);
1036  g->AddEdge(e);
1037  }
1038  }
1039  }
1040  }
1041  }
1042  else {
1043  if (m->AdjacentEdges(x, y-1, kInternalEdge) || (m->GetSplit(x, y-1) == kBackwardSplit))
1044  {
1045  if ((m->GetTile(x, y).tile2.node != kNoGraphNode) && (m->GetTile(x, y-1).tile1.node != kNoGraphNode))
1046  {
1047  if ((random()%100) < straightEdgeProb)
1048  {
1049  e = new edge(m->GetTile(x, y).tile2.node, m->GetTile(x, y-1).tile1.node, straigtEdgeCost);
1050  g->AddEdge(e);
1051  if (directed)
1052  {
1053  e = new edge(m->GetTile(x, y-1).tile1.node, m->GetTile(x, y).tile2.node, straigtEdgeCost);
1054  g->AddEdge(e);
1055  }
1056  }
1057  }
1058  }
1059  else if ((m->GetTile(x, y).tile2.node != kNoGraphNode) && (m->GetTile(x, y-1).tile2.node != kNoGraphNode))
1060  {
1061  if ((random()%100) < straightEdgeProb)
1062  {
1063  e = new edge(m->GetTile(x, y).tile2.node, m->GetTile(x, y-1).tile2.node, straigtEdgeCost);
1064  g->AddEdge(e);
1065  if (directed)
1066  {
1067  e = new edge(m->GetTile(x, y-1).tile2.node, m->GetTile(x, y).tile2.node, straigtEdgeCost);
1068  g->AddEdge(e);
1069  }
1070  }
1071  }
1072  }
1073  }
1074  e = 0;
1075  // diagonal UpperLeft edge, always node 1...
1076  // (1) we can cross each of the boundaries between tiles
1077  if ((x >= 1) && (y >= 1) && (m->AdjacentEdges(x, y, kLeftEdge)) && (m->AdjacentEdges(x, y, kTopEdge)) &&
1078  (m->AdjacentEdges(x, y-1, kLeftEdge)) && (m->AdjacentEdges(x-1, y, kTopEdge)) &&
1079  (m->GetTile(x, y).tile1.node != kNoGraphNode))
1080  {
1081  // (2) we can cross the inner tile boundaries
1082  if (((m->AdjacentEdges(x-1, y, kInternalEdge)) || (m->GetSplit(x-1, y) == kBackwardSplit)) &&
1083  ((m->AdjacentEdges(x, y-1, kInternalEdge)) || (m->GetSplit(x, y-1) == kBackwardSplit)) &&
1084  ((m->AdjacentEdges(x-1, y-1, kInternalEdge)) || (m->GetSplit(x-1, y-1) == kForwardSplit)) &&
1085  ((m->AdjacentEdges(x, y, kInternalEdge)) || (m->GetSplit(x, y) == kForwardSplit)))
1086  {
1087  // (3) find what tiles to connect
1088  if (m->AdjacentEdges(x-1, y-1, kInternalEdge))
1089  {
1090  if (m->GetTile(x-1, y-1).tile1.node != kNoGraphNode)
1091  {
1092  if ((random()%100) < diagEdgeProb)
1093  {
1094  e = new edge(m->GetTile(x, y).tile1.node, m->GetTile(x-1, y-1).tile1.node, diagEdgeCost);
1095  g->AddEdge(e);
1096  if (directed)
1097  {
1098  e = new edge(m->GetTile(x-1, y-1).tile1.node, m->GetTile(x, y).tile1.node, diagEdgeCost);
1099  g->AddEdge(e);
1100  }
1101  }
1102  }
1103  }
1104  else if (m->GetTile(x-1, y-1).tile2.node != kNoGraphNode)
1105  {
1106  if ((random()%100) < diagEdgeProb)
1107  {
1108  e = new edge(m->GetTile(x, y).tile1.node, m->GetTile(x-1, y-1).tile2.node, diagEdgeCost);
1109  g->AddEdge(e);
1110  if (directed)
1111  {
1112  e = new edge(m->GetTile(x-1, y-1).tile2.node, m->GetTile(x, y).tile1.node, diagEdgeCost);
1113  g->AddEdge(e);
1114  }
1115  }
1116  }
1117  }
1118  }
1119 
1120  // diagonal UpperRight edge
1121  // (1) we can cross each of the boundaries between tiles
1122  if ((y >= 1) && (x < m->GetMapWidth()-1) && (m->AdjacentEdges(x, y, kRightEdge)) && (m->AdjacentEdges(x, y, kTopEdge)) &&
1123  (m->AdjacentEdges(x, y-1, kRightEdge)) && (m->AdjacentEdges(x+1, y, kTopEdge)) &&
1124  (m->GetTile(x+1, y-1).tile1.node != kNoGraphNode))
1125  {
1126  // (2) we can cross the inner tile boundaries
1127  if (((m->AdjacentEdges(x+1, y, kInternalEdge)) || (m->GetSplit(x+1, y) == kForwardSplit)) &&
1128  ((m->AdjacentEdges(x, y-1, kInternalEdge)) || (m->GetSplit(x, y-1) == kForwardSplit)) &&
1129  ((m->AdjacentEdges(x+1, y-1, kInternalEdge)) || (m->GetSplit(x+1, y-1) == kBackwardSplit)) &&
1130  ((m->AdjacentEdges(x, y, kInternalEdge)) || (m->GetSplit(x, y) == kBackwardSplit)))
1131  {
1132  // (3) connect
1133  if (m->AdjacentEdges(x, y, kInternalEdge))
1134  {
1135  if (m->GetTile(x, y).tile1.node != kNoGraphNode)
1136  {
1137  if ((random()%100) < diagEdgeProb)
1138  {
1139  e = new edge(m->GetTile(x, y).tile1.node, m->GetTile(x+1, y-1).tile1.node, diagEdgeCost);
1140  g->AddEdge(e);
1141  if (directed)
1142  {
1143  e = new edge(m->GetTile(x+1, y-1).tile1.node, m->GetTile(x, y).tile1.node, diagEdgeCost);
1144  g->AddEdge(e);
1145  }
1146  }
1147  }
1148  }
1149  else if (m->GetTile(x, y).tile2.node != kNoGraphNode)
1150  {
1151  if ((random()%100) < diagEdgeProb)
1152  {
1153  e = new edge(m->GetTile(x, y).tile2.node, m->GetTile(x+1, y-1).tile1.node, diagEdgeCost);
1154  g->AddEdge(e);
1155  if (directed)
1156  {
1157  e = new edge(m->GetTile(x+1, y-1).tile1.node, m->GetTile(x, y).tile2.node, diagEdgeCost);
1158  g->AddEdge(e);
1159  }
1160  }
1161  }
1162  }
1163  }
1164  }
1165 }
1166 
1167 GraphMapInconsistentHeuristic::GraphMapInconsistentHeuristic(Map *map, Graph *graph)
1168 :GraphDistanceHeuristic(graph), m(map)
1169 {
1170  displayHeuristic = 0;
1171  compressed = false;
1172  SetMode(kMax);
1173  SetNumUsedHeuristics(1000);
1174 // std::vector<std::vector<double> > values;
1175 // FloydWarshall(graph, values);
1176 // std::vector<int> randomizer;
1177 // randomizer.resize(values.size());
1178 // for (int x = 0; x < values.size(); x++)
1179 // randomizer[x] = x;
1180 // for (int x = values.size(); x > 0; x--)
1181 // {
1182 // int tmp = randomizer[x-1];
1183 // int switcher = random()%x;
1184 // randomizer[x-1] = randomizer[switcher];
1185 // randomizer[switcher] = tmp;
1186 // }
1187 // for (int x = 0; x < values.size(); x++)
1188 // AddHeuristic(values[randomizer[x]], x);
1189 // for (int x = 0; x < HN /*10*/; x++)
1190 // {
1191 // node *n = g->GetRandomNode();
1192 // graphState loc = n->GetNum();
1193 // std::vector<double> values;
1194 // GetOptimalDistances(n, values);
1195 // AddHeuristic(values, loc);
1196 // }
1197 }
1198 
1199 double GraphMapInconsistentHeuristic::HCost(const graphState &state1, const graphState &state2) const
1200 {
1201  long x1 = g->GetNode(state1)->GetLabelL(GraphSearchConstants::kMapX);
1202  long y1 = g->GetNode(state1)->GetLabelL(GraphSearchConstants::kMapY);
1203  long x2 = g->GetNode(state2)->GetLabelL(GraphSearchConstants::kMapX);
1204  long y2 = g->GetNode(state2)->GetLabelL(GraphSearchConstants::kMapY);
1205 
1206  double a = ((x1>x2)?(x1-x2):(x2-x1));
1207  double b = ((y1>y2)?(y1-y2):(y2-y1));
1208  double val = (a>b)?(b*ROOT_TWO+a-b):(a*ROOT_TWO+b-a);
1209 
1210  if (hmode == kIgnore)
1211  return val;
1212 // if (0 != (x1+x2+y1+y2)%16) // TODO: Remove this line
1213 // return val;
1214  //for (unsigned int x = 0; x < heuristics.size(); x++)
1215  if (hmode == kRandom)
1216  {
1217  int x = (x1+x2+y1+y2)%heuristics.size();
1218  for (int y = 0; y < numHeuristics; y++)
1219  {
1220  int offset = heuristics.size()/numHeuristics;
1221  double hval = heuristics[(x+y*offset)%heuristics.size()][state1]-heuristics[(x+y*offset)%heuristics.size()][state2];
1222  if (hval < 0) hval = -hval;
1223  if (fgreater(hval, val))
1224  val = hval;
1225  }
1226  }
1227  else if (hmode == kMax) // hmode == 2, taking the max
1228  {
1229  for (unsigned int i = 0; i < heuristics.size() && i < (unsigned int)numHeuristics; i++)
1230  {
1231  double hval = heuristics[i][state1]-heuristics[i][state2];
1232  if (hval < 0)
1233  hval = -hval;
1234  if (fgreater(hval,val))
1235  val = hval;
1236  }
1237  }
1238  else if (hmode == kGridMax) // hmode == 3, return max at grid points, otherwise 0
1239  {
1240  if ( (x1+x2) % 4 == 0 && (y1+y2) % 4 == 0)
1241  {
1242  for (unsigned int i=0;i<heuristics.size();i++)
1243  {
1244  double hval = heuristics[i][state1]-heuristics[i][state2];
1245  if (hval < 0)
1246  hval = -hval;
1247  if (fgreater(hval,val))
1248  val = hval;
1249  }
1250  }
1251  else
1252  val = 0;
1253  }
1254  else if (hmode == kCompressed)
1255  {
1256  // at each state we can only look up the heuristic graphstate%H where H is the # of heuristics
1257  static std::vector<double> vals;
1258  static std::vector<double> errors;
1259  static graphState lastGoal = -1;
1260 
1261  if (lastGoal != state2)
1262  {
1263  FillInCache(vals, errors, state2);
1264  lastGoal = state2;
1265  }
1266 
1267  if (compressed)
1268  {
1269  for (unsigned int x = 0; x < heuristics.size(); x++)
1270  {
1271  double hval = vals[x*numHeuristics+state1%numHeuristics]-heuristics[x][state1];
1272  if (hval < 0)
1273  hval = -hval;
1274  hval -= errors[x*numHeuristics+state1%numHeuristics];
1275  if (fgreater(hval,val))
1276  val = hval;
1277  }
1278  }
1279  else {
1280  for (unsigned int x = (state1%numHeuristics); x < heuristics.size(); x+=numHeuristics)
1281  {
1282  double hval = vals[x]-heuristics[x][state1];
1283  if (hval < 0)
1284  hval = -hval;
1285  hval -= errors[x];
1286  if (fgreater(hval,val))
1287  val = hval;
1288  }
1289  }
1290  }
1291 
1292  return val;
1293 }
1294 
1295 // this *should* be correct except for the division at the end
1296 void GraphMapInconsistentHeuristic::Compress()
1297 {
1298  hmode = kCompressed;
1299  compressed = true;
1300 
1301  for (unsigned int state1 = 0; state1 < heuristics[0].size(); state1++)
1302  {
1303  for (unsigned int x = (state1%numHeuristics), y = 0; x < heuristics.size(); x+=numHeuristics, y++)
1304  {
1305  heuristics[y][state1] = heuristics[x][state1];
1306  }
1307  }
1308  assert((heuristics.size()%numHeuristics) == 0);
1309  heuristics.resize(heuristics.size()/numHeuristics);
1310 }
1311 
1312 void GraphMapInconsistentHeuristic::FillInCache(std::vector<double> &vals,
1313  std::vector<double> &errors,
1314  graphState state2) const
1315 {
1316  int unused;
1317  if (numHeuristics == 0)
1318  {
1319  assert(!"No heuristics being used");
1320  // Note: This would fix it, but breaks const correctness
1321  // This is old code, so need to re-analyze if we use again
1322  //numHeuristics = heuristics.size();
1323  }
1324  if (!compressed)
1325  {
1326  unused = heuristics.size(); // set these values to the uncompressed size
1327  vals.resize(heuristics.size());
1328  errors.resize(heuristics.size());
1329  }
1330  else {
1331  unused = numHeuristics*heuristics.size();
1332  vals.resize(unused);
1333  errors.resize(unused);
1334  }
1335  for (unsigned int x = 0; x < vals.size(); x++)
1336  vals[x] = errors[x] = -1;
1337 
1338  node *next = g->GetNode(state2);
1339  next->SetLabelF(kTemporaryLabel, 0.0);
1340  next->SetKeyLabel(kTemporaryLabel);
1341  Heap h;
1342  h.Add(next);
1343 
1344  if (!compressed)
1345  {
1346  for (unsigned int x = (state2%numHeuristics); x < heuristics.size(); x+=numHeuristics)
1347  {
1348  vals[x] = heuristics[x][state2];
1349  errors[x] = 0;
1350  unused--;
1351  }
1352  }
1353  else {
1354  for (unsigned int x = 0; x < heuristics.size(); x++)
1355  {
1356  vals[x*numHeuristics+state2%numHeuristics] = heuristics[x][state2];
1357  errors[x*numHeuristics+state2%numHeuristics] = 0;
1358  unused--;
1359  }
1360  }
1361 
1362  while ((unused > 0) && (!h.Empty()))
1363  {
1364  next = (node*)h.Remove();
1365 
1366  double cost = next->GetLabelF(kTemporaryLabel);
1367  neighbor_iterator ni = next->getNeighborIter();
1368  for (long tmp = next->nodeNeighborNext(ni); tmp != -1; tmp = next->nodeNeighborNext(ni))
1369  {
1370  double edgeCost = g->FindEdge(next->GetNum(), tmp)->GetWeight();
1371 
1372  if (compressed)
1373  {
1374  for (unsigned int x = 0; x < heuristics.size(); x++)
1375  {
1376  if (vals[x*numHeuristics+tmp%numHeuristics] == -1)
1377  {
1378  unused--;
1379  vals[x*numHeuristics+tmp%numHeuristics] = heuristics[x][tmp];
1380  errors[x*numHeuristics+tmp%numHeuristics] = cost+edgeCost;
1381  }
1382  }
1383  }
1384  else {
1385  for (unsigned int x = (tmp%numHeuristics); x < heuristics.size(); x+=numHeuristics)
1386  {
1387  if (vals[x] == -1)
1388  {
1389  unused--;
1390  vals[x] = heuristics[x][tmp];
1391  errors[x] = cost+edgeCost;
1392  }
1393  }
1394  }
1395 
1396  node *nb = g->GetNode(tmp);
1397  if (h.IsIn(nb))
1398  {
1399  if (fgreater(nb->GetLabelF(kTemporaryLabel), cost+edgeCost))
1400  {
1401  nb->SetLabelF(kTemporaryLabel, cost+edgeCost);
1402  h.DecreaseKey(nb);
1403  }
1404  }
1405  else {
1406  nb->SetKeyLabel(kTemporaryLabel);
1407  nb->SetLabelF(kTemporaryLabel, cost+edgeCost);
1408  h.Add(nb);
1409  }
1410  }
1411  }
1412 }
1413 
1414 void GraphMapInconsistentHeuristic::OpenGLDraw() const
1415 {
1416  //static int counter = 50;
1417  //counter = (counter+1);
1418  if (heuristics.size() == 0)
1419  {
1420  printf("No heuristics\n");
1421  return;
1422  }
1423 
1424 // long x1 = g->GetNode(state1)->GetLabelL(GraphSearchConstants::kMapX);
1425 // long y1 = g->GetNode(state1)->GetLabelL(GraphSearchConstants::kMapY);
1426 // long x2 = g->GetNode(state2)->GetLabelL(GraphSearchConstants::kMapX);
1427 // long y2 = g->GetNode(state2)->GetLabelL(GraphSearchConstants::kMapY);
1428 
1429  GraphEnvironment ge(m, g, 0);
1430 
1431  double max = 0;
1432  for (unsigned int a = 0; a < heuristics.back().size(); a++)
1433  {
1434  if (heuristics.back()[a] > max)
1435  max = heuristics.back()[a];
1436  }
1437 
1438  for (unsigned int a = 0; a < heuristics.back().size(); a++)
1439  {
1440 // GLdouble x, y, z;
1441  if ((hmode == kCompressed) &&
1442  ((a%heuristics.size() != displayHeuristic) || (heuristics.size() == displayHeuristic)))
1443  continue;
1444  node *n = g->GetNode(a);
1445 
1446  if (n)
1447  {
1448  if (heuristics.size() == displayHeuristic)
1449  {
1450  ge.SetColor(heuristics[a%heuristics.size()][a]/max, 0, 1-heuristics[a%heuristics.size()][a]/max, 1);
1451  ge.OpenGLDraw(a);
1452  }
1453  else {
1454  if (heuristics[displayHeuristic][a] != 0)
1455  {
1456  ge.SetColor(heuristics[displayHeuristic][a]/max, 0, 1-heuristics[displayHeuristic][a]/max, 1);
1457  ge.OpenGLDraw(a);
1458  }
1459  else {
1460  ge.SetColor(1, 1, 1, 1);
1461  ge.OpenGLDraw(a);
1462  }
1463  }
1464 // x = n->GetLabelF(GraphSearchConstants::kXCoordinate);
1465 // y = n->GetLabelF(GraphSearchConstants::kYCoordinate);
1466 // z = n->GetLabelF(GraphSearchConstants::kZCoordinate);
1467 //
1468 // glColor3f(0.0, sizes[a]/maxSize, 0.0);
1469 // if (dist[a] == 0)
1470 // glColor3f(1, 1, 1);
1471 // DrawSphere(x, y, z, approxSize);
1472  }
1473  }
1474 }
1475 
1476 
1477 void GraphDistanceHeuristic::OpenGLDraw() const
1478 {
1479  //static int counter = 50;
1480  //counter = (counter+1);
1481  if (heuristics.size() == 0)
1482  return;
1483 
1484  double approxSize = 2.0/sqrt(g->GetNumNodes());
1485  for (unsigned int a = 0; a < locations.size(); a++)
1486  {
1487  GLdouble x, y, z;
1488  node *n = g->GetNode(locations[a]);
1489  x = n->GetLabelF(GraphSearchConstants::kXCoordinate);
1490  y = n->GetLabelF(GraphSearchConstants::kYCoordinate);
1491  z = n->GetLabelF(GraphSearchConstants::kZCoordinate);
1492 
1493  rgbColor r(1.0, 1.0, 1.0);//GetColor((counter+locations[a])%100, 0, 100, 4);
1494 
1495  glColor3f(0.0, 0.0, 1.0);
1496  DrawSphere(x, y, z, approxSize);
1497  }
1498  double maxWeight = 0;
1499  for (unsigned int a = 0; a < weight.size(); a++)
1500  if (weight[a] > maxWeight)
1501  maxWeight = weight[a];
1502 
1503  double maxSize = 0;
1504  for (unsigned int a = 0; a < sizes.size(); a++)
1505  if (sizes[a] > maxSize)
1506  maxSize = sizes[a];
1507 
1508  for (unsigned int a = 0; a < weight.size(); a++)
1509  {
1510  GLdouble x, y, z;
1511  node *n = g->GetNode(a);
1512  if (n)
1513  {
1514  x = n->GetLabelF(GraphSearchConstants::kXCoordinate);
1515  y = n->GetLabelF(GraphSearchConstants::kYCoordinate);
1516  z = n->GetLabelF(GraphSearchConstants::kZCoordinate);
1517 
1518  glColor3f(0.0, sizes[a]/maxSize, 0.0);
1519  if (dist[a] == 0)
1520  glColor3f(1, 1, 1);
1521  DrawSphere(x, y, z, approxSize);
1522  }
1523  }
1524 }
1525 
1526 double GraphDistanceHeuristic::HCost(const graphState &state1, const graphState &state2) const
1527 {
1528  double val = 0;
1529  for (unsigned int i = 0; i < heuristics.size(); i++)
1530  {
1531  double hval = heuristics[i][state1]-heuristics[i][state2];
1532  if (hval < 0)
1533  hval = -hval;
1534  if (fgreater(hval,val))
1535  val = hval;
1536  }
1537  return val;
1538 }
1539 
1540 void GraphDistanceHeuristic::ChooseStartGoal(graphState &start, graphState &goal)
1541 {
1542  if (heuristics.size() == 0)
1543  return;
1544  double minStart=-1, minGoal=-1;
1545 
1546  minStart = heuristics[0][start];
1547  minGoal = heuristics[0][goal];
1548  for (unsigned int x = 1; x < heuristics.size(); x++)
1549  {
1550  if (heuristics[x][start] < minStart)
1551  minStart = heuristics[x][start];
1552  if (heuristics[x][goal] < minGoal)
1553  minGoal = heuristics[x][goal];
1554  }
1555  if (minStart < minGoal)
1556  {
1557  graphState tmp;
1558  tmp = start;
1559  start = goal;
1560  goal = tmp;
1561  }
1562 }
1563 
1564 void GraphDistanceHeuristic::AddHeuristic(node *n)
1565 {
1566  if (placement == kFarPlacement)
1567  n = FindFarNode(n);
1568  else if (placement == kAvoidPlacement)
1569  n = FindAvoidNode(n);
1570  else if (n == 0)
1571  n = g->GetRandomNode();
1572 
1573  std::vector<double> values;
1574 // std::cout << "Adding differential heuristic based at " << n->GetLabelL(kMapX) << ", " << n->GetLabelL(kMapY) << std::endl;
1575  GetOptimalDistances(n, values);
1576  AddHeuristic(values, n->GetNum());
1577 }
1578 
1579 void GraphDistanceHeuristic::AddHeuristic(std::vector<double> &values, graphState location)
1580 {
1581  heuristics.push_back(values);
1582  locations.push_back(location);
1583 }
1584 
1585 
1586 
1587 void GraphDistanceHeuristic::GetOptimalDistances(node *n, std::vector<double> &values)
1588 {
1589  values.resize(g->GetNumNodes());
1590  for (unsigned int x = 0; x < values.size(); x++)
1591  values[x] = -1.0;
1592  n->SetLabelF(kTemporaryLabel, 0.0);
1593  n->SetKeyLabel(kTemporaryLabel);
1594  Heap h;
1595  h.Add(n);
1596  while (!h.Empty())
1597  {
1598  node *next = (node*)h.Remove();
1599 // printf("Heap size %d, working on node %d cost %f\n", h.size(), next->GetNum(),
1600 // next->GetLabelF(kTemporaryLabel));
1601  double cost = next->GetLabelF(kTemporaryLabel);
1602  values[next->GetNum()] = next->GetLabelF(kTemporaryLabel);
1603  neighbor_iterator ni = next->getNeighborIter();
1604  for (long tmp = next->nodeNeighborNext(ni); tmp != -1; tmp = next->nodeNeighborNext(ni))
1605  {
1606  if (values[tmp] == -1)
1607  {
1608  node *nb = g->GetNode(tmp);
1609  if (h.IsIn(nb))
1610  {
1611  if (fgreater(nb->GetLabelF(kTemporaryLabel),
1612  cost + g->FindEdge(next->GetNum(), tmp)->GetWeight()))
1613  {
1614  nb->SetLabelF(kTemporaryLabel,
1615  cost+g->FindEdge(next->GetNum(), tmp)->GetWeight());
1616  h.DecreaseKey(nb);
1617  }
1618  }
1619  else {
1620  nb->SetKeyLabel(kTemporaryLabel);
1621  nb->SetLabelF(kTemporaryLabel,
1622  cost+g->FindEdge(next->GetNum(), tmp)->GetWeight());
1623  h.Add(nb);
1624  }
1625  }
1626  }
1627  }
1628 }
1629 
1630 node *GraphDistanceHeuristic::FindAvoidNode(node *n)
1631 {
1632  if (locations.size() == 0)
1633  return FindFarNode(0);
1634  n = g->GetRandomNode();
1635  // 1. Select vertex r
1636  if (n == 0)
1637  {
1638  int bestSum = MAXINT;
1639  int bestId = 0;
1640  for (unsigned int x = 0; x < heuristics[0].size(); x+=1)
1641  //for (unsigned int x = 0; x < 5; x++)
1642  {
1643  if (heuristics[0][x] == -1)
1644  continue;
1645  int sum = 0;
1646  for (unsigned int y = 0; y < heuristics.size(); y++)
1647  sum += heuristics[y][x];
1648  int diff = 0;
1649  sum /= heuristics.size();
1650  for (unsigned int y = 0; y < heuristics.size(); y++)
1651  diff = max(diff, fabs(sum-heuristics[y][x]));
1652  if (diff < bestSum)
1653  {
1654  bestId = x;
1655  bestSum = diff;
1656  }
1657  }
1658  n = g->GetNode(bestId);
1659 // n = g->GetRandomNode(); // could be done better
1660 // while (heuristics[0][n->GetNum()] < 1)
1661 // n = g->GetRandomNode();
1662  }
1663 // std::vector<double> dist;
1664 // std::vector<double> weight;
1665 // std::vector<double> sizes;
1666  //printf("Starting from %d\n", n->GetNum());
1667 
1668  // 2. build shortest path tree
1669  GetOptimalDistances(n, dist);
1670  weight.resize(dist.size());
1671  sizes.resize(dist.size());
1672  // 3. calculate difference between heuristic and actual distance for each node
1673  for (unsigned int x = 0; x < dist.size(); x++)
1674  {
1675  sizes[x] = -1;
1676  if (dist[x] != -1)
1677  {
1678  weight[x] = fabs(dist[x]-HCost(n->GetNum(), x));
1679  }
1680  else {
1681  weight[x] = -1;
1682  }
1683  }
1684  // 4. compute the size of each node (the sum of weights (#3) in the subtree if no existing landmark)
1685  ComputeSizes(n, dist, weight, sizes);
1686  // 5. select node, w, with highest weight
1687  int best = 0;
1688  for (unsigned int x = 1; x < sizes.size(); x++)
1689  if (fless(sizes[best], sizes[x]))
1690  best = x;
1691  // 6. follow the children of w by largest weight until a leaf is reached & return
1692  return FindBestChild(best, dist, sizes);
1693 }
1694 
1695 void GraphDistanceHeuristic::ComputeSizes(node *n, std::vector<double> &dist,
1696  std::vector<double> &weight, std::vector<double> &sizes)
1697 {
1698  neighbor_iterator ni = n->getNeighborIter();
1699  int nodeSize = -1;
1700  for (long tmp = n->nodeNeighborNext(ni); tmp != -1; tmp = n->nodeNeighborNext(ni))
1701  {
1702  node *nb = g->GetNode(tmp);
1703  if (sizes[nb->GetNum()] == -1) // not yet computed
1704  {
1705  // on shortest path
1706  if (fequal(dist[nb->GetNum()] - dist[n->GetNum()], g->FindEdge(n->GetNum(), nb->GetNum())->GetWeight()))
1707  {
1708  //printf("%d has successor %d\n", n->GetNum(), nb->GetNum());
1709  ComputeSizes(nb, dist, weight, sizes);
1710  if (sizes[nb->GetNum()] == 0)
1711  {
1712  nodeSize = 0;
1713  }
1714  else if (nodeSize == -1)
1715  {
1716  nodeSize = sizes[nb->GetNum()];
1717  }
1718  else if (nodeSize != 0) {
1719  nodeSize += sizes[nb->GetNum()];
1720  }
1721  }
1722  }
1723  }
1724 
1725  if (nodeSize == -1)
1726  {
1727  sizes[n->GetNum()] = weight[n->GetNum()];
1728  }
1729  else if (nodeSize != 0) {
1730  sizes[n->GetNum()] = nodeSize+weight[n->GetNum()];
1731  }
1732  else {
1733  sizes[n->GetNum()] = 0;
1734  }
1735 
1736  for (unsigned int x = 0; x < locations.size(); x++)
1737  if (locations[x] == n->GetNum())
1738  sizes[n->GetNum()] = 0;
1739 
1740  //printf("size at %d is %1.1f\n", n->GetNum(), sizes[n->GetNum()]);
1741 }
1742 
1743 node *GraphDistanceHeuristic::FindBestChild(int best, std::vector<double> &dist,
1744  std::vector<double> &sizes)
1745 {
1746  int nextChild = best;
1747  int nextSize = 0;
1748  node *n;
1749  do {
1750 // printf("Child %d has size %1.1f\n", nextChild, nextSize);
1751  n = g->GetNode(nextChild);
1752  nextChild = -1;
1753  nextSize = 0;
1754  neighbor_iterator ni = n->getNeighborIter();
1755  for (long tmp = n->nodeNeighborNext(ni); tmp != -1; tmp = n->nodeNeighborNext(ni))
1756  {
1757  node *nb = g->GetNode(tmp);
1758  // on shortest path
1759  if (fequal(dist[nb->GetNum()] - dist[n->GetNum()], g->FindEdge(n->GetNum(), nb->GetNum())->GetWeight()))
1760  {
1761  if (nextChild == -1)
1762  {
1763  //printf("Next Child %d has size %1.1f\n", nb->GetNum(), sizes[nb->GetNum()]);
1764  nextSize = sizes[nb->GetNum()];
1765  nextChild = nb->GetNum();
1766  }
1767  else if ((fless(nextSize, sizes[nb->GetNum()])))
1768  {
1769  //printf("Next Child %d has size %1.1f\n", nb->GetNum(), sizes[nb->GetNum()]);
1770  nextSize = sizes[nb->GetNum()];
1771  nextChild = nb->GetNum();
1772  }
1773  }
1774  }
1775  } while (nextChild != -1);
1776  return n;
1777 }
1778 node *GraphDistanceHeuristic::FindFarNode(node *n)
1779 {
1780  std::vector<double> values;
1781  values.resize(g->GetNumNodes());
1782  for (unsigned int x = 0; x < values.size(); x++)
1783  values[x] = -1;
1784 
1785  Heap h;
1786  for (unsigned int x = 0; x < locations.size(); x++)
1787  {
1788  n = g->GetNode(locations[x]);
1789  n->SetLabelF(kTemporaryLabel, 0.0);
1790  n->SetKeyLabel(kTemporaryLabel);
1791  h.Add(n);
1792  }
1793  if ((locations.size() == 0) && n)
1794  {
1795  n->SetLabelF(kTemporaryLabel, 0.0);
1796  n->SetKeyLabel(kTemporaryLabel);
1797  h.Add(n);
1798  }
1799  else if (n == 0) { // cheap way of finding largest region with high liklihood
1800  for (int x = 0; x < 10; x++)
1801  {
1802  n = g->GetNode(x*g->GetNumNodes()/10);
1803  n->SetLabelF(kTemporaryLabel, 0.0);
1804  n->SetKeyLabel(kTemporaryLabel);
1805  h.Add(n);
1806  }
1807  }
1808 
1809  while (!h.Empty())
1810  {
1811  node *next = (node*)h.Remove();
1812  // printf("Heap size %d, working on node %d cost %f\n", h.size(), next->GetNum(),
1813  // next->GetLabelF(kTemporaryLabel));
1814  double cost = next->GetLabelF(kTemporaryLabel);
1815  values[next->GetNum()] = next->GetLabelF(kTemporaryLabel);
1816  neighbor_iterator ni = next->getNeighborIter();
1817  for (long tmp = next->nodeNeighborNext(ni); tmp != -1; tmp = next->nodeNeighborNext(ni))
1818  {
1819  if (values[tmp] == -1)
1820  {
1821  node *nb = g->GetNode(tmp);
1822  if (h.IsIn(nb))
1823  {
1824  if (fgreater(nb->GetLabelF(kTemporaryLabel),
1825  cost + g->FindEdge(next->GetNum(), tmp)->GetWeight()))
1826  {
1827  nb->SetLabelF(kTemporaryLabel,
1828  cost+g->FindEdge(next->GetNum(), tmp)->GetWeight());
1829  h.DecreaseKey(nb);
1830  }
1831  }
1832  else {
1833  nb->SetKeyLabel(kTemporaryLabel);
1834  nb->SetLabelF(kTemporaryLabel,
1835  cost+g->FindEdge(next->GetNum(), tmp)->GetWeight());
1836  h.Add(nb);
1837  }
1838  }
1839  }
1840  if (h.Empty())
1841  {
1842 // printf("Selecting node at (%ld, %ld)\n", next->GetLabelL(GraphSearchConstants::kMapX),
1843 // next->GetLabelL(GraphSearchConstants::kMapY));
1844  return next;
1845  }
1846  }
1847  return 0;
1848 }
1849 
1850 
1851 //GraphMapInconsistentHeuristic::GraphMapInconsistentHeuristic(Map *map, Graph *graph)
1852 //:m(map), g(graph)
1853 //{
1854 // for (int x = 0; x < HN /*10*/; x++)
1855 // {
1856 // node *n = g->GetRandomNode();
1857 // graphState loc = n->GetNum();
1858 // std::vector<double> values;
1859 // GetOptimalDistances(n, values);
1860 // AddHeuristic(values, loc);
1861 // }
1862 //}
1863 //
1864 //double GraphMapInconsistentHeuristic::HCost(graphState &state1, graphState &state2)
1865 //{
1866 // int x1 = g->GetNode(state1)->GetLabelL(GraphSearchConstants::kMapX);
1867 // int y1 = g->GetNode(state1)->GetLabelL(GraphSearchConstants::kMapY);
1868 // int x2 = g->GetNode(state2)->GetLabelL(GraphSearchConstants::kMapX);
1869 // int y2 = g->GetNode(state2)->GetLabelL(GraphSearchConstants::kMapY);
1870 //
1871 // double a = ((x1>x2)?(x1-x2):(x2-x1));
1872 // double b = ((y1>y2)?(y1-y2):(y2-y1));
1873 // double val = (a>b)?(b*ROOT_TWO+a-b):(a*ROOT_TWO+b-a);
1874 //
1875 // if (hmode == 0)
1876 // return val;
1877 //
1878 // //for (unsigned int x = 0; x < heuristics.size(); x++)
1879 // if (hmode == 1) {
1880 // int x = (x1+x2+y1+y2)%heuristics.size();
1881 // {
1882 // double hval = heuristics[x][state1]-heuristics[x][state2];
1883 // if (hval < 0) hval = -hval;
1884 // if (fgreater(hval, val))
1885 // val = hval;
1886 // }
1887 // }
1888 // else if (hmode == 2) { // hmode == 2, taking the max
1889 // for (unsigned int i=0;i<heuristics.size();i++) {
1890 // double hval = heuristics[i][state1]-heuristics[i][state2];
1891 // if (hval < 0)
1892 // hval = -hval;
1893 // if (fgreater(hval,val))
1894 // val = hval;
1895 // }
1896 // }
1897 // else { // hmode == 3, return max at grid points, otherwise 0
1898 // if ( (x1+x2) % 4 == 0 && (y1+y2) % 4 == 0) {
1899 // for (unsigned int i=0;i<heuristics.size();i++) {
1900 // double hval = heuristics[i][state1]-heuristics[i][state2];
1901 // if (hval < 0)
1902 // hval = -hval;
1903 // if (fgreater(hval,val))
1904 // val = hval;
1905 // }
1906 // }
1907 // else
1908 // val = 0;
1909 // }
1910 //
1911 // return val;
1912 //}
1913 //
1914 //void GraphMapInconsistentHeuristic::AddHeuristic(std::vector<double> &values,
1915 // graphState location)
1916 //{
1917 // heuristics.push_back(values);
1918 // locations.push_back(location);
1919 //}
1920 //
1921 //
1922 //void GraphMapInconsistentHeuristic::GetOptimalDistances(node *n, std::vector<double> &values)
1923 //{
1924 // values.resize(g->GetNumNodes());
1925 // for (unsigned int x = 0; x < values.size(); x++)
1926 // values[x] = -1.0;
1927 // n->SetLabelF(kTemporaryLabel, 0.0);
1928 // n->SetKeyLabel(kTemporaryLabel);
1929 // Heap h;
1930 // h.Add(n);
1931 // while (!h.Empty())
1932 // {
1933 // node *next = (node*)h.Remove();
1936 // double cost = next->GetLabelF(kTemporaryLabel);
1937 // values[next->GetNum()] = next->GetLabelF(kTemporaryLabel);
1938 // neighbor_iterator ni = next->getNeighborIter();
1939 // for (long tmp = next->nodeNeighborNext(ni); tmp != -1; tmp = next->nodeNeighborNext(ni))
1940 // {
1941 // if (values[tmp] == -1)
1942 // {
1943 // node *nb = g->GetNode(tmp);
1944 // if (h.IsIn(nb))
1945 // {
1946 // if (fgreater(nb->GetLabelF(kTemporaryLabel),
1947 // cost + g->FindEdge(next->GetNum(), tmp)->GetWeight()))
1948 // {
1949 // nb->SetLabelF(kTemporaryLabel,
1950 // cost+g->FindEdge(next->GetNum(), tmp)->GetWeight());
1951 // h.DecreaseKey(nb);
1952 // }
1953 // }
1954 // else {
1955 // nb->SetKeyLabel(kTemporaryLabel);
1956 // nb->SetLabelF(kTemporaryLabel,
1957 // cost+g->FindEdge(next->GetNum(), tmp)->GetWeight());
1958 // h.Add(nb);
1959 // }
1960 // }
1961 // }
1962 // }
1963 //}
1964 
1965 
1966 /*
1967 AbstractionGraphEnvironment::AbstractionGraphEnvironment( GraphAbstraction *_gabs, unsigned int level, GraphHeuristic *gh ):
1968  GraphEnvironment( _gabs->GetAbstractGraph(level), gh ), gabs(_gabs)
1969 {
1970  // compute graph scale
1971  node_iterator ni = g->getNodeIter();
1972  node *n;
1973  double min_x = DBL_MAX, max_x = DBL_MIN;
1974  double min_y = DBL_MAX, max_y = DBL_MIN;
1975  double min_z = DBL_MAX, max_z = DBL_MIN;
1976  n = g->nodeIterNext( ni );
1977  while( n != NULL ) {
1978  double x = n->GetLabelF(GraphAbstractionConstants::kXCoordinate);
1979  double y = n->GetLabelF(GraphAbstractionConstants::kYCoordinate);
1980  double z = n->GetLabelF(GraphAbstractionConstants::kZCoordinate);
1981  if ( x < min_x ) min_x = x;
1982  if ( x > max_x ) max_x = x;
1983  if ( y < min_y ) min_y = y;
1984  if ( y > max_y ) max_y = y;
1985  if ( z < min_z ) min_z = z;
1986  if ( z > max_z ) max_z = z;
1987  n = g->nodeIterNext( ni );
1988  }
1989  graphscale = 0.;
1990  int count = 0;
1991  if ( fgreater(max_x, min_x) ) { graphscale += max_x-min_x; count++; }
1992  if ( fgreater(max_y, min_y) ) { graphscale += max_y-min_y; count++; }
1993  if ( fgreater(max_z, min_z) ) { graphscale += max_z-min_z; count++; }
1994  // average over all the dimensions and divide by root(nodecount,dimensions)
1995  graphscale /= count * pow( (double)g->GetNumNodes(), 1./(double)count );
1996 };
1997 
1998 AbstractionGraphEnvironment::~AbstractionGraphEnvironment() {
1999  //~GraphEnvironment();
2000 };
2001 
2002 void AbstractionGraphEnvironment::OpenGLDraw() const {
2003  if ((g == 0) || (g->GetNumNodes() == 0)) return;
2004 
2005  glBegin(GL_LINES);
2006 
2007  edge_iterator ei = g->getEdgeIter();
2008  for (edge *e = g->edgeIterNext(ei); e; e = g->edgeIterNext(ei))
2009  {
2010  //int x, y;
2011  //double offsetx, offsety;
2012  node *n;
2013  n = g->GetNode(e->getFrom());
2014 
2015  glColor3f( 0,0,0 );
2016  //glColor3f(1, 0, 0);
2017  //if (e->getMarked())
2018  // glColor3f(1, 1, 1);
2019 
2020  GLdouble x, y, z;
2021  x = n->GetLabelF(GraphAbstractionConstants::kXCoordinate);
2022  y = n->GetLabelF(GraphAbstractionConstants::kYCoordinate);
2023  z = n->GetLabelF(GraphAbstractionConstants::kZCoordinate);
2024  glVertex3f(x, y, z);
2025 
2026  n = g->GetNode(e->getTo());
2027  x = n->GetLabelF(GraphAbstractionConstants::kXCoordinate);
2028  y = n->GetLabelF(GraphAbstractionConstants::kYCoordinate);
2029  z = n->GetLabelF(GraphAbstractionConstants::kZCoordinate);
2030 
2031  glVertex3f(x, y, z);
2032  }
2033  glEnd();
2034 };
2035 
2036 */
Graphics::Display::DrawLine
void DrawLine(point start, point end, float lineWidth, rgbColor c)
Definition: Graphics.cpp:184
Graph::AddNode
int AddNode(node *)
Definition: Graph.cpp:136
Graphics::point
Definition: Graphics.h:32
node::SetLabelL
void SetLabelL(unsigned int index, long val) const
Definition: Graph.cpp:702
edge::GetWeight
double GetWeight()
Definition: Graph.h:140
kMax
@ kMax
Definition: GraphEnvironment.h:258
kFarPlacement
@ kFarPlacement
Definition: GraphEnvironment.h:217
OutlineRect
void OutlineRect(GLdouble left, GLdouble top, GLdouble right, GLdouble bottom, double zz)
Definition: GLUtil.cpp:384
GraphMapInconsistentHeuristic::SetMode
void SetMode(tHeuristicCombination mode)
Definition: GraphEnvironment.h:268
GraphDistanceHeuristic::AddHeuristic
void AddHeuristic(node *n=0)
Definition: GraphEnvironment.cpp:1564
GraphEnvironment::nodeScale
double nodeScale
Definition: GraphEnvironment.h:365
GraphEnvironment::GetLocation
Graphics::point GetLocation(const graphState &s) const
Definition: GraphEnvironment.cpp:826
DrawSquare
void DrawSquare(GLdouble xx, GLdouble yy, GLdouble zz, GLdouble rad)
Definition: GLUtil.cpp:396
node::SetLabelF
void SetLabelF(unsigned int index, double val) const
Definition: Graph.cpp:687
GraphDistanceHeuristic::heuristics
std::vector< std::vector< double > > heuristics
Definition: GraphEnvironment.h:245
graphMove
Definition: GraphEnvironment.h:34
GraphEnvironment::OpenGLDraw
virtual void OpenGLDraw() const
Definition: GraphEnvironment.cpp:206
kRightEdge
@ kRightEdge
Definition: Map.h:83
rgbColor::b
float b
Definition: Colors.h:71
rgbColor
A color; r/g/b are between 0...1.
Definition: Colors.h:17
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
min
double min(double a, double b)
Definition: FPUtil.h:35
Map::OpenGLDraw
void OpenGLDraw(tDisplay how=kPolygons) const
Does actual OpenGL drawing of the map.
Definition: Map.cpp:1777
node::getOutgoingEdgeIter
edge_iterator getOutgoingEdgeIter() const
Definition: Graph.cpp:733
graphState
unsigned long graphState
Definition: GraphEnvironment.h:32
GraphSearchConstants::AddNodesToGraph
void AddNodesToGraph(Map *m, Graph *g)
Definition: GraphEnvironment.cpp:884
GraphSearchConstants
Definition: GraphEnvironment.cpp:838
terrainBits
const int terrainBits
Definition: Map.h:49
GraphDistanceHeuristic::dist
std::vector< double > dist
Definition: GraphEnvironment.h:249
Heap.h
kOutOfBounds
@ kOutOfBounds
Definition: Map.h:52
GraphSearchConstants::GetEightConnectedGraph
Graph * GetEightConnectedGraph(Map *m, bool directed)
Definition: GraphEnvironment.cpp:854
GraphEnvironment::m
Map * m
Definition: GraphEnvironment.h:359
GraphDistanceHeuristic::sizes
std::vector< double > sizes
Definition: GraphEnvironment.h:251
GraphDistanceHeuristic::ComputeSizes
void ComputeSizes(node *n, std::vector< double > &dist, std::vector< double > &weight, std::vector< double > &sizes)
Definition: GraphEnvironment.cpp:1695
GraphDistanceHeuristic::g
Graph * g
Definition: GraphEnvironment.h:244
SVGDrawText
std::string SVGDrawText(float x1, float y1, const char *txt, rgbColor c, double size, const char *typeface, SVG::svgAlignment align, SVG::svgBaseline base)
Definition: SVGUtil.cpp:227
graphMove::from
uint32_t from
Definition: GraphEnvironment.h:38
Graph::AddEdge
void AddEdge(edge *)
Definition: Graph.cpp:170
GraphDistanceHeuristic
Definition: GraphEnvironment.h:222
Graphics::rect
Definition: Graphics.h:94
kGridMax
@ kGridMax
Definition: GraphEnvironment.h:259
GraphEnvironment::GetSuccessors
virtual void GetSuccessors(const graphState &stateID, std::vector< graphState > &neighbors) const
Definition: GraphEnvironment.cpp:75
edge_iterator
std::vector< edge * >::const_iterator edge_iterator
Definition: Graph.h:30
DrawSphere
void DrawSphere(GLdouble _x, GLdouble _y, GLdouble _z, GLdouble tRadius)
Definition: GLUtil.cpp:433
GraphEnvironment::~GraphEnvironment
virtual ~GraphEnvironment()
Definition: GraphEnvironment.cpp:52
node::edgeIterNextOutgoing
edge * edgeIterNextOutgoing(edge_iterator &) const
Definition: Graph.cpp:738
width
int width
Definition: SFML_HOG.cpp:54
GraphMapInconsistentHeuristic::hmode
tHeuristicCombination hmode
Definition: GraphEnvironment.h:284
Map::GetTile
Tile & GetTile(long x, long y)
Return the tile at location x, y.
Definition: Map.cpp:994
GraphMapInconsistentHeuristic::GraphMapInconsistentHeuristic
GraphMapInconsistentHeuristic(Map *map, Graph *graph)
Definition: GraphEnvironment.cpp:1167
GraphSearchConstants::kMapY
@ kMapY
Definition: GraphEnvironment.h:56
Tile::tile1
halfTile tile1
Definition: Map.h:116
GraphMapInconsistentHeuristic::SetNumUsedHeuristics
void SetNumUsedHeuristics(int count)
Definition: GraphEnvironment.h:271
rgbColor::g
float g
Definition: Colors.h:71
GraphSearchConstants::kXCoordinate
@ kXCoordinate
Definition: GraphEnvironment.h:51
Heap::DecreaseKey
void DecreaseKey(graph_object *val)
Indicate that the key for a particular object has decreased.
Definition: Heap.cpp:47
SVGDrawCircle
std::string SVGDrawCircle(double x, double y, double radius, rgbColor c)
Definition: SVGUtil.cpp:60
Graph
A generic Graph class.
Definition: Graph.h:66
GraphEnvironment::DrawLERP
void DrawLERP(Graphics::Display &disp, Graph *a, Graph *b, float mix) const
Definition: GraphEnvironment.cpp:559
Graph::GetNode
node * GetNode(unsigned long num)
Definition: Graph.cpp:152
GraphEnvironment::GoalTest
virtual bool GoalTest(const graphState &state, const graphState &goal) const
Definition: GraphEnvironment.cpp:182
GraphEnvironment::DrawStateLabel
virtual void DrawStateLabel(Graphics::Display &disp, const graphState &l1, const char *txt) const
Definition: GraphEnvironment.cpp:780
Graph::edgeIterNext
edge * edgeIterNext(edge_iterator &) const
Definition: Graph.cpp:320
GraphEnvironment::g
Graph * g
Definition: GraphEnvironment.h:360
GraphEnvironment::GetStateHash
virtual uint64_t GetStateHash(const graphState &state) const
Definition: GraphEnvironment.cpp:187
Graphics::textBaselineMiddle
@ textBaselineMiddle
Definition: Graphics.h:27
kGround
@ kGround
Definition: Map.h:55
GraphDistanceHeuristic::HCost
virtual double HCost(const graphState &state1, const graphState &state2) const
Definition: GraphEnvironment.cpp:1526
node::getEdgeIter
edge_iterator getEdgeIter() const
Definition: Graph.cpp:749
Tile::tile2
halfTile tile2
Definition: Map.h:116
kNoGraphNode
const int kNoGraphNode
Definition: Map.h:93
SearchEnvironment::SetColor
virtual void SetColor(const rgbColor &r) const
Definition: SearchEnvironment.h:102
GraphEnvironment::drawEdgeCosts
bool drawEdgeCosts
Definition: GraphEnvironment.h:362
GraphDistanceHeuristic::FindAvoidNode
node * FindAvoidNode(node *n)
Definition: GraphEnvironment.cpp:1630
GraphEnvironment::InvertAction
virtual bool InvertAction(graphMove &a) const
Definition: GraphEnvironment.cpp:147
node::SetKeyLabel
void SetKeyLabel(int which)
Definition: Graph.h:208
SearchEnvironment::color
rgbColor color
Definition: SearchEnvironment.h:114
Colors::black
const rgbColor black
Definition: Colors.h:119
SVGUtil.h
Graph::getEdgeIter
edge_iterator getEdgeIter() const
Definition: Graph.cpp:315
GraphDistanceHeuristic::locations
std::vector< graphState > locations
Definition: GraphEnvironment.h:246
DrawTextCentered
void DrawTextCentered(double x, double y, double z, double scale, const char *str)
Definition: GLUtil.cpp:542
GraphEnvironment::ApplyAction
virtual void ApplyAction(graphState &s, graphMove a) const
Definition: GraphEnvironment.cpp:141
graphMove::to
uint32_t to
Definition: GraphEnvironment.h:38
kAvoidPlacement
@ kAvoidPlacement
Definition: GraphEnvironment.h:219
Heap::Empty
bool Empty()
Returns true if no items are in the Heap.
Definition: Heap.cpp:83
kForwardSplit
@ kForwardSplit
Definition: Map.h:69
GraphEnvironment::directed
bool directed
Definition: GraphEnvironment.h:358
Graphics::Display
Definition: Graphics.h:146
kBackwardSplit
@ kBackwardSplit
Definition: Map.h:70
kRandom
@ kRandom
Definition: GraphEnvironment.h:257
fless
bool fless(double a, double b)
Definition: FPUtil.h:28
GraphMapInconsistentHeuristic::HCost
double HCost(const graphState &state1, const graphState &state2) const
Definition: GraphEnvironment.cpp:1199
DrawText
void DrawText(double x, double y, double z, double scale, const char *str)
Definition: GLUtil.cpp:526
ROOT_TWO
static const double ROOT_TWO
Definition: GLUtil.h:61
GraphEnvironment::GetStateFromHash
virtual void GetStateFromHash(uint64_t parent, graphState &s) const
Definition: GraphEnvironment.cpp:192
GraphSearchConstants::GetFourConnectedGraph
Graph * GetFourConnectedGraph(Map *m, bool directed)
Definition: GraphEnvironment.cpp:869
Map::GetMapWidth
long GetMapWidth() const
return the width of the map
Definition: Map.h:163
kCompressed
@ kCompressed
Definition: GraphEnvironment.h:260
node::getUniqueID
int getUniqueID() const
Definition: Graph.h:177
GraphEnvironment::Draw
virtual void Draw(Graphics::Display &disp) const
Definition: GraphEnvironment.cpp:643
SearchEnvironment< graphState, graphMove >::GetColor
virtual rgbColor GetColor() const
Definition: SearchEnvironment.h:105
kInternalEdge
@ kInternalEdge
Definition: Map.h:81
GraphEnvironment::GCost
virtual double GCost(const graphState &state1, const graphState &state2) const
Definition: GraphEnvironment.cpp:173
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
GraphEnvironment::integerEdgeCosts
bool integerEdgeCosts
Definition: GraphEnvironment.h:363
GraphEnvironment::DrawLine
virtual void DrawLine(Graphics::Display &disp, const graphState &x, const graphState &y, double width=1.0) const
Definition: GraphEnvironment.cpp:797
GraphEnvironment::SVGLabelState
std::string SVGLabelState(const graphState &s, const char *) const
Definition: GraphEnvironment.cpp:458
GraphDistanceHeuristic::ChooseStartGoal
void ChooseStartGoal(graphState &start, graphState &goal)
Definition: GraphEnvironment.cpp:1540
Heap::Remove
graph_object * Remove()
Remove the item with the lowest key from the Heap & re-heapify.
Definition: Heap.cpp:66
Graphics::Display::FrameCircle
void FrameCircle(rect r, rgbColor c, float lineWidth)
Definition: Graphics.cpp:110
GraphEnvironment::GetNumSuccessors
virtual int GetNumSuccessors(const graphState &stateID) const
Definition: GraphEnvironment.cpp:59
GraphSearchConstants::kYCoordinate
@ kYCoordinate
Definition: GraphEnvironment.h:52
fgreater
bool fgreater(double a, double b)
Definition: FPUtil.h:29
GraphDistanceHeuristic::GetOptimalDistances
void GetOptimalDistances(node *n, std::vector< double > &values)
Definition: GraphEnvironment.cpp:1587
max
#define max(a, b)
Definition: MinimalSectorAbstraction.cpp:40
GraphMapInconsistentHeuristic::compressed
bool compressed
Definition: GraphEnvironment.h:287
GraphEnvironment::HCost
virtual double HCost(const graphState &state1, const graphState &state2) const
Heuristic value between two arbitrary nodes.
Definition: GraphEnvironment.cpp:157
Graph::GetNumNodes
int GetNumNodes()
Definition: Graph.cpp:403
GLUtil.h
Graphics::textAlignCenter
@ textAlignCenter
Definition: Graphics.h:20
node::nodeNeighborNext
int nodeNeighborNext(neighbor_iterator &) const
Definition: Graph.cpp:807
Heap::Add
void Add(graph_object *val)
Add object into Heap.
Definition: Heap.cpp:36
halfTile::node
long node
Definition: Map.h:110
Graphics::Display::DrawArrow
void DrawArrow(point start, point end, float lineWidth, rgbColor c)
Definition: Graphics.cpp:193
rgbColor::r
float r
Definition: Colors.h:71
GraphDistanceHeuristic::weight
std::vector< double > weight
Definition: GraphEnvironment.h:250
GraphSearchConstants::AddEdges
void AddEdges(Map *m, Graph *g, int x, int y, bool directed, double straigtEdgeCost, double diagEdgeCost, int straightEdgeProb, int diagEdgeProb)
AddEdges(map, Graph, x, y)
Definition: GraphEnvironment.cpp:960
GraphDistanceHeuristic::FindBestChild
node * FindBestChild(int best, std::vector< double > &dist, std::vector< double > &weight)
Definition: GraphEnvironment.cpp:1743
GraphEnvironment::GLDrawLine
virtual void GLDrawLine(const graphState &x, const graphState &y) const
Definition: GraphEnvironment.cpp:419
GraphMapInconsistentHeuristic::FillInCache
void FillInCache(std::vector< double > &vals, std::vector< double > &errors, graphState state2) const
Definition: GraphEnvironment.cpp:1312
node::GetLabelF
double GetLabelF(unsigned int index) const
Definition: Graph.h:215
Colors::red
const rgbColor red
Definition: Colors.h:128
Graphics::Display::FillCircle
void FillCircle(rect r, rgbColor c)
Definition: Graphics.cpp:128
GraphEnvironment::h
GraphHeuristic * h
Definition: GraphEnvironment.h:361
GraphEnvironment::GetActionHash
virtual uint64_t GetActionHash(graphMove act) const
Definition: GraphEnvironment.cpp:198
Heap
A simple & efficient Heap class which uses Graph objects.
Definition: Heap.h:27
Graph::GetRandomNode
node * GetRandomNode()
Definition: Graph.cpp:281
GraphDistanceHeuristic::placement
placementScheme placement
Definition: GraphEnvironment.h:243
GraphSearchConstants::kMapX
@ kMapX
Definition: GraphEnvironment.h:55
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
GraphSearchConstants::GetUndirectedGraph
Graph * GetUndirectedGraph(Map *m)
GetMapGraph(map)
Definition: GraphEnvironment.cpp:848
MAXINT
#define MAXINT
Definition: Graph.h:24
GraphAbstractionConstants::kTemporaryLabel
@ kTemporaryLabel
Definition: GraphAbstraction.h:29
GraphEnvironment::SVGDraw
std::string SVGDraw() const
Definition: GraphEnvironment.cpp:484
Tile
Definition: Map.h:113
GraphEnvironment::GetAction
virtual graphMove GetAction(const graphState &s1, const graphState &s2) const
Definition: GraphEnvironment.cpp:136
Graphics::textAlignLeft
@ textAlignLeft
Definition: Graphics.h:21
Map::GetSplit
tSplit GetSplit(long x, long y) const
Return the split of the tile at x, y.
Definition: Map.cpp:1004
GraphMapInconsistentHeuristic::Compress
void Compress()
Definition: GraphEnvironment.cpp:1296
Graphics::rect::left
float left
Definition: Graphics.h:100
GraphEnvironment::GLLabelState
virtual void GLLabelState(const graphState &, const char *) const
Definition: GraphEnvironment.cpp:398
Graphics::textBaselineBottom
@ textBaselineBottom
Definition: Graphics.h:28
kTopEdge
@ kTopEdge
Definition: Map.h:84
GraphDistanceHeuristic::FindFarNode
node * FindFarNode(node *n)
Definition: GraphEnvironment.cpp:1778
ONE_OVER_ROOT_TWO
static const double ONE_OVER_ROOT_TWO
Definition: GLUtil.h:62
Colors::blue
const rgbColor blue
Definition: Colors.h:142
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
GraphEnvironment::GetActions
virtual void GetActions(const graphState &stateID, std::vector< graphMove > &actions) const
Definition: GraphEnvironment.cpp:105
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
kLeftEdge
@ kLeftEdge
Definition: Map.h:82
GraphSearchConstants::GetGraph
Graph * GetGraph(Map *m)
Definition: GraphEnvironment.cpp:851
GraphEnvironment::drawNodeLabels
bool drawNodeLabels
Definition: GraphEnvironment.h:364
FloydWarshall.h
node::GetLabelL
long GetLabelL(unsigned int index) const
Definition: Graph.h:220
node::getNeighborIter
neighbor_iterator getNeighborIter() const
Definition: Graph.cpp:802
GraphHeuristic::HCost
virtual double HCost(const graphState &state1, const graphState &state2) const =0
Graphics::Display::DrawText
void DrawText(const char *text, point location, rgbColor c, float height, const char *typeface=0)
Definition: Graphics.cpp:221
GraphSearchConstants::kZCoordinate
@ kZCoordinate
Definition: GraphEnvironment.h:53
Graph::findDirectedEdge
edge * findDirectedEdge(unsigned int from, unsigned int to)
Definition: Graph.cpp:189
fequal
bool fequal(double a, double b, double tolerance=TOLERANCE)
Definition: FPUtil.h:32
node::edgeIterNext
edge * edgeIterNext(edge_iterator &) const
Definition: Graph.cpp:754
GraphMapInconsistentHeuristic::numHeuristics
int numHeuristics
Definition: GraphEnvironment.h:285
GraphEnvironment::SVGHeader
std::string SVGHeader() const
Definition: GraphEnvironment.cpp:447
GraphEnvironment::GraphEnvironment
GraphEnvironment(Graph *g, GraphHeuristic *gh=0)
Definition: GraphEnvironment.cpp:22
GraphDistanceHeuristic::OpenGLDraw
virtual void OpenGLDraw() const
Definition: GraphEnvironment.cpp:1477
GraphMapInconsistentHeuristic::m
Map * m
Definition: GraphEnvironment.h:288
GraphEnvironment
Definition: GraphEnvironment.h:291
node::GetNumEdges
int GetNumEdges()
Definition: Graph.h:204
node
Nodes to be stored within a Graph.
Definition: Graph.h:170
Map
A tile-based representation of the world.
Definition: Map.h:142
kIgnore
@ kIgnore
Definition: GraphEnvironment.h:256
node::getNumOutgoingEdges
int getNumOutgoingEdges()
Definition: Graph.cpp:784
GraphMapInconsistentHeuristic::OpenGLDraw
virtual void OpenGLDraw() const
Definition: GraphEnvironment.cpp:1414
GraphHeuristic
Definition: GraphEnvironment.h:77
Heap::IsIn
bool IsIn(graph_object *val)
Returns true if the object is in the Heap.
Definition: Heap.cpp:55
GraphEnvironment.h
edge
Edge class for connections between node in a Graph.
Definition: Graph.h:129
GraphMapInconsistentHeuristic::displayHeuristic
int displayHeuristic
Definition: GraphEnvironment.h:286
node::GetName
const char * GetName() const
Definition: Graph.h:175
Generated by   doxygen 1.8.17