collisiondetector.h

Go to the documentation of this file.

/*
  Created by Fabrizio Di Vittorio (fdivitto2013@gmail.com) - <http://www.fabgl.com>
  Copyright (c) 2019-2022 Fabrizio Di Vittorio.
  All rights reserved.
 
 
* Please contact fdivitto2013@gmail.com if you need a commercial license.
 
 
* This library and related software is available under GPL v3.
 
  FabGL is free software: you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  (at your option) any later version.
 
  FabGL is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.
 
  You should have received a copy of the GNU General Public License
  along with FabGL.  If not, see <http://www.gnu.org/licenses/>.
 */
 
 
#pragma once
 
 
 
#include <stdint.h>
#include <stddef.h>
 
#include "fabglconf.h"
#include "displaycontroller.h"
 
 
 
namespace fabgl {
 
 
 
class CollisionDetector;
 
class QuadTree;
 
 
struct QuadTreeObject {
  QuadTree *       owner;
  QuadTreeObject * next;
  Sprite *         sprite;
 
  QuadTreeObject(QuadTreeObject * next_, Sprite * sprite_)
    : owner(nullptr), next(next_), sprite(sprite_)
  {
  }
};
 
 
#define QUADTREE_LEVEL_SPLIT_THRESHOLD 3
 
 
enum QuadTreeQuadrant {
  TopLeft,
  TopRight,
  BottomLeft,
  BottomRight,
  None,
};
 
 
typedef void (*CollisionDetectionCallback)(void * callbackObj, Sprite * spriteA, Sprite * spriteB, Point collisionPoint);
 
 
class QuadTree {
 
public:
 
  QuadTree(CollisionDetector * collisionDetector, QuadTree * parent, QuadTreeQuadrant quadrant, int x, int y, int width, int height);
 
  void insert(QuadTreeObject * object);
 
  static void remove(QuadTreeObject * object);
 
  //void dump(int level = 0);
 
  QuadTreeObject * detectCollision(QuadTreeObject * object, CollisionDetectionCallback callbackFunc = nullptr, void * callbackObj = nullptr);
 
  bool isEmpty();
 
  void detachFromParent();
 
  static void update(QuadTreeObject * object);
 
private:
 
  QuadTreeQuadrant getQuadrant(QuadTreeObject * object);
  void createQuadrant(QuadTreeQuadrant quadrant);
  bool objectsIntersect(QuadTreeObject * objectA, QuadTreeObject * objectB);
  bool objectIntersectsQuadTree(QuadTreeObject * object, QuadTree * quadTree);
  bool checkMaskCollision(QuadTreeObject * objectA, QuadTreeObject * objectB, Point * collisionPoint);
 
  static bool objectInRect(QuadTreeObject * object, int x, int y, int width, int height);
 
  CollisionDetector * m_collisionDetector;
  QuadTree *          m_parent;
  QuadTreeQuadrant    m_quadrant;
  int                 m_x;
  int                 m_y;
  int                 m_width;
  int                 m_height;
  QuadTreeObject *    m_objects;
  int                 m_objectsCount;
  QuadTree *          m_children[4]; // index is Quadrant
 
};
 
 
 
class CollisionDetector {
 
friend class QuadTree;
 
public:
 
  CollisionDetector(int maxObjectsCount, int width, int height);
 
  ~CollisionDetector();
 
  void addSprite(Sprite * sprite);
 
  void removeSprite(Sprite * sprite);
 
  Sprite * detectCollision(Sprite * sprite, bool removeCollidingSprites = true);
 
  void detectCollision(Sprite * sprite, CollisionDetectionCallback callbackFunc, void * callbackObj);
 
  void update(Sprite * sprite);
 
  Sprite * updateAndDetectCollision(Sprite * sprite, bool removeCollidingSprites = true);
 
  void updateAndDetectCollision(Sprite * sprite, CollisionDetectionCallback callbackFunc, void * callbackObj);
 
  //void dump();
 
 
private:
 
  QuadTree * initEmptyQuadTree(QuadTree * parent, QuadTreeQuadrant quadrant, int x, int y, int width, int height);
 
 
  QuadTree *       m_rootQuadTree;
  QuadTree *       m_quadTreePool;
  int              m_quadTreePoolSize;
  QuadTreeObject * m_objectPool;
  int              m_objectPoolSize;
};
 
 
 
 
 
} // end of namespace