1
\$\begingroup\$

I'm making a simple and easy game and I need to detect the collision between 2 boxes. It only needs to return trueor false, no physics involved.

I started working and couldn't find an algorithm that would check the collision for turned squares.

Here I visualized the problem. enter image description here

As you can see squares 1, 2 and 3 would return true because they collide with the green squares. 4 would return false because it isn't colliding.

I do have all the squares of both colors in separate array lists.

Does anybody know a library or algorithm for this problem? Thanks in advance.

\$\endgroup\$
  • 1
    \$\begingroup\$ You might want to consider another interesting corner-case: i.imgur.com/Q1DKpp1.png \$\endgroup\$ – Philipp Jul 24 '15 at 11:33
2
\$\begingroup\$

Box2D has a Java library. It might be a bit more than you need but it's pretty robust and used in all sorts of projects. Maybe someone else can recommend a better library solely for collision detection.

If you want to roll your own solution, which would probably be better if you want to keep it simple, you'll need to look into Oriented Bounding Box (OBB) collision detection. The Axis Aligned Bounding Box (AABB) algorithm is super simple but OBB is not nearly as nice. It requires a fair amount of math involving matrices so if you're not solid on that this is a great opportunity to learn.

Separating Axis Theorem (SAT) might be a bit much for 2d OBBs but it's a solid multi-purpose collision detection algorithm. Gilbert–Johnson–Keerthi (GJK) is another algorithm that's used more for objects that are in motion but may also be good for your needs.

Real-time Collision Detection by Christopher Ericson has some really great samples and the book is great for all things related to collision detection. The book actually has a really great example method that I don't think I can paste here because of copyright. However there are always more examples online.

http://rocketmandevelopment.com/blog/separation-of-axis-theorem-for-collision-detection/

http://back2basic.phatcode.net/?Issue_%231:2D_Convex_Polygon_Collision_using_SAT

\$\endgroup\$
  • 1
    \$\begingroup\$ SAT is what is needed. The links given in this answer are overly complex in my opinion though. Here is a great tutorial about 2D polygon physics from MetaNet Software which covers SAT. It has some nice interactive examples as well so you can see how the algorithm behaves. metanetsoftware.com/technique/tutorialA.html \$\endgroup\$ – Fuzzy Logic Jul 23 '15 at 20:39
0
\$\begingroup\$

You're assumption that you do not need any physics is wrong, anytime you are dealing with moving objects in 1D, 2D, 3D... environments and you need to detect if two objects will collide then you are doing physics calculations. You can not get away from it.

Returning true or false is easy, but figuring out if a collision has happened or not can range from simple to extremely complex. Let's say you have something like this:

class RenderModel {
private:
    Vector3 m_size;      // For 2D Set Z to 0 and Ignore
    Vector3 m_origin;    // Center Point Of The Model
    Vector3 m_position;  // Position In World Space
    std::vector<Vector3> m_vMeshCoordinates;
    std::vector<Vector2> m_vTextureCoordinates;

public:
   Model( Vector3& worldPosition, Vector3& size );
   virtual ~Model();

   virtual void render() = 0; // Purely Virtual
   virtual void update() = 0; // Purely Virtual

private:
    RenderModel( const RenderModel& c ); // not implemented
    RenderModel& operator=( const RenderModel& c ); // not implemented

}; // RenderModel

class Box : public RenderModel {
public:
    Box( Vector3& worldPosition, Vector3& size );
    virtual ~Box();

    virtual void render() override;
    virtual void update() override;

private:
    Box( const Box& c ); // not implemented
    Box& operator=( const Box& c ); // not implemented
}; // Box       

Here we have a class hierarchy were RenderModel is abstract and can not be instantiated but a derived class can be. With this setup each model type would have to implement its own render & update function.

The render call will only draw its contents and the update function is where the object's world position will change.

If you are working with only a 2D environment then I would use an Edge Detecting system with simple ray tracing or Bounding Circles around each object and check the distance between each radius and if they intersect. You need to incorporate a property to these boxes or objects to define them if they are static or dynamic. All static objects will not move in the game or simulation. Anything dynamic will move.

