Java-Gaming.org Hi !
 Featured games (84) games approved by the League of Dukes Games in Showcase (574) Games in Android Showcase (154) games submitted by our members Games in WIP (620) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Basic Collision Detection  (Read 10359 times) 0 Members and 1 Guest are viewing this topic.
DrHalfway
 « Posted 2012-09-07 02:49:23 »

Hello Again and welcome to basic collision detection tutorial, I'm not good at writing tutorials but i'll do my best here. In this tutorial we will be exploring very basic collision detection on two of the most used primitive types. Axis Aligned Bounding Boxes and Circles (and their 3D variants). So lets get started.

First we are going to define a simple Vector class. This class is very straightforward, it simply defines two points, x and y for 2D. We will be using it as a position for the rest of the tutorial.

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17 `public class Vector {   public float x;   public float y;      public Vector() {      x = 0.0f;      y = 0.0f;   }                // returns the (squared) distance between this Vector and another   public float distSQ(final Vector vec) {      float distX = x - vec.x;      float distY = y - vec.y;            return distX * distX + distY * distY;   }}`

Let us go ahead and create our first Axis Aligned Bounding Box. We define it as follows.

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16 `public class AABB {   public Vector center;   public float r[];      public AABB(final float width, final float height) {      center = new Vector();      r = new float[2];      r[0] = width * 0.5f;      r[1] = height * 0.5f;   }      public void update(final Vector position) {      center.x = position.x;      center.y = position.y;   }}`

The AABB is also very straightforward, it has a Vector as its center point and a float array of size 2 defining its halfWidth and halfHeight which extend from the center itself. The update method simply updates the position of the AABB itself. This AABB can be effectively described in 3D by changing the size of r to 3 instead of 2. By defining a halfWidth extend in the Z axis, it is turned into a 3D AABB.

Let us go ahead and create our Circle. We define it as follows.

 1  2  3  4  5  6  7  8  9  10  11  12  13  14 `public class Circle {   public Vector center;   public float radius;      public Circle(final float radius) {      center = new Vector();      this.radius = radius;   }      public void update(final Vector position) {      center.x = position.x;      center.y = position.y;   }}`

The Circle is also fairly straightforward, it has a center point and a radius. The Circle can effectively be trated as a Sphere in 3D by adding a z axis in the Vector itself.

Let us define the most basic primitive tests. First we will define a test for AABB-AABB collision detection. We will define a "collision library" class of static methods that will test our primitives.

 1  2  3  4  5  6 `public class CollisionLibrary {   /*     * our static methods will go here. We can use this class by calling    * CollisionLibrary.method();    */}`

And our first static method is going to be for 2D AABB overlap test. We simply check the bounds of the AABB.

 1  2  3  4  5 `public static boolean testAABBAABB(final AABB box1, final AABB box2) {   if (Math.abs(box1.center.x - box2.center.x) > (box1.r[0] + box2.r[0])) return false;   if (Math.abs(box1.center.y - box2.center.y) > (box1.r[1] + box2.r[1])) return false;   return true;}`

To extend this test for 3D we simply need to check an extra axis. Below is the AABB (3D) test.

 1  2  3  4  5  6 `public static boolean testAABBAABB(final AABB box1, final AABB box2) {   if (Math.abs(box1.center.x - box2.center.x) > (box1.r[0] + box2.r[0])) return false;   if (Math.abs(box1.center.y - box2.center.y) > (box1.r[1] + box2.r[1])) return false;   if (Math.abs(box1.center.z - box2.center.z) > (box1.r[2] + box2.r[2])) return false;   return true;}`

Let us create our second method which will test Circle-Circle collision. We simply check to ensure the squared Distance is less than suqared sum of their radii.

 1  2  3  4  5  6 `public static boolean testCircleCircle(final Circle c1, final Circle c2) {   final float distSQ = c1.center.distSQ(c2.center);   final float radiusSum = c1.radius + c2.radius;         return distSQ <= radiusSum * radiusSum;}`

To extend this test for 3D we simply modify the Vector.distSQ function to take into account the Z axis. This will effectively turn this test into a Sphere-Sphere collision overlap.

Testing for Circle-AABB is quite a bit more involved. For this test we are going to define a new function called sqDistPointAABB(). It effectively takes a point and returns the (squared) distance between that point and the closest point found in the AABB itself. This multi-purpose function can also be used for Circle-Object Aligned Bounding Box (OBB) test by bringing the Circle to the OBB coordinate frame and trating the OBB as an AABB. We won't go into OBB's in this tutorial.

The function is as follows

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26 `public static float sqDistPointAABB(final Vector p, final AABB aabb) {   float sqDist = 0.0f;   float v;   float minX, minY, maxX, maxY;         // get the minX, maxX, minY and maxY points of the AABB   minX = aabb.center.x - aabb.r[0];   maxX = aabb.center.x + aabb.r[0];         minY = aabb.center.y - aabb.r[1];   maxY = aabb.center.y + aabb.r[1];         // test the bounds against the points X axis   v = p.x;         if (v < minX) sqDist += (minX - v) * (minX - v);   if (v > maxX) sqDist += (v - maxX) * (v - maxX);         // test the bounds against the points Y axis   v = p.y;         if (v < minY) sqDist += (minY - v) * (minY - v);   if (v > maxY) sqDist += (v - maxY) * (v - maxY);         return sqDist;}`

