1 /*************************************************************************/ 2 /* broad_phase_2d_hash_grid.h */ 3 /*************************************************************************/ 4 /* This file is part of: */ 5 /* GODOT ENGINE */ 6 /* https://godotengine.org */ 7 /*************************************************************************/ 8 /* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ 9 /* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ 10 /* */ 11 /* Permission is hereby granted, free of charge, to any person obtaining */ 12 /* a copy of this software and associated documentation files (the */ 13 /* "Software"), to deal in the Software without restriction, including */ 14 /* without limitation the rights to use, copy, modify, merge, publish, */ 15 /* distribute, sublicense, and/or sell copies of the Software, and to */ 16 /* permit persons to whom the Software is furnished to do so, subject to */ 17 /* the following conditions: */ 18 /* */ 19 /* The above copyright notice and this permission notice shall be */ 20 /* included in all copies or substantial portions of the Software. */ 21 /* */ 22 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ 23 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ 24 /* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ 25 /* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ 26 /* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ 27 /* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ 28 /* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ 29 /*************************************************************************/ 30 #ifndef BROAD_PHASE_2D_HASH_GRID_H 31 #define BROAD_PHASE_2D_HASH_GRID_H 32 33 #include "broad_phase_2d_sw.h" 34 #include "map.h" 35 36 class BroadPhase2DHashGrid : public BroadPhase2DSW { 37 38 struct PairData { 39 40 bool colliding; 41 int rc; 42 void *ud; PairDataPairData43 PairData() { 44 colliding = false; 45 rc = 1; 46 ud = NULL; 47 } 48 }; 49 50 struct Element { 51 52 ID self; 53 CollisionObject2DSW *owner; 54 bool _static; 55 Rect2 aabb; 56 int subindex; 57 uint64_t pass; 58 Map<Element *, PairData *> paired; 59 }; 60 61 struct RC { 62 63 int ref; 64 incRC65 _FORCE_INLINE_ int inc() { 66 ref++; 67 return ref; 68 } decRC69 _FORCE_INLINE_ int dec() { 70 ref--; 71 return ref; 72 } 73 RCRC74 _FORCE_INLINE_ RC() { 75 ref = 0; 76 } 77 }; 78 79 Map<ID, Element> element_map; 80 Map<Element *, RC> large_elements; 81 82 ID current; 83 84 uint64_t pass; 85 86 struct PairKey { 87 88 union { 89 struct { 90 ID a; 91 ID b; 92 }; 93 uint64_t key; 94 }; 95 96 _FORCE_INLINE_ bool operator<(const PairKey &p_key) const { 97 return key < p_key.key; 98 } 99 PairKeyPairKey100 PairKey() { key = 0; } PairKeyPairKey101 PairKey(ID p_a, ID p_b) { 102 if (p_a > p_b) { 103 a = p_b; 104 b = p_a; 105 } else { 106 a = p_a; 107 b = p_b; 108 } 109 } 110 }; 111 112 Map<PairKey, PairData> pair_map; 113 114 int cell_size; 115 int large_object_min_surface; 116 117 PairCallback pair_callback; 118 void *pair_userdata; 119 UnpairCallback unpair_callback; 120 void *unpair_userdata; 121 122 void _enter_grid(Element *p_elem, const Rect2 &p_rect, bool p_static); 123 void _exit_grid(Element *p_elem, const Rect2 &p_rect, bool p_static); 124 template <bool use_aabb, bool use_segment> 125 _FORCE_INLINE_ void _cull(const Point2i p_cell, const Rect2 &p_aabb, const Point2 &p_from, const Point2 &p_to, CollisionObject2DSW **p_results, int p_max_results, int *p_result_indices, int &index); 126 127 struct PosKey { 128 129 union { 130 struct { 131 int32_t x; 132 int32_t y; 133 }; 134 uint64_t key; 135 }; 136 hashPosKey137 _FORCE_INLINE_ uint32_t hash() const { 138 uint64_t k = key; 139 k = (~k) + (k << 18); // k = (k << 18) - k - 1; 140 k = k ^ (k >> 31); 141 k = k * 21; // k = (k + (k << 2)) + (k << 4); 142 k = k ^ (k >> 11); 143 k = k + (k << 6); 144 k = k ^ (k >> 22); 145 return k; 146 } 147 148 bool operator==(const PosKey &p_key) const { return key == p_key.key; } 149 _FORCE_INLINE_ bool operator<(const PosKey &p_key) const { 150 return key < p_key.key; 151 } 152 }; 153 154 struct PosBin { 155 156 PosKey key; 157 Map<Element *, RC> object_set; 158 Map<Element *, RC> static_object_set; 159 PosBin *next; 160 }; 161 162 uint32_t hash_table_size; 163 PosBin **hash_table; 164 165 void _pair_attempt(Element *p_elem, Element *p_with); 166 void _unpair_attempt(Element *p_elem, Element *p_with); 167 void _check_motion(Element *p_elem); 168 169 public: 170 virtual ID create(CollisionObject2DSW *p_object_, int p_subindex = 0); 171 virtual void move(ID p_id, const Rect2 &p_aabb); 172 virtual void set_static(ID p_id, bool p_static); 173 virtual void remove(ID p_id); 174 175 virtual CollisionObject2DSW *get_object(ID p_id) const; 176 virtual bool is_static(ID p_id) const; 177 virtual int get_subindex(ID p_id) const; 178 179 virtual int cull_segment(const Vector2 &p_from, const Vector2 &p_to, CollisionObject2DSW **p_results, int p_max_results, int *p_result_indices = NULL); 180 virtual int cull_aabb(const Rect2 &p_aabb, CollisionObject2DSW **p_results, int p_max_results, int *p_result_indices = NULL); 181 182 virtual void set_pair_callback(PairCallback p_pair_callback, void *p_userdata); 183 virtual void set_unpair_callback(UnpairCallback p_unpair_callback, void *p_userdata); 184 185 virtual void update(); 186 187 static BroadPhase2DSW *_create(); 188 189 BroadPhase2DHashGrid(); 190 ~BroadPhase2DHashGrid(); 191 }; 192 193 #endif // BROAD_PHASE_2D_HASH_GRID_H 194