Class WorldMap {
public: 
    enum BoundingType {
        // 2D
        BT_BOUNDING_TRIANGLE,  // Rarely Used
        BT_BOUNDING_BOX,
        BT_BOUNDING_CIRCLE,
        BT_BOUNDING_ELIPSE,
        // 3D
        BT_BOUDNING_PYRAMID,   // Rarely Used
        BT_BOUDNING_CUBE,      // Doesn't Have To Be Perfect Cube Just A 3D Box
        BT_BOUNDING_CYLINDER,
        BT_BOUNDING_SPHERE
    }; // BoundingType

    enum CollisionType {
        CT_RAY_TRACE,
        CT_LINE_INTERSECTION,
        CT_SHAPE_TO_SHAPE_INTERSECTION
  }; // CollisionType

private:
    std::vector<std::shared_ptr<RenderModel>> m_vStaticObjects;
    std::vector<std::shared_ptr<RenderModel>> m_vDynamicObjects;
    Vector3  m_origin;  // Center Location of World
    Vector3  m_size;    // Size Of World for 2D set Z to 0 and ignore

    // ... other various world elements, objects, properties etc.

public:
    WorldMap();
    ~WorldMap();

    void render();
    void update();

    bool testCollisions( const RenderModel& modelTested, const Vector3& velocity, const enum BoundingType& bt, const enum CollisionType& ct,   );

}; // WorldMap

bool WorldMap::testCollision( const RenderModel& modelTested, const Vector3& velocity, const enum BoundingType& bt, const enum CollisionType& ct ) {
    // Here you would need different case statements based on bounding type 
    // as well as collision type you are using.

    // The simplest for 2D is Circle against Circle, and you would return 
    // true or false if their radius intersects at the given moment of detection.

    // Since this WorldMap Class has two containers of shared ptrs of Render Model Objects 
    // where one is static and their world positions are fixed and 
    // the other container are objects that can be moved around in the world;
    // these two containers will help you simplify and reduce the number of calls to test for collisions.

    // Since you know that the static container of objects will not move 
    // you do not have to test them against another static object.

    // This leaves you with only testing Dynamic against Static and Dynamic against Dynamic.

    // If you want to get a little more advanced you can still use Circle to Circle 
    // intersection and use the velocity direction vector to add in ray tracing 
    // and if that ray doesn't see any other object then you know this object 
    // will always return false and can skip it.

    // If the ray does intersect into another object then this object will probably 
    // collide within a period of time.

    // You would then return true when the collision happens.               

} // testCollision

The nice thing about ray tracing is due to the fact that it looks ahead the entire time in that direction. If their are no bounding shapes in its sight then no collision will happen, this is cheaper then testing each object against every other object!

Think of the ray tracing algorithm in this manner. Your character has a bow and arrow and when you fire the arrow, you do not want your collision detection system to have this arrow test against every single block object etc each frame for that is very expensive. So what you do is use this arrows velocity - facing direction of motion and use that ray. Then you test to see if any object is inline with that ray. If anything does come into contact with that ray (peeking ahead) then you know a collision is possible within a short period of time. Now in 3D this same concept will apply however the Ray will not exactly work because of the Parabola that the arrow will cause as it moves over a long distance versus time due to simulation of gravity, but for short distances it can still be applied. So what I would do is have two bounding circles around your object of interest to be detecting for collision. The first radius is very close and encompasses all edges of your model. This inner circle is when the collision takes place and returns true, the outer circle is a specified radius to check to see if a collision is near! The larger you make the outer circle will be more tests that will be called on this render frame, the smaller this circle the less tests there will be called this render frame but more frames will be called before collision is detected. Keep this in mind to keep a nice balance between the two otherwise it can lead to a bottle neck in your application because one thread is stuck in a for loop doing many calculations and other threads are waiting on it.

Here is a website for reference to simple 2D collision detection algorithms devmag

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.