Collision detection book now online

jeffthompson

Hi everyone, I have finally had time to update a set of collision detection examples I built a few years ago, but it sort of morphed from a simple tutorial repo to an online book with interactive examples:

http://jeffreythompson.org/collision-detection/

Would very much appreciate any feedback, comments, suggestions, typo-finding, etc from everyone before it goes into wide release!

callmepaul

wow! amazing! I am new to processing so I can't give much feedback but I give you a thank you :)

_vk

Thanks for sharing!!! Great work. Congrats.

GoToLoop

Indeed it's very detailed & easy to follow. >:D<
However, I'd be gr8 if there was some more directly example codes too.
For example, when dealing w/ circles, we don't really need any sqrt() for collision purposes:

http://jeffreythompson.org/collision-detection/point-circle.php
https://github.com/jeffThompson/CollisionDetection/blob/master/CodeExamples/PointCircle/PointCircle.pde

// POINT/CIRCLE
boolean pointCircle(float px, float py, float cx, float cy, float r) {

  // get distance between the point and circle's center
  // using the Pythagorean Theorem
  float distX = px - cx;
  float distY = py - cy;
  float distance = sqrt( (distX*distX) + (distY*distY) );

  // if the distance is less than the circle's 
  // radius the point is inside!
  if (distance <= r) {
    return true;
  }
  return false;
}

All of the above can be synthesized in 1 return expression: *-:)

static final boolean pointCircle(float px, float py, float cx, float cy, float r) {
  return sq(px - cx) + sq(py - cy) <= r*r;
}

IMO, both the longer & shorter versions should be provided! O:-)

jeffthompson

Definitely a balance between simplicity/efficiency and clarity. The example above can definitely be shortened, but it loses readability, especially for new programmers. Hard to know if adding another example will be helpful, or confusing.

For example, this statement in the Polygon/Point example:

(vc.y > py) != (vn.y > py)

Does the same thing as this:

(vc.y > py && vn.y < py) || (vc.y < py && vn.y > py)

The first version is really clean and super smart, but it even took me a while to understand it. I debated leaving it in, and ultimately decided it was too clever to omit.

Chrisir

dist()

slow and easy....

jeffthompson

Yes! I skipped using dist() because I want the algorithms to be as clear as possible, step-by-step. It gets a little repetitive with all the Pythagorean theorem, for sure.

Did you find it annoying not to use dist()?

Chrisir

no, it's ok

GoToLoop

Hard to know if adding another example will be helpful, or confusing.

• Well as you just shown us, you already did for Polygon/Point! :-\"
• If it's explained it's merely a shorter version, I can't see why could n1 get confused about it. :-@
• And it is helpful b/c it's more efficient & concise code! $-)
• Most times in a game, collisions are done for a whole Collection of "sprites" against another 1!
• If you omit the shorter version, every1 who learns from your book most probably gonna keep using the less efficient model for all situations! :-<
• It's imperative to tip them that once they learn how it is done w/ the longer version, they can choose the shorter version for their projects! *-:)

P.S.: vc.y > py != vn.y > py can be replaced w/ (vc.y > py) ^ (vn.y > py). ;)
Although in this case there's no performance gain. Just another silly way to do it! :P

PhiLho

"Did you find it annoying not to use dist()?"
Explaining what is the algorithm is good, but perhaps you can mention that dist() is a shortcut for this formula.
Explaining that sqrt() is not necessary for distance checking can be explained as an optimization, near the end perhaps.

Unlike GoToLoop, I don't believe that shorter code is more performant, but dropping the sqrt() is really a good tip.

jeffthompson

Yes, there is an explanation about dist() in an early example. It sounds like a chapter on optimization at the end might be the way to go.

Any place you can point to showing that sqrt() is less efficient than dist()? I'd like to explain why/how that's the case.

jeffthompson

FWIW, there's a major disclaimer that the code is definitely not super efficient. The explanations are meant to be simple as a jumping off point – not for building whole game engines.

GoToLoop

Any place you can point to showing that sqrt() is less efficient than dist()?

dist() does the same thing as my shorter sq(px - cx) + sq(py - cy) example.
Only that it adds sqrt() as your longer example does:

https://github.com/processing/processing/blob/master/core/src/processing/core/PApplet.java#L4300

static public final float dist(float x1, float y1, float x2, float y2) {
  return sqrt(sq(x2-x1) + sq(y2-y1));
}

It'd be really gr8 if Processing had distSq() function just like "java.awt.geom" package got Point2D's distanceSq(): 8-|

http://docs.oracle.com/javase/8/docs/api/java/awt/geom/Point2D.html#distanceSq-double-double-double-double-

jeffthompson

