Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (539)
Games in Android Showcase (132)
games submitted by our members
Games in WIP (603)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Basic Collision Detection  (Read 9419 times)
0 Members and 1 Guest are viewing this topic.
Offline 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 =]

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

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

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

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline 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 Cheesy

- Jonas
Offline 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.

Offline 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];

// or

float x = vec.val[0];

// or

for (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  Grin

Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

rwatson462 (33 views)
2014-12-15 09:26:44

Mr.CodeIt (23 views)
2014-12-14 19:50:38

BurntPizza (51 views)
2014-12-09 22:41:13

BurntPizza (84 views)
2014-12-08 04:46:31

JscottyBieshaar (45 views)
2014-12-05 12:39:02

SHC (59 views)
2014-12-03 16:27:13

CopyableCougar4 (59 views)
2014-11-29 21:32:03

toopeicgaming1999 (123 views)
2014-11-26 15:22:04

toopeicgaming1999 (114 views)
2014-11-26 15:20:36

toopeicgaming1999 (32 views)
2014-11-26 15:20:08
Resources for WIP games
by kpars
2014-12-18 10:26:14

Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50
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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!