This function can be used for 3D AABB by testing against an extra axis. The 3D sqDistPointAABB function is as follows

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35 `public static float sqDistPointAABB(final Vector p, final AABB aabb) {   float sqDist = 0.0f;   float v;   float minX, minY, minZ, maxX, maxY, maxZ;         // get the minX, maxX, minY, maxY and minZ, maxZ points of the AABB   minX = aabb.center.x - aabb.r[0];   maxX = aabb.center.x + aabb.r[0];         minY = aabb.center.y - aabb.r[1];   maxY = aabb.center.y + aabb.r[1];         minZ = aabb.center.z - aabb.r[2];   maxZ = aabb.center.z + aabb.r[2];         // test the bounds against the points X axis   v = p.x;         if (v < minX) sqDist += (minX - v) * (minX - v);   if (v > maxX) sqDist += (v - maxX) * (v - maxX);         // test the bounds against the points Y axis   v = p.y;         if (v < minY) sqDist += (minY - v) * (minY - v);   if (v > maxY) sqDist += (v - maxY) * (v - maxY);         // test the bounds against the points Z axis   v = p.z;         if (v < minZ) sqDist += (minZ - v) * (minZ - v);   if (v > maxZ) sqDist += (v - maxZ) * (v - maxZ);         return sqDist;}`

And finally our new static function for testing AABB against a Circle is as follows. This method will work for Sphere and 3D AABB by switching the sqDistPointAABB to the 3D variant found above.

 1  2  3  4  5  6  7 `public static boolean testCircleAABB(final Circle circle, final AABB box) {   // get the squared distance between circle center and the AABB   float sqDist = sqDistPointAABB(circle.center, box);   float r = c.radius;         return sqDist <= r * r;}`

And there we have it! A simple method for testing overlaps between AABB's Circles AABB-Circle collisions. This tutorial would become too big for collsiion resolution, however it is not too difficult to modify the functions above to return the needed value to push both objects apart.

Here is a small test on how to use the functions

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21 `public class CollisionTest {   public static void main(String[] args) {      Circle circle = new Circle(5);      AABB box = new AABB(10,5);      Vector somePosition = new Vector();      somePosition.x = 10;      somePosition.y = 5;            // make sure to update the position of the colliders before testing for them      box.update(somePosition);      circle.update(somePosition);            // test for overlap      if(CollisionLibrary.testCircleAABB(circle,box)) {         // they are overlapping! do something      }      else {         // no overlap! continue happily      }   }}`

I hope this simple tutorial will be of some use to you the reader, any feedback is much appreciated! Good luck and have fun =]

Roquen
 « Reply #1 - Posted 2012-09-07 13:24:36 »

Showing up, posting code straight away AND writing a tutorial = awesome
DrHalfway
 « Reply #2 - Posted 2012-09-07 13:34:28 »

Just a fellow (novice) programmer, trying to do my part for the community

Ultroman

JGO Knight

Medals: 25
Projects: 1

Snappin' at snizzes since '83

 « Reply #3 - Posted 2012-09-07 13:49:54 »

DrHalfway, you went the full mile there. Good job

- Jonas
actual

JGO Coder

Medals: 24

 « Reply #4 - Posted 2012-09-07 22:18:33 »

A nice, concise article, thanks! One question I did have, was there a reason you used a two element array for the half width & half height? It seems like it would be easier to just have a halfHeight and halfWeight field, and would be more descriptive when using it.

DrHalfway
 « Reply #5 - Posted 2012-09-08 07:43:03 »

@ actual

No real reason, you can use any structure you like. This is a similar structure that we use in our engine because it allows us do to operations in a loop via accessing an index, for example our Vectors look something like this.

 1  2  3  4  5  6  7  8  9  10  11 `public class Vector {   public static final int X = 0;   public static final int Y = 1;   public static final int Z = 2;      public final float val[];      public Vector() {      val = new float[3];   }}`

This allows us for example to use a Vector in loop situations. As far as I know, there is no performance penalty either way, whatever suits you best =]

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15 `Vector vec = new Vector();float x = vec.val[Vector.X];// orfloat x = vec.val[0];// orfor (int i = 0; i < 3; i++) {   float vecVal = vec.val[i];      // perform some long operation on vecVal here}`

so short answer no specific reason, use whatever you are comfortable with

Pages: [1]
 ignore  |  Print

You cannot reply to this message, because it is very, very old.

 Riven (27 views) 2015-04-16 10:48:47 Duke0200 (42 views) 2015-04-16 01:59:01 Fairy Tailz (32 views) 2015-04-14 20:13:12 Riven (33 views) 2015-04-12 21:36:37 bus hotdog (49 views) 2015-04-10 02:39:32 CopyableCougar4 (51 views) 2015-04-10 00:51:04 BurntPizza (51 views) 2015-04-06 22:06:58 ags1 (53 views) 2015-04-02 10:58:48 Riven (52 views) 2015-04-01 18:27:05 ags1 (69 views) 2015-03-31 10:55:12
 theagentd 26x BurntPizza 18x wessles 15x 65K 11x kingroka123 11x Rayvolution 11x alwex 10x KevinWorkman 9x phu004 8x kevglass 8x ra4king 7x Olo 7x Roquen 7x chrislo27 7x Ecumene 7x Hanksha 7x
 How to: JGO Wikiby Mac702015-02-17 20:56:162D Dynamic Lighting2015-01-01 20:25:42How do I start Java Game Development?by gouessej2014-12-27 19:41:21Resources for WIP gamesby kpars2014-12-18 10:26:14Understanding relations between setOrigin, setScale and setPosition in libGdx2014-10-09 22:35:00Definite guide to supporting multiple device resolutions on Android (2014)2014-10-02 22:36:02List of Learning Resources2014-08-16 10:40:00List of Learning Resources2014-08-05 19:33:27
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org