A ran a little test with interesting results: my version using the vanilla Pythagorean Theorem is very fast (390ms for 1-billion calculations) versus dist() which took 400ms and an algorithm I found on a forum without square roots (392ms).

GoToLoop

Have you tested how my version fared compared to those? =P~

static final boolean pointCircle(float px, float py, float cx, float cy, float r) {
  return sq(px - cx) + sq(py - cy) < r*r;
}

jeffthompson

About the same for the distance calculation: 404ms.

GoToLoop

Indeed there's almost no diff. among those approaches. :-\"
Got no idea what kinda voodoo optimizations Java's runtime is doing behind the scenes! 8-}

Made 2 tests. 1 where coordinates are picked randomly once.
And the other coordinates are picked randomly for each single iteration:

static final int ITERS = MAX_INT - 1;

void setup() {
  size(1280, 800, JAVA2D);
  noLoop();

  int ms, i;

  float x1  = random(width), y1 = random(height);
  float x2  = random(width), y2 = random(height);
  float rad = random(width>>1);

  println(ITERS, "iterations for each function:\n");

  // warm-up for pointCircle():
  for (i = 0; i++ != ITERS>>1; pointCircle (x1, y1, x2, y2, rad));
  // commencing speed test for pointCircle():
  println("Starting pointCircle()...");
  ms = millis();
  for (i = 0; i++ != ITERS; pointCircle (x1, y1, x2, y2, rad));
  ms = millis() - ms;
  println("Finished pointCircle():", ms, '\n');

  // warm-up for distance():
  for (i = 0; i++ != ITERS>>1; distance (x1, y1, x2, y2, rad));
  // commencing speed test for distance():
  println("Starting distance()...");
  ms = millis();
  for (i = 0; i++ != ITERS; distance (x1, y1, x2, y2, rad));
  ms = millis() - ms;
  println("Finished distance():", ms, '\n');

  // warm-up for mouseDistInCircle():
  for (i = 0; i++ != ITERS>>1; mouseDistInCircle (x1, y1, x2, y2, rad));
  // commencing speed test for mouseDistInCircle():
  println("Starting mouseDistInCircle()...");
  ms = millis();
  for (i = 0; i++ != ITERS; mouseDistInCircle (x1, y1, x2, y2, rad));
  ms = millis() - ms;
  println("Finished mouseDistInCircle():", ms, '\n');

  // warm-up for mouseDistSqInCircle():
  for (i = 0; i++ != ITERS>>1; mouseDistSqInCircle (x1, y1, x2, y2, rad));
  // commencing speed test for mouseDistSqInCircle():
  println("Starting mouseDistSqInCircle()...");
  ms = millis();
  for (i = 0; i++ != ITERS; mouseDistSqInCircle (x1, y1, x2, y2, rad));
  ms = millis() - ms;
  println("Finished mouseDistSqInCircle():", ms, '\n');

  int ix1 = (int) random(width), iy1 = (int) random(height);
  int ix2 = (int) random(width), iy2 = (int) random(height);
  int irad = (int) random(width>>1);

  // warm-up for mouseDistSqInCircleInt():
  for (i = 0; i++ != ITERS>>1; mouseDistSqInCircleInt (ix1, iy1, ix2, iy2, irad));
  // commencing speed test for mouseDistSqInCircleInt():
  println("Starting mouseDistSqInCircleInt()...");
  ms = millis();
  for (i = 0; i++ != ITERS; mouseDistSqInCircleInt (ix1, iy1, ix2, iy2, irad));
  ms = millis() - ms;
  println("Finished mouseDistSqInCircleInt():", ms, '\n');

  exit();
}

static final boolean pointCircle(float px, float py, float cx, float cy, float r) {
  float distX = px - cx;
  float distY = py - cy;
  float distance = sqrt( (distX*distX) + (distY*distY) );

  if (distance < r) {
    return true;
  }

  return false;
}

static final boolean distance(double x1, double y1, double x2, double y2, double r) {
  double axD = Math.abs(x2 - x1);
  double ayD = Math.abs(y2 - y1);
  double dD  = Math.min(axD, ayD);

  double d = dD * 1.4142135623730950488016887242097;
  d += (axD - dD) + (ayD - dD);

  return d < r;
}

static final boolean mouseDistInCircle(float px, float py, float cx, float cy, float r) {
  return dist(px, py, cx, cy) < r;
}

static final boolean mouseDistSqInCircle(float px, float py, float cx, float cy, float r) {
  return sq(px - cx) + sq(py - cy) < r*r;
}

static final boolean mouseDistSqInCircleInt(int px, int py, int cx, int cy, int r) {
  return sq(px - cx) + sq(py - cy) < r*r;
}

