HOG2
Map3DGrid.cpp
Go to the documentation of this file.
1 /*
2  * Map3DGrid.cpp
3  * hog2
4  *
5  * Created by Nathan Sturtevant on 5/6/11.
6  * Copyright 2011 University of Denver. All rights reserved.
7  *
8  */
9 
10 #include "Map3DGrid.h"
11 
12 int gSectorSize = 16;
13 //double gInvSectorSize = 1/16;
14 
15 // uint8_t points[gSectorSize*gSectorSize];
16 // 8 bits - movable directions
17 // 5 bits - base height offset
19 // 3 bits - blockage
20 
21 const uint8_t kUnpassableHeight = 0x1F;
22 
23 int GridData::AddMove(unsigned index, moveDir dir, bool local)
24 {
25  assert(index < gSectorSize*gSectorSize);
26  int cnt = 1;
27  if (points[index]&(((int)dir)<<8))
28  cnt = 0;
29  points[index] |= (((int)dir)<<8);
30  uint32_t val = (((int)dir)<<16);
31  if (local)
32  points[index] |= val;
33  else
34  points[index] &= (~val);
35  return cnt;
36 }
37 
38 void GridData::AddMove(unsigned int x, unsigned int y, moveDir dir, bool local)
39 {
40  points[indexFromXY(x, y)] |= (((int)dir)<<8);
41  uint32_t val = (((int)dir)<<16);
42  if (local)
43  points[indexFromXY(x, y)] |= val;
44  else
45  points[indexFromXY(x, y)] &= (~val);
46 }
47 
48 int GridData::ReMove(unsigned index, moveDir dir)
49 {
50  assert(index < gSectorSize*gSectorSize);
51  int cnt = 0;
52  if (points[index]&(((int)dir)<<8))
53  cnt = 1;
54  points[index] &= ~(((int)dir)<<8);
55  return cnt;
56 }
57 
58 void GridData::ReMove(unsigned int x, unsigned int y, moveDir dir)
59 {
60  if ((x >= gSectorSize) || (y >= gSectorSize))
61  return;
62  uint16_t val = (((int)dir)<<8);
63  points[indexFromXY(x, y)] &= (~val);
64 }
65 
66 uint8_t GridData::GetMoves(int x, int y) const
67 {
68  return (points[indexFromXY(x, y)]>>8)&0xFF;
69 }
70 
71 uint8_t GridData::GetMoves(int offset) const
72 {
73  return (points[offset]>>8)&0xFF;
74 }
75 
76 uint8_t GridData::GetMoveLocality(int x, int y) const
77 {
78  return (points[indexFromXY(x, y)]>>16)&0xFF;
79 }
80 
81 uint8_t GridData::GetMoveLocality(int offset) const
82 {
83  return (points[offset]>>16)&0xFF;
84 }
85 
86 
87 void GridData::ClearMoves(int x, int y)
88 {
89  points[indexFromXY(x, y)] &= 0xFFFF00FF;
90 }
91 
92 bool GridData::AddPoint(int x, int y, int height)
93 {
94  SetHeightOffset(x, y, height);
95  return true;
96 }
97 
98 void GridData::RemovePoint(int x, int y)
99 {
100  points[indexFromXY(x, y)] = points[indexFromXY(x, y)]|(kUnpassableHeight<<3);
101  //SetHeightOffset(x, y, kUnpassableHeight);
102 }
103 
104 bool GridData::IsPointPassable(unsigned int x, unsigned int y) const
105 {
106  if ((x >= gSectorSize) || (y >= gSectorSize))
107  return false;
108  return ((points[indexFromXY(x, y)]>>3)&0x1F)!=kUnpassableHeight;
109 }
110 
111 bool GridData::CanPass(unsigned int x, unsigned int y, int offsetx, int offsety) const
112 {
113  return (IsPointPassable(x, y) && IsPointPassable(x+offsetx, y+offsety) &&
114  abs(GetHeightOffset(x, y)-GetHeightOffset(x+offsetx, y+offsety)) <= 1);
115 }
116 
117 
118 int GridData::GetHeightOffset(int offset) const
119 {
120  return (points[offset]>>3)&0x1F;
121 }
122 
123 int GridData::GetHeightOffset(unsigned int x, unsigned int y) const
124 {
125  if ((x >= gSectorSize) || (y >= gSectorSize))
126  return 0x1F;
127  return (points[indexFromXY(x, y)]>>3)&0x1F;
128 }
129 
130 void GridData::SetHeightOffset(int offset, int height)
131 {
132  assert(height < 31 && height >= 0);
133  points[offset] = (points[offset]&0xFF07)|height<<3;
134  // return points[indexFromXY(x, y)]>>4;
135 }
136 
137 void GridData::SetHeightOffset(int x, int y, int height)
138 {
139  assert(height < 31 && height >= 0);
140  points[indexFromXY(x, y)] = (points[indexFromXY(x, y)]&0xFF07)|height<<3;
141 // return points[indexFromXY(x, y)]>>4;
142 }
143 
144 int GridData::GetBlocked(int x, int y)
145 {
146  return points[indexFromXY(x, y)]&7;
147 }
148 
149 void GridData::AddBlocked(int x, int y)
150 {
151  int curr = points[indexFromXY(x, y)]&7;
152  if (curr < 7)
153  points[indexFromXY(x, y)]++;
154 }
155 
156 void GridData::SubtractBlocked(int x, int y)
157 {
158  int curr = points[indexFromXY(x, y)]&7;
159  if (curr > 0)
160  points[indexFromXY(x, y)]--;
161 }
162 
163 int GridData::LabelAreas(std::vector<int> &labels, std::vector<int> &counts, std::vector<int> &heights)
164 {
165  labels.resize(gSectorSize*gSectorSize);
166  heights.resize(gSectorSize*gSectorSize);
167  counts.resize(0);
168  for (unsigned int x = 0; x < gSectorSize*gSectorSize; x++)
169  labels[x] = -1;
170  int nextID = 0;
171  for (unsigned int x = 0; x < gSectorSize*gSectorSize; x++)
172  {
173  int height = GetHeightOffset(x);
174  heights[x] = height;
175  if ((labels[x] == -1) && (height != kUnpassableHeight))
176  {
177  counts.push_back(BFS(labels, x, nextID));
178  nextID++;
179  }
180  }
181  return nextID;
182 }
183 
184 int GridData::BFS(std::vector<int> &labels, int offset, int label)
185 {
186  static std::vector<int> q;
187  q.resize(0);
188  q.push_back(offset);
189  int cnt = 0;
190  while (q.size() != 0)
191  {
192  int nextLoc = q.back();
193  q.pop_back();
194  if (labels[nextLoc] != -1)
195  {
196  assert(labels[nextLoc] == label);
197  continue;
198  }
199  cnt++;
200  labels[nextLoc] = label;
201  int height = GetHeightOffset(nextLoc);
202  if (nextLoc > gSectorSize)
203  {
204  if ((labels[nextLoc-gSectorSize] == -1) &&
205  (abs(GetHeightOffset(nextLoc-gSectorSize)-height) <= 1))
206  q.push_back(nextLoc-gSectorSize);
207  }
208  if (nextLoc%gSectorSize != 0)
209  {
210  if ((labels[nextLoc-1] == -1) &&
211  (abs(GetHeightOffset(nextLoc-1)-height) <= 1))
212  q.push_back(nextLoc-1);
213  }
214  if ((nextLoc%gSectorSize) != gSectorSize-1)
215  {
216  if ((labels[nextLoc+1] == -1) &&
217  (abs(GetHeightOffset(nextLoc+1)-height) <= 1))
218  q.push_back(nextLoc+1);
219  }
220  if ((nextLoc < gSectorSize*gSectorSize-gSectorSize) != 0)
221  {
222  if ((labels[nextLoc+gSectorSize] == -1) &&
223  (abs(GetHeightOffset(nextLoc+gSectorSize)-height) <= 1))
224  q.push_back(nextLoc+gSectorSize);
225  }
226  }
227  return cnt;
228 }
229 
230 // at the top of regions we have:
231 // [8 bits] last edge
232 // [8 bits] center location
233 // [16 bits] grid location
234 // [8 bits] base height
235 // [8 bits] # points in region
236 // [8 bits] # number partially blocked points
237 
238 // each edge has 16 bits
239 // 3 bits direction
240 // 5 bits cost(?)
241 // 8 bits target region
242 
243 //int RegionData::GetRegionEdgeCount(int region)
244 //{
245 // loc = data->at(7*region);
246 // if (region > 1)
247 // loc -= data->at(7*(region-1));
248 // return loc;
249 //}
250 //
251 //int RegionData::GetRegionGridIndex(int region)
252 //{
253 // return (data->at(7*region+2)<<8)|data->at(7*region+3);
254 //}
255 //
256 //int RegionData::GetRegionEdge(int region, int edge)
257 //{
259 //}
260 //
261 //int RegionData::GetRegionBaseHeight(int region)
262 //{
263 //}
264 //
265 //void RegionData::GetRegionCenter(int region, int &x, int &y)
266 //{
267 //}
268 //
269 //int RegionData::GetRegionPoints(int region)
270 //{
271 //}
272 //
273 //int RegionData::GetRegionBlocked(int region)
274 //{
275 //}
276 
277 bool RegionData::LowerBase()
278 {
279  int maxHeight = 0;
280  for (int x = 0; x < gSectorSize*gSectorSize; x++)
281  {
282  int val = grid.GetHeightOffset(x);
283  if ((val != kUnpassableHeight) && (val > maxHeight))
284  maxHeight = val;
285  }
286  if (maxHeight < 30)
287  {
288  baseHeight--;
289  for (int x = 0; x < gSectorSize*gSectorSize; x++)
290  {
291  int val = grid.GetHeightOffset(x);
292  if (val != kUnpassableHeight)
293  grid.SetHeightOffset(x, val+1);
294  }
295  return true;
296  }
297  return false;
298 }
299 
300 // points passed in local region coordinates
301 bool RegionData::CanAddPoint(int x, int y, int z)
302 {
303  // check max height and other sanity checks
304  if (pointCount != 0)
305  {
306  if (z-baseHeight > 30)
307  return false;
308  }
309  if (grid.IsPointPassable(x, y))
310  return false;
311  // check if next to another passable point
312  if ((grid.IsPointPassable(x+1, y ) && abs(grid.GetHeightOffset(x+1, y )-(z-baseHeight)) < 2) ||
313  (grid.IsPointPassable(x-1, y ) && abs(grid.GetHeightOffset(x-1, y )-(z-baseHeight)) < 2) ||
314  (grid.IsPointPassable(x , y-1) && abs(grid.GetHeightOffset(x , y-1)-(z-baseHeight)) < 2) ||
315  (grid.IsPointPassable(x , y+1) && abs(grid.GetHeightOffset(x , y+1)-(z-baseHeight)) < 2))
316  {
317  if (z < baseHeight)
318  return LowerBase();
319  return true;
320  }
321  return false;
322 
323  // if region does not exist, create it & add point (done)
324 
325  // if region exists, check if neighbor is on grid
326 
327  // if not, create new region & add point (done)
328 
329  // if point is blocked, create new region & add connections (done)
330 }
331 
332 bool RegionData::AddPoint(int x, int y, int z)
333 {
334  if (pointCount == 0)
335  {
336  baseHeight = z;
337  centerLocation = y*gSectorSize+x;
338  }
339  else {
340  RedoCenterLocation();
341  // int newx=0, newy=0, cnt=0;
342 // for (int t = 0; t < gSectorSize*gSectorSize; t++)
343 // {
344 // if (grid.GetHeightOffset(t) != kUnpassableHeight)
345 // {
346 // int tmpx, tmpy;
347 // xyFromIndex(t, tmpx, tmpy);
348 // newx += tmpx;
349 // newy += tmpy;
350 // cnt++;
351 // }
352 // }
353 // centerLocation = indexFromXY(newx/cnt, newy/cnt);
354  }
355  pointCount++;
356  //int offset = indexFromXY(x, y);
357  return grid.AddPoint(x, y, z-baseHeight);
358 }
359 
360 void RegionData::RedoCenterLocation()
361 {
362  int newx=0, newy=0, cnt=0;
363  for (int t = 0; t < gSectorSize*gSectorSize; t++)
364  {
365  if (grid.GetHeightOffset(t) != kUnpassableHeight)
366  {
367  int tmpx, tmpy;
368  xyFromIndex(t, tmpx, tmpy);
369  newx += tmpx;
370  newy += tmpy;
371  cnt++;
372  }
373  }
374  if (cnt != 0)
375  centerLocation = indexFromXY(newx/cnt, newy/cnt);
376 }
377 
378 void RegionData::AddEdge(EdgeData &e)
379 {
380  for (unsigned int x = 0; x < edges.size(); x++)
381  {
382  if ((e.sector == edges[x].sector) && (e.region == edges[x].region))
383  {
384  edges[x].support += e.support;
385  return;
386  }
387  }
388  edges.push_back(e);
389 }
390 
391 void RegionData::RemoveEdge(EdgeData &e)
392 {
393  for (unsigned int x = 0; x < edges.size(); x++)
394  {
395  if ((e.sector == edges[x].sector) && (e.region == edges[x].region))
396  {
397  edges[x].support -= e.support;
398  if (edges[x].support == 0)
399  {
400  edges[x] = edges.back();
401  edges.resize(edges.size()-1);
402  }
403  return;
404  }
405  }
406 }
407 
408 
409 bool SectorData::AddPoint(int x, int y, int z)
410 {
411  int regionX = x%gSectorSize;
412  int regionY = y%gSectorSize;
413  //int addedTo = -1;
414  for (unsigned int t = 0; t < regions.size(); t++)
415  {
416  if (regions[t].CanAddPoint(regionX, regionY, z))
417  {
418  // don't know how to handle failure
419  assert(regions[t].AddPoint(regionX, regionY, z));
420  //addedTo = t;
421  return true;
422  }
423  else {
424 // regions[t].AddInterRegionEdges(regionX, regionY);
425  }
426  }
427  regions.resize(regions.size()+1);
428  return regions.back().AddPoint(regionX, regionY, z);
429 }
430 
431 bool SectorData::RemovePoint(int x, int y, int z)
432 {
433  int regionX = x%gSectorSize;
434  int regionY = y%gSectorSize;
435  for (unsigned int t = 0; t < regions.size(); t++)
436  {
437  if (regions[t].grid.GetHeightOffset(regionX, regionY) + regions[t].baseHeight == z)
438  {
439  regions[t].grid.RemovePoint(regionX, regionY);
440  return true;
441  }
442  }
443  return false;
444 }
445 
446 Map3DGrid::Map3DGrid(Map *map, int theSectorSize)
447 {
448  drawGrid = false;
449  mWidth = map->GetMapWidth();
450  mHeight = map->GetMapHeight();
451  gSectorSize = theSectorSize;
452 // gInvSectorSize = 1.0/gSectorSize;
453  mXSectors = ceil((double)mWidth/(double)gSectorSize);
454  mYSectors = ceil((double)mHeight/(double)gSectorSize);
455  sectors.resize(mXSectors*mYSectors);
456  AddMap(map, 0);
457 }
458 
459 Map3DGrid::Map3DGrid(int width, int height, int theSectorSize)
460 :mWidth(width), mHeight(height)
461 {
462  drawGrid = false;
463  gSectorSize = theSectorSize;
464  mXSectors = ceil((double)width/(double)gSectorSize);
465  mYSectors = ceil((double)height/(double)gSectorSize);
466  sectors.resize(mXSectors*mYSectors);
467 }
468 
469 
470 void Map3DGrid::AddMap(Map *map, int elevation)
471 {
472  std::vector<bool> visited(map->GetMapWidth()*map->GetMapHeight());
473 
474  for (unsigned int loc = 0; loc < visited.size(); loc++)
475  {
476  if (!visited[loc] && (map->GetTerrainType(loc%map->GetMapWidth(), loc/map->GetMapWidth())>>terrainBits) == (kGround>>terrainBits))
477  {
478  AddMapPoints(map, visited, loc%map->GetMapWidth(), loc/map->GetMapWidth(), elevation);
479  }
480  }
481 }
482 
483 void Map3DGrid::AddMapPoints(Map *map, std::vector<bool> &visited, int x, int y, int elevation)
484 {
485  std::deque<int> nextx;
486  std::deque<int> nexty;
487 
488  nextx.push_back(x);
489  nexty.push_back(y);
490 
491  int sector = GetSector(x, y);
492  int xLoc, yLoc;
493  while (nextx.size() > 0)
494  {
495  xLoc = nextx.front();
496  yLoc = nexty.front();
497  nextx.pop_front();
498  nexty.pop_front();
499 
500  if (visited[yLoc*map->GetMapWidth()+xLoc])
501  continue;
502  if (GetSector(xLoc, yLoc) != sector)
503  continue;
504 
505  visited[yLoc*map->GetMapWidth()+xLoc] = true;
506  AddPoint(xLoc, yLoc, elevation);
507 
508  if (map->GetTerrainType(xLoc+1, yLoc)>>terrainBits == (kGround>>terrainBits))
509  {
510  nextx.push_back(xLoc+1);
511  nexty.push_back(yLoc);
512  }
513  if (map->GetTerrainType(xLoc-1, yLoc)>>terrainBits == (kGround>>terrainBits))
514  {
515  nextx.push_back(xLoc-1);
516  nexty.push_back(yLoc);
517  }
518  if (map->GetTerrainType(xLoc, yLoc+1)>>terrainBits == (kGround>>terrainBits))
519  {
520  nextx.push_back(xLoc);
521  nexty.push_back(yLoc+1);
522  }
523  if (map->GetTerrainType(xLoc, yLoc-1)>>terrainBits == (kGround>>terrainBits))
524  {
525  nextx.push_back(xLoc);
526  nexty.push_back(yLoc-1);
527  }
528  }
529 }
530 
531 void Map3DGrid::GetSuccessors(const state3d &nodeID, std::vector<state3d> &neighbors) const
532 {
533  if (nodeID.GetOffset() != -1) // on the actual grid
534  {
535  static const moveDir m[8] = {kWest, kEast, kNorth, kSouth, kNorthEast, kNorthWest, kSouthEast, kSouthWest};
536  moveDir dirs = (moveDir)sectors[nodeID.GetSector()].regions[nodeID.GetRegion()].grid.GetMoves(nodeID.GetOffset());
537  //uint8_t local = (moveDir)sectors[nodeID.GetSector()].regions[nodeID.GetRegion()].grid.GetMoveLocality(nodeID.GetOffset());
538  action3d a;
539  state3d s;
540  a.destRegion = 0xFF;
541  neighbors.resize(0);
542 
543  int x = -1, y, z;
544 
545  for (int t = 0; t < 8; t++)
546  {
547  if (dirs & m[t])
548  {
549  s = nodeID;
550  if ((sectors[nodeID.GetSector()].regions.size() == 1) &&
551  (nodeID.GetOffset() >= gSectorSize) && (nodeID.GetOffset() < gSectorSize*gSectorSize-gSectorSize) &&
552  ((nodeID.GetOffset()%gSectorSize) != 0) && (nodeID.GetOffset()%gSectorSize) != gSectorSize-1)
553  //if (0 && local & m[t])// && ((dirs^local) == 0))
554  {
555  switch (m[t])
556  {
557  case kWest:
558  { s.offset--; break; }
559  case kEast:
560  { s.offset++; break; }
561  case kNorth:
562  { s.offset-=gSectorSize; break; }
563  case kSouth:
564  { s.offset+=gSectorSize; break; }
565  case kNorthEast:
566  { s.offset=s.offset-gSectorSize+1; break; }
567  case kNorthWest:
568  { s.offset=s.offset-gSectorSize-1; break; }
569  case kSouthEast:
570  { s.offset=s.offset+gSectorSize+1; break; }
571  case kSouthWest:
572  { s.offset=s.offset+gSectorSize-1; break; }
573  }
574  }
575  else {
576  if (x == -1)
577  GetXYZFromState(nodeID, x, y, z);
578 
579  switch (m[t])
580  {
581  case kWest:
582  GetStateFromXYZ(s, x-1, y, z); break;
583  case kEast:
584  GetStateFromXYZ(s, x+1, y, z); break;
585  case kNorth:
586  GetStateFromXYZ(s, x, y-1, z); break;
587  case kSouth:
588  GetStateFromXYZ(s, x, y+1, z); break;
589  case kNorthEast:
590  GetStateFromXYZ(s, x+1, y-1, z); break;
591  case kNorthWest:
592  GetStateFromXYZ(s, x-1, y-1, z); break;
593  case kSouthEast:
594  GetStateFromXYZ(s, x+1, y+1, z); break;
595  case kSouthWest:
596  GetStateFromXYZ(s, x-1, y+1, z); break;
597  }
598  }
599  neighbors.push_back(s);
600  }
601  }
602 // static std::vector<action3d> acts;
603 // GetActions(nodeID, acts);
604 // neighbors.resize(0);
605 //
606 // if ((nodeID.GetOffset() >= gSectorSize) && (nodeID.GetOffset() < gSectorSize*gSectorSize-gSectorSize) &&
607 // ((nodeID.GetOffset()%gSectorSize) != 0) && (nodeID.GetOffset()%gSectorSize) != gSectorSize-1)
608 // {
609 // if (sectors[nodeID.GetSector()].regions.size() == 1)
610 // {
611 // for (unsigned int t = 0; t < acts.size(); t++)
612 // {
613 // state3d s(nodeID);
614 // switch (acts[t].direction)
615 // {
616 // case kWest:
617 // { s.offset--; break; }
618 // case kEast:
619 // { s.offset++; break; }
620 // case kNorth:
621 // { s.offset-=gSectorSize; break; }
622 // case kSouth:
623 // { s.offset+=gSectorSize; break; }
624 // case kNorthEast:
625 // { s.offset=s.offset-gSectorSize+1; break; }
626 // case kNorthWest:
627 // { s.offset=s.offset-gSectorSize-1; break; }
628 // case kSouthEast:
629 // { s.offset=s.offset+gSectorSize+1; break; }
630 // case kSouthWest:
631 // { s.offset=s.offset+gSectorSize-1; break; }
632 // }
633 // // state3d s = nodeID;
634 // // ApplyAction(s, acts[x]);
635 // neighbors.push_back(s);
636 // }
637 // }
638 // else {
639 // // just generate and check if neighbor is on the same grid with an appropriate height
640 // // if so we're done
641 // int h2 = sectors[nodeID.GetSector()].regions[nodeID.GetRegion()].grid.GetHeightOffset(nodeID.GetOffset());
642 // int x = -1, y, z;
643 // for (unsigned int t = 0; t < acts.size(); t++)
644 // {
645 // state3d s(nodeID);
646 // switch (acts[t].direction)
647 // {
648 // case kWest:
649 // {
650 // int h1 = sectors[s.GetSector()].regions[s.GetRegion()].grid.GetHeightOffset(s.GetOffset()-1);
651 // if (abs(h1-h2)<=1 && (h1 != kUnpassableHeight))
652 // {
653 // s.offset--;
654 // }
655 // else {
656 // if (x == -1)
657 // GetXYZFromState(nodeID, x, y, z);
658 // GetStateFromXYZ(s, x-1, y, z);
659 // }
660 // break;
661 // }
662 // case kEast:
663 // {
664 // int h1 = sectors[s.GetSector()].regions[s.GetRegion()].grid.GetHeightOffset(s.GetOffset()+1);
665 // if (abs(h1-h2)<=1 && (h1 != kUnpassableHeight))
666 // {
667 // s.offset++;
668 // }
669 // else {
670 // if (x == -1)
671 // GetXYZFromState(nodeID, x, y, z);
672 // GetStateFromXYZ(s, x+1, y, z);
673 // }
674 // break;
675 //
677 // }
678 // case kNorth:
679 // {
680 // int h1 = sectors[s.GetSector()].regions[s.GetRegion()].grid.GetHeightOffset(s.GetOffset()-gSectorSize);
681 // if (abs(h1-h2)<=1 && (h1 != kUnpassableHeight))
682 // {
683 // s.offset-=gSectorSize;
684 // }
685 // else {
686 // if (x == -1)
687 // GetXYZFromState(nodeID, x, y, z);
688 // GetStateFromXYZ(s, x, y-1, z);
689 // }
690 // break;
691 // //s.offset-=gSectorSize; break;
692 // }
693 // case kSouth:
694 // {
695 // int h1 = sectors[s.GetSector()].regions[s.GetRegion()].grid.GetHeightOffset(s.GetOffset()+gSectorSize);
696 // if (abs(h1-h2)<=1 && (h1 != kUnpassableHeight))
697 // {
698 // s.offset+=gSectorSize;
699 // }
700 // else {
701 // if (x == -1)
702 // GetXYZFromState(nodeID, x, y, z);
703 // GetStateFromXYZ(s, x, y+1, z);
704 // }
705 // break;
706 // //s.offset+=gSectorSize; break;
707 // }
708 // case kNorthEast:
709 // { s.offset=s.offset-gSectorSize+1; break; }
710 // case kNorthWest:
711 // { s.offset=s.offset-gSectorSize-1; break; }
712 // case kSouthEast:
713 // { s.offset=s.offset+gSectorSize+1; break; }
714 // case kSouthWest:
715 // { s.offset=s.offset+gSectorSize-1; break; }
716 // }
717 // // state3d s = nodeID;
718 // // ApplyAction(s, acts[x]);
719 // neighbors.push_back(s);
720 // }
721 // }
722 // }
723 // else {
724 // int x, y, z;
725 // GetXYZFromState(nodeID, x, y, z);
726 // for (unsigned int t = 0; t < acts.size(); t++)
727 // {
728 // state3d s(nodeID);
729 // switch (acts[t].direction)
730 // {
731 // case kWest:
732 // // if (sectors[nodeID.GetSector()].regions[nodeID.GetRegion()].grid.CanPass(x, y, -1, 0))
733 // // { s.offset--; break; }
734 // GetStateFromXYZ(s, x-1, y, z); break;
735 // case kEast:
736 // // if (sectors[nodeID.GetSector()].regions[nodeID.GetRegion()].grid.CanPass(x, y, +1, 0))
737 // // { s.offset++; break; }
738 // GetStateFromXYZ(s, x+1, y, z); break;
739 // case kNorth:
740 // // if (sectors[nodeID.GetSector()].regions[nodeID.GetRegion()].grid.CanPass(x, y, 0, -1))
741 // // { s.offset-=gSectorSize; break; }
742 // GetStateFromXYZ(s, x, y-1, z); break;
743 // case kSouth:
744 // // if (sectors[nodeID.GetSector()].regions[nodeID.GetRegion()].grid.CanPass(x, y, 0, 1))
745 // // { s.offset+=gSectorSize; break; }
746 // GetStateFromXYZ(s, x, y+1, z); break;
747 // case kNorthEast:
748 // // if (sectors[nodeID.GetSector()].regions[nodeID.GetRegion()].grid.CanPass(x, y, 1, -1))
749 // // { s.offset=s.offset-gSectorSize+1; break; }
750 // GetStateFromXYZ(s, x+1, y-1, z); break;
751 // case kNorthWest:
752 // // if (sectors[nodeID.GetSector()].regions[nodeID.GetRegion()].grid.CanPass(x, y, -1, -1))
753 // // { s.offset=s.offset-gSectorSize-1; break; }
754 // GetStateFromXYZ(s, x-1, y-1, z); break;
755 // case kSouthEast:
756 // // if (sectors[nodeID.GetSector()].regions[nodeID.GetRegion()].grid.CanPass(x, y, 1, 1))
757 // // { s.offset=s.offset+gSectorSize+1; break; }
758 // GetStateFromXYZ(s, x+1, y+1, z); break;
759 // case kSouthWest:
760 // // if (sectors[nodeID.GetSector()].regions[nodeID.GetRegion()].grid.CanPass(x, y, -1, 1))
761 // // { s.offset=s.offset+gSectorSize-1; break; }
762 // GetStateFromXYZ(s, x-1, y+1, z); break;
763 // }
764 //
765 //
766 // // state3d s = nodeID;
767 // // ApplyAction(s, acts[x]);
768 // neighbors.push_back(s);
769 // }
770 // }
771  //moveDir = sectors[nodeID.GetSector()].regions[nodeID.GetRegion()].grid.GetMoves(nodeID.GetOffset());
772  }
773  else {
774  neighbors.resize(0);
775  unsigned int cnt = sectors[nodeID.GetSector()].regions[nodeID.GetRegion()].edges.size();
776  for (unsigned int x = 0; x < cnt; x++)
777  {
778  neighbors.push_back(state3d(sectors[nodeID.GetSector()].regions[nodeID.GetRegion()].edges[x].sector,
779  sectors[nodeID.GetSector()].regions[nodeID.GetRegion()].edges[x].region,
780  -1));
781  }
782  }
783 }
784 
785 void Map3DGrid::GetActions(const state3d &nodeID, std::vector<action3d> &actions) const
786 {
787  static const moveDir m[8] = {kWest, kEast, kNorth, kSouth, kNorthEast, kNorthWest, kSouthEast, kSouthWest};
788 
789  if (nodeID.GetOffset() != -1) // on the actual grid
790  {
791  actions.resize(0);
792  moveDir dirs = (moveDir)sectors[nodeID.GetSector()].regions[nodeID.GetRegion()].grid.GetMoves(nodeID.GetOffset());
793  action3d a;
794  a.destRegion = 0xFF;
795  for (int x = 0; x < 8; x++)
796  {
797  if (dirs & m[x])
798  {
799  a.direction = m[x];
800  actions.push_back(a);
801  }
802  }
803  }
804 }
805 
806 void Map3DGrid::ApplyAction(state3d &s, action3d a) const
807 {
808  // grid move
809  if (s.GetOffset() != -1)
810  {
811  int x, y, z;
812  GetXYZFromState(s, x, y, z);
813  switch (a.direction)
814  {
815  case kWest: x--; break;
816  case kEast: x++; break;
817  case kNorth: y--; break;
818  case kSouth: y++; break;
819  case kNorthEast: y--; x++; break;
820  case kNorthWest: y--; x--; break;
821  case kSouthEast: y++; x++; break;
822  case kSouthWest: y++; x--; break;
823  }
824  GetStateFromXYZ(s, x, y, z);
825  }
826  else { // abstraction move
827  s.Init(a.destSector, a.destRegion, -1);
828  }
829 }
830 
831 double Map3DGrid::HCost(const state3d &node1, const state3d &node2) const
832 {
833  assert(false);
834  return 1;
835 }
836 
837 double Map3DGrid::GCost(const state3d &node1, const state3d &node2) const
838 {
839  assert(false);
840  return 1;
841 }
842 
843 double Map3DGrid::GCost(const state3d &node, const action3d &act) const
844 {
845  assert(false);
846  return 1;
847 }
848 
849 bool Map3DGrid::GoalTest(const state3d &node, const state3d &goal) const
850 {
851  return (node == goal);
852 }
853 
854 
855 uint64_t Map3DGrid::GetStateHash(const state3d &node) const
856 {
857  assert(false);
858  return 0;
859 }
860 
861 uint64_t Map3DGrid::GetActionHash(action3d act) const
862 {
863  assert(false);
864  return 0;
865 }
866 
867 bool Map3DGrid::AddPoint(int x, int y, int z)
868 {
869  if (x >= mWidth)
870  return false;
871  if (y >= mHeight)
872  return false;
873  if ((x < 0) || (y < 0))
874  return false;
875 
876  bool result = sectors[GetSector(x, y)].AddPoint(x, y, z);
877 
878  state3d neighborhood[9];
879  int found[9];
880 
881  found[0] = FindNearState(x-1, y-1, z, neighborhood[0]);
882  if (found[0] != -1)
883  {
884  int x1, y1;
885  GetXYFromState(neighborhood[0], x1, y1);
886  assert(x1 == x-1);
887  assert(y1 == y-1);
888  }
889  found[1] = FindNearState(x , y-1, z, neighborhood[1]);
890  if (found[1] != -1)
891  {
892  int x1, y1;
893  GetXYFromState(neighborhood[1], x1, y1);
894  assert(x1 == x);
895  assert(y1 == y-1);
896  }
897  found[2] = FindNearState(x+1, y-1, z, neighborhood[2]);
898  if (found[2] != -1)
899  {
900  int x1, y1;
901  GetXYFromState(neighborhood[2], x1, y1);
902  assert(x1 == x+1);
903  assert(y1 == y-1);
904  }
905 
906  found[3] = FindNearState(x-1, y, z, neighborhood[3]);
907  if (found[3] != -1)
908  {
909  int x1, y1;
910  GetXYFromState(neighborhood[3], x1, y1);
911  assert(x1 == x-1);
912  assert(y1 == y);
913  }
914  found[4] = FindNearState(x , y, z, neighborhood[4]);
915  if (found[4] != -1)
916  {
917  int x1, y1;
918  GetXYFromState(neighborhood[4], x1, y1);
919  assert(x1 == x);
920  assert(y1 == y);
921  }
922  found[5] = FindNearState(x+1, y, z, neighborhood[5]);
923  if (found[5] != -1)
924  {
925  int x1, y1;
926  GetXYFromState(neighborhood[5], x1, y1);
927  assert(x1 == x+1);
928  assert(y1 == y);
929  }
930 
931  found[6] = FindNearState(x-1, y+1, z, neighborhood[6]);
932  if (found[6] != -1)
933  {
934  int x1, y1;
935  GetXYFromState(neighborhood[6], x1, y1);
936  assert(x1 == x-1);
937  assert(y1 == y+1);
938  }
939  found[7] = FindNearState(x , y+1, z, neighborhood[7]);
940  if (found[7] != -1)
941  {
942  int x1, y1;
943  GetXYFromState(neighborhood[7], x1, y1);
944  assert(x1 == x);
945  assert(y1 == y+1);
946  }
947  found[8] = FindNearState(x+1, y+1, z, neighborhood[8]);
948  if (found[8] != -1)
949  {
950  int x1, y1;
951  GetXYFromState(neighborhood[8], x1, y1);
952  assert(x1 == x+1);
953  assert(y1 == y+1);
954  }
955 
956  assert(found[4] != -1);
957 
958  // connect horizontals
959  if (found[1] != -1)
960  {
961 // printf("Add 4-1\n");
962  AddEdge(neighborhood[4], neighborhood[1]);
963  }
964  if (found[3] != -1)
965  {
966 // printf("Add 4-3 [%d-%d]\n", found[4], found[3]);
967  AddEdge(neighborhood[4], neighborhood[3]);
968  }
969  if (found[5] != -1)
970  {
971 // printf("Add 4-5\n");
972  AddEdge(neighborhood[4], neighborhood[5]);
973  }
974  if (found[7] != -1)
975  {
976 // printf("Add 4-7\n");
977  AddEdge(neighborhood[4], neighborhood[7]);
978  }
979 
980  // connect diagonals
981  if ((found[0] != -1) && (found[1] != -1) && (found[3] != -1) &&
982  (abs(found[0]-found[1]) <= 1) && (abs(found[0]-found[3]) <= 1))
983  {
984  AddEdge(neighborhood[4], neighborhood[0]);
985  if (abs(found[1]-found[3]) <= 1)
986  AddEdge(neighborhood[1], neighborhood[3]);
987  }
988 
989  if ((found[1] != -1) && (found[2] != -1) && (found[5] != -1) &&
990  (abs(found[1]-found[2]) <= 1) && (abs(found[2]-found[5]) <= 1))
991  {
992  AddEdge(neighborhood[4], neighborhood[2]);
993  if (abs(found[1]-found[5]) <= 1)
994  AddEdge(neighborhood[1], neighborhood[5]);
995  }
996 
997  if ((found[3] != -1) && (found[6] != -1) && (found[7] != -1) &&
998  (abs(found[3]-found[6]) <= 1) && (abs(found[6]-found[7]) <= 1))
999  {
1000  AddEdge(neighborhood[4], neighborhood[6]);
1001  if (abs(found[3]-found[7]) <= 1)
1002  AddEdge(neighborhood[3], neighborhood[7]);
1003  }
1004 
1005  if ((found[5] != -1) && (found[8] != -1) && (found[7] != -1) &&
1006  (abs(found[5]-found[8]) <= 1) && (abs(found[8]-found[7]) <= 1))
1007  {
1008  AddEdge(neighborhood[4], neighborhood[8]);
1009  if (abs(found[5]-found[7]) <= 1)
1010  AddEdge(neighborhood[5], neighborhood[7]);
1011  }
1012 
1013  return result;
1014 }
1015 
1016 void Map3DGrid::AddEdge(int sec1, int reg1, int sec2, int reg2, int weight)
1017 {
1018 // printf("Adding edge between sec/reg %d/%d and %d/%d\n", sec1, reg1, sec2, reg2);
1019  assert(sectors.size() > sec1);
1020  assert(sectors.size() > sec2);
1021  assert(reg1 != -1);
1022  assert(reg2 != -1);
1023  EdgeData e1(sec1, reg1, weight);
1024  EdgeData e2(sec2, reg2, weight);
1025  sectors[sec1].regions[reg1].AddEdge(e2);
1026  sectors[sec2].regions[reg2].AddEdge(e1);
1027 }
1028 
1029 void Map3DGrid::AddEdge(state3d &from, state3d &to)
1030 {
1031  assert(from.GetOffset() != -1);
1032  assert(from.GetSector() != -1);
1033  assert(from.GetRegion() != -1);
1034  assert(to.GetOffset() != -1);
1035  assert(to.GetSector() != -1);
1036  assert(to.GetRegion() != -1);
1037  if ((from.sector == to.sector) && (from.region == to.region))
1038  {
1039  AddGridEdge(from, to, true);
1040  return;
1041  }
1042  else if (from.sector == to.sector) // but different regions
1043  {
1044 // printf("Adding between %d/%d/%d and %d/%d/%d\n",
1045 // from.GetSector(), from.GetRegion(), from.GetOffset(),
1046 // to.GetSector(), to.GetRegion(), to.GetOffset());
1047  int cnt = AddGridEdge(from, to, false);
1048  AddEdge(from.sector, from.region, to.sector, to.region, cnt);
1049  }
1050  else {
1051 // printf("Adding between %d/%d/%d and %d/%d/%d\n",
1052 // from.GetSector(), from.GetRegion(), from.GetOffset(),
1053 // to.GetSector(), to.GetRegion(), to.GetOffset());
1054  int cnt = AddSectorEdge(from, to);
1055  AddEdge(from.sector, from.region, to.sector, to.region, cnt);
1056  }
1057 }
1058 
1059 int Map3DGrid::AddGridEdge(state3d &from, state3d &to, bool local)
1060 {
1061  int val = from.offset-to.offset;
1062  if (val == 1)
1063  return sectors[from.sector].regions[from.region].grid.AddMove(from.offset, kWest, local)+
1064  sectors[to.sector].regions[to.region].grid.AddMove(to.offset, kEast, local);
1065  if (val == -1)
1066  return sectors[from.sector].regions[from.region].grid.AddMove(from.offset, kEast, local)+
1067  sectors[to.sector].regions[to.region].grid.AddMove(to.offset, kWest, local);
1068  if (val == gSectorSize)
1069  return sectors[from.sector].regions[from.region].grid.AddMove(from.offset, kNorth, local)+
1070  sectors[to.sector].regions[to.region].grid.AddMove(to.offset, kSouth, local);
1071  if (val == -gSectorSize)
1072  return sectors[from.sector].regions[from.region].grid.AddMove(from.offset, kSouth, local)+
1073  sectors[to.sector].regions[to.region].grid.AddMove(to.offset, kNorth, local);
1074  // diagonal moves
1075  if (val == gSectorSize+1)
1076  return sectors[from.sector].regions[from.region].grid.AddMove(from.offset, kNorthWest, local)+
1077  sectors[to.sector].regions[to.region].grid.AddMove(to.offset, kSouthEast, local);
1078  if (val == gSectorSize-1)
1079  return sectors[from.sector].regions[from.region].grid.AddMove(from.offset, kNorthEast, local)+
1080  sectors[to.sector].regions[to.region].grid.AddMove(to.offset, kSouthWest, local);
1081  if (val == -gSectorSize+1)
1082  return sectors[from.sector].regions[from.region].grid.AddMove(from.offset, kSouthWest, local)+
1083  sectors[to.sector].regions[to.region].grid.AddMove(to.offset, kNorthEast, local);
1084  if (val == -gSectorSize-1)
1085  return sectors[from.sector].regions[from.region].grid.AddMove(from.offset, kSouthEast, local)+
1086  sectors[to.sector].regions[to.region].grid.AddMove(to.offset, kNorthWest, local);
1087  return 0;
1088 }
1089 
1090 int Map3DGrid::AddSectorEdge(state3d &from, state3d &to)
1091 {
1092  int x1, y1, x2, y2;
1093  GetXYFromState(from, x1, y1);
1094  GetXYFromState(to, x2, y2);
1095  int offsetDiff = (y1*mWidth+x1)-(y2*mWidth+x2);
1096  // cardinal moves
1097  if (offsetDiff == 1)
1098  {
1099  return sectors[from.sector].regions[from.region].grid.AddMove(from.offset, kWest, false)+
1100  sectors[to.sector].regions[to.region].grid.AddMove(to.offset, kEast, false);
1101  }
1102  else if (offsetDiff == -1)
1103  {
1104  return sectors[from.sector].regions[from.region].grid.AddMove(from.offset, kEast, false)+
1105  sectors[to.sector].regions[to.region].grid.AddMove(to.offset, kWest, false);
1106  }
1107  else if (offsetDiff == mWidth)
1108  {
1109  return sectors[from.sector].regions[from.region].grid.AddMove(from.offset, kNorth, false)+
1110  sectors[to.sector].regions[to.region].grid.AddMove(to.offset, kSouth, false);
1111  }
1112  else if (offsetDiff == -mWidth)
1113  {
1114  return sectors[from.sector].regions[from.region].grid.AddMove(from.offset, kSouth, false)+
1115  sectors[to.sector].regions[to.region].grid.AddMove(to.offset, kNorth, false);
1116  }
1117  // diagonal moves
1118  else if (offsetDiff == mWidth+1)
1119  {
1120  return sectors[from.sector].regions[from.region].grid.AddMove(from.offset, kNorthWest, false)+
1121  sectors[to.sector].regions[to.region].grid.AddMove(to.offset, kSouthEast, false);
1122  }
1123  else if (offsetDiff == mWidth-1)
1124  {
1125  return sectors[from.sector].regions[from.region].grid.AddMove(from.offset, kNorthEast, false)+
1126  sectors[to.sector].regions[to.region].grid.AddMove(to.offset, kSouthWest, false);
1127  }
1128  else if (offsetDiff == -mWidth+1)
1129  {
1130  return sectors[from.sector].regions[from.region].grid.AddMove(from.offset, kSouthWest, false)+
1131  sectors[to.sector].regions[to.region].grid.AddMove(to.offset, kNorthEast, false);
1132  }
1133  else if (offsetDiff == -mWidth-1)
1134  {
1135  return sectors[from.sector].regions[from.region].grid.AddMove(from.offset, kSouthEast, false)+
1136  sectors[to.sector].regions[to.region].grid.AddMove(to.offset, kNorthWest, false);
1137  }
1138  return 0;
1139 }
1140 
1141 bool Map3DGrid::RemovePoint(int x, int y, int z, bool split)
1142 {
1143  int theRegion = InternalRemovePoint(x, y, z);
1144  if (theRegion == -1)
1145  return false;
1146 
1147  if (!split)
1148  return true;
1149 
1150  // now check if we need to split the sector
1151  static std::vector<int> labels;
1152  static std::vector<int> counts;
1153  static std::vector<int> heights;
1154  int regions = sectors[GetSector(x, y)].regions[theRegion].grid.LabelAreas(labels, counts, heights);
1155  if (regions > 1)
1156  {
1157  printf("%d regions; split needed\n", regions);
1158  for (int t = 0; t < gSectorSize; t++)
1159  {
1160  for (int u = 0; u < gSectorSize; u++)
1161  {
1162  printf("%2d", labels[t*gSectorSize+u]);
1163  }
1164  printf("\n");
1165  }
1166  int basex = x-(x%gSectorSize);
1167  int basey = y-(y%gSectorSize);
1168  while (regions > 1)
1169  {
1170  int smallest = 0;
1171  // find smallest region
1172  for (int t = 1; t < counts.size(); t++)
1173  {
1174  if (counts[t] < counts[smallest])
1175  smallest = t;
1176  }
1177 
1178  // remove points from region
1179  for (unsigned int t = 0; t < gSectorSize*gSectorSize; t++)
1180  {
1181  if (labels[t] == smallest)
1182  InternalRemovePoint(basex+t%gSectorSize, basey + t/gSectorSize, heights[t]);
1183  }
1184 
1185  // re-add (will appear in new region)
1186  for (unsigned int t = 0; t < gSectorSize*gSectorSize; t++)
1187  {
1188  if (labels[t] == smallest)
1189  AddPoint(basex+t%gSectorSize, basey + t/gSectorSize, heights[t]);
1190  }
1191  regions--;
1192  }
1193  }
1194  return true;
1195 }
1196 
1197 // returns region of x/y/z point
1198 int Map3DGrid::InternalRemovePoint(int x, int y, int z)
1199 {
1200  // first remove all edges; THEN remove the actual point
1201  state3d neighborhood[9];
1202  int found[9];
1203 
1204 
1205  found[0] = FindNearState(x-1, y-1, z, neighborhood[0]);
1206  found[1] = FindNearState(x , y-1, z, neighborhood[1]);
1207  found[2] = FindNearState(x+1, y-1, z, neighborhood[2]);
1208 
1209  found[3] = FindNearState(x-1, y, z, neighborhood[3]);
1210  found[4] = FindNearState(x , y, z, neighborhood[4]);
1211  found[5] = FindNearState(x+1, y, z, neighborhood[5]);
1212 
1213  found[6] = FindNearState(x-1, y+1, z, neighborhood[6]);
1214  found[7] = FindNearState(x , y+1, z, neighborhood[7]);
1215  found[8] = FindNearState(x+1, y+1, z, neighborhood[8]);
1216 
1217  if (found[4] == -1)
1218  return -1;
1219  //assert(found[4] != -1);
1220 
1221  // connect horizontals
1222  if (found[1] != -1)
1223  RemoveEdge(neighborhood[4], neighborhood[1]);
1224  if (found[3] != -1)
1225  RemoveEdge(neighborhood[4], neighborhood[3]);
1226  if (found[5] != -1)
1227  RemoveEdge(neighborhood[4], neighborhood[5]);
1228  if (found[7] != -1)
1229  RemoveEdge(neighborhood[4], neighborhood[7]);
1230 
1231  // connect diagonals
1232  if ((found[0] != -1) && (found[1] != -1) && (found[3] != -1) &&
1233  (abs(found[0]-found[1]) <= 1) && (abs(found[0]-found[3]) <= 1))
1234  {
1235  RemoveEdge(neighborhood[4], neighborhood[0]);
1236  if (abs(found[1]-found[3]) <= 1)
1237  RemoveEdge(neighborhood[1], neighborhood[3]);
1238  }
1239 
1240  if ((found[1] != -1) && (found[2] != -1) && (found[5] != -1) &&
1241  (abs(found[1]-found[2]) <= 1) && (abs(found[2]-found[5]) <= 1))
1242  {
1243  RemoveEdge(neighborhood[4], neighborhood[2]);
1244  if (abs(found[1]-found[5]) <= 1)
1245  RemoveEdge(neighborhood[1], neighborhood[5]);
1246  }
1247 
1248  if ((found[3] != -1) && (found[6] != -1) && (found[7] != -1) &&
1249  (abs(found[3]-found[6]) <= 1) && (abs(found[6]-found[7]) <= 1))
1250  {
1251  RemoveEdge(neighborhood[4], neighborhood[6]);
1252  if (abs(found[3]-found[7]) <= 1)
1253  RemoveEdge(neighborhood[3], neighborhood[7]);
1254  }
1255 
1256  if ((found[5] != -1) && (found[8] != -1) && (found[7] != -1) &&
1257  (abs(found[5]-found[8]) <= 1) && (abs(found[8]-found[7]) <= 1))
1258  {
1259  RemoveEdge(neighborhood[4], neighborhood[8]);
1260  if (abs(found[5]-found[7]) <= 1)
1261  RemoveEdge(neighborhood[5], neighborhood[7]);
1262  }
1263 
1264  // actually remove point
1265  sectors[GetSector(x, y)].RemovePoint(x, y, z);
1266 
1267  sectors[neighborhood[4].GetSector()].regions[neighborhood[4].GetRegion()].RedoCenterLocation();
1268  return neighborhood[4].GetRegion();
1269 }
1270 
1271 void Map3DGrid::RemoveEdge(int sec1, int reg1, int sec2, int reg2, int weight)
1272 {
1273  EdgeData e1(sec1, reg1, weight);
1274  EdgeData e2(sec2, reg2, weight);
1275  sectors[sec1].regions[reg1].RemoveEdge(e2);
1276  sectors[sec2].regions[reg2].RemoveEdge(e1);
1277 }
1278 
1279 void Map3DGrid::RemoveEdge(state3d &from, state3d &to)
1280 {
1281  if ((from.sector == to.sector) && (from.region == to.region))
1282  {
1283  RemoveGridEdge(from, to);
1284  return;
1285  }
1286  else if (from.sector == to.sector) // but different regions
1287  {
1288  int cnt = RemoveGridEdge(from, to);
1289  RemoveEdge(from.sector, from.region, to.sector, to.region, cnt);
1290  }
1291  else {
1292  int cnt = RemoveSectorEdge(from, to);
1293  RemoveEdge(from.sector, from.region, to.sector, to.region, cnt);
1294  }
1295 }
1296 
1297 int Map3DGrid::RemoveGridEdge(state3d &from, state3d &to)
1298 {
1299  int val = from.offset-to.offset;
1300  if (val == 1)
1301  return sectors[from.sector].regions[from.region].grid.ReMove(from.offset, kWest)+
1302  sectors[to.sector].regions[to.region].grid.ReMove(to.offset, kEast);
1303  if (val == -1)
1304  return sectors[from.sector].regions[from.region].grid.ReMove(from.offset, kEast)+
1305  sectors[to.sector].regions[to.region].grid.ReMove(to.offset, kWest);
1306  if (val == gSectorSize)
1307  return sectors[from.sector].regions[from.region].grid.ReMove(from.offset, kNorth)+
1308  sectors[to.sector].regions[to.region].grid.ReMove(to.offset, kSouth);
1309  if (val == -gSectorSize)
1310  return sectors[from.sector].regions[from.region].grid.ReMove(from.offset, kSouth)+
1311  sectors[to.sector].regions[to.region].grid.ReMove(to.offset, kNorth);
1312  // diagonal moves
1313  if (val == gSectorSize+1)
1314  return sectors[from.sector].regions[from.region].grid.ReMove(from.offset, kNorthWest)+
1315  sectors[to.sector].regions[to.region].grid.ReMove(to.offset, kSouthEast);
1316  if (val == gSectorSize-1)
1317  return sectors[from.sector].regions[from.region].grid.ReMove(from.offset, kNorthEast)+
1318  sectors[to.sector].regions[to.region].grid.ReMove(to.offset, kSouthWest);
1319  if (val == -gSectorSize+1)
1320  return sectors[from.sector].regions[from.region].grid.ReMove(from.offset, kSouthWest)+
1321  sectors[to.sector].regions[to.region].grid.ReMove(to.offset, kNorthEast);
1322  if (val == -gSectorSize-1)
1323  return sectors[from.sector].regions[from.region].grid.ReMove(from.offset, kSouthEast)+
1324  sectors[to.sector].regions[to.region].grid.ReMove(to.offset, kNorthWest);
1325  assert(false);
1326  return 0;
1327 
1328 }
1329 
1330 int Map3DGrid::RemoveSectorEdge(state3d &from, state3d &to)
1331 {
1332  int x1, y1, x2, y2;
1333  GetXYFromState(from, x1, y1);
1334  GetXYFromState(to, x2, y2);
1335  int offsetDiff = (y1*mWidth+x1)-(y2*mWidth+x2);
1336  // cardinal moves
1337  if (offsetDiff == 1)
1338  {
1339  return sectors[from.sector].regions[from.region].grid.ReMove(from.offset, kWest)+
1340  sectors[to.sector].regions[to.region].grid.ReMove(to.offset, kEast);
1341  }
1342  else if (offsetDiff == -1)
1343  {
1344  return sectors[from.sector].regions[from.region].grid.ReMove(from.offset, kEast)+
1345  sectors[to.sector].regions[to.region].grid.ReMove(to.offset, kWest);
1346  }
1347  else if (offsetDiff == mWidth)
1348  {
1349  return sectors[from.sector].regions[from.region].grid.ReMove(from.offset, kNorth)+
1350  sectors[to.sector].regions[to.region].grid.ReMove(to.offset, kSouth);
1351  }
1352  else if (offsetDiff == -mWidth)
1353  {
1354  return sectors[from.sector].regions[from.region].grid.ReMove(from.offset, kSouth)+
1355  sectors[to.sector].regions[to.region].grid.ReMove(to.offset, kNorth);
1356  }
1357  // diagonal moves
1358  else if (offsetDiff == mWidth+1)
1359  {
1360  return sectors[from.sector].regions[from.region].grid.ReMove(from.offset, kNorthWest)+
1361  sectors[to.sector].regions[to.region].grid.ReMove(to.offset, kSouthEast);
1362  }
1363  else if (offsetDiff == mWidth-1)
1364  {
1365  return sectors[from.sector].regions[from.region].grid.ReMove(from.offset, kNorthEast)+
1366  sectors[to.sector].regions[to.region].grid.ReMove(to.offset, kSouthWest);
1367  }
1368  else if (offsetDiff == -mWidth+1)
1369  {
1370  return sectors[from.sector].regions[from.region].grid.ReMove(from.offset, kSouthWest)+
1371  sectors[to.sector].regions[to.region].grid.ReMove(to.offset, kNorthEast);
1372  }
1373  else if (offsetDiff == -mWidth-1)
1374  {
1375  return sectors[from.sector].regions[from.region].grid.ReMove(from.offset, kSouthEast)+
1376  sectors[to.sector].regions[to.region].grid.ReMove(to.offset, kNorthWest);
1377  }
1378  assert(false);
1379  return 0;
1380 }
1381 
1382 
1383 int Map3DGrid::FindNearState(int x, int y, int z, state3d &s) const
1384 {
1385  if ((x >= mWidth) || (x < 0) || (y >= mHeight) || (y < 0))
1386  return -1;
1387  int sect = GetSector(x, y);
1388  for (unsigned t = 0; t < sectors[sect].regions.size(); t++)
1389  {
1390  int height = sectors[sect].regions[t].grid.GetHeightOffset(x%gSectorSize, y%gSectorSize);
1391  if ((height != kUnpassableHeight) &&
1392  abs(z-(height+sectors[sect].regions[t].baseHeight)) < 2)
1393  {
1394  s.Init(sect, t, indexFromXY(x%gSectorSize, y%gSectorSize));
1395  //printf("Found (%d, %d, %d) (%d)\n", x, y, z, height);
1396  return height+sectors[sect].regions[t].baseHeight;
1397  }
1398  }
1399  //printf("\n");
1400  return -1;
1401 }
1402 
1403 void Map3DGrid::GetXYFromState(const state3d &s, int &x, int &y) const
1404 {
1405  int regx, regy;
1406  xyFromIndex(s.GetOffset(), regx, regy);
1407  x = (s.GetSector()%mXSectors)*gSectorSize+regx;
1408  y = (s.GetSector()/mXSectors)*gSectorSize+regy;
1409 }
1410 
1411 void Map3DGrid::GetXYZFromState(const state3d &s, int &x, int &y, int &z) const
1412 {
1413  GetXYFromState(s, x, y);
1414  z = sectors[s.GetSector()].regions[s.GetRegion()].baseHeight+
1415  sectors[s.GetSector()].regions[s.GetRegion()].grid.GetHeightOffset(s.GetOffset());
1416 }
1417 
1418 void Map3DGrid::GetStateFromXYZ(state3d &s, int x, int y, int z) const
1419 {
1420  // TODO: this is only for 2D worlds
1421 // s.sector = GetSector(x, y);
1422 // s.region = 0;
1423 // s.offset = (x%gSectorSize)+(y%gSectorSize)*gSectorSize;
1424 // return;
1425  int val = FindNearState(x, y, z, s);
1426  assert(val != -1);
1427 }
1428 
1429 void Map3DGrid::GetPointFromCoordinate(point3d loc, int &px, int &py, int &pz) const
1430 {
1431  int xOffset = max(mHeight, mWidth)-mWidth;
1432  int yOffset = max(mHeight, mWidth)-mHeight;
1433  double scale = max(mHeight, mWidth);
1434  scale = 1.0/scale;
1435 
1436  px = (loc.x-(-1+scale+xOffset*scale))/(2.0*scale);
1437  py = (loc.y-(-1+scale+yOffset*scale))/(2.0*scale);
1438  pz = -loc.z/(scale*0.1);
1439 }
1440 
1441 
1442 void Map3DGrid::OpenGLDraw() const
1443 {
1444  glColor4f(0.0, 1.0, 0.0, 1.0);
1445 // glBegin(GL_LINE_LOOP);
1446 // glVertex3f(-1, -1, 0);
1447 // glVertex3f(-1, 1, 0);
1448 // glVertex3f( 1, 1, 0);
1449 // glVertex3f( 1, -1, 0);
1450 // glEnd();
1451  GLdouble x1, y1, z1, rad, h;
1452 // GLdouble x2, y2, z2, rad2, h2;
1453  GLdouble left, right, top, bottom;
1454  GetOpenGLCoord(0, 0, 0, left, top, z1, rad, h);
1455  GetOpenGLCoord(mWidth, mHeight, 0, right, bottom, z1, rad, h);
1456  glBegin(GL_LINES);
1457  for (int x = 0; x < mWidth; x+=gSectorSize)
1458  {
1459  GetOpenGLCoord(x, 0, 0, x1, y1, z1, rad, h);
1460  glVertex3f(x1-rad, top, z1);
1461  glVertex3f(x1-rad, bottom, z1);
1462  }
1463  GetOpenGLCoord(mWidth, 0, 0, x1, y1, z1, rad, h);
1464  glVertex3f(x1-rad, top, z1);
1465  glVertex3f(x1-rad, bottom, z1);
1466 
1467  for (int y = 0; y < mHeight; y+=gSectorSize)
1468  {
1469  GetOpenGLCoord(0, y, 0, x1, y1, z1, rad, h);
1470  glVertex3f(left, y1-rad, z1);
1471  glVertex3f(right, y1-rad, z1);
1472  }
1473  GetOpenGLCoord(0, mHeight, 0, x1, y1, z1, rad, h);
1474  glVertex3f(left, y1-rad, z1);
1475  glVertex3f(right, y1-rad, z1);
1476  glEnd();
1477 
1478  glColor3f(0, 0, 0);
1479  glBegin(GL_QUADS);
1480  glVertex3f(-1, -1, 0.01);
1481  glVertex3f( 1, -1, 0.01);
1482  glVertex3f( 1, 1, 0.01);
1483  glVertex3f(-1, 1, 0.01);
1484  glEnd();
1485 
1486  glEnable(GL_LIGHTING);
1487  for (unsigned int x = 0; x < sectors.size(); x++)
1488  {
1489  //printf("%d regions in sector %d\n", sectors[x].regions.size(), x);
1490  for (unsigned int y = 0; y < sectors[x].regions.size(); y++)
1491  {
1492  //SetColor(0.7, 0.7, 0.7, 0.7);
1493  SetColor(1.0, 1.0, 1.0, 1.0);
1494  glTranslatef(0, 0, -5*h);
1495  for (unsigned int z = 0; z < sectors[x].regions[y].edges.size(); z++)
1496  {
1497  state3d s1, s2;
1498  s1.Init(x, y, sectors[x].regions[y].centerLocation);
1499  s2.Init(sectors[x].regions[y].edges[z].sector,
1500  sectors[x].regions[y].edges[z].region,
1501  sectors[sectors[x].regions[y].edges[z].sector].regions[sectors[x].regions[y].edges[z].region].centerLocation);
1502  glLineWidth(2+sectors[x].regions[y].edges[z].support/4);
1503  GLDrawLine(s1, s2);
1504  }
1505  glTranslatef(0, 0, 5*h);
1506  glLineWidth(1.0);
1507 
1508  GLdouble r=0, g=0, b=0;
1509  switch ((y+x)%4)
1510  {
1511  case 0: g=0.25;r=0.5;b=0.15; break;
1512  case 1: g=0.35;r=0.5;b=0.15; break;
1513  case 2: g=0.25;r=0.4;b=0.15; break;
1514  case 3: g=0.25;r=0.5;b=0.25; break;
1515  }
1516  for (unsigned int z = 0; z < gSectorSize*gSectorSize; z++)
1517  {
1518  int xLoc, yLoc, zLoc;
1519  int xRegLoc, yRegLoc;
1520  xyFromIndex(z, xLoc, yLoc);
1521  xRegLoc = xLoc;
1522  yRegLoc = yLoc;
1523  if (!sectors[x].regions[y].grid.IsPointPassable(xRegLoc, yRegLoc))
1524  continue;
1525 
1526  zLoc = sectors[x].regions[y].baseHeight + sectors[x].regions[y].grid.GetHeightOffset(xRegLoc, yRegLoc);
1527  xLoc += (x%mXSectors)*gSectorSize;
1528  yLoc += (x/mXSectors)*gSectorSize;
1529  GetOpenGLCoord(xLoc, yLoc, zLoc, x1, y1, z1, rad, h);
1530  glColor3f(r, g, b);
1531  glBegin(GL_QUADS);
1532  glNormal3f(0, 0, -1);
1533  glVertex3f(x1-rad, y1-rad, z1);
1534  glVertex3f(x1-rad, y1+rad, z1);
1535  glVertex3f(x1+rad, y1+rad, z1);
1536  glVertex3f(x1+rad, y1-rad, z1);
1537  glEnd();
1538 
1539  if (drawGrid)
1540  {
1541  std::vector<state3d> suc;
1542  state3d currState;
1543  currState.Init(x, y, indexFromXY(xRegLoc, yRegLoc));
1544  GetSuccessors(currState, suc);
1545  for (unsigned int t = 0; t < suc.size(); t++)
1546  {
1547  // printf("Drawing line between (%d/%d/%d) and (%d/%d/%d)\n",
1548  // currState.GetSector(), currState.GetRegion(), currState.GetOffset(),
1549  // suc[t].GetSector(), suc[t].GetRegion(), suc[t].GetOffset());
1550  SetColor(1, 1, 1, 1);
1551  GLDrawLine(currState, suc[t]);
1552  }
1553  }
1554  }
1555  }
1556  }
1557 }
1558 
1559 
1560 void Map3DGrid::OpenGLDraw(const state3d &s) const
1561 {
1562 // s.part1
1563 }
1564 
1565 void Map3DGrid::GLDrawLine(const state3d &a, const state3d &b) const
1566 {
1567  GLdouble x1, y1, z1, rad, h;
1568  GLfloat rr, gg, bb, tt;
1569  int xLoc, yLoc, zLoc;
1570 
1571  GetXYZFromState(a, xLoc, yLoc, zLoc);
1572  GetOpenGLCoord(xLoc, yLoc, zLoc, x1, y1, z1, rad, h);
1573 
1574  //glLineWidth(2.0);
1575  glDisable(GL_LIGHTING);
1576  GetColor(rr, gg, bb, tt);
1577  glColor4f(rr, gg, bb, tt);
1578  glBegin(GL_LINES);
1579  glVertex3f(x1, y1, z1-h);
1580 
1581  GetXYZFromState(b, xLoc, yLoc, zLoc);
1582  GetOpenGLCoord(xLoc, yLoc, zLoc, x1, y1, z1, rad, h);
1583 
1584  glVertex3f(x1, y1, z1-h);
1585  glEnd();
1586  glEnable(GL_LIGHTING);
1587  //glLineWidth(1.0);
1588 }
1589 
1590 
1591 void Map3DGrid::GetOpenGLCoord(int xLoc, int yLoc, int zLoc,
1592  GLdouble &x, GLdouble &y, GLdouble &z,
1593  GLdouble &r, GLdouble &h) const
1594 {
1595  int xOffset = max(mHeight, mWidth)-mWidth;
1596  int yOffset = max(mHeight, mWidth)-mHeight;
1597  double scale = max(mHeight, mWidth);
1598  scale = 1.0/scale;
1599  x = 2.0*xLoc*scale-1+scale+xOffset*scale;
1600  y = 2.0*yLoc*scale-1+scale+yOffset*scale;
1601  h = scale*0.2;
1602  z = -zLoc*h;
1603  r = scale;
1604 }
1605 
1606 void Map3DGrid::PrintStats()
1607 {
1608  std::vector<int> regCnt;
1609  int regions = 0;
1610  printf("%lu sectors\n", sectors.size());
1611  for (unsigned int x = 0; x < sectors.size(); x++)
1612  {
1613  if (sectors[x].regions.size() >= regCnt.size())
1614  regCnt.resize(sectors[x].regions.size()+1);
1615  regCnt[sectors[x].regions.size()]++;
1616  regions += sectors[x].regions.size();
1617  }
1618  printf("%d regions [avg: %1.2f]\n", regions, (float)regions/sectors.size());
1619  for (unsigned int x = 0; x < regCnt.size(); x++)
1620  {
1621  printf("%d : %d\n", x, regCnt[x]);
1622  }
1623 }
1624 
1625 int Map3DGrid::GetAbstractionBytesUsed()
1626 {
1627  int mem = sectors.size() * 4;
1628 
1629  for (unsigned int x = 0; x < sectors.size(); x++)
1630  {
1631  mem += sectors[x].regions.size()*12;
1632  for (int y = 0; y < sectors[x].regions.size(); y++)
1633  mem += sectors[x].regions[y].edges.size()*4;
1634  }
1635  return mem;
1636 }
1637 
1638 int Map3DGrid::GetGridBytesUsed()
1639 {
1640  int mem = 0;
1641 
1642  for (unsigned int x = 0; x < sectors.size(); x++)
1643  {
1644  mem += sectors[x].regions.size()*gSectorSize*gSectorSize*2;
1645  }
1646  return mem;
1647 }
Map3DGrid::sectors
std::vector< SectorData > sectors
Definition: Map3DGrid.h:262
loc::x
int x
Definition: MapGenerators.cpp:296
Map3DGrid::mXSectors
int mXSectors
Definition: Map3DGrid.h:261
Map3DGrid::GetActionHash
uint64_t GetActionHash(action3d act) const
Definition: Map3DGrid.cpp:861
moveDir
moveDir
Definition: Map3DGrid.h:32
RegionData::RemoveEdge
void RemoveEdge(EdgeData &e)
Definition: Map3DGrid.cpp:391
GridData::GetHeightOffset
int GetHeightOffset(unsigned int x, unsigned int y) const
Definition: Map3DGrid.cpp:123
Map3DGrid::mHeight
int mHeight
Definition: Map3DGrid.h:260
state3d::GetRegion
int GetRegion() const
Definition: Map3DGrid.h:175
Map3DGrid::GetSector
int GetSector(int x, int y) const
Definition: Map3DGrid.h:253
GridData::SetHeightOffset
void SetHeightOffset(int x, int y, int height)
Definition: Map3DGrid.cpp:137
kWest
@ kWest
Definition: Map3DGrid.h:33
GridData::AddBlocked
void AddBlocked(int x, int y)
Definition: Map3DGrid.cpp:149
RegionData::LowerBase
bool LowerBase()
Definition: Map3DGrid.cpp:277
terrainBits
const int terrainBits
Definition: Map.h:49
kEast
@ kEast
Definition: Map3DGrid.h:34
loc::y
int y
Definition: MapGenerators.cpp:296
GridData::GetMoves
uint8_t GetMoves(int x, int y) const
Definition: Map3DGrid.cpp:66
Map3DGrid::mWidth
int mWidth
Definition: Map3DGrid.h:260
kSouthEast
@ kSouthEast
Definition: Map3DGrid.h:39
EdgeData::sector
uint16_t sector
Definition: Map3DGrid.h:123
Map3DGrid::AddEdge
void AddEdge(state3d &from, state3d &to)
Definition: Map3DGrid.cpp:1029
RegionData::centerLocation
uint8_t centerLocation
Definition: Map3DGrid.h:149
EdgeData::region
uint8_t region
Definition: Map3DGrid.h:124
width
int width
Definition: SFML_HOG.cpp:54
indexFromXY
int indexFromXY(int x, int y)
Definition: Map3DGrid.h:26
state3d::sector
uint16_t sector
Definition: Map3DGrid.h:179
GridData::AddPoint
bool AddPoint(int x, int y, int height)
Definition: Map3DGrid.cpp:92
Map3DGrid::GetPointFromCoordinate
void GetPointFromCoordinate(point3d loc, int &px, int &py, int &pz) const
Definition: Map3DGrid.cpp:1429
RegionData::baseHeight
uint8_t baseHeight
Definition: Map3DGrid.h:150
GridData::RemovePoint
void RemovePoint(int x, int y)
Definition: Map3DGrid.cpp:98
GridData::ClearMoves
void ClearMoves(int x, int y)
Definition: Map3DGrid.cpp:87
Map3DGrid::OpenGLDraw
void OpenGLDraw() const
Definition: Map3DGrid.cpp:1442
Map3DGrid::AddPoint
bool AddPoint(int x, int y, int z)
Definition: Map3DGrid.cpp:867
Map3DGrid::Map3DGrid
Map3DGrid(int width, int height, int theSectorSize)
Definition: Map3DGrid.cpp:459
Map3DGrid::AddMapPoints
void AddMapPoints(Map *map, std::vector< bool > &visited, int x, int y, int elevation)
Definition: Map3DGrid.cpp:483
kNorth
@ kNorth
Definition: Map3DGrid.h:35
RegionData::edges
std::vector< EdgeData > edges
Definition: Map3DGrid.h:153
SectorData::RemovePoint
bool RemovePoint(int x, int y, int z)
Definition: Map3DGrid.cpp:431
GridData::GetBlocked
int GetBlocked(int x, int y)
Definition: Map3DGrid.cpp:144
kGround
@ kGround
Definition: Map.h:55
Map3DGrid::drawGrid
bool drawGrid
Definition: Map3DGrid.h:263
SearchEnvironment< state3d, action3d >::SetColor
virtual void SetColor(const rgbColor &r) const
Definition: SearchEnvironment.h:102
Map3DGrid::GetGridBytesUsed
int GetGridBytesUsed()
Definition: Map3DGrid.cpp:1638
loc
Definition: MapGenerators.cpp:296
action3d::destSector
uint8_t destSector
Definition: Map3DGrid.h:197
SectorData::regions
std::vector< RegionData > regions
Definition: Map3DGrid.h:162
state3d::region
uint8_t region
Definition: Map3DGrid.h:180
Map3DGrid::RemovePoint
bool RemovePoint(int x, int y, int z, bool split=true)
Definition: Map3DGrid.cpp:1141
Map3DGrid::RemoveEdge
void RemoveEdge(int sec1, int reg1, int sec2, int reg2, int weight)
Definition: Map3DGrid.cpp:1271
kNorthEast
@ kNorthEast
Definition: Map3DGrid.h:37
point3d
#define point3d
Definition: GLUtil.h:123
action3d::direction
uint8_t direction
Definition: Map3DGrid.h:195
Map3DGrid::GoalTest
bool GoalTest(const state3d &node, const state3d &goal) const
Definition: Map3DGrid.cpp:849
GridData::ReMove
int ReMove(unsigned index, moveDir dir)
Definition: Map3DGrid.cpp:48
GridData::CanPass
bool CanPass(unsigned int x, unsigned int y, int offsetx, int offsety) const
Definition: Map3DGrid.cpp:111
Map3DGrid::GetActions
void GetActions(const state3d &nodeID, std::vector< action3d > &actions) const
Definition: Map3DGrid.cpp:785
Map3DGrid::GetXYZFromState
void GetXYZFromState(const state3d &s, int &x, int &y, int &z) const
Definition: Map3DGrid.cpp:1411
Map3DGrid::FindNearState
int FindNearState(int x, int y, int z, state3d &s) const
Definition: Map3DGrid.cpp:1383
RegionData::AddEdge
void AddEdge(EdgeData &e)
Definition: Map3DGrid.cpp:378
Map3DGrid::GLDrawLine
void GLDrawLine(const state3d &x, const state3d &y) const
Definition: Map3DGrid.cpp:1565
Map::GetMapWidth
long GetMapWidth() const
return the width of the map
Definition: Map.h:163
GridData::AddMove
int AddMove(unsigned index, moveDir dir, bool local)
Definition: Map3DGrid.cpp:23
kSouthWest
@ kSouthWest
Definition: Map3DGrid.h:40
EdgeData
Definition: Map3DGrid.h:100
SearchEnvironment< state3d, action3d >::GetColor
virtual rgbColor GetColor() const
Definition: SearchEnvironment.h:105
Map::GetTerrainType
long GetTerrainType(long x, long y, tSplitSide split=kWholeTile) const
Get the terrain type of the (split) tile at x, y.
Definition: Map.cpp:1028
height
int height
Definition: SFML_HOG.cpp:54
GridData::SubtractBlocked
void SubtractBlocked(int x, int y)
Definition: Map3DGrid.cpp:156
GridData::points
uint32_t * points
Definition: Map3DGrid.h:89
Map3DGrid::ApplyAction
void ApplyAction(state3d &s, action3d a) const
Definition: Map3DGrid.cpp:806
Map3DGrid::AddGridEdge
int AddGridEdge(state3d &from, state3d &to, bool local)
Definition: Map3DGrid.cpp:1059
kNorthWest
@ kNorthWest
Definition: Map3DGrid.h:38
Map3DGrid::GetAbstractionBytesUsed
int GetAbstractionBytesUsed()
Definition: Map3DGrid.cpp:1625
Map3DGrid::HCost
double HCost(const state3d &node1, const state3d &node2) const
Heuristic value between two arbitrary nodes.
Definition: Map3DGrid.cpp:831
Map3DGrid::GetStateHash
uint64_t GetStateHash(const state3d &node) const
Definition: Map3DGrid.cpp:855
max
#define max(a, b)
Definition: MinimalSectorAbstraction.cpp:40
Map3DGrid::RemoveGridEdge
int RemoveGridEdge(state3d &from, state3d &to)
Definition: Map3DGrid.cpp:1297
xyFromIndex
void xyFromIndex(int index, int &x, int &y)
Definition: Map3DGrid.h:29
GridData::BFS
int BFS(std::vector< int > &labels, int offset, int label)
Definition: Map3DGrid.cpp:184
action3d
Definition: Map3DGrid.h:192
Map3DGrid.h
GridData::GetMoveLocality
uint8_t GetMoveLocality(int x, int y) const
Definition: Map3DGrid.cpp:76
state3d
Definition: Map3DGrid.h:167
Map3DGrid::RemoveSectorEdge
int RemoveSectorEdge(state3d &from, state3d &to)
Definition: Map3DGrid.cpp:1330
RegionData::pointCount
uint8_t pointCount
Definition: Map3DGrid.h:151
Map3DGrid::GetXYFromState
void GetXYFromState(const state3d &s, int &x, int &y) const
Definition: Map3DGrid.cpp:1403
Map3DGrid::AddSectorEdge
int AddSectorEdge(state3d &from, state3d &to)
Definition: Map3DGrid.cpp:1090
RegionData::grid
GridData grid
Definition: Map3DGrid.h:154
state3d::Init
void Init(int sector, int region, int offset)
Definition: Map3DGrid.h:172
Map3DGrid::AddMap
void AddMap(Map *map, int elevation)
Definition: Map3DGrid.cpp:470
Map3DGrid::GetStateFromXYZ
void GetStateFromXYZ(state3d &s, int x, int y, int z) const
Definition: Map3DGrid.cpp:1418
RegionData::AddPoint
bool AddPoint(int x, int y, int z)
Definition: Map3DGrid.cpp:332
SectorData::AddPoint
bool AddPoint(int x, int y, int z)
Definition: Map3DGrid.cpp:409
Map::GetMapHeight
long GetMapHeight() const
return the height of the map
Definition: Map.h:165
kUnpassableHeight
const uint8_t kUnpassableHeight
Definition: Map3DGrid.cpp:21
action3d::destRegion
uint8_t destRegion
Definition: Map3DGrid.h:196
gSectorSize
int gSectorSize
Definition: Map3DGrid.cpp:12
split
std::vector< std::string > split(const std::string &s, char delim)
Splits a string into elements.
Definition: StringUtils.cpp:16
Map3DGrid::InternalRemovePoint
int InternalRemovePoint(int x, int y, int z)
Definition: Map3DGrid.cpp:1198
GridData::LabelAreas
int LabelAreas(std::vector< int > &labels, std::vector< int > &counts, std::vector< int > &heights)
Definition: Map3DGrid.cpp:163
Map3DGrid::GetOpenGLCoord
void GetOpenGLCoord(int xLoc, int yLoc, int zLoc, GLdouble &x, GLdouble &y, GLdouble &z, GLdouble &r, GLdouble &h) const
Definition: Map3DGrid.cpp:1591
EdgeData::support
uint8_t support
Definition: Map3DGrid.h:125
RegionData::CanAddPoint
bool CanAddPoint(int x, int y, int z)
Definition: Map3DGrid.cpp:301
Map3DGrid::PrintStats
void PrintStats()
Definition: Map3DGrid.cpp:1606
kSouth
@ kSouth
Definition: Map3DGrid.h:36
RegionData::RedoCenterLocation
void RedoCenterLocation()
Definition: Map3DGrid.cpp:360
Map3DGrid::GCost
double GCost(const state3d &node1, const state3d &node2) const
Definition: Map3DGrid.cpp:837
state3d::GetSector
int GetSector() const
Definition: Map3DGrid.h:174
state3d::offset
uint8_t offset
Definition: Map3DGrid.h:180
node
Nodes to be stored within a Graph.
Definition: Graph.h:170
Map
A tile-based representation of the world.
Definition: Map.h:142
state3d::GetOffset
int GetOffset() const
Definition: Map3DGrid.h:176
Map3DGrid::GetSuccessors
void GetSuccessors(const state3d &nodeID, std::vector< state3d > &neighbors) const
Definition: Map3DGrid.cpp:531
GridData::IsPointPassable
bool IsPointPassable(unsigned int x, unsigned int y) const
Definition: Map3DGrid.cpp:104
Map3DGrid::mYSectors
int mYSectors
Definition: Map3DGrid.h:261
Generated by   doxygen 1.8.17