1 /***************************************************************************
2 * Copyright (C) 2005-2019 by the FIFE team *
3 * http://www.fifengine.net *
4 * This file is part of FIFE. *
5 * *
6 * FIFE is free software; you can redistribute it and/or *
7 * modify it under the terms of the GNU Lesser General Public *
8 * License as published by the Free Software Foundation; either *
9 * version 2.1 of the License, or (at your option) any later version. *
10 * *
11 * This library is distributed in the hope that it will be useful, *
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
14 * Lesser General Public License for more details. *
15 * *
16 * You should have received a copy of the GNU Lesser General Public *
17 * License along with this library; if not, write to the *
18 * Free Software Foundation, Inc., *
19 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA *
20 ***************************************************************************/
21
22 #ifndef FIFE_UTIL_QUADTREE_H
23 #define FIFE_UTIL_QUADTREE_H
24
25 // Standard C++ library includes
26 #include <cassert>
27
28 // 3rd party library includes
29
30 // FIFE includes
31 // These includes are split up in two parts, separated by one empty line
32 // First block: files included from the FIFE root src directory
33 // Second block: files included from the same folder
34 #include "rect.h"
35
36 namespace FIFE {
37
38 /** QuadTree Node
39 */
40 template<typename DataType, int32_t MinimumSize = 128>
41 class QuadNode {
42 protected:
43 QuadNode *m_parent;
44 QuadNode *m_nodes[4];
45 int32_t m_x,m_y,m_size;
46 DataType m_data;
47
48 public:
49 /** Create a new QuadNode
50 * @param parent The parent QuadNode this node is contained in or null.
51 * @param x The X position of this QuadNode.
52 * @param y The Y position of this QuadNode.
53 * @param size The width and height of this QuadNode.
54 */
QuadNode(QuadNode * parent,int32_t x,int32_t y,int32_t size)55 QuadNode(QuadNode* parent, int32_t x, int32_t y, int32_t size)
56 : m_parent(parent),m_x(x),m_y(y),m_size(size),m_data() {
57 m_nodes[0] = m_nodes[1] = m_nodes[2] = m_nodes[3] = 0L;
58 }
59
~QuadNode()60 ~QuadNode() {
61 delete m_nodes[0];
62 delete m_nodes[1];
63 delete m_nodes[2];
64 delete m_nodes[3];
65 }
66
67 /** Find a container node for a given rectangle.
68 * This guarantees to return a Node with the following
69 * properties:
70 * 1.) The node contains the rectangle (as defined by the contains
71 * function). 2.) All subnodes can not contain the rectangle or it has the MinimumSize.
72 * 3.) In case these properties can only be fulfilled by extending the tree upwards,
73 * that is by creating a new root node - this function will return null.
74 *
75 * This function will extend the tree automatically so that this guarantee
76 * can be fulfilled.
77 */
78 QuadNode* find_container(int32_t x, int32_t y, int32_t w, int32_t h);
find_container(const Rect & rect)79 QuadNode* find_container(const Rect& rect) {
80 return find_container(rect.x,rect.y,rect.w,rect.h);
81 }
82
83 /** Apply a visitor recursively to the QuadTree
84 * A visitor is an object which has a @c visit method which
85 * takes as parameters a pointer to a @c QuadNode and an integer.
86 * The integer is the depth of the given node.
87 * If the method returns @c true it is applied recursivly to all
88 * existing subnodes with a depth increased by one.
89 * The application happens in Z order (top left, top right, bottom
90 * left and finally bottom right).
91 */
92 template<typename Visitor>
93 void apply_visitor(Visitor& visitor, int32_t d = 0) {
94 if( !visitor.visit(this, d) )
95 return;
96 if( m_nodes[0] ) m_nodes[0]->apply_visitor(visitor, d + 1);
97 if( m_nodes[1] ) m_nodes[1]->apply_visitor(visitor, d + 1);
98 if( m_nodes[2] ) m_nodes[2]->apply_visitor(visitor, d + 1);
99 if( m_nodes[3] ) m_nodes[3]->apply_visitor(visitor, d + 1);
100 }
101
102 /** Return the X position of the node.
103 */
x()104 int32_t x() const { return m_x; };
105
106 /** Return the Y position of the node.
107 */
y()108 int32_t y() const { return m_y; };
109
110 /** Return the size (width and height) of the node.
111 */
size()112 int32_t size() const { return m_size; };
113
114 /** Return a reference to the data of the node.
115 */
data()116 DataType& data() { return m_data; };
117
118 /** Check whether a rectangle is contained in the node.
119 * A rectangle is contained in a node, iff:
120 * @code
121 * x >= x() and x + w < x() + size() and y >= y() and y + h < y() + size()
122 * @endcode
123 * That is the top and left borders are inclusive, but the right and bottom
124 * borders are exclusive.
125 */
126 bool contains(int32_t x, int32_t y, int32_t w, int32_t h) const;
127
128 /// Expand the subnodes - only needed for debugging/profiling worst cases.
129 void splice();
130
131 /** Return the parent node
132 */
parent()133 QuadNode* parent() { return m_parent; };
134
135 /** Create a new parent node for a rectangle
136 * This will create a new parent node end expand the tree so that
137 * the given rectangle will eventually be contained after enough calls
138 * of this function.
139 */
140 QuadNode* create_parent(int32_t x, int32_t y, int32_t w, int32_t h);
141 protected:
142 int32_t subnode(int32_t x, int32_t y, int32_t w, int32_t h) const;
143 };
144
145 /** Dynamic QuadTree
146 * A space partitioning tree automatically expanding to adjust
147 * to any object size put into the data structure.
148 */
149 template<typename DataType, int32_t MinimumSize = 128>
150 class QuadTree {
151 public:
152 typedef QuadNode<DataType,MinimumSize> Node;
153
154 /** Create a new QuadTree
155 * @param x The X position of the starting node.
156 * @param y The Y position of the starting node.
157 * @param starting_size The width and height of the starting node.
158 */
159 QuadTree(int32_t x = 0, int32_t y = 0, int32_t starting_size = MinimumSize) {
160 assert(starting_size>1);
161 m_cursor = m_root = new Node(0L,x,y,starting_size);
162 }
163
~QuadTree()164 ~QuadTree() {
165 assert( m_root->parent() == 0 );
166 delete m_root;
167 }
168
169 /** Find a container node for a given rectangle.
170 * This guarantees to return a Node with the following
171 * properties:
172 * 1.) The node contains the rectangle (as defined by the contains
173 * function). 2.) All subnodes can not contain the rectangle or it has the MinimumSize.
174 * This function will extend the tree automatically so that this guarantee
175 * can be fulfilled.
176 * This function is optimized for sequential access. This means accessing different rectangles
177 * that are 'near' to each other will be fast.
178 * @warning If you put different sized objects in (for example) lists in the quadnode,
179 * the returned node will @b not contain all objects which might intersect with the given
180 * rectangle.
181 */
182 Node* find_container(int32_t x, int32_t y, int32_t w, int32_t h);
find_container(const Rect & rect)183 Node* find_container(const Rect& rect) {
184 return find_container(rect.x,rect.y,rect.w,rect.h);
185 }
186
187 /** Apply a visitor recursively to the QuadTree
188 */
189 template<typename Visitor>
apply_visitor(Visitor & visitor)190 Visitor& apply_visitor(Visitor& visitor) {
191 m_root->apply_visitor(visitor,0);
192 return visitor;
193 }
194
clear()195 void clear() {
196 int32_t x = m_root->x();
197 int32_t y = m_root->y();
198 int32_t s = m_root->size();
199 delete m_root;
200 m_cursor = m_root = new Node(0L,x,y,s);
201 }
202
203 protected:
204 Node *m_root;
205 Node *m_cursor;
206 };
207
208
209 template<typename DataType, int32_t MinimumSize>
210 inline
contains(int32_t x,int32_t y,int32_t w,int32_t h)211 bool QuadNode<DataType,MinimumSize>::contains(int32_t x, int32_t y, int32_t w, int32_t h) const {
212 if (x < m_x)
213 return false;
214 if (y < m_y)
215 return false;
216 if (x + w >= m_x + m_size)
217 return false;
218 if (y + h >= m_y + m_size)
219 return false;
220 return true;
221 }
222
223 template<typename DataType, int32_t MinimumSize>
224 inline
subnode(int32_t x,int32_t y,int32_t w,int32_t h)225 int32_t QuadNode<DataType,MinimumSize>::subnode(int32_t x, int32_t y, int32_t w, int32_t h) const {
226 /*
227 Very small performance impact - roughly 5% for
228 the already very fast find_container function.
229 */
230 //assert(contains(x,y,w,h));
231
232 if (x >= m_x + m_size/2) {
233 if (y >= m_y + m_size/2) {
234 return 3;
235 }
236 if (y + h < m_y + m_size/2) {
237 return 1;
238 }
239 return -1;
240 }
241 if (x + w < m_x + m_size/2) {
242 if (y >= m_y + m_size/2) {
243 return 2;
244 }
245 if (y + h < m_y + m_size/2) {
246 return 0;
247 }
248 }
249 return -1;
250 }
251
252 template<typename DataType,int32_t MinimumSize>
253 QuadNode<DataType,MinimumSize>*
find_container(int32_t x,int32_t y,int32_t w,int32_t h)254 QuadNode<DataType,MinimumSize>::find_container(int32_t x, int32_t y, int32_t w, int32_t h) {
255 if( !contains(x,y,w,h) ) {
256 if (m_parent) {
257 return m_parent->find_container(x,y,w,h);
258 }
259 return 0L;
260 }
261
262 if (m_size <= MinimumSize) {
263 return this;
264 }
265
266 int32_t r = subnode(x,y,w,h);
267 switch(r) {
268 case -1:
269 return this;
270 case 0:
271 if( m_nodes[0] == 0) {
272 m_nodes[0] = new QuadNode<DataType,MinimumSize>(this,m_x,m_y,m_size/2);
273 }
274 return m_nodes[0]->find_container(x,y,w,h);
275 case 1:
276 if( m_nodes[1] == 0) {
277 m_nodes[1] = new QuadNode<DataType,MinimumSize>(this,m_x + m_size/2,m_y,m_size/2);
278 }
279 return m_nodes[1]->find_container(x,y,w,h);
280 case 2:
281 if( m_nodes[2] == 0) {
282 m_nodes[2] = new QuadNode<DataType,MinimumSize>(this,m_x,m_y + m_size/2,m_size/2);
283 }
284 return m_nodes[2]->find_container(x,y,w,h);
285 case 3:
286 if( m_nodes[3] == 0) {
287 m_nodes[3] = new QuadNode<DataType,MinimumSize>(this,m_x + m_size/2,m_y + m_size/2,m_size/2);
288 }
289 return m_nodes[3]->find_container(x,y,w,h);
290 default:
291 assert("BUG in QuadTree !" == 0);
292 return 0L;
293 }
294 }
295
296 template<typename DataType,int32_t MinimumSize>
297 QuadNode<DataType,MinimumSize>*
create_parent(int32_t x,int32_t y,int32_t w,int32_t h)298 QuadNode<DataType,MinimumSize>::create_parent(int32_t x, int32_t y, int32_t w, int32_t h) {
299 /*
300 If used only by the tree, these two are superfluous.
301 */
302 if( contains(x,y,w,h) )
303 return this;
304 if( m_parent )
305 return m_parent;
306
307 if (x >= m_x) {
308 if (y >= m_y) { // we are node 0
309 m_parent = new QuadNode(0L,m_x,m_y,m_size*2);
310 m_parent->m_nodes[0] = this;
311 return m_parent;
312 }
313 if (y + w < m_y + m_size) { // we are node 2
314 m_parent = new QuadNode(0L,m_x,m_y - m_size,m_size*2);
315 m_parent->m_nodes[2] = this;
316 return m_parent;
317 }
318 }
319 if (x + h < m_x + m_size) {
320 if (y >= m_y) { // we are node 1
321 m_parent = new QuadNode(0L,m_x-m_size,m_y,m_size*2);
322 m_parent->m_nodes[1] = this;
323 return m_parent;
324 }
325 if (y + w < m_y + m_size) { // we are node 3
326 m_parent = new QuadNode(0L,m_x-m_size,m_y - m_size,m_size*2);
327 m_parent->m_nodes[3] = this;
328 return m_parent;
329 }
330 }
331
332 // It does not matter....
333 m_parent = new QuadNode(0L,m_x,m_y,m_size*2);
334 m_parent->m_nodes[0] = this;
335 return m_parent;
336 }
337
338 template<typename DataType,int32_t MinimumSize>
splice()339 void QuadNode<DataType,MinimumSize>::splice() {
340 if (m_size <= MinimumSize)
341 return;
342
343 if( m_nodes[0] == 0) {
344 m_nodes[0] = new QuadNode<DataType,MinimumSize>(this,m_x,m_y,m_size/2);
345 }
346 if( m_nodes[1] == 0) {
347 m_nodes[1] = new QuadNode<DataType,MinimumSize>(this,m_x + m_size/2,m_y,m_size/2);
348 }
349 if( m_nodes[2] == 0) {
350 m_nodes[2] = new QuadNode<DataType,MinimumSize>(this,m_x,m_y + m_size/2,m_size/2);
351 }
352 if( m_nodes[3] == 0) {
353 m_nodes[3] = new QuadNode<DataType,MinimumSize>(this,m_x + m_size/2,m_y + m_size/2,m_size/2);
354 }
355 }
356
357 template<typename DataType,int32_t MinimumSize>
358 QuadNode<DataType,MinimumSize>*
find_container(int32_t x,int32_t y,int32_t w,int32_t h)359 QuadTree<DataType,MinimumSize>::find_container(int32_t x, int32_t y, int32_t w, int32_t h) {
360 m_cursor = m_cursor->find_container(x,y,w,h);
361 while( m_cursor == 0L ) {
362 m_root = m_root->create_parent(x,y,w,h);
363 m_cursor = m_root->find_container(x,y,w,h);
364 }
365 return m_cursor;
366 }
367
368
369 }
370
371 #endif // QUADTREE_H
372