Better Fast Moving Object Collision Detection

Following on from this post: Double hit on object collision and repeat trigger

I’m now focusing on the collision detection algorithm used in my program, rather than the simple detection used in the post above I want to account for the movement of the objects to ensure collision detection.

To make it simpler I have stripped out all the buoy stuff and am just working with circles and waves. The circles move around the screen and the waves expand hitting the circles, creating more waves, each wave can only trigger a collision once per circle and new waves created can’t trigger any circles in the chain before them (hope that makes sense!).

Based on @NumericPrime’s advice and reading around I have been trying to implement better collision detection for fast moving objects by constructing a line between each circles previous x/y and current x/y, and then checking if any point on that line is wave.radius distance away from the centre of the wave.

For some reason the circles are being triggered multiple times by the waves on each collision, maybe this has something to do with mixing int and float types but I can’t get my head around it.

Do I need to account for the movement/expansion of the wave each frame?

Am I doing what I think I’m doing?!?

Any help appreciated :slight_smile:

Here is the code:

import java.util.Iterator;

ArrayList<Circ> circs = new ArrayList<Circ>();
int numcircs = 2;

ArrayList<Wave> waves = new ArrayList<Wave>();
int time;

void setup() {
  size(800, 800);
  for (int a = 1; a < numcircs +1; a++) {
    Circ c = new Circ(random(100, width-100), random(100, height-100), a);
    circs.add(c);
  }
}

void draw() {
  background(0);
  for ( Circ i : circs) {
    i.update();
    i.show();
  }
  makeWaves();
  checkHits(circs);
}

class Circ {
  int id;
  float x; //current x 
  float y; //current y
  float speed;
  float xdirection; //x angle of motion
  float ydirection; //y angle of motion
  float px; //x last frame
  float py; //y last frame
  float vx; //x velocity
  float vy; //y velocity
  color c;
  int size = 50;
  int limit = size/2;

  Circ(float startx, float starty, int i) {
    id = i;
    x = startx;
    y = starty;
    speed = 10;
    float startd = random(0, 2*PI);
    xdirection = startd;
    ydirection = startd;
    //calculate velocities based on angle of motion
    vx = cos(xdirection)*speed;
    vy = sin(ydirection)*speed;
  }

  void update() {
    //save old x/y
    px = x;
    py = y;
    if ( (x < limit) || (x > width - limit)) {
      xdirection += PI;
    }
    if ( (y < limit) || (y > height- limit)) {
      ydirection += PI;
    }
    //update velocities
    vx = cos(xdirection)*speed;
    vy = sin(ydirection)*speed;
    //update x/y locations
    x += vx;
    y += vy;
  }

  void show() {
    ellipseMode(CENTER);
    fill(255);
    stroke(255);
    ellipse(x, y, size, size);
  }
}

class Wave {
  float xpos, ypos, maxdia, dia, speed, setf;
  color colour;
  int alphalevel;
  int[] hitcircs;

  Wave ( float x, float y, int sd, float md, float s, int sf, color c, int[] hc) {
    xpos = x;
    ypos = y;
    maxdia = md; //set max diameter for wave
    dia = sd; //set start diameter for wave
    speed = s;
    setf = sf;
    alphalevel = 255;
    colour = c;
    hitcircs = hc;
  }
  void update() {
    if ( setf > 0) {
      alphalevel = int(map( dia, 0, maxdia, 255, 0));
    }
    strokeWeight(5);
    noFill();
    stroke(color(colour, alphalevel));
    ellipse(xpos, ypos, dia, dia);
    dia += speed;
  }
}

void makeWaves() {
  if ( millis() > time) {
    int[] init = {0};
    waves.add(new Wave(width, height/2, 0, 2*width, random(2, 4), 1, color(0, random(40, 240), random(220, 255)), init));
    if ( random(0, 1) > 0.9) {
      time = millis() + int(random(1600, 2000));
    } else {
      time = millis() + int(random(4000, 8000));
    }
  }

  Iterator itrW = waves.iterator();
  Wave waveElement = null;
  while (itrW.hasNext()) {
    waveElement = (Wave)itrW.next();
    waveElement.update();
    if (waveElement.dia > waveElement.maxdia) {
      itrW.remove();
    }
  }
}

void checkHits(ArrayList circs) {
  //create arraylist to add circwaves to
  ArrayList<Wave> circwaves = new ArrayList<Wave>();
  //iterate through circs
  Iterator itrC = circs.iterator();
  Circ circElement = null;
  while (itrC.hasNext()) {
    circElement = (Circ)itrC.next();
    //iterate through waves
    for (Wave wave : waves) {  
      //check this circ is not int the array of circs already hit by this wave so only strike once
      boolean hitbefore = false;
      for (int a : wave.hitcircs) {
        if (a == circElement.id) {
          hitbefore = true;
        }
      }
      if (hitbefore == false) {
        float r = wave.dia/2;
        float px = circElement.px;
        float py = circElement.py;
        float x = circElement.x;
        float y = circElement.y;
        float vx = circElement.vx;
        float vy = circElement.vy;
        //calculate distance traveled by the circ last frame to this
        float circdisttravel = dist(px, py, x, y);
        //iterate over the line and check each point against distance from centre of wave
        for (int i = 0; i <= circdisttravel; i++) {
          int xtocheck = int(px + (vx*(i/circdisttravel)));
          int ytocheck = int(py + (vy*(i/circdisttravel)));
          int diff = int(dist(xtocheck, ytocheck, wave.xpos, wave.ypos) - r);
          if (diff == 0 ) {
            //add this circ to the array of circs alreay hit by this wave to avoid double strike
            wave.hitcircs = append(wave.hitcircs, circElement.id);
            //create new circ wave which inherits circs already hit by the wave that triggered it
            circwaves.add(new Wave(circElement.x, circElement.y, circElement.size, map(wave.alphalevel, 0, 255, circElement.size, 800), random(1, 2), 1, 255, wave.hitcircs));
          }
        }
      }
    }
  }
  waves.addAll(circwaves);
}

You could make variables like xold and yold and override them with the current ones at the end of a movement. E.g. here is a line that is drawn to the last x/y.

float x,y=0;
float xold,yold=0;
void setup(){}
void draw(){
x+=random(1,100);
y+=random(1,100);
line(xold,yold,x,y);
xold=x;
yold=y;
}