23 #include "freertos/FreeRTOS.h" 24 #include "freertos/task.h" 42 QuadTree::QuadTree(CollisionDetector * collisionDetector, QuadTree * parent, QuadTreeQuadrant quadrant,
int x,
int y,
int width,
int height)
44 m_collisionDetector = collisionDetector;
46 m_quadrant = quadrant;
53 m_children[TopLeft] =
nullptr;
54 m_children[TopRight] =
nullptr;
55 m_children[BottomLeft] =
nullptr;
56 m_children[BottomRight] =
nullptr;
60 bool QuadTree::isEmpty()
62 return m_objectsCount == 0 &&
63 m_children[TopLeft] ==
nullptr &&
64 m_children[TopRight] ==
nullptr &&
65 m_children[BottomLeft] ==
nullptr &&
66 m_children[BottomRight] ==
nullptr;
70 void QuadTree::detachFromParent()
73 m_parent->m_children[m_quadrant] =
nullptr;
79 void QuadTree::insert(QuadTreeObject *
object)
81 QuadTreeQuadrant quadrant = getQuadrant(
object);
82 if (quadrant !=
None && m_children[quadrant]) {
83 m_children[quadrant]->insert(
object);
88 object->next = m_objects;
92 if (m_objectsCount < QUADTREE_LEVEL_SPLIT_THRESHOLD)
97 QuadTreeObject * obj = m_objects;
98 QuadTreeObject * prev =
nullptr;
100 QuadTreeObject * next = obj->next;
101 QuadTreeQuadrant quadrant = getQuadrant(obj);
102 if (quadrant !=
None) {
103 createQuadrant(quadrant);
104 m_children[quadrant]->insert(obj);
118 void QuadTree::remove(QuadTreeObject *
object)
121 QuadTreeObject * obj =
object->owner->m_objects;
122 QuadTreeObject * prev =
nullptr;
126 object->owner->m_objects =
object->next;
128 prev->next =
object->next;
134 object->owner->m_objectsCount -= 1;
135 object->owner =
nullptr;
136 object->next =
nullptr;
140 void QuadTree::createQuadrant(QuadTreeQuadrant quadrant)
142 if (m_children[quadrant] ==
nullptr) {
143 int halfWidth = m_width >> 1;
144 int halfHeight = m_height >> 1;
147 m_children[TopLeft] = m_collisionDetector->initEmptyQuadTree(
this, TopLeft, m_x, m_y, halfWidth, halfHeight);
150 m_children[TopRight] = m_collisionDetector->initEmptyQuadTree(
this, TopRight, m_x + halfWidth, m_y, halfWidth, halfHeight);
153 m_children[BottomLeft] = m_collisionDetector->initEmptyQuadTree(
this, BottomLeft, m_x, m_y + halfHeight, halfWidth, halfHeight);
156 m_children[BottomRight] = m_collisionDetector->initEmptyQuadTree(
this, BottomRight, m_x + halfWidth, m_y + halfHeight, halfWidth, halfHeight);
166 bool QuadTree::objectInRect(QuadTreeObject *
object,
int x,
int y,
int width,
int height)
168 return (object->sprite->x >= x) &&
169 (
object->sprite->y >= y) &&
170 (object->sprite->x + object->sprite->getWidth() <= x +
width) &&
171 (object->sprite->y + object->sprite->getHeight() <= y +
height);
175 QuadTreeQuadrant QuadTree::getQuadrant(QuadTreeObject *
object)
177 int hWidth = m_width >> 1;
178 int hHeight = m_height >> 1;
179 if (objectInRect(
object, m_x, m_y, hWidth, hHeight))
181 if (objectInRect(
object, m_x + hWidth, m_y, hWidth, hHeight))
183 if (objectInRect(
object, m_x, m_y + hHeight, hWidth, hHeight))
185 if (objectInRect(
object, m_x + hWidth, m_y + hHeight, hWidth, hHeight))
191 void QuadTree::update(QuadTreeObject *
object)
193 QuadTree * qtree =
object->owner;
195 if (qtree->m_parent ==
nullptr || objectInRect(
object, qtree->m_x, qtree->m_y, qtree->m_width, qtree->m_height)) {
197 QuadTreeQuadrant quadrant = qtree->getQuadrant(
object);
198 if (qtree == object->owner && qtree->m_children[quadrant] ==
nullptr)
205 qtree->insert(
object);
208 qtree = qtree->m_parent;
215 QuadTreeObject * QuadTree::detectCollision(QuadTreeObject *
object, CollisionDetectionCallback callbackFunc,
void * callbackObj)
217 if (!object->sprite->visible)
221 QuadTreeObject * obj = m_objects;
223 QuadTreeObject * next = obj->next;
225 Point collisionPoint;
226 if (
object != obj && obj->sprite->visible && objectsIntersect(
object, obj) && checkMaskCollision(
object, obj, &collisionPoint)) {
229 callbackFunc(callbackObj, object->sprite, obj->sprite, collisionPoint);
237 QuadTreeQuadrant quadrant = getQuadrant(
object);
238 if (quadrant !=
None) {
240 if (m_children[quadrant])
241 return m_children[quadrant]->detectCollision(
object, callbackFunc, callbackObj);
244 for (
int i = 0; i < 4; ++i) {
245 QuadTreeObject * obj = m_children[i] && objectIntersectsQuadTree(
object, m_children[i]) ? m_children[i]->detectCollision(
object, callbackFunc, callbackObj) :
nullptr;
246 if (obj && !callbackFunc)
255 bool QuadTree::objectsIntersect(QuadTreeObject * objectA, QuadTreeObject * objectB)
257 return objectA->sprite->x + objectA->sprite->getWidth() >= objectB->sprite->x &&
258 objectB->sprite->x + objectB->sprite->getWidth() >= objectA->sprite->x &&
259 objectA->sprite->y + objectA->sprite->getHeight() >= objectB->sprite->y &&
260 objectB->sprite->y + objectB->sprite->getHeight() >= objectA->sprite->y;
265 bool QuadTree::objectIntersectsQuadTree(QuadTreeObject *
object, QuadTree * quadTree)
267 return object->sprite->x +
object->sprite->getWidth() >= quadTree->m_x &&
268 quadTree->m_x + quadTree->m_width >=
object->sprite->x &&
269 object->sprite->y +
object->sprite->getHeight() >= quadTree->m_y &&
270 quadTree->m_y + quadTree->m_height >=
object->sprite->y;
274 bool QuadTree::checkMaskCollision(QuadTreeObject * objectA, QuadTreeObject * objectB, Point * collisionPoint)
277 int x1 = tmax(objectA->sprite->x, objectB->sprite->x);
278 int y1 = tmax(objectA->sprite->y, objectB->sprite->y);
279 int x2 = tmin(objectA->sprite->x + objectA->sprite->getWidth() - 1, objectB->sprite->x + objectB->sprite->getWidth() - 1);
280 int y2 = tmin(objectA->sprite->y + objectA->sprite->getHeight() - 1, objectB->sprite->y + objectB->sprite->getHeight() - 1);
283 Bitmap * bitmapA = objectA->sprite->getFrame();
284 Bitmap * bitmapB = objectB->sprite->getFrame();
287 for (
int y = y1; y <= y2; ++y) {
288 uint8_t
const * rowA = bitmapA->data + bitmapA->width * (y - objectA->sprite->y);
289 uint8_t
const * rowB = bitmapB->data + bitmapB->width * (y - objectB->sprite->y);
290 for (
int x = x1; x <= x2; ++x) {
291 int alphaA = rowA[x - objectA->sprite->x] >> 6;
292 int alphaB = rowB[x - objectB->sprite->x] >> 6;
293 if (alphaA && alphaB) {
294 *collisionPoint = (Point){(int16_t)x, (int16_t)y};
301 for (
int y = y1; y <= y2; ++y) {
302 for (
int x = x1; x <= x2; ++x) {
303 int alphaA = bitmapA->getAlpha(x - objectA->sprite->x, y - objectA->sprite->y);
304 int alphaB = bitmapB->getAlpha(x - objectB->sprite->x, y - objectB->sprite->y);
305 if (alphaA && alphaB) {
306 *collisionPoint = (Point){(int16_t)x, (int16_t)y};
342 : m_quadTreePool(nullptr), m_objectPool(nullptr)
344 m_objectPoolSize = maxObjectsCount;
345 m_quadTreePoolSize = (5 * maxObjectsCount + 1) / 3;
347 if (maxObjectsCount > 0) {
350 m_quadTreePool = (QuadTree*) malloc(
sizeof(QuadTree) * m_quadTreePoolSize);
353 m_quadTreePool[0] = QuadTree(
this,
nullptr,
None, 0, 0,
width,
height);
354 m_rootQuadTree = m_quadTreePool;
357 for (
int i = 1; i < m_quadTreePoolSize; ++i)
358 m_quadTreePool[i] = QuadTree(
this,
nullptr,
None, 0, 0, 0, 0);
361 m_objectPool = (QuadTreeObject*) malloc(
sizeof(QuadTreeObject) * m_objectPoolSize);
362 for (
int i = 0; i < m_objectPoolSize; ++i)
363 m_objectPool[i] = QuadTreeObject(
nullptr,
nullptr);
369 CollisionDetector::~CollisionDetector()
371 free(m_quadTreePool);
376 QuadTree * CollisionDetector::initEmptyQuadTree(QuadTree * parent, QuadTreeQuadrant quadrant,
int x,
int y,
int width,
int height)
379 for (
int i = 1; i < m_quadTreePoolSize; ++i) {
380 if (m_quadTreePool[i].isEmpty()) {
381 m_quadTreePool[i].detachFromParent();
382 m_quadTreePool[i] = QuadTree(
this, parent, quadrant, x, y,
width,
height);
383 return &m_quadTreePool[i];
386 assert(
false &&
"No enough quadtrees");
393 for (
int i = 0; i < m_objectPoolSize; ++i)
394 if (m_objectPool[i].sprite ==
nullptr) {
395 QuadTreeObject * obj = &m_objectPool[i];
396 obj->sprite = sprite;
397 sprite->collisionDetectorObject = obj;
398 m_rootQuadTree->insert(obj);
401 assert(
false &&
"No enough objects");
407 QuadTree::remove(sprite->collisionDetectorObject);
408 sprite->collisionDetectorObject->sprite =
nullptr;
422 QuadTreeObject * obj = m_rootQuadTree->detectCollision(sprite->collisionDetectorObject);
424 Sprite * cSprite = obj->sprite;
435 m_rootQuadTree->detectCollision(sprite->collisionDetectorObject, callbackFunc, callbackObj);
441 m_rootQuadTree->update(sprite->collisionDetectorObject);
This file contains fabgl::CollisionDetector class definition.
void addSprite(Sprite *sprite)
Adds the specified sprite to collision detector.
CollisionDetector(int maxObjectsCount, int width, int height)
Creates an instance of CollisionDetector.
void removeSprite(Sprite *sprite)
Removes the specified sprite from collision detector.
This file contains some utility classes and functions.
Sprite * detectCollision(Sprite *sprite, bool removeCollidingSprites=true)
Detects first collision with the specified sprite.
Sprite * updateAndDetectCollision(Sprite *sprite, bool removeCollidingSprites=true)
Updates collision detector and detect collision with the specified sprite.
void update(Sprite *sprite)
Updates collision detector.