static final int sq(int n) {
  return n*n;
}

GoToLoop

static final int ITERS = MAX_INT>>7;

float x1, y1, x2, y2, rad;

void setup() {
  size(1280, 800, JAVA2D);
  noLoop();

  int ms, i;

  println(ITERS, "iterations for each function:\n");

  // warm-up for pointCircle():
  for (i = 0; i++ != ITERS>>1; getRandomCoords (), pointCircle (x1, y1, x2, y2, rad));
  // commencing speed test for pointCircle():
  println("Starting pointCircle()...");
  ms = millis();
  for (i = 0; i++ != ITERS; getRandomCoords (), pointCircle (x1, y1, x2, y2, rad));
  ms = millis() - ms;
  println("Finished pointCircle():", ms, '\n');

  // warm-up for distance():
  for (i = 0; i++ != ITERS>>1; getRandomCoords (), distance (x1, y1, x2, y2, rad));
  // commencing speed test for distance():
  println("Starting distance()...");
  ms = millis();
  for (i = 0; i++ != ITERS; getRandomCoords (), distance (x1, y1, x2, y2, rad));
  ms = millis() - ms;
  println("Finished distance():", ms, '\n');

  // warm-up for mouseDistInCircle():
  for (i = 0; i++ != ITERS>>1; getRandomCoords (), mouseDistInCircle (x1, y1, x2, y2, rad));
  // commencing speed test for mouseDistInCircle():
  println("Starting mouseDistInCircle()...");
  ms = millis();
  for (i = 0; i++ != ITERS; getRandomCoords (), mouseDistInCircle (x1, y1, x2, y2, rad));
  ms = millis() - ms;
  println("Finished mouseDistInCircle():", ms, '\n');

  // warm-up for mouseDistSqInCircle():
  for (i = 0; i++ != ITERS>>1; getRandomCoords (), mouseDistSqInCircle (x1, y1, x2, y2, rad));
  // commencing speed test for mouseDistSqInCircle():
  println("Starting mouseDistSqInCircle()...");
  ms = millis();
  for (i = 0; i++ != ITERS; getRandomCoords (), mouseDistSqInCircle (x1, y1, x2, y2, rad));
  ms = millis() - ms;
  println("Finished mouseDistSqInCircle():", ms, '\n');

  // warm-up for mouseDistSqInCircleInt():
  for (i = 0; i++ != ITERS>>1; getRandomMouseDistSqInCircleInt ());
  // commencing speed test for mouseDistSqInCircleInt():
  println("Starting mouseDistSqInCircleInt()...");
  ms = millis();
  for (i = 0; i++ != ITERS; getRandomMouseDistSqInCircleInt ());
  ms = millis() - ms;
  println("Finished mouseDistSqInCircleInt():", ms, '\n');

  exit();
}

void getRandomCoords() {
  x1 = random(width);
  y1 = random(height);
  x2 = random(width);
  y2 = random(height);
  rad = random(width>>1);
}

boolean getRandomMouseDistSqInCircleInt() {
  int x1  = (int) random(width), y1 = (int) random(height);
  int x2  = (int) random(width), y2 = (int) random(height);
  int rad = (int) random(width>>1);

  return mouseDistSqInCircleInt(x1, y1, x2, y2, rad);
}

static final boolean pointCircle(float px, float py, float cx, float cy, float r) {
  float distX = px - cx;
  float distY = py - cy;
  float distance = sqrt( (distX*distX) + (distY*distY) );

  if (distance < r) {
    return true;
  }

  return false;
}

static final boolean distance(double x1, double y1, double x2, double y2, double r) {
  double axD = Math.abs(x2 - x1);
  double ayD = Math.abs(y2 - y1);
  double dD  = Math.min(axD, ayD);

  double d = dD * 1.4142135623730950488016887242097;
  d += (axD - dD) + (ayD - dD);

  return d < r;
}

static final boolean mouseDistInCircle(float px, float py, float cx, float cy, float r) {
  return dist(px, py, cx, cy) < r;
}

static final boolean mouseDistSqInCircle(float px, float py, float cx, float cy, float r) {
  return sq(px - cx) + sq(py - cy) < r*r;
}

static final boolean mouseDistSqInCircleInt(int px, int py, int cx, int cy, int r) {
  return sq(px - cx) + sq(py - cy) < r*r;
}

static final int sq(int n) {
  return n*n;
}

blindfish

I suspect avoiding the sqrt will provide better results in p5js, so it's worth including it as a possible optimisation. One thing I see a lot of in posted questions is unoptimised loops being used to do multi-object collision detection, so that's a good subject for a chapter ;)