Nested Loop in moving object collision extremely slow

kaskus

Hi, I am trying to create simple collision detection between moving objects from different direction. when the object meet the other object in close range they will detect collision and move up/down try not to collide each other. the problem is when i use nested loop to check the collision after 20 seconds of simulation the object move very slow. is it normal or is there a solution to optimize this. FYI my laptop specification is core i5. Here is my simple code.. thanks

ArrayList<Car> car;
int timer = 1000;
int _timer = 100;

void setup(){
  size(800,800);
  car = new ArrayList();
}

void draw(){
  background(0);

  text("millis="+millis(), 20, 20);

  for (int i = 0; i < car.size(); i++)
  {

    car.get(i).drawCar();
    car.get(i).move(car.get(i).getDx(), car.get(i).getDy());

    for (int j = i+1; j < car.size(); j++){  
      car.get(i).collideCircle(car.get(j));
    }


  }

  if(itstime()){
    car.add(new Car(-20, 360, 50, 30, random_color(255), 1, 2, 0, 1)); //x, y, w, h, c, d, dx, dy, t
    int ran = int(random(1000,1500));
    timer = timer + ran;
  }

  if(_itstime()){
    car.add(new Car(820, 360, 50, 30, random_color(255), -1, -2, 0, 1));
    int ran = int(random(1000,1500));
    _timer = _timer + ran;
  }

}

boolean itstime(){
  return millis() >= timer;
}

boolean _itstime(){
  return millis() >= _timer;
}

color random_color(float v) {
  return color(random(v), random(v), random(v));
}

//CAR CLASS
class Car {
  int x, y; //x position, y position
  int w, h; //weight, height/lenght
  color c; //color
  int direction; // 1 = left-to-right, 2 = right-to-left
  int dx, dy; //dx = x velocity, dy = y velocity
  int turn; //turn=> 1 = Straight, 2 = right, 3 = left
  int radius;

  Car(int x, int y, int w, int h, color c,int direction, int dx, int dy, int turn) {
    this.x = x;
    this.y = y;
    this.w = w;
    this.h = h;
    this.c = c;;
    this.direction = direction;
    this.dx = dx;
    this.dy = dy;
    this.turn = turn;
    this.radius = 20;
  }

  void drawCar() {
    fill(c);
    ellipse(x, y, radius, radius); 
  }

  int getDx(){
    return dx;
  }

  void setDx(int vx){
    this.dx = dx + vx;
  }

  int getDy(){
    return dy;
  }

  void setDy(int vy){
    this.dy = dy + vy;
  }

  void setDx_zero(){
    this.dx = 0;
  }

  int getDir(){
    return direction;
  }

  void move() {
    this.x = this.x + this.dx;
    this.y = this.y + this.dy;  
  }

  //with parameter
  void move(int dx, int dy) {
    this.dx = dx;
    this.dy = dy;

    this.x = this.x + this.dx;
    this.y = this.y + this.dy;
  }

  void collideCircle(Car other){

    println(direction+"  "+other.getDir()); 
    if(direction != other.getDir()){
      if (radius + other.radius > dist(x, y, other.x, other.y)){
        println("r1="+radius+" r2="+other.radius+ " x1="+x+ " x2="+other.x);
        setDx_zero();
        if(getDy() < 4){
          setDy(1);
        }else{
          setDy(0);
        }

        other.setDx_zero();
        if(other.getDy() < -4){
          other.setDy(0);
        }else{
          other.setDy(-1);
        }
      }else{
        println("No collision");
      }
    }
  } //collideCircle
}  

koogs

comment out the printlns. earlier versions of processing had problems writing too much to the console.

then add line 39 println("Size: ", cars.size());

koogs

also this:

int timer = 1000;
int _timer = 100;

why do this to yourself?

kaskus

comment out the printlns. earlier versions of processing had problems writing too much to the console.

then add line 39 println("Size: ", cars.size());

oh great it works better.. thank you

int timer = 1000; int _timer = 100;

first car appears and moves from both directions..

GoToLoop

for (int i = 0; i < car.size(); i++) {
  car.get(i).drawCar();
  car.get(i).move(car.get(i).getDx(), car.get(i).getDy());

  for (int j = i+1; j < car.size(); j++) {  
    car.get(i).collideCircle(car.get(j));
  }
}

It's worth noting how many times car.get(i) is invoked there! @-)

The returned value from car.get(i) should be cached in some local variable instead: *-:)

for (int len = car.size(), i = 0; i < len; ) {
  final Car c = car.get(i++);

  c.drawCar();
  c.move(c.getDx(), c.getDy());

  for (int j = i; j < len; c.collideCircle(car.get(j++)));
}

A similar online sketch w/ double collision check loop too: :bz
http://Studio.ProcessingTogether.com/sp/pad/export/ro.989GaZC5t7EkE

P.S.: B/c it is holding a container, variable car should have a plural name instead: cars. ;)

koogs

the bigger problem is that when the cars go offscreen nothing is done about them. the number of cars just keeps going up, the number of collisions keeps going up O(n^2)

if you have 10 cars then each step does 9 + 8 + 7 + ... + 2 comparisons = 45

if you have 20 cars then each step does 19 + 18 + 17 + ... + 2 comparisons = 190

100 cars = 4500 collisions

in general: n * (n -1) / 2

why do you think i got you to print out the number of cars?

Chrisir

When you remove () cars from ArrayList which are outside screen, remember to for loop backwards through the ArrayList