HOG2
DynamicWeightedGrid.h
Go to the documentation of this file.
1 //
2 // DynamicWeightedGrid.h
3 // Dynamic Weighted Abstraction
4 //
5 // Created by Nathan Sturtevant on 5/16/19.
6 // Copyright © 2019 University of Denver. All rights reserved.
7 //
8 
9 #ifndef DynamicWeightedGrid_h
10 #define DynamicWeightedGrid_h
11 
12 #include <stdio.h>
13 #include "Map2DEnvironment.h"
14 
15 namespace DWG {
16 
17  enum TerrainType {
18  kBlack = 0,//A
19  kDeepWater = 1,//B
20  kWater = 2,//C
21  kRiver = 3,//D
22  kSwamp = 4,//E
23  kGround = 5,//F
24  kTrees = 6,//G
25  kRoad = 7,//H
26  kDesert = 8,//I
27  kIce = 9,//J
28  kJungle = 10,//K
29  kPlains = 11,//L
30  kBlight = 12,//M
31  kTundra = 13,//N
32  kMountain = 14,//O
33  kHills = 15//P
34  };
35 
36  struct abstractState {
37  int sector, region;
38  };
39 
40  static bool operator==(const abstractState &s1, const abstractState &s2)
41  {
42  return s1.sector == s2.sector && s2.region == s1.region;
43  }
44 
45  struct edge {
46 // edge(int f, int t) :from(f), to(t) {}
47  int sectorFrom, regionFrom;
48  int sectorTo, regionTo;
49  };
50 
51  const uint8_t kNoRegion = 0xFF;
52 
53  struct regionData {
54  xyLoc center;
55  uint8_t terrain;
56  uint16_t count;
57  };
58 
59  template <int sectorSize>
60  struct SectorData {
61  uint8_t cells[sectorSize][sectorSize];
62  uint8_t region[sectorSize][sectorSize];
63  std::vector<edge> edges;
64  std::vector<regionData> regionCenters;
65  };
66 
67  // This is a dynamic weighted grid with an abstraction.
68  // As a search environment it returns abstract states.
69  template <int sectorSize>
70  class DynamicWeightedGrid : public SearchEnvironment<abstractState, edge>
71  {
72  public:
73  DynamicWeightedGrid(int width, int height);
74  DynamicWeightedGrid(const char *map, int minRegionSize = 80);
75  void SaveMap(const char *filename);
76  int GetWidth() const;
77  int GetHeight() const;
78  void SetTerrainType(const xyLoc &l, TerrainType t);
79  TerrainType GetTerrainType(const xyLoc &l) const;
80  void GetSuccessors(const abstractState &nodeID, std::vector<abstractState> &neighbors) const;
81  void GetActions(const abstractState &nodeID, std::vector<edge> &actions) const;
82  void ApplyAction(abstractState &s, edge a) const;
83  bool InvertAction(edge &a) const;
84  edge GetAction(const abstractState &s1, const abstractState &s2) const;
86  double HCost(const abstractState &node1, const abstractState &node2) const;
87  double GCost(const abstractState &node1, const abstractState &node2) const;
88  double GCost(const abstractState &node, const edge &act) const;
89  bool GoalTest(const abstractState &node, const abstractState &goal) const;
90 
91  uint64_t GetStateHash(const abstractState &node) const;
92  uint64_t GetActionHash(edge act) const;
93 
94  void Draw(Graphics::Display &display) const;
95  void Draw(Graphics::Display &display, const abstractState &) const;
96  void OpenGLDraw() const {}
97  void OpenGLDraw(const abstractState&) const {}
98  void OpenGLDraw(const abstractState&, const edge&) const { }
99  void GLDrawLine(const abstractState &x, const abstractState &y) const {}
100 
101  void GetPointFromCoordinate(point3d loc, int &px, int &py) const;
102  void SetCosts(std::vector<double> &c)
103  {
104  costs = c;
105  ValidateEdges();
106  }
107  void SetCost(TerrainType t, double cost)
108  {
109  costs[t] = cost;
110  }
111  std::vector<double> &GetCosts()
112  {
113  return costs;
114  }
115  abstractState GetState(const xyLoc &l);
116  xyLoc GetLocation(const abstractState &a);
117  uint64_t EstimateMemoryInBytes()
118  {
119  int numEdges = 0;
120  int numSectors = sectors.size();
121  int numRegions = 0;
122  for (const auto &i : sectors)
123  {
124  numEdges += i.edges.size();
125  numRegions += i.regionCenters.size();
126  }
127  // 8 bits per cell for type
128  // 3 pointers in the sectors for regions, edges, and map data
129  return mWidth*mHeight+numEdges*sizeof(edge)+numRegions+sizeof(regionData)+3*numSectors*sizeof(SectorData<sectorSize>*);
130  }
131  int GetNumEdges()
132  {
133  int numEdges = 0;
134  for (const auto &i : sectors)
135  {
136  numEdges += i.edges.size();
137  }
138  return numEdges;
139  }
140  int GetNumRegions()
141  {
142  int numRegions = 0;
143  for (const auto &i : sectors)
144  {
145  numRegions += i.regionCenters.size();
146  }
147  return numRegions;
148  }
149  void SetDrawAbstraction(bool draw) {drawAbstraction = draw;}
150  bool GetDrawAbstraction() { return drawAbstraction; }
151  void ValidateEdges() const;
152  private:
153  bool FindEdge(int fromSector, int fromRegion, int toSector, int toRegion) const;
154  void DrawSector(Graphics::Display &display, int sector) const;
155 
156  void EliminateSmallRegions(int limit);
157  void BuildAbstraction();
158  void GetRegions(int sector);
159  void GetEdges(int sector);
160  regionData BFS(SectorData<sectorSize> &d, int x, int y, int whichRegion);
161  void AddEdge(SectorData<sectorSize> &d, int s1, int r1, int s2, int r2);
162 
163  int GetNumSectors() const;
164  int GetNumXSectors() const;
165  int GetNumYSectors() const;
166  int GetRegion(const xyLoc &l);
167  int GetSector(const xyLoc &l) const;
168  void GetSectorOffset(const xyLoc &l, int &x, int &y) const;
169  void SetTerrainTypeNoRepair(const xyLoc &l, TerrainType t);
170  std::vector<SectorData<sectorSize>> sectors;
171  int mWidth, mHeight;
172  bool drawAbstraction;
173  std::vector<double> costs;
174  public:
175  void GetCoordinate(const xyLoc &l, float &x, float &y, float &r) const;
176  static rgbColor GetTerrainColor(TerrainType t)
177  {
178  uint8_t val = (uint8_t)t;
179  if (val >= 16)
180  val = 15;
181 // return rgbColor(val/15.0, val/15.0, val/15.0);
182  switch (t)
183  {
184  case kBlack: return Colors::black;
185  case kGround: return Colors::brown;
186  case kTrees: return Colors::darkgreen;
187  case kSwamp: return Colors::bluegreen;
188  case kRoad: return Colors::yellow;
189  case kWater: return Colors::blue;
190  case kDeepWater: return Colors::darkblue;
191  case kRiver: return Colors::lightblue;
192  case kDesert: return Colors::lightyellow;
193  case kIce: return (Colors::white+Colors::cyan);
194  case kJungle: return Colors::darkbluegray;
195  case kPlains: return Colors::lightbrown;
196  case kBlight: return Colors::darkyellow;
197  case kTundra: return Colors::lightgray;
198  case kMountain: return Colors::darkgray;
199  case kHills: return Colors::green;
200  default: return Colors::orange;
201  }
202  }
203 
204  };
205 
206 #pragma mark -
207 #pragma mark DynamicWeightedGridEnvironment
208 #pragma mark -
209 
210  // This is just a dynamic weighted grid
211  class DynamicWeightedGridEnvironment : public SearchEnvironment<xyLoc, tDirection> {
212  public:
213  DynamicWeightedGridEnvironment(const char *map);
214  DynamicWeightedGridEnvironment(int width, int height);
215  void GetSuccessors(const xyLoc &nodeID, std::vector<xyLoc> &neighbors) const;
216  void GetActions(const xyLoc &nodeID, std::vector<tDirection> &actions) const;
217  void ApplyAction(xyLoc &s, tDirection a) const;
218  bool InvertAction(tDirection &a) const;
219  tDirection GetAction(const xyLoc &s1, const xyLoc &s2) const;
221  double HCost(const xyLoc &node1, const xyLoc &node2) const;
222  double GCost(const xyLoc &node1, const xyLoc &node2) const;
223  double GCost(const xyLoc &node, const tDirection &act) const;
224  bool GoalTest(const xyLoc &node, const xyLoc &goal) const;
225 
226  uint64_t GetStateHash(const xyLoc &node) const;
227  uint64_t GetMaxHash() const { return mWidth*mHeight; }
228  uint64_t GetActionHash(tDirection act) const;
229 
230  void Draw(Graphics::Display &display) const;
231  void Draw(Graphics::Display &display, const xyLoc &) const;
232  void OpenGLDraw() const {}
233  void OpenGLDraw(const xyLoc&) const {}
234  void OpenGLDraw(const xyLoc&, const tDirection&) const {}
235  void GLDrawLine(const xyLoc &x, const xyLoc &y) const {}
236  void SetCosts(std::vector<double> &c)
237  {
238  costs = c;
239  }
240  void SetCost(TerrainType t, double cost)
241  {
242  costs[t] = cost;
243  }
244  std::vector<double> &GetCosts()
245  {
246  return costs;
247  }
248  void SetTerrainType(const xyLoc &l, TerrainType t)
249  {
250  terrain[l.y*mWidth+l.x] = t;
251  }
252  private:
253  void GetCoordinate(const xyLoc &l, float &x, float &y, float &r) const;
254  std::vector<double> costs;
255  std::vector<uint8_t> terrain;
256  int mWidth, mHeight;
257  };
258 
259 
260 #pragma mark -
261 #pragma mark DynamicWeightedGrid Implementation
262 #pragma mark -
263 
264 
265  template <int sectorSize>
266  DynamicWeightedGrid<sectorSize>::DynamicWeightedGrid(int width, int height)
267  :mWidth(width), mHeight(height)
268  {
269  drawAbstraction = false;
270  sectors.resize(GetNumSectors());
271  for (uint16_t y = 0; y < mHeight; y++)
272  {
273  for (uint16_t x = 0; x < mWidth; x++)
274  {
275  SetTerrainTypeNoRepair({x, y}, kGround);
276  }
277  }
278  BuildAbstraction();
279  }
280 
281  template <int sectorSize>
282  DynamicWeightedGrid<sectorSize>::DynamicWeightedGrid(const char *map, int minRegionSize)
283  {
284  drawAbstraction = false;
285  FILE *f = fopen(map, "r");
286  if (f == 0)
287  {
288  printf("Unable to open file '%s'\n", map);
289  exit(0);
290  }
291  char format[32];
292  int num = fscanf(f, "type %s\nheight %d\nwidth %d\nmap\n", format, &mHeight, &mWidth);
293  if (num != 3)
294  {
295  printf("Bad file format: '%s'\n", map);
296  exit(0);
297  }
298  sectors.resize(GetNumSectors());
299  char what;
300  for (uint16_t y = 0; y < mHeight; y++)
301  {
302  for (uint16_t x = 0; x < mWidth; x++)
303  {
304  fscanf(f, "%c", &what);
305  SetTerrainTypeNoRepair({x, y}, (DWG::TerrainType)(what-'A'));
306  }
307  fscanf(f, "%c", &what);
308  if (what != '\n')
309  printf("Error loading\n");
310  }
311  EliminateSmallRegions(minRegionSize);
312  BuildAbstraction();
313  }
314 
315  template <int sectorSize>
316  void DynamicWeightedGrid<sectorSize>::SaveMap(const char *filename)
317  {
318  FILE *f = fopen(filename, "w");
319  if (f == 0)
320  {
321  printf("Error opening '%s'\n", filename);
322  return;
323  }
324  fprintf(f, "type octile\nheight %d\nwidth %d\nmap\n", mHeight, mWidth);
325  for (uint16_t y = 0; y < mHeight; y++)
326  {
327  for (uint16_t x = 0; x < mWidth; x++)
328  {
329  fprintf(f, "%c", 'A'+(char)GetTerrainType({x, y}));
330  }
331  fprintf(f, "\n");
332  }
333  fclose(f);
334  }
335 
336  template <int sectorSize>
337  int DynamicWeightedGrid<sectorSize>::GetWidth() const
338  { return mWidth; }
339 
340  template <int sectorSize>
341  int DynamicWeightedGrid<sectorSize>::GetHeight() const
342  { return mHeight; }
343 
344  template <int sectorSize>
345  void DynamicWeightedGrid<sectorSize>::SetTerrainType(const xyLoc &l, TerrainType t)
346  {
347  int sec = GetSector(l);
348  int x, y;
349  GetSectorOffset(l, x, y);
350  if (sectors[sec].cells[x][y] != t)
351  {
352  sectors[sec].cells[x][y] = t;
353  GetRegions(sec);
354  GetEdges(sec);
355  GetEdges(sec-1);
356  GetEdges(sec+1);
357  GetEdges(sec-GetNumXSectors());
358  GetEdges(sec-GetNumXSectors()+1);
359  GetEdges(sec-GetNumXSectors()-1);
360  GetEdges(sec+GetNumXSectors());
361  GetEdges(sec+GetNumXSectors()+1);
362  GetEdges(sec+GetNumXSectors()-1);
363  }
364  }
365 
366  template <int sectorSize>
367  TerrainType DynamicWeightedGrid<sectorSize>::GetTerrainType(const xyLoc &l) const
368  {
369  int sec = GetSector(l);
370  int x, y;
371  GetSectorOffset(l, x, y);
372  return static_cast<TerrainType>(sectors[sec].cells[x][y]);
373  }
374 
375 
376  template <int sectorSize>
377  void DynamicWeightedGrid<sectorSize>::BuildAbstraction()
378  {
379  for (int x = 0; x < GetNumSectors(); x++)
380  {
381  GetRegions(x);
382  }
383  for (int x = 0; x < GetNumSectors(); x++)
384  {
385  GetEdges(x);
386  }
387  }
388 
389  template <int sectorSize>
390  void DynamicWeightedGrid<sectorSize>::GetRegions(int sector)
391  {
392  SectorData<sectorSize> &d = sectors[sector];
393  d.regionCenters.clear();
394  int regionOffsetX = (sector%GetNumXSectors())*sectorSize;
395  int regionOffsetY = (sector/GetNumXSectors())*sectorSize;
396 
397  for (int x = 0; x < sectorSize; x++)
398  {
399  for (int y = 0; y < sectorSize; y++)
400  {
401  d.region[x][y] = kNoRegion;
402  }
403  }
404  int whichRegion = 0;
405  for (int x = 0; x < sectorSize; x++)
406  {
407  for (int y = 0; y < sectorSize; y++)
408  {
409  if (d.region[x][y] == kNoRegion)
410  {
411  d.regionCenters.push_back(BFS(d, x, y, whichRegion));
412  d.regionCenters.back().center.x += regionOffsetX;
413  d.regionCenters.back().center.y += regionOffsetY;
414  whichRegion++;
415  }
416  }
417  }
418  }
419 
420  template <int sectorSize>
421  regionData DynamicWeightedGrid<sectorSize>::BFS(SectorData<sectorSize> &d, int x, int y, int whichRegion)
422  {
423  int avgx = 0, avgy = 0;
424  float count = 0;
425  static std::vector<std::pair<int, int>> inRegion;
426  static std::vector<std::pair<int, int>> stack;
427  inRegion.clear();
428  stack.clear();
429  stack.push_back({x, y});
430  while (stack.size() > 0)
431  {
432  auto i = stack.back();
433  stack.pop_back();
434  if (d.region[i.first][i.second] == kNoRegion)
435  {
436  d.region[i.first][i.second] = whichRegion;
437  inRegion.push_back({i.first, i.second});
438  count++;
439  avgx += i.first;
440  avgy += i.second;
441  if (i.first+1 < sectorSize && (d.cells[i.first][i.second] == d.cells[i.first+1][i.second]))
442  stack.push_back({i.first+1, i.second});
443  if (i.first > 0 && (d.cells[i.first][i.second] == d.cells[i.first-1][i.second]))
444  stack.push_back({i.first-1, i.second});
445  if (i.second+1 < sectorSize && (d.cells[i.first][i.second] == d.cells[i.first][i.second+1]))
446  stack.push_back({i.first, i.second+1});
447  if (i.second > 0 && (d.cells[i.first][i.second] == d.cells[i.first][i.second-1]))
448  stack.push_back({i.first, i.second-1});
449  }
450  }
451  xyLoc middle(avgx/count, avgy/count);
452  xyLoc best(inRegion[0].first, inRegion[0].second);
453  for (auto &loc : inRegion)
454  {
455  if ((loc.first-middle.x)*(loc.first-middle.x)+(loc.second-middle.y)*(loc.second-middle.y) <
456  (best.x-middle.x)*(best.x-middle.x)+(best.y-middle.y)*(best.y-middle.y))
457  {
458  best.x = loc.first;
459  best.y = loc.second;
460  }
461  }
462  return {best, static_cast<uint8_t>(d.cells[x][y]), static_cast<uint16_t>(count)};
463  }
464 
465 
466  template <int sectorSize>
467  void DynamicWeightedGrid<sectorSize>::GetEdges(int sector)
468  {
469  if (sector < 0 || sector >= GetNumSectors())
470  return;
471  SectorData<sectorSize> &d = sectors[sector];
472  d.edges.clear();
473 
474  int regionOffsetX = (sector%GetNumXSectors())*sectorSize;
475  int regionOffsetY = (sector/GetNumXSectors())*sectorSize;
476 
477  for (int x = 0; x < sectorSize; x++)
478  {
479  for (int y = 0; y < sectorSize; y++)
480  {
481  xyLoc middle(regionOffsetX+x, regionOffsetY+y);
482  int r = GetRegion(middle);
483  int s = GetSector(middle);
484 
485  for (int x1 = -1; x1 <= 1; x1++)
486  {
487  for (int y1 = -1; y1 <= 1; y1++)
488  {
489  xyLoc next(middle.x+x1, middle.y+y1);
490  if (next.x >= mWidth || next.y >= mHeight)
491  continue;
492  int r1 = GetRegion(next);
493  int s1 = GetSector(next);
494  if (r1 != r || s1 != s)
495  {
496  AddEdge(d, s, r, s1, r1);
497  }
498  }
499  }
500  }
501  }
502  }
503 
504  template <int sectorSize>
505  void DynamicWeightedGrid<sectorSize>::AddEdge(SectorData<sectorSize> &d, int s1, int r1, int s2, int r2)
506  {
507  for (auto &e : d.edges)
508  {
509  if (e.sectorFrom == s1 && e.sectorTo == s2 && e.regionFrom == r1 && e.regionTo == r2)
510  return;
511  }
512  edge e = {s1, r1, s2, r2};
513  d.edges.push_back(e);
514  }
515 
516  template <int sectorSize>
517  void DynamicWeightedGrid<sectorSize>::ValidateEdges() const
518  {
519  bool success = true;
520  for (const auto &s : sectors)
521  {
522  for (const auto &e : s.edges)
523  {
524  bool result = FindEdge(e.sectorTo, e.regionTo, e.sectorFrom, e.regionFrom);
525  abstractState f = {e.sectorFrom, e.regionFrom};
526  abstractState t = {e.sectorTo, e.regionTo};
527  assert(fequal(HCost(f, t), HCost(t, f)));
528  if (result == false)
529  {
530  printf("Found edge from %d:%d to %d:%d, but missing reverse edge\n", e.sectorFrom, e.regionFrom, e.sectorTo, e.regionTo);
531  success = false;
532  }
533  }
534  }
535  if (success)
536  printf("Edges validated\n");
537  else
538  printf("Edges did not validate\n");
539  }
540 
541  template <int sectorSize>
542  bool DynamicWeightedGrid<sectorSize>::FindEdge(int fromSector, int fromRegion, int toSector, int toRegion) const
543  {
544  for (const auto &e : sectors[fromSector].edges)
545  if (e.sectorFrom == fromSector && e.regionFrom == fromRegion &&
546  e.sectorTo == toSector && e.regionTo == toRegion)
547  return true;
548  return false;
549  }
550 
551  template <int sectorSize>
552  void DynamicWeightedGrid<sectorSize>::EliminateSmallRegions(int limit)
553  {
554  std::vector<int> regionCount;
555  std::vector<int32_t> regions(mWidth*mHeight, -1);
556  int whichRegion = 0;
557  for (int x = 0; x < mWidth; x++)
558  {
559  for (int y = 0; y < mHeight; y++)
560  {
561  if (regions[y*mWidth+x] == -1)
562  {
563  regionCount.resize(regionCount.size()+1);
564  std::vector<xyLoc> stack;
565  stack.push_back({static_cast<uint16_t>(x), static_cast<uint16_t>(y)});
566  while (stack.size() > 0)
567  {
568  xyLoc i = stack.back();
569  stack.pop_back();
570  if (regions[i.y*mWidth+i.x] == -1)
571  {
572  regions[i.y*mWidth+i.x] = whichRegion;
573  regionCount[whichRegion]++;
574  xyLoc tmp;
575  tmp = i; tmp.x++;
576  if (tmp.x < mWidth && (GetTerrainType(i) == GetTerrainType(tmp)))
577  stack.push_back(tmp);
578  tmp = i; tmp.x--;
579  if (i.x > 0 && (GetTerrainType(i) == GetTerrainType(tmp)))
580  stack.push_back(tmp);
581  tmp = i; tmp.y++;
582  if (tmp.y < mHeight && (GetTerrainType(i) == GetTerrainType(tmp)))
583  stack.push_back(tmp);
584  tmp = i; tmp.y--;
585  if (i.y > 0 && (GetTerrainType(i) == GetTerrainType(tmp)))
586  stack.push_back(tmp);
587  }
588  }
589  whichRegion++;
590  }
591  }
592  }
593  printf("%d regions after first BFS\n", whichRegion);
594  for (int x = 0; x < mWidth; x++)
595  {
596  for (int y = 0; y < mHeight; y++)
597  {
598  if (regionCount[regions[y*mWidth+x]] > limit)
599  {
600  xyLoc i(x, y), tmp;
601  tmp = i; tmp.x++;
602  if (tmp.x < mWidth && (regionCount[regions[tmp.y*mWidth+tmp.x]]) <= limit)
603  {
604  SetTerrainTypeNoRepair(tmp, GetTerrainType(i));
605  regions[tmp.y*mWidth+tmp.x] = regions[y*mWidth+x];
606  }
607  tmp = i; tmp.x--;
608  if (i.x > 0 && (regionCount[regions[tmp.y*mWidth+tmp.x]]) <= limit)
609  {
610  SetTerrainTypeNoRepair(tmp, GetTerrainType(i));
611  regions[tmp.y*mWidth+tmp.x] = regions[y*mWidth+x];
612  }
613  tmp = i; tmp.y++;
614  if (tmp.y < mHeight && (regionCount[regions[tmp.y*mWidth+tmp.x]]) <= limit)
615  {
616  SetTerrainTypeNoRepair(tmp, GetTerrainType(i));
617  regions[tmp.y*mWidth+tmp.x] = regions[y*mWidth+x];
618  }
619  tmp = i; tmp.y--;
620  if (i.y > 0 && (regionCount[regions[tmp.y*mWidth+tmp.x]]) <= limit)
621  {
622  SetTerrainTypeNoRepair(tmp, GetTerrainType(i));
623  regions[tmp.y*mWidth+tmp.x] = regions[y*mWidth+x];
624  }
625  }
626  }
627  }
628  regionCount.resize(0);
629  for (auto &x : regions)
630  x = -1;
631  whichRegion = 0;
632  for (int x = 0; x < mWidth; x++)
633  {
634  for (int y = 0; y < mHeight; y++)
635  {
636  if (regions[y*mWidth+x] == -1)
637  {
638  regionCount.resize(regionCount.size()+1);
639  std::vector<xyLoc> stack;
640  stack.push_back({static_cast<uint16_t>(x), static_cast<uint16_t>(y)});
641  while (stack.size() > 0)
642  {
643  xyLoc i = stack.back();
644  stack.pop_back();
645  if (regions[i.y*mWidth+i.x] == -1)
646  {
647  regions[i.y*mWidth+i.x] = whichRegion;
648  regionCount[whichRegion]++;
649  xyLoc tmp;
650  tmp = i; tmp.x++;
651  if (tmp.x < mWidth && (GetTerrainType(i) == GetTerrainType(tmp)))
652  stack.push_back(tmp);
653  tmp = i; tmp.x--;
654  if (i.x > 0 && (GetTerrainType(i) == GetTerrainType(tmp)))
655  stack.push_back(tmp);
656  tmp = i; tmp.y++;
657  if (tmp.y < mHeight && (GetTerrainType(i) == GetTerrainType(tmp)))
658  stack.push_back(tmp);
659  tmp = i; tmp.y--;
660  if (i.y > 0 && (GetTerrainType(i) == GetTerrainType(tmp)))
661  stack.push_back(tmp);
662  }
663  }
664  whichRegion++;
665  }
666  }
667  }
668  printf("%d regions after second BFS\n", whichRegion);
669 // for (int x = 0; x < regionCount.size(); x++)
670 // printf("%d : %d\n", x, regionCount[x]);
671  }
672 
673  template <int sectorSize>
674  abstractState DynamicWeightedGrid<sectorSize>::GetState(const xyLoc &l)
675  {
676  abstractState s;
677  s.sector = GetSector(l);
678  s.region = GetRegion(l);
679  return s;
680  }
681 
682  template <int sectorSize>
683  xyLoc DynamicWeightedGrid<sectorSize>::GetLocation(const abstractState &a)
684  {
685  return sectors[a.sector].regionCenters[a.region].center;
686  }
687 
688  template <int sectorSize>
689  int DynamicWeightedGrid<sectorSize>::GetNumSectors() const
690  {
691  return ((mWidth+sectorSize-1)/sectorSize)*((mHeight+sectorSize-1)/sectorSize);
692 
693  }
694 
695  template <int sectorSize>
696  int DynamicWeightedGrid<sectorSize>::GetNumXSectors() const
697  {
698  return ((mWidth+sectorSize-1)/sectorSize);
699 
700  }
701 
702  template <int sectorSize>
703  int DynamicWeightedGrid<sectorSize>::GetNumYSectors() const
704  {
705  return ((mHeight+sectorSize-1)/sectorSize);
706 
707  }
708 
709  template <int sectorSize>
710  int DynamicWeightedGrid<sectorSize>::GetRegion(const xyLoc &l)
711  {
712  int x, y;
713  GetSectorOffset(l, x, y);
714  return sectors[GetSector(l)].region[x][y];
715  }
716 
717  template <int sectorSize>
718  int DynamicWeightedGrid<sectorSize>::GetSector(const xyLoc &l) const
719  {
720  int secx = l.x/sectorSize;
721  int secy = l.y/sectorSize;
722  return secy*GetNumXSectors()+secx;
723  }
724 
725  template <int sectorSize>
726  void DynamicWeightedGrid<sectorSize>::GetSectorOffset(const xyLoc &l, int &x, int &y) const
727  {
728  x = l.x%sectorSize;
729  y = l.y%sectorSize;
730  }
731 
732  template <int sectorSize>
733  void DynamicWeightedGrid<sectorSize>::SetTerrainTypeNoRepair(const xyLoc &l, TerrainType t)
734  {
735  int sec = GetSector(l);
736  int x, y;
737  GetSectorOffset(l, x, y);
738  if (sectors[sec].cells[x][y] != t)
739  {
740  sectors[sec].cells[x][y] = t;
741  }
742  }
743 
744  template <int sectorSize>
745  void DynamicWeightedGrid<sectorSize>::GetSuccessors(const abstractState &nodeID, std::vector<abstractState> &neighbors) const
746  {
747  neighbors.clear();
748  const SectorData<sectorSize> &d = sectors[nodeID.sector];
749  for (auto e : d.edges)
750  {
751  if (e.regionFrom != nodeID.region)
752  continue;
753  neighbors.push_back({e.sectorTo, e.regionTo});
754  }
755  }
756 
757  template <int sectorSize>
758  void DynamicWeightedGrid<sectorSize>::GetActions(const abstractState &nodeID, std::vector<edge> &actions) const
759  {
760  actions.clear();
761  const SectorData<sectorSize> &d = sectors[nodeID.sector];
762  for (auto e : d.edges)
763  {
764  if (e.regionFrom != nodeID.region)
765  continue;
766  actions.push_back(e);
767  }
768  }
769 
770  template <int sectorSize>
771  void DynamicWeightedGrid<sectorSize>::ApplyAction(abstractState &s, edge a) const
772  {
773  s.sector = a.sectorTo;
774  s.region = a.regionTo;
775  }
776 
777  template <int sectorSize>
778  bool DynamicWeightedGrid<sectorSize>::InvertAction(edge &a) const
779  {
780  std::swap(a.sectorFrom, a.sectorTo);
781  std::swap(a.regionFrom, a.regionTo);
782  return true;
783  }
784 
785  template <int sectorSize>
786  edge DynamicWeightedGrid<sectorSize>::GetAction(const abstractState &s1, const abstractState &s2) const
787  {
788  assert(!"Not implemented");
789  return edge();
790  }
791 
792  template <int sectorSize>
793  double DynamicWeightedGrid<sectorSize>::HCost(const abstractState &n1, const abstractState &n2) const
794  {
795  xyLoc l1 = sectors[n1.sector].regionCenters[n1.region].center;
796  xyLoc l2 = sectors[n2.sector].regionCenters[n2.region].center;
797 
798  const double DIAGONAL_COST = M_SQRT2;
799  double a = ((l1.x>l2.x)?(l1.x-l2.x):(l2.x-l1.x));
800  double b = ((l1.y>l2.y)?(l1.y-l2.y):(l2.y-l1.y));
801  // if (a == 0 && b == 0)
802  // return 0;
803  return ((a>b)?(b*DIAGONAL_COST+a-b):(a*DIAGONAL_COST+b-a));
804  }
805 
806  template <int sectorSize>
807  double DynamicWeightedGrid<sectorSize>::GCost(const abstractState &n1, const abstractState &n2) const
808  {
809  xyLoc l1 = sectors[n1.sector].regionCenters[n1.region].center;
810  xyLoc l2 = sectors[n2.sector].regionCenters[n2.region].center;
811 
812  const double DIAGONAL_COST = M_SQRT2;
813  double a = ((l1.x>l2.x)?(l1.x-l2.x):(l2.x-l1.x));
814  double b = ((l1.y>l2.y)?(l1.y-l2.y):(l2.y-l1.y));
815  // if (a == 0 && b == 0)
816  // return 0;
817  double c1 = costs[sectors[n1.sector].regionCenters[n1.region].terrain];
818  double c2 = costs[sectors[n2.sector].regionCenters[n2.region].terrain];
819  return 0.5*(c1+c2)*((a>b)?(b*DIAGONAL_COST+a-b):(a*DIAGONAL_COST+b-a));
820  }
821 
822  template <int sectorSize>
823  double DynamicWeightedGrid<sectorSize>::GCost(const abstractState &node, const edge &act) const
824  {
825  abstractState tmp = node;
826  ApplyAction(tmp, act);
827  return GCost(node, tmp);
828  }
829 
830  template <int sectorSize>
831  bool DynamicWeightedGrid<sectorSize>::GoalTest(const abstractState &node, const abstractState &goal) const
832  {
833  return node == goal;
834  }
835 
836  template <int sectorSize>
837  uint64_t DynamicWeightedGrid<sectorSize>::GetStateHash(const abstractState &node) const
838  {
839  uint64_t a = node.sector;
840  uint64_t b = node.region;
841  return (a<<32)|b;
842  }
843 
844  template <int sectorSize>
845  uint64_t DynamicWeightedGrid<sectorSize>::GetActionHash(edge act) const
846  {
847  assert(!"not implemented");
848  return 0;
849  }
850 
851  template <int sectorSize>
852  void DynamicWeightedGrid<sectorSize>::GetCoordinate(const xyLoc &l, float &x, float &y, float &radius) const
853  {
854  float _scale, xOffset, yOffset;
855  if (mHeight > mWidth)
856  {
857  _scale = 2.0/(float)(mHeight);
858  xOffset = (2.0-mWidth*_scale)*0.5;
859  yOffset = 0;
860  }
861  else {
862  _scale = 2.0/(float)(mWidth);
863  yOffset = (2.0-mHeight*_scale)*0.5;
864  xOffset = 0;
865  }
866  float epsilon = _scale/2.0;
867  x = -1+l.x*_scale+epsilon+xOffset;
868  y = -1+l.y*_scale+epsilon+yOffset;
869  // x = (2*_x-width)*_scale+epsilon;
870  // y = (2*_y-height)*_scale+epsilon;
871  radius = epsilon;
872  }
873 
874  template <int sectorSize>
875  void DynamicWeightedGrid<sectorSize>::GetPointFromCoordinate(point3d loc, int &px, int &py) const
876  {
877  double _x, _y;
878  double _scale, xOffset, yOffset;
879  if (mHeight > mWidth)
880  {
881  _scale = 2.0/(double)(mHeight);
882  xOffset = (2.0-mWidth*_scale)*0.5;
883  yOffset = 0;
884  }
885  else {
886  _scale = 2.0/(double)(mWidth);
887  yOffset = (2.0-mHeight*_scale)*0.5;
888  xOffset = 0;
889  }
890  double epsilon = _scale/2.0;
891 
892  _x = (loc.x-epsilon+1-xOffset)/_scale;
893  _y = (loc.y-epsilon+1-yOffset)/_scale;
894 
895  px = (int)(_x+0.5); // round off!
896  py = (int)(_y+0.5);
897  if ((px < 0) || (py < 0) || (px >= mWidth) || (py >= mHeight))
898  {
899  px = py = -1;
900  }
901  }
902 
903  template <int sectorSize>
904  void DynamicWeightedGrid<sectorSize>::DrawSector(Graphics::Display &display, int sector) const
905  {
906  auto &s = sectors[sector];
907  int regionOffsetX = (sector%GetNumXSectors())*sectorSize;
908  int regionOffsetY = (sector/GetNumXSectors())*sectorSize;
909  uint16_t largest = 0;
910  for (size_t x = 1; x < s.regionCenters.size(); x++)
911  {
912  if (s.regionCenters[x].count > s.regionCenters[largest].count)
913  largest = x;
914  }
915 
916  float x, y, r;
917  xyLoc l(regionOffsetX, regionOffsetY);
918  GetCoordinate(l, x, y, r);
919  //r=r*sectorSize*0.5f;
920  display.FillSquare({x-r+r*sectorSize, y-r+r*sectorSize}, r*sectorSize,
921  GetTerrainColor((TerrainType)s.regionCenters[largest].terrain));
922  for (int yy = 0; yy < sectorSize; yy++)
923  {
924  int startx = 0;
925  int starty = yy;
926  for (int xx = 0; xx < sectorSize; xx++)
927  {
928  // Same type of cell
929  if (s.cells[xx][yy] == s.cells[startx][starty])
930  continue;
931 
932  // draw previous area
933  if (s.cells[startx][starty] != (TerrainType)s.regionCenters[largest].terrain)
934  {
935  l.x = regionOffsetX+startx;
936  l.y = regionOffsetY+starty;
937  GetCoordinate(l, x, y, r);
938  display.FillRect({x-r, y-r, x-r+2*r*(xx-startx), y+r},
939  GetTerrainColor((TerrainType)s.cells[startx][starty]));
940  }
941  startx = xx;
942  }
943  if (startx < sectorSize)
944  {
945  if (s.cells[startx][starty] != (TerrainType)s.regionCenters[largest].terrain)
946  {
947  l.x = regionOffsetX+startx;
948  l.y = regionOffsetY+starty;
949  GetCoordinate(l, x, y, r);
950  display.FillRect({x-r, y-r, x-r+2*r*(sectorSize-startx), y+r},
951  GetTerrainColor((TerrainType)s.cells[startx][starty]));
952  }
953  }
954  }
955  }
956 
957  template <int sectorSize>
958  void DynamicWeightedGrid<sectorSize>::Draw(Graphics::Display &display) const
959  {
960  for (int t = 0; t < sectors.size(); t++)
961  {
962  DrawSector(display, t);
963  }
964  if (!drawAbstraction)
965  return;
966 
967  // Draw sector boundaries
968  for (int x = 0; x < mWidth; x+=sectorSize)
969  {
970  float xx1, yy1, rr, xx2, yy2;
971  xyLoc l1(x, 0), l2(x, mHeight);
972  GetCoordinate(l1, xx1, yy1, rr);
973  GetCoordinate(l2, xx2, yy2, rr);
974  display.DrawLine({xx1-rr, yy1-rr}, {xx2-rr, yy2-rr}, rr*0.5f, Colors::darkgray);
975  }
976  for (int y = 0; y < mHeight; y+=sectorSize)
977  {
978  float xx1, yy1, rr, xx2, yy2;
979  xyLoc l1(0, y), l2(mWidth, y);
980  GetCoordinate(l1, xx1, yy1, rr);
981  GetCoordinate(l2, xx2, yy2, rr);
982  display.DrawLine({xx1-rr, yy1-rr}, {xx2-rr, yy2-rr}, rr*0.5f, Colors::darkgray);
983  }
984  // Draw edges in sectors
985  for (int s = 0; s < GetNumSectors(); s++)
986  {
987  const SectorData<sectorSize> &d = sectors[s];
988  for (auto i : d.regionCenters)
989  {
990  float x, y, r;
991  GetCoordinate(i.center, x, y, r);
992  display.FillCircle({x, y}, r, Colors::gray);
993  }
994  for (auto e : d.edges)
995  {
996  xyLoc l1 = sectors[e.sectorFrom].regionCenters[e.regionFrom].center;
997  xyLoc l2 = sectors[e.sectorTo].regionCenters[e.regionTo].center;
998 
999  float xx1, yy1, rr, xx2, yy2;
1000  GetCoordinate(l1, xx1, yy1, rr);
1001  GetCoordinate(l2, xx2, yy2, rr);
1002  display.DrawLine({xx1, yy1}, {xx2, yy2}, rr*0.5f, Colors::green);
1003  }
1004  }
1005  }
1006 
1007  template <int sectorSize>
1008  void DynamicWeightedGrid<sectorSize>::Draw(Graphics::Display &display, const abstractState &absState) const
1009  {
1010  xyLoc l = sectors[absState.sector].regionCenters[absState.region].center;
1011  float x, y, r;
1012  GetCoordinate(l, x, y, r);
1013  display.FillCircle({x, y}, 4*r, GetColor());
1014  }
1015 
1016 
1017 }
1018 #endif /* DynamicWeightedGrid_h */
Graphics::Display::DrawLine
void DrawLine(point start, point end, float lineWidth, rgbColor c)
Definition: Graphics.cpp:184
DWG::DynamicWeightedGridEnvironment::GCost
double GCost(const xyLoc &node1, const xyLoc &node2) const
Definition: DynamicWeightedGrid.cpp:215
DWG::DynamicWeightedGridEnvironment::GLDrawLine
void GLDrawLine(const xyLoc &x, const xyLoc &y) const
Definition: DynamicWeightedGrid.h:235
DWG::DynamicWeightedGrid::HCost
double HCost(const abstractState &node1, const abstractState &node2) const
Heuristic value between two arbitrary nodes.
Definition: DynamicWeightedGrid.h:793
loc::x
int x
Definition: MapGenerators.cpp:296
Colors::GetColor
rgbColor GetColor(float v, float vmin, float vmax, int type)
Given min/max values, get a color from a color schema.
Definition: Colors.cpp:24
DWG::DynamicWeightedGridEnvironment::SetCost
void SetCost(TerrainType t, double cost)
Definition: DynamicWeightedGrid.h:240
DWG::DynamicWeightedGrid::Draw
void Draw(Graphics::Display &display) const
Definition: DynamicWeightedGrid.h:958
DWG::DynamicWeightedGrid::GetPointFromCoordinate
void GetPointFromCoordinate(point3d loc, int &px, int &py) const
Definition: DynamicWeightedGrid.h:875
DWG::DynamicWeightedGrid::GetActionHash
uint64_t GetActionHash(edge act) const
Definition: DynamicWeightedGrid.h:845
DWG::DynamicWeightedGrid::ApplyAction
void ApplyAction(abstractState &s, edge a) const
Definition: DynamicWeightedGrid.h:771
Colors::lightyellow
const rgbColor lightyellow
Definition: Colors.h:147
DWG::kBlight
@ kBlight
Definition: DynamicWeightedGrid.h:30
rgbColor
A color; r/g/b are between 0...1.
Definition: Colors.h:17
DWG::DynamicWeightedGrid::GetSector
int GetSector(const xyLoc &l) const
Definition: DynamicWeightedGrid.h:718
DWG
Definition: DynamicWeightedGrid.cpp:15
DWG::regionData::terrain
uint8_t terrain
Definition: DynamicWeightedGrid.h:55
DWG::edge::regionFrom
int regionFrom
Definition: DynamicWeightedGrid.h:47
Graphics::Display::FillSquare
void FillSquare(point p, float radius, rgbColor c)
Definition: Graphics.cpp:92
DWG::DynamicWeightedGrid::GetCoordinate
void GetCoordinate(const xyLoc &l, float &x, float &y, float &r) const
Definition: DynamicWeightedGrid.h:852
DWG::kPlains
@ kPlains
Definition: DynamicWeightedGrid.h:29
DWG::DynamicWeightedGrid::SetTerrainTypeNoRepair
void SetTerrainTypeNoRepair(const xyLoc &l, TerrainType t)
Definition: DynamicWeightedGrid.h:733
DWG::DynamicWeightedGrid
Definition: DynamicWeightedGrid.h:70
DWG::DynamicWeightedGrid::SetCosts
void SetCosts(std::vector< double > &c)
Definition: DynamicWeightedGrid.h:102
loc::y
int y
Definition: MapGenerators.cpp:296
DWG::DynamicWeightedGrid::GetCosts
std::vector< double > & GetCosts()
Definition: DynamicWeightedGrid.h:111
DWG::DynamicWeightedGrid::mWidth
int mWidth
Definition: DynamicWeightedGrid.h:171
xyLoc::y
uint16_t y
Definition: Map2DEnvironment.h:42
DWG::DynamicWeightedGrid::GetRegions
void GetRegions(int sector)
Definition: DynamicWeightedGrid.h:390
DWG::kBlack
@ kBlack
Definition: DynamicWeightedGrid.h:18
d
mcData d[]
Definition: MotionCaptureMovement.cpp:21
DWG::DynamicWeightedGrid::GetNumSectors
int GetNumSectors() const
Definition: DynamicWeightedGrid.h:689
DWG::DynamicWeightedGridEnvironment::GetAction
tDirection GetAction(const xyLoc &s1, const xyLoc &s2) const
Definition: DynamicWeightedGrid.cpp:196
DWG::DynamicWeightedGrid::drawAbstraction
bool drawAbstraction
Definition: DynamicWeightedGrid.h:172
DWG::kIce
@ kIce
Definition: DynamicWeightedGrid.h:27
DWG::DynamicWeightedGridEnvironment::GetCoordinate
void GetCoordinate(const xyLoc &l, float &x, float &y, float &r) const
Definition: DynamicWeightedGrid.cpp:261
xyLoc
Definition: Map2DEnvironment.h:37
width
int width
Definition: SFML_HOG.cpp:54
Colors::darkblue
const rgbColor darkblue
Definition: Colors.h:143
DWG::DynamicWeightedGrid::GetLocation
xyLoc GetLocation(const abstractState &a)
Definition: DynamicWeightedGrid.h:683
DWG::kRoad
@ kRoad
Definition: DynamicWeightedGrid.h:25
DWG::DynamicWeightedGrid::SaveMap
void SaveMap(const char *filename)
Definition: DynamicWeightedGrid.h:316
Colors::lightblue
const rgbColor lightblue
Definition: Colors.h:144
Map2DEnvironment.h
DWG::DynamicWeightedGrid::GetEdges
void GetEdges(int sector)
Definition: DynamicWeightedGrid.h:467
Colors::darkbluegray
const rgbColor darkbluegray
Definition: Colors.h:124
DWG::DynamicWeightedGrid::FindEdge
bool FindEdge(int fromSector, int fromRegion, int toSector, int toRegion) const
Definition: DynamicWeightedGrid.h:542
DWG::DynamicWeightedGrid::sectors
std::vector< SectorData< sectorSize > > sectors
Definition: DynamicWeightedGrid.h:170
DWG::DynamicWeightedGridEnvironment::InvertAction
bool InvertAction(tDirection &a) const
Definition: DynamicWeightedGrid.cpp:179
DWG::DynamicWeightedGrid::GetSectorOffset
void GetSectorOffset(const xyLoc &l, int &x, int &y) const
Definition: DynamicWeightedGrid.h:726
DWG::DynamicWeightedGrid::GetNumRegions
int GetNumRegions()
Definition: DynamicWeightedGrid.h:140
DWG::DynamicWeightedGrid::OpenGLDraw
void OpenGLDraw(const abstractState &, const edge &) const
Definition: DynamicWeightedGrid.h:98
DWG::DynamicWeightedGrid::SetCost
void SetCost(TerrainType t, double cost)
Definition: DynamicWeightedGrid.h:107
DWG::DynamicWeightedGridEnvironment::OpenGLDraw
void OpenGLDraw(const xyLoc &) const
Definition: DynamicWeightedGrid.h:233
DWG::DynamicWeightedGrid::SetDrawAbstraction
void SetDrawAbstraction(bool draw)
Definition: DynamicWeightedGrid.h:149
xyLoc::x
uint16_t x
Definition: Map2DEnvironment.h:41
DWG::SectorData
Definition: DynamicWeightedGrid.h:60
Colors::brown
const rgbColor brown
Definition: Colors.h:132
DWG::edge::sectorFrom
int sectorFrom
Definition: DynamicWeightedGrid.h:47
DWG::DynamicWeightedGrid::AddEdge
void AddEdge(SectorData< sectorSize > &d, int s1, int r1, int s2, int r2)
Definition: DynamicWeightedGrid.h:505
DWG::kDeepWater
@ kDeepWater
Definition: DynamicWeightedGrid.h:19
DWG::kJungle
@ kJungle
Definition: DynamicWeightedGrid.h:28
DWG::DynamicWeightedGridEnvironment
Definition: DynamicWeightedGrid.h:211
DWG::DynamicWeightedGrid::EliminateSmallRegions
void EliminateSmallRegions(int limit)
Definition: DynamicWeightedGrid.h:552
DWG::edge::sectorTo
int sectorTo
Definition: DynamicWeightedGrid.h:48
DWG::DynamicWeightedGridEnvironment::costs
std::vector< double > costs
Definition: DynamicWeightedGrid.h:254
DWG::DynamicWeightedGrid::costs
std::vector< double > costs
Definition: DynamicWeightedGrid.h:173
DWG::SectorData::cells
uint8_t cells[sectorSize][sectorSize]
Definition: DynamicWeightedGrid.h:61
DWG::DynamicWeightedGrid::BFS
regionData BFS(SectorData< sectorSize > &d, int x, int y, int whichRegion)
Definition: DynamicWeightedGrid.h:421
loc
Definition: MapGenerators.cpp:296
DWG::DynamicWeightedGrid::mHeight
int mHeight
Definition: DynamicWeightedGrid.h:171
DWG::DynamicWeightedGridEnvironment::DynamicWeightedGridEnvironment
DynamicWeightedGridEnvironment(const char *map)
Definition: DynamicWeightedGrid.cpp:17
Colors::black
const rgbColor black
Definition: Colors.h:119
DWG::DynamicWeightedGrid::GetTerrainColor
static rgbColor GetTerrainColor(TerrainType t)
Definition: DynamicWeightedGrid.h:176
DWG::DynamicWeightedGridEnvironment::GetActionHash
uint64_t GetActionHash(tDirection act) const
Definition: DynamicWeightedGrid.cpp:243
costs
Definition: FringeSearch.h:15
BFS
Definition: BFS.h:21
DWG::DynamicWeightedGridEnvironment::SetCosts
void SetCosts(std::vector< double > &c)
Definition: DynamicWeightedGrid.h:236
DWG::abstractState
Definition: DynamicWeightedGrid.h:36
point3d
#define point3d
Definition: GLUtil.h:123
DWG::operator==
static bool operator==(const abstractState &s1, const abstractState &s2)
Definition: DynamicWeightedGrid.h:40
DWG::DynamicWeightedGridEnvironment::OpenGLDraw
void OpenGLDraw() const
Definition: DynamicWeightedGrid.h:232
Colors::lightbrown
const rgbColor lightbrown
Definition: Colors.h:133
DWG::DynamicWeightedGrid::GetTerrainType
TerrainType GetTerrainType(const xyLoc &l) const
Definition: DynamicWeightedGrid.h:367
DWG::kGround
@ kGround
Definition: DynamicWeightedGrid.h:23
Graphics::Display
Definition: Graphics.h:146
DWG::DynamicWeightedGridEnvironment::GetStateHash
uint64_t GetStateHash(const xyLoc &node) const
Definition: DynamicWeightedGrid.cpp:238
DWG::DynamicWeightedGrid::GetNumYSectors
int GetNumYSectors() const
Definition: DynamicWeightedGrid.h:703
Colors::darkgray
const rgbColor darkgray
Definition: Colors.h:123
DWG::DynamicWeightedGridEnvironment::mHeight
int mHeight
Definition: DynamicWeightedGrid.h:256
DWG::DynamicWeightedGridEnvironment::Draw
void Draw(Graphics::Display &display) const
Definition: DynamicWeightedGrid.cpp:248
DWG::DynamicWeightedGrid::SetTerrainType
void SetTerrainType(const xyLoc &l, TerrainType t)
Definition: DynamicWeightedGrid.h:345
DWG::DynamicWeightedGrid::GetNumXSectors
int GetNumXSectors() const
Definition: DynamicWeightedGrid.h:696
tDirection
tDirection
Definition: Map2DEnvironment.h:77
Colors::cyan
const rgbColor cyan
Definition: Colors.h:153
DWG::DynamicWeightedGridEnvironment::GoalTest
bool GoalTest(const xyLoc &node, const xyLoc &goal) const
Definition: DynamicWeightedGrid.cpp:233
DWG::abstractState::sector
int sector
Definition: DynamicWeightedGrid.h:37
DWG::kTundra
@ kTundra
Definition: DynamicWeightedGrid.h:31
height
int height
Definition: SFML_HOG.cpp:54
DWG::DynamicWeightedGridEnvironment::OpenGLDraw
void OpenGLDraw(const xyLoc &, const tDirection &) const
Definition: DynamicWeightedGrid.h:234
DWG::kSwamp
@ kSwamp
Definition: DynamicWeightedGrid.h:22
DWG::kTrees
@ kTrees
Definition: DynamicWeightedGrid.h:24
DWG::DynamicWeightedGrid::GetWidth
int GetWidth() const
Definition: DynamicWeightedGrid.h:337
DWG::edge::regionTo
int regionTo
Definition: DynamicWeightedGrid.h:48
DWG::DynamicWeightedGrid::GetStateHash
uint64_t GetStateHash(const abstractState &node) const
Definition: DynamicWeightedGrid.h:837
DWG::DynamicWeightedGrid::GetState
abstractState GetState(const xyLoc &l)
Definition: DynamicWeightedGrid.h:674
DWG::regionData::count
uint16_t count
Definition: DynamicWeightedGrid.h:56
DWG::kHills
@ kHills
Definition: DynamicWeightedGrid.h:33
DWG::regionData::center
xyLoc center
Definition: DynamicWeightedGrid.h:54
DWG::DynamicWeightedGrid::GLDrawLine
void GLDrawLine(const abstractState &x, const abstractState &y) const
Definition: DynamicWeightedGrid.h:99
DWG::DynamicWeightedGrid::OpenGLDraw
void OpenGLDraw() const
Definition: DynamicWeightedGrid.h:96
DWG::SectorData::edges
std::vector< edge > edges
Definition: DynamicWeightedGrid.h:63
DWG::DynamicWeightedGridEnvironment::mWidth
int mWidth
Definition: DynamicWeightedGrid.h:256
Colors::darkyellow
const rgbColor darkyellow
Definition: Colors.h:149
DWG::DynamicWeightedGrid::DynamicWeightedGrid
DynamicWeightedGrid(int width, int height)
Definition: DynamicWeightedGrid.h:266
DWG::DynamicWeightedGrid::DrawSector
void DrawSector(Graphics::Display &display, int sector) const
Definition: DynamicWeightedGrid.h:904
DWG::DynamicWeightedGridEnvironment::terrain
std::vector< uint8_t > terrain
Definition: DynamicWeightedGrid.h:255
DWG::DynamicWeightedGrid::EstimateMemoryInBytes
uint64_t EstimateMemoryInBytes()
Definition: DynamicWeightedGrid.h:117
Colors::orange
const rgbColor orange
Definition: Colors.h:155
DWG::regionData
Definition: DynamicWeightedGrid.h:53
Graphics::Display::FillCircle
void FillCircle(rect r, rgbColor c)
Definition: Graphics.cpp:128
DWG::DynamicWeightedGrid::GetRegion
int GetRegion(const xyLoc &l)
Definition: DynamicWeightedGrid.h:710
DWG::DynamicWeightedGridEnvironment::GetCosts
std::vector< double > & GetCosts()
Definition: DynamicWeightedGrid.h:244
DWG::kWater
@ kWater
Definition: DynamicWeightedGrid.h:20
DWG::kMountain
@ kMountain
Definition: DynamicWeightedGrid.h:32
DWG::DynamicWeightedGrid::ValidateEdges
void ValidateEdges() const
Definition: DynamicWeightedGrid.h:517
DWG::DynamicWeightedGridEnvironment::ApplyAction
void ApplyAction(xyLoc &s, tDirection a) const
Definition: DynamicWeightedGrid.cpp:163
Colors::darkgreen
const rgbColor darkgreen
Definition: Colors.h:136
Colors::yellow
const rgbColor yellow
Definition: Colors.h:148
DWG::DynamicWeightedGridEnvironment::GetMaxHash
uint64_t GetMaxHash() const
Definition: DynamicWeightedGrid.h:227
DWG::kRiver
@ kRiver
Definition: DynamicWeightedGrid.h:21
DWG::DynamicWeightedGrid::GetDrawAbstraction
bool GetDrawAbstraction()
Definition: DynamicWeightedGrid.h:150
Colors::gray
const rgbColor gray
Definition: Colors.h:121
Colors::white
const rgbColor white
Definition: Colors.h:120
DWG::DynamicWeightedGrid::BuildAbstraction
void BuildAbstraction()
Definition: DynamicWeightedGrid.h:377
DWG::DynamicWeightedGrid::InvertAction
bool InvertAction(edge &a) const
Definition: DynamicWeightedGrid.h:778
DWG::edge
Definition: DynamicWeightedGrid.h:45
DWG::DynamicWeightedGridEnvironment::SetTerrainType
void SetTerrainType(const xyLoc &l, TerrainType t)
Definition: DynamicWeightedGrid.h:248
Colors::blue
const rgbColor blue
Definition: Colors.h:142
DWG::abstractState::region
int region
Definition: DynamicWeightedGrid.h:37
DWG::DynamicWeightedGrid::OpenGLDraw
void OpenGLDraw(const abstractState &) const
Definition: DynamicWeightedGrid.h:97
swap
void swap(uint64_t &state, int loc1, int loc2)
Definition: RubiksCube7Edges.cpp:359
DWG::DynamicWeightedGrid::GetAction
edge GetAction(const abstractState &s1, const abstractState &s2) const
Definition: DynamicWeightedGrid.h:786
DWG::DynamicWeightedGrid::GetActions
void GetActions(const abstractState &nodeID, std::vector< edge > &actions) const
Definition: DynamicWeightedGrid.h:758
Colors::lightgray
const rgbColor lightgray
Definition: Colors.h:125
DWG::DynamicWeightedGridEnvironment::HCost
double HCost(const xyLoc &node1, const xyLoc &node2) const
Heuristic value between two arbitrary nodes.
Definition: DynamicWeightedGrid.cpp:204
DWG::DynamicWeightedGridEnvironment::GetActions
void GetActions(const xyLoc &nodeID, std::vector< tDirection > &actions) const
Definition: DynamicWeightedGrid.cpp:125
DWG::DynamicWeightedGridEnvironment::GetSuccessors
void GetSuccessors(const xyLoc &nodeID, std::vector< xyLoc > &neighbors) const
Definition: DynamicWeightedGrid.cpp:76
fequal
bool fequal(double a, double b, double tolerance=TOLERANCE)
Definition: FPUtil.h:32
Graphics::Display::FillRect
void FillRect(rect r, rgbColor c)
Definition: Graphics.cpp:101
DWG::kNoRegion
const uint8_t kNoRegion
Definition: DynamicWeightedGrid.h:51
DWG::SectorData::regionCenters
std::vector< regionData > regionCenters
Definition: DynamicWeightedGrid.h:64
Colors::green
const rgbColor green
Definition: Colors.h:135
DWG::DynamicWeightedGrid::GetNumEdges
int GetNumEdges()
Definition: DynamicWeightedGrid.h:131
DWG::DynamicWeightedGrid::GetHeight
int GetHeight() const
Definition: DynamicWeightedGrid.h:341
DWG::DynamicWeightedGrid::GetSuccessors
void GetSuccessors(const abstractState &nodeID, std::vector< abstractState > &neighbors) const
Definition: DynamicWeightedGrid.h:745
DWG::DynamicWeightedGrid::GCost
double GCost(const abstractState &node1, const abstractState &node2) const
Definition: DynamicWeightedGrid.h:807
DWG::kDesert
@ kDesert
Definition: DynamicWeightedGrid.h:26
SearchEnvironment
Definition: SearchEnvironment.h:30
node
Nodes to be stored within a Graph.
Definition: Graph.h:170
DWG::SectorData::region
uint8_t region[sectorSize][sectorSize]
Definition: DynamicWeightedGrid.h:62
Colors::bluegreen
const rgbColor bluegreen
Definition: Colors.h:139
DWG::TerrainType
TerrainType
Definition: DynamicWeightedGrid.h:17
DWG::DynamicWeightedGrid::GoalTest
bool GoalTest(const abstractState &node, const abstractState &goal) const
Definition: DynamicWeightedGrid.h:831
Generated by   doxygen 1.8.17