Angel 3.2
A 2D Game Prototyping Engine
SpatialGraph.h
1 
2 // Copyright (C) 2008-2013, Shane Liesegang
3 // All rights reserved.
4 //
5 // Redistribution and use in source and binary forms, with or without
6 // modification, are permitted provided that the following conditions are met:
7 //
8 // * Redistributions of source code must retain the above copyright
9 // notice, this list of conditions and the following disclaimer.
10 // * Redistributions in binary form must reproduce the above copyright
11 // notice, this list of conditions and the following disclaimer in the
12 // documentation and/or other materials provided with the distribution.
13 // * Neither the name of the copyright holder nor the names of any
14 // contributors may be used to endorse or promote products derived from
15 // this software without specific prior written permission.
16 //
17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
21 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27 // POSSIBILITY OF SUCH DAMAGE.
29 
30 #pragma once
31 
32 #include "../AI/BoundingShapes.h"
33 
34 #include <Box2D/Box2D.h>
35 
36 class SpatialGraph;
37 class SpatialGraphKDNode;
38 
39 typedef std::vector<SpatialGraphKDNode*> SpatialGraphNeighborList;
40 typedef std::vector<Vector2> Vector2List;
41 typedef std::vector<bool> BoolList;
43 {
44 public:
45 
47  : BBox(bb)
48  , LHC(NULL)
49  , RHC(NULL)
50  , Parent(_parent)
51  {
52  }
53 
54  void Render();
55 
56  bool HasChildren() {return LHC != NULL && RHC != NULL;}
57  void GetGridPoints( Vector2List& points, int& xPoints, int& yPoints );
58 
59  BoundingBox BBox;
60  SpatialGraphKDNode* LHC;
61  SpatialGraphKDNode* RHC;
62  SpatialGraphKDNode* Parent;
63  SpatialGraph* Tree;
64  int Index;
65  int Depth;
66  bool bBlocked;
67 
68  SpatialGraphNeighborList Neighbors;
69  BoolList NeighborLOS;
70 
71 };
72 #if defined(__APPLE__) || defined(__linux__)
73 //have to give a hashing function for specific pointers
74 namespace hashmap_ns {
75  template<> struct hash< SpatialGraphKDNode* >
76  {
77  size_t operator()( const SpatialGraphKDNode* const & x ) const
78  {
79  return hash<long int>()( (long int)x );
80  }
81  };
82 }
83 #endif
84 
86 {
87 public:
88  SpatialGraph(float entityWidth, const BoundingBox& startBox );
89  ~SpatialGraph();
90 
91  SpatialGraphKDNode* FindNode(SpatialGraphKDNode* node, const BoundingBox& bbox);
92  SpatialGraphKDNode* FindNode(SpatialGraphKDNode* node, const Vector2& point);
93  SpatialGraphKDNode* FindNode(const BoundingBox& bbox);
94  SpatialGraphKDNode* FindNode(const Vector2& point);
95  void Render();
96 
97  int GetDepth() {return _depth;}
98  Vector2 GetSmallestDimensions() {return _smallestDimensions;}
99  bool CanGo( const Vector2& vFrom, const Vector2 vTo );
100 
101 private:
102  SpatialGraphKDNode* CreateTree(int depth, const BoundingBox& bbox, SpatialGraphKDNode* parent = NULL, int index = 0 );
103  void AddNeighbor( SpatialGraphKDNode* node, const Vector2& pos );
104  void ComputeNeighbors( SpatialGraphKDNode* node );
105  void ValidateNeighbors( SpatialGraphKDNode* node );
106  void DeleteNode( SpatialGraphKDNode* pNode );
107  bool IsFullyBlocked( SpatialGraphKDNode* pNode );
108  bool CanGoInternal( const Vector2& vFrom, const Vector2 vTo, SpatialGraphKDNode* pSourceNode, SpatialGraphKDNode* pDestNode );
109  bool CanGoNodeToNode( SpatialGraphKDNode* pSourceNode, SpatialGraphKDNode* pDestNode );
110 
111 private:
112  int _depth;
113  float _entityWidth;
114  Vector2 _smallestDimensions;
115  SpatialGraphKDNode* _root;
116  int _dirMasks[4];
117 
118 };
119 
120 #define theSpatialGraph SpatialGraphManager::GetInstance()
121 
122 class SpatialGraphManager : public b2QueryCallback
123 {
124 public:
125  static SpatialGraphManager &GetInstance();
126 
127  bool ReportFixture(b2Fixture* fixture);
128 
129  SpatialGraph* GetGraph() {return _spatialGraph;}
130  void CreateGraph( float entityWidth, const BoundingBox& bounds );
131 
132  void Render();
133 
134  bool GetPath( const Vector2& source, const Vector2& dest, Vector2List& path );
135 
136  bool CanGo( const Vector2& from, const Vector2 to );
137  bool IsInPathableSpace( const Vector2& point );
138  bool FindNearestNonBlocked( const Vector2& fromPoint, Vector2& goTo );
139 
140  void EnableDrawBounds(bool enable);
141  const bool ToggleDrawBounds();
142  const bool GetDrawBounds();
143  void EnableDrawBlocked(bool enable);
144  const bool ToggleDrawBlocked();
145  const bool GetDrawBlocked();
146  void EnableDrawGridPoints(bool enable);
147  const bool ToggleDrawGridPoints();
148  const bool GetDrawGridPoints();
149  void EnableDrawGraph(bool enable);
150  const bool ToggleDrawGraph();
151  const bool GetDrawGraph();
152  void EnableDrawNodeIndex(bool enable);
153  const bool ToggleDrawNodeIndex();
154  const bool GetDrawNodeIndex();
155 
156 protected:
159  void Initialize();
160  static SpatialGraphManager *s_SpatialGraphManager;
161 
162 private:
163  SpatialGraph* _spatialGraph;
164 
165  bool _drawBounds;
166  bool _drawBlocked;
167  bool _drawGridPoints;
168  bool _drawGraph;
169  bool _drawNodeIndex;
170 };