HOG2
BOAStar.h
Go to the documentation of this file.
1 //
2 // BOAStar.h
3 // HOG2 ObjC
4 //
5 // Created by Nathan Sturtevant on 2/16/23.
6 // Copyright © 2023 MovingAI. All rights reserved.
7 //
8 // Bi-objective A* By Ulloa et, 2020
9 
10 #include "TemplateAStar.h"
11 
12 #ifndef BOAStar_h
13 #define BOAStar_h
14 
15 template <class state, class action, class environment>
16 class BOAStar //: public GenericSearchAlgorithm<state,action,environment>
17 {
18 public:
19  BOAStar() { ResetNodeCount(); };
20  virtual ~BOAStar() {}
21  void GetPath(environment *env1, environment *env2, Heuristic<state> *h1, Heuristic<state> *h2,
22  const state& from, const state& to, std::vector<state> &thePath);
23 // void GetPath(environment *, const state& , const state& , std::vector<action> & );
24 
25  state goal, start;
26 
27  bool InitializeSearch(environment *env1, environment *env2, Heuristic<state> *h1, Heuristic<state> *h2,
28  const state& from, const state& to, std::vector<state> &thePath);
29  bool DoSingleSearchStep(std::vector<state> &thePath);
30 
31  void ExtractPathToStart(state &node, std::vector<state> &thePath);
32  void ExtractPathToStartFromID(size_t node, std::vector<state> &thePath);
33  virtual const char *GetName() { return "BOAStar"; }
34 
35  uint64_t GetUniqueNodesExpanded() { return uniqueNodesExpanded; }
36  void ResetNodeCount() { nodesExpanded = nodesTouched = 0; uniqueNodesExpanded = 0; }
37 // int GetMemoryUsage();
38 //
39  size_t GetNumItems() const { return allStates.size(); }
40  bool IsOpen(size_t item) const { return allStates[item].open; }
41  state GetItem(size_t item) const { return allStates[item].s; }
42  float GetItemGCost(size_t item) const { return allStates[item].gCost; }
43  float GetItemHCost(size_t item) const { return allStates[item].hCost; }
44 
45 // void SetHeuristic(Heuristic<state> *h) { theHeuristic = h; }
46 
47  uint64_t GetNodesExpanded() const { return nodesExpanded; }
48  uint64_t GetNodesTouched() const { return nodesTouched; }
49 
50  void LogFinalStats(StatCollection *) {}
51 //
52  void Draw(Graphics::Display &d) const;
53  void DrawFrontier(Graphics::Display &d, int selected = -1) const;
54  void DrawAllPaths(Graphics::Display &d) const;
55  void DrawGoal(Graphics::Display &d, int which, rgbColor c = Colors::blue, float width = 1.0) const;
56  int GetClosestGoal(Graphics::point p, float limit);
57  void SetPhi(std::function<double(double, double)> p)
58  {
59  phi = p;
60  }
61  double Phi(double h, double g) const
62  {
63  return phi(h, g);
64  }
65  void SetOptimalityBound(double w)
66  {
67  phi = [w](double h, double g){ return g/w+h; };
68  bound = w;
69  }
70  double GetOptimalityBound() { return bound; }
71 private:
72  void GetMinFOnOpen() const;
73  size_t GetBestStateOnOpen() const;
74 
75  void DrawOpen(Graphics::Display &d) const;
76  void Expand(size_t which);
77  void UpdateCost(size_t next, size_t parent);
78  void AddState(const state &s, size_t parent);
79  size_t Lookup(const state &s);
80  uint64_t nodesTouched, nodesExpanded;
81 
82  struct stateInfo {
83  stateInfo() {gmin = std::numeric_limits<float>::max();}
84  bool Update(float v) {if (fless(v, gmin)) {gmin = std::min(gmin, v); return true; } return false; }
85  float gmin;
86  };
87  struct item {
88  state s;
89  float gCost1, gCost2;
90  float hCost1, hCost2;
91  float fCost1() const { return gCost1+hCost1; }
92  float fCost2() const { return gCost2+hCost2; }
93  bool open;
94  size_t parent;
95  };
96  // stores gmin for all states seen thus far
97  std::unordered_map<uint64_t, stateInfo> hashTable;
98  std::vector<item> allStates;
99  std::vector<state> neighbors;
100 // std::vector<item> closed;
101 // std::vector<uint64_t> neighborID;
102 // std::vector<double> edgeCosts;
103 // std::vector<dataLocation> neighborLoc;
104 
105  std::vector<item> goals;
106  std::vector<int> openDrawing;
107  mutable std::vector<Graphics::point> goalDrawLocs;
108  std::vector<state> solution;
109  environment *e1, *e2;
110  Heuristic<state> *h1, *h2;
111  // double bestSolution;
112  double bound;
113  uint64_t uniqueNodesExpanded;
114  //Heuristic<state> *theHeuristic;
115 
116  std::function<double(double, double)> phi;
117 };
118 
119 template <class state, class action, class environment>
120 void BOAStar<state, action, environment>::GetPath(environment *env1, environment *env2, Heuristic<state> *h1, Heuristic<state> *h2,
121  const state& from, const state& to, std::vector<state> &thePath)
122 {
123  if (!InitializeSearch(env1, env2, h1, h2, from, to, thePath))
124  {
125  return;
126  }
127  while (!DoSingleSearchStep(thePath))
128  {
129  }
130 }
131 
132 template <class state, class action, class environment>
133 bool BOAStar<state, action, environment>::InitializeSearch(environment *env1, environment *env2,
134  Heuristic<state> *h1, Heuristic<state> *h2,
135  const state& from, const state& to, std::vector<state> &thePath)
136 {
137  hashTable.clear();
138  thePath.resize(0);
139  e1 = env1;
140  e2 = env2;
141  allStates.resize(0);
142  solution.clear();
143  ResetNodeCount();
144  start = from;
145  goal = to;
146  goals.resize(0);
147  this->h1 = h1;
148  this->h2 = h2;
149  allStates.push_back({start, 0, 0,
150  (float)h1->HCost(start, goal),
151  (float)h2->HCost(start, goal),
152  true, 0});
153  // so we only draw each location once, even if it is in open many times
154  // keeping track of how many are in open
155  // unseen states are -1
156  openDrawing.resize(e1->GetMaxHash());
157  std::fill(openDrawing.begin(), openDrawing.end(), -1);
158  openDrawing[e1->GetStateHash(start)]+=2;
159 
160  return true; // success
161 }
162 
163 template <class state, class action, class environment>
164 bool BOAStar<state, action, environment>::DoSingleSearchStep(std::vector<state> &thePath)
165 {
166  // 1. Find min lexicographical state on open
167  size_t which = GetBestStateOnOpen();
168 
169  if (which == allStates.size()) // search is done
170  {
171  std::cout << "Search done; " << GetNodesExpanded() << " expanded;" << goals.size() << " paths found\n";
172  return true;
173  }
174 
175  // 2. Prune this state if it is dominated
176  allStates[which].open = false;
177  openDrawing[e1->GetStateHash(allStates[which].s)]--;
178 
179 // printf("Goal gmin: %f\n", hashTable[e1->GetStateHash(goal)].gmin);
180 
181  // Didn't decrease g2; since f1 is increasing, node is dominated
182  //if (i.gCost2 >= hashTable[e1->GetStateHash(neighbors[x])].gmin)
183  if (allStates[which].gCost2 >= hashTable[e1->GetStateHash(allStates[which].s)].gmin)
184  {
185 // std::cout << "dominated1\n";
186  return false;
187  }
188 
189 // printf("Goal gmin: %f\n", hashTable[e1->GetStateHash(goal)].gmin);
190  // Can't reach the goal on a non-dominated path
191  if (allStates[which].fCost2() >= hashTable[e1->GetStateHash(goal)].gmin)
192  {
193 // std::cout << "dominated2\n";
194  return false;
195  }
196 
197  hashTable[e1->GetStateHash(allStates[which].s)].gmin = allStates[which].gCost2;
198 
199  // 3. Check for goal
200  if (e1->GoalTest(allStates[which].s, goal))
201  {
202  std::cout << "Adding goal " << allStates[which].s << " with costs {" << to_string_with_precision(allStates[which].gCost1, 10) << ", " << allStates[which].gCost2 << "}\n";
203  goals.push_back(allStates[which]);
204  assert(allStates[which].open == false);
205  //openDrawing[e1->GetStateHash(allStates[which].s)]--;
206  }
207 
208  // 4. Expand state
209  Expand(which);
210 
211  return false;
212 }
213 
214 template <class state, class action, class environment>
215 size_t BOAStar<state, action, environment>::GetBestStateOnOpen() const
216 {
217  bool found = false;
218  size_t which;
219  for (size_t x = 0; x < allStates.size(); x++)
220  {
221  if (allStates[x].open)
222  {
223  found = true;
224  which = x;
225  break;
226  }
227  }
228  if (!found)
229  return allStates.size();
230 
231  for (size_t x = which+1; x < allStates.size(); x++)
232  {
233  if (allStates[x].open &&
234  (fless(allStates[x].fCost1(), allStates[which].fCost1()) ||
235  (fequal(allStates[x].fCost1(), allStates[which].fCost1()) &&
236  fless(allStates[x].fCost2(), allStates[which].fCost2()))
237  )
238  )
239  {
240  which = x;
241  }
242  }
243 // std::cout << "x" << which << "-" << allStates[which].s << " [" << goal << "]";
244 // printf(" Next expansions: f1: %1.2f, f2: %1.2f ", allStates[which].fCost1(), allStates[which].fCost2());
245 // std::cout << "{parent: " << allStates[allStates[which].parent].s << "|\n";
246  return which;
247 }
248 
249 template <class state, class action, class environment>
250 void BOAStar<state, action, environment>::Expand(size_t which)
251 {
252  nodesExpanded++;
253  e1->GetSuccessors(allStates[which].s, neighbors);
254  for (int x = 0; x < neighbors.size(); x++)
255  {
256 // std::cout << "g" << neighbors[x];
257  item i =
258  {neighbors[x],
259  static_cast<float>(allStates[which].gCost1+e1->GCost(allStates[which].s, neighbors[x])),
260  static_cast<float>(allStates[which].gCost2+e2->GCost(allStates[which].s, neighbors[x])),
261  static_cast<float>(h1->HCost(neighbors[x], goal)),
262  static_cast<float>(h2->HCost(neighbors[x], goal)),
263  true,
264  which
265  };
266  // Check if state is dominated
267  // Already have shorter gmin for neighbor
268  if (i.gCost2 >= hashTable[e1->GetStateHash(neighbors[x])].gmin)
269  {
270 // std::cout << "prune\n";
271  continue;
272  }
273 
274  // Can't reach the goal on a non-dominated path
275  if (i.fCost2() >= hashTable[e1->GetStateHash(goal)].gmin)
276  {
277 // std::cout << "prune\n";
278  continue;
279  }
280 
281  allStates.push_back(i);
282  auto hash = e1->GetStateHash(i.s);
283  openDrawing[hash]++;
284  if (openDrawing[hash] == 0)
285  openDrawing[hash]++;
286 // std::cout << "add " << allStates.size()-1 << "\n";
287  }
288 }
289 
290 template <class state, class action, class environment>
291 void BOAStar<state, action, environment>::Draw(Graphics::Display &d) const
292 {
293  int maxVal = 0;
294  for (int x = 0; x < e1->GetMaxHash(); x++)
295  maxVal = std::max(openDrawing[x], maxVal);
296  for (int x = 0; x < e1->GetMaxHash(); x++)
297  {
298  if (openDrawing[x] == -1)
299  continue;
300  state s;
301  e1->GetStateFromHash(x, s);
302  if (openDrawing[x] > 0) // open
303  {
304  rgbColor c = Colors::green;
305  c *= openDrawing[x]/(float)maxVal;
306  e1->SetColor(c);
307  e1->Draw(d, s);
308  }
309  else {
310  e1->SetColor(Colors::red);
311  e1->Draw(d, s);
312  }
313  }
314 // for (size_t x = 0; x < allStates.size(); x++)
315 // {
316 // if (allStates[x].open)
317 // {
318 // e1->SetColor(Colors::green);
319 // e1->Draw(d, allStates[x].s);
320 // }
321 // else {
322 // e1->SetColor(Colors::red);
323 // e1->Draw(d, allStates[x].s);
324 // }
325 // }
326  e1->SetColor(Colors::blue);
327  e1->Draw(d, goal);
328 }
329 
330 template <class state, class action, class environment>
331 void BOAStar<state, action, environment>::DrawFrontier(Graphics::Display &d, int selected) const
332 {
333  static std::string s;
334  s = std::to_string(goals.size())+" goals";
335  d.DrawText(s.c_str(), {1, -1}, Colors::white, 0.1f, Graphics::textAlignRight, Graphics::textBaselineTop);
336 
337  if (selected != -1)
338  {
339  static std::string s;
340  s = "Path cost {"+to_string_with_precision(goals[selected].gCost1, 2)+", "+to_string_with_precision(goals[selected].gCost2, 2)+"}";
341  d.DrawText(s.c_str(), {1, -1+0.11}, Colors::white, 0.1f, Graphics::textAlignRight, Graphics::textBaselineTop);
342  }
343 
344  goalDrawLocs.resize(0);
345  float minf1 = (float)h1->HCost(start, goal);
346  float maxf1 = (float)h1->HCost(start, goal);
347  float minf2 = (float)h2->HCost(start, goal);
348  float maxf2 = (float)h2->HCost(start, goal);
349  for (int x = 0; x < goals.size(); x++)
350  {
351  minf1 = std::min(minf1, goals[x].fCost1());
352  maxf1 = std::max(maxf1, goals[x].fCost1());
353  minf2 = std::min(minf2, goals[x].fCost2());
354  maxf2 = std::max(maxf2, goals[x].fCost2());
355  }
356  // axes
357  d.DrawLine({-1, 1}, {-1, -1}, 0.0125, Colors::white);
358  d.DrawText("Objective 1", {0, 1+0.02f}, Colors::white, 0.05, Graphics::textAlignCenter, Graphics::textBaselineTop);
359  d.DrawLine({-1, 1}, {1, 1}, 0.0125, Colors::white);
360  const char o2[] = "O\0b\0j\0e\0c\0t\0i\0v\0e\0 \0002\0";
361  for (int y = 0; y < 11; y++)
362  {
363  Graphics::point p(-1-0.025, 0-5.5*0.05+0.05f*y);
364  d.DrawText(&o2[2*y], p, Colors::white, 0.05, Graphics::textAlignCenter, Graphics::textBaselineMiddle);
365  }
366  // x-labels
367  d.DrawText(to_string_with_precision(minf1, 1).c_str(), {-1, 1+.01}, Colors::white, 0.05, Graphics::textAlignLeft, Graphics::textBaselineTop);
368  d.DrawText(to_string_with_precision(maxf1, 1).c_str(), {1, 1+.01}, Colors::white, 0.05, Graphics::textAlignRight, Graphics::textBaselineTop);
369  // y-labels
370  d.DrawText(to_string_with_precision(minf2, 1).c_str(), {-1-.01, 1}, Colors::white, 0.05, Graphics::textAlignRight, Graphics::textBaselineBottom);
371  d.DrawText(to_string_with_precision(maxf2, 1).c_str(), {-1-.01, -1}, Colors::white, 0.05, Graphics::textAlignRight, Graphics::textBaselineTop);
372 
373  for (int x = 0; x < goals.size(); x++)
374  {
375  float denom1 = 1;
376  if (!fequal(maxf1, minf1))
377  denom1 = maxf1-minf1;
378  float denom2 = 1;
379  if (!fequal(maxf2, minf2))
380  denom2 = maxf2-minf2;
381  Graphics::point p(-1+2*(goals[x].fCost1()-minf1)/(denom1), 1-2*((goals[x].fCost2()-minf2)/(denom2)));
382  if (x != selected)
383  d.FillCircle(p, 0.025, Colors::lightblue);
384  else
385  d.FillCircle(p, 0.025*1.5, Colors::lightblue);
386  goalDrawLocs.emplace_back(p);
387 // maxf1 = std::max(maxf1, goals[x].fCost1());
388 // maxf2 = std::max(maxf2, goals[x].fCost2());
389  }
390 
391  // for (size_t x = 0; x < allStates.size(); x++)
392 // {
393 // if (allStates[x].open)
394 // {
395 // e1->SetColor(Colors::green);
396 // e1->Draw(d, allStates[x].s);
397 // }
398 // else {
399 // e1->SetColor(Colors::red);
400 // e1->Draw(d, allStates[x].s);
401 // }
402 // }
403 // e1->SetColor(Colors::blue);
404 // e1->Draw(d, goal);
405 }
406 
407 template <class state, class action, class environment>
408 void BOAStar<state, action, environment>::DrawAllPaths(Graphics::Display &d) const
409 {
410  e1->SetColor(Colors::blue);
411 
412  for (int x = 0; x < goals.size(); x++)
413  {
414  int current = goals[x].parent;
415  e1->DrawLine(d, goals[x].s, allStates[current].s, 4);
416  while (current != 0)
417  {
418  e1->DrawLine(d, allStates[current].s, allStates[allStates[current].parent].s, 4);
419  current = allStates[current].parent;
420  }
421  }
422 }
423 
424 template <class state, class action, class environment>
425 void BOAStar<state, action, environment>::DrawGoal(Graphics::Display &d, int which, rgbColor c, float width) const
426 {
427  int x = which;
428  e1->SetColor(c);
429 
430  {
431  int current = goals[x].parent;
432  e1->DrawLine(d, goals[x].s, allStates[current].s);
433  while (current != 0)
434  {
435  e1->DrawLine(d, allStates[current].s, allStates[allStates[current].parent].s, width);
436  current = allStates[current].parent;
437  }
438  }
439 }
440 
441 template <class state, class action, class environment>
442 int BOAStar<state, action, environment>::GetClosestGoal(Graphics::point p, float limit)
443 {
444  if (goals.size() < 1)
445  return -1;
446  int which = 0;
447  float dist = (goalDrawLocs[0]-p).squaredLength();
448  for (int x = 1; x < goals.size(); x++)
449  {
450  float d = (goalDrawLocs[x]-p).squaredLength();
451  if (fless(d, dist))
452  {
453  dist = d;
454  which = x;
455  }
456  }
457  if (fless(dist, limit*limit))
458  return which;
459  return -1;
460 }
461 
462 #endif /* BOAStar_h */
BOAStar::UpdateCost
void UpdateCost(size_t next, size_t parent)
BOAStar::stateInfo
Definition: BOAStar.h:82
BOAStar::GetClosestGoal
int GetClosestGoal(Graphics::point p, float limit)
Definition: BOAStar.h:442
Graphics::point
Definition: Graphics.h:32
BOAStar::GetItemGCost
float GetItemGCost(size_t item) const
Definition: BOAStar.h:42
BOAStar::item::gCost2
float gCost2
Definition: BOAStar.h:89
rgbColor
A color; r/g/b are between 0...1.
Definition: Colors.h:17
BOAStar::item::hCost1
float hCost1
Definition: BOAStar.h:90
BOAStar::GetMinFOnOpen
void GetMinFOnOpen() const
min
double min(double a, double b)
Definition: FPUtil.h:35
BOAStar::GetNumItems
size_t GetNumItems() const
Definition: BOAStar.h:39
BOAStar::~BOAStar
virtual ~BOAStar()
Definition: BOAStar.h:20
BOAStar::stateInfo::Update
bool Update(float v)
Definition: BOAStar.h:84
BOAStar::Lookup
size_t Lookup(const state &s)
BOAStar::nodesExpanded
uint64_t nodesExpanded
Definition: BOAStar.h:80
BOAStar::item
Definition: BOAStar.h:87
Heuristic
Definition: Heuristic.h:30
BOAStar::GetOptimalityBound
double GetOptimalityBound()
Definition: BOAStar.h:70
BOAStar::goalDrawLocs
std::vector< Graphics::point > goalDrawLocs
Definition: BOAStar.h:107
Graphics::textAlignRight
@ textAlignRight
Definition: Graphics.h:22
d
mcData d[]
Definition: MotionCaptureMovement.cpp:21
BOAStar::h2
Heuristic< state > * h2
Definition: BOAStar.h:110
BOAStar::DrawFrontier
void DrawFrontier(Graphics::Display &d, int selected=-1) const
Definition: BOAStar.h:331
BOAStar::stateInfo::stateInfo
stateInfo()
Definition: BOAStar.h:83
BOAStar::GetItem
state GetItem(size_t item) const
Definition: BOAStar.h:41
BOAStar::bound
double bound
Definition: BOAStar.h:112
BOAStar::item::fCost2
float fCost2() const
Definition: BOAStar.h:92
width
int width
Definition: SFML_HOG.cpp:54
Colors::lightblue
const rgbColor lightblue
Definition: Colors.h:144
BOAStar::item::open
bool open
Definition: BOAStar.h:93
BOAStar::GetNodesTouched
uint64_t GetNodesTouched() const
Definition: BOAStar.h:48
BOAStar::item::fCost1
float fCost1() const
Definition: BOAStar.h:91
BOAStar::ExtractPathToStart
void ExtractPathToStart(state &node, std::vector< state > &thePath)
Graphics::textBaselineMiddle
@ textBaselineMiddle
Definition: Graphics.h:27
BOAStar::Phi
double Phi(double h, double g) const
Definition: BOAStar.h:61
BOAStar::goals
std::vector< item > goals
Definition: BOAStar.h:105
to_string_with_precision
std::string to_string_with_precision(const T a_value, const int n=6)
Definition: GLUtil.h:185
BOAStar::e1
environment * e1
Definition: BOAStar.h:109
BOAStar::phi
std::function< double(double, double)> phi
Definition: BOAStar.h:116
BOAStar::GetUniqueNodesExpanded
uint64_t GetUniqueNodesExpanded()
Definition: BOAStar.h:35
BOAStar::neighbors
std::vector< state > neighbors
Definition: BOAStar.h:99
BOAStar::DrawGoal
void DrawGoal(Graphics::Display &d, int which, rgbColor c=Colors::blue, float width=1.0) const
Definition: BOAStar.h:425
BOAStar::BOAStar
BOAStar()
Definition: BOAStar.h:19
BOAStar::GetName
virtual const char * GetName()
Definition: BOAStar.h:33
BOAStar::goal
state goal
Definition: BOAStar.h:25
Graphics::Display
Definition: Graphics.h:146
BOAStar::DrawOpen
void DrawOpen(Graphics::Display &d) const
fless
bool fless(double a, double b)
Definition: FPUtil.h:28
BOAStar::SetPhi
void SetPhi(std::function< double(double, double)> p)
Definition: BOAStar.h:57
BOAStar::allStates
std::vector< item > allStates
Definition: BOAStar.h:98
BOAStar::ExtractPathToStartFromID
void ExtractPathToStartFromID(size_t node, std::vector< state > &thePath)
Heuristic::HCost
virtual double HCost(const state &a, const state &b) const
Definition: Heuristic.h:73
TemplateAStar.h
BOAStar::hashTable
std::unordered_map< uint64_t, stateInfo > hashTable
Definition: BOAStar.h:97
BOAStar::solution
std::vector< state > solution
Definition: BOAStar.h:108
BOAStar::GetBestStateOnOpen
size_t GetBestStateOnOpen() const
Definition: BOAStar.h:215
BOAStar::LogFinalStats
void LogFinalStats(StatCollection *)
Definition: BOAStar.h:50
max
#define max(a, b)
Definition: MinimalSectorAbstraction.cpp:40
BOAStar::start
state start
Definition: BOAStar.h:25
Graphics::textAlignCenter
@ textAlignCenter
Definition: Graphics.h:20
BOAStar::ResetNodeCount
void ResetNodeCount()
Definition: BOAStar.h:36
Graphics::textBaselineTop
@ textBaselineTop
Definition: Graphics.h:26
StatCollection
The StatCollection class is for collecting stats across different parts of the simulation.
Definition: StatCollection.h:34
BOAStar::e2
environment * e2
Definition: BOAStar.h:109
BOAStar::InitializeSearch
bool InitializeSearch(environment *env1, environment *env2, Heuristic< state > *h1, Heuristic< state > *h2, const state &from, const state &to, std::vector< state > &thePath)
Definition: BOAStar.h:133
BOAStar::nodesTouched
uint64_t nodesTouched
Definition: BOAStar.h:80
BOAStar::item::parent
size_t parent
Definition: BOAStar.h:94
BOAStar::stateInfo::gmin
float gmin
Definition: BOAStar.h:85
Colors::red
const rgbColor red
Definition: Colors.h:128
BOAStar::openDrawing
std::vector< int > openDrawing
Definition: BOAStar.h:106
BOAStar::DrawAllPaths
void DrawAllPaths(Graphics::Display &d) const
Definition: BOAStar.h:408
Graphics::textAlignLeft
@ textAlignLeft
Definition: Graphics.h:21
BOAStar::GetItemHCost
float GetItemHCost(size_t item) const
Definition: BOAStar.h:43
Colors::white
const rgbColor white
Definition: Colors.h:120
BOAStar::h1
Heuristic< state > * h1
Definition: BOAStar.h:110
BOAStar::SetOptimalityBound
void SetOptimalityBound(double w)
Definition: BOAStar.h:65
Graphics::textBaselineBottom
@ textBaselineBottom
Definition: Graphics.h:28
Colors::blue
const rgbColor blue
Definition: Colors.h:142
BOAStar::Expand
void Expand(size_t which)
Definition: BOAStar.h:250
BOAStar::item::gCost1
float gCost1
Definition: BOAStar.h:89
BOAStar::uniqueNodesExpanded
uint64_t uniqueNodesExpanded
Definition: BOAStar.h:113
fequal
bool fequal(double a, double b, double tolerance=TOLERANCE)
Definition: FPUtil.h:32
BOAStar::Draw
void Draw(Graphics::Display &d) const
Definition: BOAStar.h:291
Colors::green
const rgbColor green
Definition: Colors.h:135
BOAStar
Definition: BOAStar.h:16
BOAStar::GetNodesExpanded
uint64_t GetNodesExpanded() const
Definition: BOAStar.h:47
BOAStar::item::s
state s
Definition: BOAStar.h:88
BOAStar::item::hCost2
float hCost2
Definition: BOAStar.h:90
BOAStar::AddState
void AddState(const state &s, size_t parent)
node
Nodes to be stored within a Graph.
Definition: Graph.h:170
BOAStar::GetPath
void GetPath(environment *env1, environment *env2, Heuristic< state > *h1, Heuristic< state > *h2, const state &from, const state &to, std::vector< state > &thePath)
Definition: BOAStar.h:120
BOAStar::DoSingleSearchStep
bool DoSingleSearchStep(std::vector< state > &thePath)
Definition: BOAStar.h:164
BOAStar::IsOpen
bool IsOpen(size_t item) const
Definition: BOAStar.h:40
Generated by   doxygen 1.8.17