Processing 1.0 - Processing Discourse - Collision checking within a certain area

We closed this forum 18 June 2010. It has served us well since 2005 as the ALPHA forum did before it from 2002 to 2005. New discussions are ongoing at the new URL http://forum.processing.org. You'll need to sign up and get a new user account. We're sorry about that inconvenience, but we think it's better in the long run. The content on this forum will remain online.

Index › Programming Questions & Help › Programs › Collision checking within a certain area

‹ Previous Topic | Next Topic ›

Pages: 1

Collision checking within a certain area (Read 848 times)

tomcrichton

Collision checking within a certain area
Oct 7^th, 2009, 1:01am

I'm trying to make a simple program where circles are randomly placed inside the sketch and grow. When one circle collides with another, they both stop growing. I've managed to make it all work (have a look here: musicandrambling<dot>com<slash>applet), but it's slow with more than 100 circles. This is because the 101st circle has to check for collision against 100 others and so on. I considered checking with circles that are within a 100px radius of the circle, but the only way I could think of was
Code:

if(PVector.dist(fillers[i].position, fillers[j].position) < 100)

Which is just as slow 'cause it still has to check against 100 circles. Can anyone think of a better way to check for collisions within a certain area?

Cheers,
Tom

EDIT: Almost as soon as I posted this, I worked out what was wrong Tongue

. I had the above code snippet called every frame, but since the circles don't move at all it can be called in setup().

I still want to know of other ways to do it, though- in the next version I'm going to replace my arrays with arraylists so that an unlimited number of circles can be created. However, this means that collision areas can't be defined in setup().

PhiLho

Re: Collision checking within a certain area
Reply #1 - Oct 7^th, 2009, 1:56am

Maybe your tests aren't as much efficient as they can be.
My computer isn't very fast, but using your idea, I can see 1000 circles to grow at a reasonable speed.
My code: Code:

final int BALL_NB = 1000;
final int MARGIN = 50;
Ball[] balls = new Ball[BALL_NB];

void setup()
{
  size(800, 800);
  smooth();

  for (int i = 0; i < BALL_NB; i++)
  {
    float x = random(MARGIN, width - MARGIN);
    float y = random(MARGIN, height - MARGIN);
    color c = color(random(50, 150), random(100, 200), random(150, 255));
    balls[i] = new Ball(x, y, c);
  }
}

void draw()
{
  boolean bOneCanGrow = false;
  for (int i = 0; i < BALL_NB; i++)
  {
    for (int j = 0; j < BALL_NB; j++)
    {
	if (i != j)
	{
	  if (dist(balls[i].posX, balls[i].posY, balls[j].posX, balls[j].posY) <=
		balls[i].radius + balls[j].radius)
	  {
	    balls[i].bCanGrow = balls[j].bCanGrow = false;
	  }
	}
    }
    if (balls[i].bCanGrow)
    {
	bOneCanGrow = true;
    }
  }
  if (bOneCanGrow)
  {
    background(#AAFFEE);
  }
  else
  {
    background(#EEFFEE);
  }
  for (int i = 0; i < BALL_NB; i++)
  {
    balls[i].Grow();
    balls[i].Display();
  }
}

class Ball
{
  float posX, posY; // Position
  float radius = 1;
  color ballColor;
  boolean bCanGrow = true;

  Ball(float px, float py, color c)
  {
    posX = px; posY = py;
    ballColor = c;
  }

  void Grow()
  {
    if (bCanGrow)
    {
	radius += 1;
    }
  }

  void Display()
  {
    noStroke();
    fill(ballColor);
    ellipse(posX, posY, radius * 2, radius * 2);
  }
}

I can still improve a bit the speed by tweaking the code, although probably not in a significant way.

I can see some ways to improve the speed, for example at start up, for each ball, sort the list of circles by distance to this ball, and keep the n closest. Then in the drawing loop, check only against this short list.

tomcrichton

Re: Collision checking within a certain area
Reply #2 - Oct 7^th, 2009, 2:30am

Thanks PhiLho! I never thought I'd get such awesome help. You're right- after seeing how it can be done, my code is hideously inefficient. Arrays all over the show. I think I'd better start over again and try to reuse things as much as possible.

Out of interest, why do you put 'final' in front of some of the variables at the beginning? The reference says that final stops them from being changed later on, but you don't try to change them. Do the variables require less memory that way?

PhiLho

Re: Collision checking within a certain area
Reply #3 - Oct 7^th, 2009, 3:16am

The final keyword: it is just a way to mark a "variable" as constant.
It is an indication for the compiler, which will error out if somebody attempts to change such value. The compiler might also make some optimization for such variables (but don't expect wonders!).
It is a bit "show off" in such small sketch, but I still think it is a good habit to take, so I try and put it when needed. Note that a constant in a class which you expect to be instanced lot of times should be marked as "static" as well, so that its value is shared among all the instances: the value isn't duplicated.
Lastly, it can be useful if you make a library (a re-usable class): this way you ensure some user won't change data you expect to be immutable!

Pages: 1

‹ Previous Topic | Next Topic ›