[SOLVED] collision and obstacles detection

m4l4

Hi, i'm working on the next phase of my project (https://forum.processing.org/two/discussion/23539/genetic-algorithm-driven-ecosystem), i've managed to implement a neural network for the creatures (as soon as i finish commenting it i'll share the whole code) and now i'm trying to improve the creatures perception of the environment. right now they just perceive the environment by triangulating the distance of the closest food source (distance from body, distance from antenna sx and antenna dx).

i've made a simple code to explain what i'd like to achieve:

you can move the ship with WASD, the ship has 5 eyes represented by lines, length of the lines represent how far it can sees. there are random obstacles of random dimension and random color.

i've made a function (collision) to calculate the minimum distance from an obstacle (ship radius/2 + obstacle radius/2) and to check if we are exceeding those values (the ship turns red if we touch something).

now, first of all i'd like the ship to be unable to update its position if that means exceeding the minimum distance from something (ie. ship gets stuck even if slightly touching something diagonally).

and the most important thing: the lines representing the eyes should modify their length if they touch something, that way i can calculate objects distance and position by simply looking at the various lines sizes. Optional the line should be able to get the rgb color of the object they are "seeing".

I know i'm asking a lot, but bare with me and i'll present you a fully functional, easy to use (sort of), Neural Network to play with :D

Ship myShip;

float obsNum;
ArrayList<Obstacle> obstacles;
boolean [] keys = new boolean[128];

void setup() {
  size(600, 600); 
  smooth();
  myShip = new Ship();
  obsNum = 5;
  obstacles = new ArrayList<Obstacle>();
  for (int i = 0; i < obsNum; i++){
    obstacles.add(new Obstacle(random(width), random(height)));
  }
}

void draw() {
  background(255);
  myShip.run();
  for (int i = 0; i < obstacles.size(); i++){
    Obstacle o = obstacles.get(i);
    o.display();
  }
}

void keyPressed() {    //allows to move while rotate
  keys[key] = true;
}

void keyReleased() {
  keys[key] = false;
}


class Ship {  
  PVector pos, vel;     // position and velocity
  int speed;            // constant speed
  float theta;          // angle of rotation
  float rotS;           // rotation speed
  float sight;          //sight distance
  float sightSpread;    //distance between eyes
  float radius;         //radius of the ship
  float col;            //color of the ship

  Ship() {
    speed = 5;
    rotS = 5;
    theta = 0;          // must be initialized at 0°
    sight = 200;
    sightSpread = 30;
    radius = 50;
    col = 0;
    pos = new PVector(width/2, height/2);
    vel = new PVector();
  }

  void run() {        //generic function container 
    move();
    collision();
    display();
  }

  void move() {
    vel.x = speed*cos(theta);  //this modify vel.x and vel.y
    vel.y = speed*sin(theta);  //based ont the actual angle

    if (keys['w'])              //move forward
      pos.add(vel);

    if (keys['s'])              //move backward half speed
      pos.sub(vel.div(2));

    if (keys['d'])              //rotate right
      theta += radians(rotS);

    if (keys['a'])              //rotate left 
      theta -= radians(rotS);
  }

  void collision() {
    int touchedObs = 0;
    for (int i=0; i < obstacles.size(); i++) {                    //check obstacles array
      float minDist = (radius/2) + (obstacles.get(i).radius/2);   //calculate minimumdistance based on ship radius and obstacle radius
      PVector obsPos = obstacles.get(i).position.copy();
      float d = PVector.dist(pos, obsPos);

      if (d < minDist) {      
        touchedObs ++;
      }
    }
    if (touchedObs > 0) col = 255;
    else                col = 0;
  }


  void display() {    
    pos.x=constrain(pos.x, 25, width-25);     // limit position vector to screen size
    pos.y=constrain(pos.y, 25, height-25);

    pushMatrix();
    translate(pos.x, pos.y);               //translate origin to allow rotation
    rotate(theta);              

    stroke(0);                             //lines of sight, Player MUST face east if theta=0
    line(0, 0, sight, -sightSpread*2);     //leftmost eye
    line(0, 0, sight, -sightSpread);       //left eye
    line(0, 0, sight, 0);                  //central eye
    line(0, 0, sight, sightSpread);        //right eye
    line(0, 0, sight, sightSpread*2);      //rightmost eye

    fill(col, 0, 0);                              
    ellipseMode(CENTER);
    ellipse(0, 0, radius, radius);         //player body
    popMatrix();
  }
}


class Obstacle{

  PVector position;
  float radius;
  color col;

  Obstacle(float x,float y){
   radius = random(20, 50);
   position= new PVector(x,y);
   col = color(random(255), random(255), random(255));
  }

  void display(){
   stroke(0);
   fill(col);
   ellipseMode(CENTER);
   ellipse(position.x,position.y,radius,radius);
  }

}

jeremydouglass

I think I understand.

Are you sure that you want the eyes to be represented by lines -- not by an arc wedge?

In any case, what are obstacles -- are they circles, rectangles, polygons, or something else? Your demo shows them as ellipses -- is that all they will be?

m4l4

@jeremydouglass that's a good question, how would you approach the problem with arc wedge?

the problem is related to the architecture of the project. i'll try to explain: every neuron of the neural net can take a single input each frame, so if i use a "cone of view" i have no idea about how to feed informations to the net about "what's inside the cone". with the line method i will get 5 separate distance (thus the net can understand both distance AND direction) by adding color detection the plan is: detect color of the touched objects, sum up the rgb components of their colors, feed the 3 summed components as inputs to understand "what am i seeing" (3 rgb neurons for the left eye and 3 for the right one).

that was my plan, but if any of you guys have a different approach or idea, you're welcome.

m4l4

about the "will there be just ellipses colliding?" question: i don't know, but right now it's not that important, i can easily use ellipse only if that will make things easier

m4l4

i solved the body collision issue in a pretty simple way: just added a "stucked" boolean, and a nexPosition vector to forecast what my next position will be. check if my next position will exceed minimum distance from obstacles, if not, allow movement, otherwise, deny it.

here's an updated ship class, if the ship is red at the beginning of the simulation please restart it (you spawned inside an obstacle so no movement is allowed, but it's irrelevant right now so i don't need to fix it)

class Ship {  
  PVector pos, vel;     // position and velocity

  int speed;            // constant speed
  float theta;          // angle of rotation
  float rotS;           // rotation speed
  float sight;          //sight distance
  float sightSpread;    //distance between eyes
  float radius;         //radius of the ship
  float col;            //color of the ship

  boolean stucked;

  Ship() {
    speed = 5;
    rotS = 5;
    theta = 0;          // must be initialized at 0°
    sight = 200;
    sightSpread = 30;
    radius = 50;
    col = 0;

    pos = new PVector(width/2, height/2);
    vel = new PVector();
    stucked = false;
  }

  void run() {        //generic function container 
    move();
    collision();
    display();
    println(vel.x +" "+vel.y);
  }

  void move() {
    vel.x = speed*cos(theta);  //this modify vel.x and vel.y
    vel.y = speed*sin(theta);  //based ont the actual angle

    if (keys['w'] && stucked == false)   //move forward if next move won't stuck us
      pos.add(vel);

    if (keys['d'])              //rotate right
      theta += radians(rotS);

    if (keys['a'])              //rotate left 
      theta -= radians(rotS);
  }

  void collision() {
    int touchedObs = 0;
    for (int i=0; i < obstacles.size(); i++) {                    //check obstacles array
      float minDist = (radius/2) + (obstacles.get(i).radius/2);   //calculate minimumdistance based on ship radius and obstacle radius
      PVector obsPos = obstacles.get(i).position.copy();          //get obs position
      PVector futurePos = PVector.add(pos, vel);                  //forecast yourfuture position
      float d = PVector.dist(futurePos, obsPos);                  //check if your movement will exceed minDist

      if (d < minDist) {     //keep track of "future" touched obj till the end of the array
        touchedObs ++;
      }
    }
    if (touchedObs > 0) {    //if we will touch something
      col = 255;             //change color to red
      stucked = true;        //get stucked
    } else {              
      col = 0;
      stucked = false;
    }
  }


  void display() {    
    pos.x=constrain(pos.x, 25, width-25);     // limit position vector to screen size
    pos.y=constrain(pos.y, 25, height-25);

    pushMatrix();
    translate(pos.x, pos.y);               //translate origin to allow rotation
    rotate(theta);              

    stroke(0);                             //lines of sight, Player MUST face east if theta=0
    line(0, 0, sight, -sightSpread*2);     //leftmost eye
    line(0, 0, sight, -sightSpread);       //left eye
    line(0, 0, sight, 0);                  //central eye
    line(0, 0, sight, sightSpread);        //right eye
    line(0, 0, sight, sightSpread*2);      //rightmost eye

    fill(col, 0, 0);                              
    ellipseMode(CENTER);
    ellipse(0, 0, radius, radius);         //player body
    popMatrix();
  }
}

m4l4

now... onto the eye problem

m4l4

for those of you interested in the solution, here's the final code, i solved it myself: move the ship with WAD (forward and rotation) obstacle collision (the ship will turn red if next move will collide with an obstacle) if you spawn inside an obstacle, movement that will increase distance will be allowed (so you can exit the obstacle but you cannot get inside). the ship has 6 lines of sight, all of them perceive both distance of the closest object and its color (lines change color based on detection), the 2 eyes just make a sum of the perceived colors and returns a summed color.

Ship myShip;

float obsNum;
ArrayList<Obstacle> obstacles;
boolean [] keys = new boolean[128];

void setup() {
  size(600, 600); 
  smooth();
  myShip = new Ship();
  obsNum = 15;
  obstacles = new ArrayList<Obstacle>();
  for (int i = 0; i < obsNum; i++){
    obstacles.add(new Obstacle(random(width), random(height)));
  }
}

void draw() {
  colorMode(RGB, 255);
  background(255);
  myShip.run();
  for (int i = 0; i < obstacles.size(); i++){
    Obstacle o = obstacles.get(i);
    o.display();
  }
}

void keyPressed() {    //allows to move while rotate
  keys[key] = true;
}

void keyReleased() {
  keys[key] = false;
}

class Ship {  
  PVector pos, vel;     // position and velocity
  ArrayList<PVector> eyePos; 
  ArrayList<Float> eyeDist;
  ArrayList<Integer> eyeColor;

  int speed;            // constant speed
  float theta;          // angle of rotation
  float rotS;           // rotation speed
  float sight;          //sight distance
  float sightSpread;    //distance between eyes
  float radius;         //radius of the ship
  float col;            //color of the ship
  int eyesNum;          //number of eyes
  int leftEyeVision;
  int rightEyeVision;

  boolean stuck;
  boolean isIntersecting;

  Ship() {
    speed = 5;
    rotS = 2;
    theta = 0;          // must be initialized at 0°
    sight = 200;
    sightSpread = 30;
    radius = 50;
    col = 0;
    eyesNum = 6;
    leftEyeVision = 0;
    rightEyeVision = 0;

    pos = new PVector(width/2, height/2);
    vel = new PVector();
    eyePos = new ArrayList<PVector>();
    eyeDist = new ArrayList<Float>();
    eyeColor = new ArrayList<Integer>();

    for (int i = 0; i < eyesNum; i++) {
      eyePos.add(new PVector(random (width), random(height)));
    }
    stuck = false;
  }

  void run() {        //generic function container 
    move(); 
    sight(); 
    collision(); 
    display();
  }

  void move() {
    vel.x = speed*cos(theta); //this modify vel.x and vel.y
    vel.y = speed*sin(theta); //based ont the actual angle

    if (keys['w'] && stuck == false)   //move forward if next move won't stuck us
      pos.add(vel); 

    if (keys['s'] && stuck == false)  
      pos.sub(vel.div(2));

    if (keys['d'])              //rotate right
      theta += radians(rotS); 

    if (keys['a'])              //rotate left 
      theta -= radians(rotS);
  }

  void collision() {
    int touchedObs = 0; 
    for (int i=0; i < obstacles.size(); i++) {                    //check obstacles array
      float minDist = (radius/2) + (obstacles.get(i).radius/2); //calculate minimumdistance based on ship radius and obstacle radius
      PVector obsPos = obstacles.get(i).position.copy(); //get obs position
      PVector futurePos = PVector.add(pos, vel); //forecast your future position
      float futureDist = PVector.dist(futurePos, obsPos); //check if your movement will exceed minDist
      float actualDist = PVector.dist(pos, obsPos);

      if (futureDist < minDist && futureDist < actualDist) {     //keep track of "future" touched obj till the end of the array
        touchedObs ++;
      }
    }
    if (touchedObs > 0) {    //if we will touch something
      col = 255; //change color to red
      stuck = true; //get stucked
    } else {              
      col = 0; 
      stuck = false;
    }
  }

  void sight() {
    eyeDist.clear();
    eyeColor.clear();
    leftEyeVision = 0;
    rightEyeVision = 0;

    for (int i=0; i < eyePos.size(); i++) {
      float closestObs = sight;
      int obsColor = color(0);           

      for (int j=0; j < obstacles.size(); j++) {
        Obstacle o = obstacles.get(j); 

        float tempEyeDist = checkIntersection(pos.x, pos.y, eyePos.get(i).x, eyePos.get(i).y, 
          o.position.x, o.position.y, o.radius); 
        if (tempEyeDist < closestObs) {
          closestObs = tempEyeDist;
          obsColor = o.col;
        }
      }
      eyeDist.add(closestObs);
      eyeColor.add(obsColor);
    }
    for (int l = 0; l < eyesNum/2; l++){
      leftEyeVision += eyeColor.get(l);
    }
    for (int r = eyesNum/2; r < eyesNum; r++){
      rightEyeVision += eyeColor.get(r);
    }
    println("Eye distance left to right:");
    printArray(eyeDist);
    println("Eye color detection left to right:");
    printArray(eyeColor);
    println("Left eye sum / right eye sum");
    println(leftEyeVision + " / " + rightEyeVision);
  }


  float checkIntersection(float x1, float y1, float x2, float y2, 
    float cx, float cy, float cRad ) {

    float cr = cRad/2; //radius of the obstacle (not the diameter)
    float dx = x2 - x1; // xlength of the line
    float dy = y2 - y1; // ylength of the line

    float a = dx*dx + dy*dy; 
    float b = (dx*(x1 - cx) + (y1 - cy)*dy) * 2; 
    float c = cx*cx + cy*cy; 

    c += x1*x1 + y1*y1; 
    c -= (cx*x1 + cy*y1) * 2; 
    c -= cr*cr; 

    float delta = b*b - 4*a*c; 

    if (delta < 0) {              // Not intersecting
      isIntersecting = false; 
      return sight; //we're seeing full length
    } else {
      isIntersecting = true; 
      delta = sqrt(delta); 

      float mu = (b + delta) / (-2*a); 
      float ix2 = x1 + mu*dx; //coordinates of intersection
      float iy2 = y1 + mu*dy; 

      // Intersection points
//      ellipse(ix2, iy2, 5, 5);    //display ellipse at intersection point

      float allign = dist(ix2, iy2, x2, y2);      //distance between intersection and eye farest point
      float dist = dist(pos.x, pos.y, ix2, iy2);  //distance between position and intersection
      if (dist < sight && allign < sight) return dist; //if the obstacle is nearest than sight and in front of us return distance
      else                               return sight;
    }
  }

  void display() {    
    pos.x=constrain(pos.x, 25, width-25); // limit position vector to screen size
    pos.y=constrain(pos.y, 25, height-25); 

    pushMatrix(); 
    translate(pos.x, pos.y); //translate origin to allow rotation
    rotate(theta);           //lines of sight, Player MUST face east if theta=0


    stroke(eyeColor.get(0));
    line(0, 0, sight, -sightSpread*2.5); //leftmost eye
    eyePos.get(0).x = screenX(sight, -sightSpread*2.5); 
    eyePos.get(0).y = screenY(sight, -sightSpread*2.5); 

    stroke(eyeColor.get(1));
    line(0, 0, sight, -sightSpread*1.5); //left eye
    eyePos.get(1).x = screenX(sight, -sightSpread*1.5); 
    eyePos.get(1).y = screenY(sight, -sightSpread*1.5); 

    stroke(eyeColor.get(2));
    line(0, 0, sight, -sightSpread/2); //central left eye
    eyePos.get(2).x = screenX(sight, -sightSpread/2); 
    eyePos.get(2).y = screenY(sight, -sightSpread/2); 

    stroke(eyeColor.get(3));
    line(0, 0, sight, sightSpread/2); //central right eye
    eyePos.get(3).x = screenX(sight, sightSpread/2); 
    eyePos.get(3).y = screenY(sight, sightSpread/2); 

    stroke(eyeColor.get(4));
    line(0, 0, sight, sightSpread*1.5); //right eye
    eyePos.get(4).x = screenX(sight, sightSpread*1.5); 
    eyePos.get(4).y = screenY(sight, sightSpread*1.5); 

    stroke(eyeColor.get(5));
    line(0, 0, sight, sightSpread*2.5); //rightmost eye
    eyePos.get(5).x = screenX(sight, sightSpread*2.5); 
    eyePos.get(5).y = screenY(sight, sightSpread*2.5); 

    stroke(0);
    fill(col, 0, 0); 
    ellipseMode(CENTER); 
    ellipse(0, 0, radius, radius); //player body
    fill(leftEyeVision);
    ellipse(radius/4, -radius/5, radius/4, radius/4);
    fill(rightEyeVision);
    ellipse(radius/4, radius/5, radius/4, radius/4);
    popMatrix();
  }
}

class Obstacle{

  PVector position;
  float radius;
  color col;

  Obstacle(float x,float y){
   radius = random(20, 50);
   position= new PVector(x,y);
   col = color(random(255), random(255), random(255));
  }

  void display(){
   stroke(0);
   fill(col);
   ellipseMode(CENTER);
   ellipse(position.x,position.y,radius,radius);
  }

}