Collision avoidance and hit test - Need help creating a minigame

Pixels

Hi everyone!

I'm quite in a rush at the moment but I am trying to create a small game where the player (the mouse pointer) is chased by several enemies.

So far, 5 enemies spawn randomly on the map and start chasing the pointer at a regular speed. However, since they quickly converge towards the same target, the objects tend to overlap until a "single object" is left on the screen. They didn't merge or anything, they simply find themselves in the same position as it's the what the code tells them to do.

Picture below for your reference.

However, by doing that, it looses the goal of having several enemies. Thus my question, how can I make each of the enemies maintain a distance between each other when they come close to one another?

Here is my code without my attempts:

Enemy[] enemies = {};

void setup() {
 size(800, 800);
 background(#2c3e50);

 for (int i = 0; i < 5; i++) {
   Enemy newEnemy = new Enemy(i * random(25,150), i * random(25,150));
   enemies = (Enemy[]) append(enemies, newEnemy);
 }
}

void draw() {
 background(#2c3e50);

  for (int i = 0; i < enemies.length; i++) {
   enemies[i].move();
   enemies[i].display();
  }
}

// ///// Enemy class /////

class Enemy {

  float x;
  float y;

  PVector location;
  PVector speed;
  int enemySize = 20;

  Enemy[] otherEnemies = {};

  Enemy(float x, float y) {
    this.x = x;
    this.y = y;
    location = new PVector(random(800), random(800));
    speed = new PVector(2, -2);
  }

  void move() { //Or void update()
    PVector target = new PVector(mouseX, mouseY);
    PVector movement = PVector.sub(target, location);
    speed.add(movement);
    speed.limit(3);
    //Updating the location of the enemy
    location.add(speed);
  }

  void display() {
    fill(255);
    noStroke();
    ellipse(location.x, location.y, enemySize - 16, enemySize - 16);
    noFill();
    stroke(255, 100);
    strokeWeight(2);
    ellipse(location.x, location.y, enemySize - 10, 10);
    noFill();
    stroke(255, 100);
    strokeWeight(1);
    ellipse(location.x, location.y, 20, 20);
    checkBounds();
  }

  //Function to invert the velocity vector values
  //So that the ball stays within the frame
  void checkBounds() {
    if ((location.x > width) || (location.x < 0)) {
      speed.x = speed.x * -1;
    }

    if ((location.y > height) || (location.y < 0)) {
      speed.y = speed.y * -1;
    }
  }
}

I know there is something I can do with the dist() function and/or arrays, but being new to programming I can't put it down properly. Any hint or advice on how to proceed from there?

Thanks!

P.S.: Spirit, an iOS game - http://iappsin.com/arcade-game-spirit-for-iphone-and-ipad.htm - has been a good source of inspiration. Different types of enemies including green ones that follow the player and never overlap with their peers.

Ater

You need to add another method to your Enemy class, that would take Enemy as argument and check the distance between current object and different enemy, something like

void avoidEnemies(Enemy e){
if (dist(this.x, this.y, e.x, e.y) < minDist){
// your code for avoidance here
  }
}

In your main draw() method you'll need a nested loop to check each enemy against all other enemies, except itself.

for (int i; i < enemies.length; i++){
    for (int j; j < enemies.length; j++){
       if (i != j) {
    enemies[i].avoidEnemies(enemies[j]);
    }
  }
}

Pixels

Thanks for the answer, Ater! I tried your method but had no idea what to do for the avoidance code; so I tried to set the distance to a bit more than twice an enemy's radius:

if (d < minDist) {
  d = minDist*1,1;
}

That's probably not so easy (which explained why it didn't work, enemies kept overlapping)...

I deleted that bit and went a step back: I printed the values I got with the dist() function and it returned ridiculously high values. Considering my window is 1200x1200, I don't see why dist() (named "d") gives me values like that.

See picture below for your reference (far right column).

Here's what I added to the existing code

//Main sketch draw()
//Same as your idea, just changed the variables names
for (int currentE = 0; currentE < enemies.length; currentE++) {
  for (int otherE = 0; otherE < enemies.length; otherE++) {
    if (currentE != otherE) {
      enemies[currentE].avoidEnemies(enemies[otherE]); 
    }
  } 
}

//Enemy class
//Set a value for minDist, in my case it equals 80 (see picture above)
void avoidEnemies(Enemy enmy) {
  int minDist = r * 2;
  float d = dist(this.x, this.y, enmy.x, enmy.y); 
  println("displayHeight = ", displayHeight, " | r = ", r, " | minDist = ", minDist, " | d = ", d);
}

Is that normal and I'm just more confused than I thought?

blindfish

@Ater has fed you a sub-optimal nested loop solution for collision detection which might come back to bite you, but we can live with that for the moment. As for the value of d, not sure: it sounds like you're also manipulating that elsewhere: it would be better to post the full code so we can run it ;)

Anyway, in terms of avoidance code you'd need to calculate the angle between the two enemies and adjust the speed vector, based on this, so they move away from each other...

Pixels

If I didn't mess up too badly, d is only used in the piece of code in my previous message.

And calculating the angle between the enemies to adjust the vector... Trigonometry, my old friend! This is already way past what I've been studying in my unit. >.< Anyone know a good tutorial(s) or example(s) about it? The more simple, the better.

Posting the full code (is there a way I can make the code snippet scrollable so it isn't so long?)

//There may have been a few minor changes (variables names, stuff like that)

//Main sketch
//Declare array of Enemy objects
Enemy[] enemies = {};
int nbrEnemies = 10;

void setup() {
  size(displayHeight, displayHeight);
  background(#2c3e50);

  //Initialize several enemies
  for (int i = 0; i < nbrEnemies; i++) {
    Enemy newEnemy = new Enemy(i * random(25, displayHeight), i * random(25, displayHeight));
    enemies = (Enemy[]) append(enemies, newEnemy);
  }
}

void draw() {
  background(#2c3e50);

  //Call methods on each Enemy initialized
  for (int i = 0; i < enemies.length; i++) {
    enemies[i].update();
    enemies[i].display();
  }

  for (int currentE = 0; currentE < enemies.length; currentE++) {
    for (int otherE = 0; otherE < enemies.length; otherE++) {
      if (currentE != otherE) {
        enemies[currentE].avoidEnemies(enemies[otherE]);
      }
    }
  }
}

//Enemy class
class Enemy {

  float x;
  float y;

  PVector location;
  PVector speed;
  int r = displayHeight/40;

  Enemy[] otherEnemies = {};

  Enemy(float x, float y) {
    this.x = x;
    this.y = y;
    location = new PVector(random(800), random(800));
    speed = new PVector(2, -2);
  }

  void update() {
    PVector target = new PVector(mouseX, mouseY);
    PVector movement = PVector.sub(target, location);
    speed.add(movement);
    speed.limit(3);
    //Updating the location of the enemy
    location.add(speed);
  }

  void display() {
    fill(255);
    noStroke();
    ellipse(location.x, location.y, r, r);

    checkBounds();
  }

  //Function to invert the velocity vector values
  void checkBounds() {
    if ((location.x > width) || (location.x < 0)) {
      speed.x = speed.x * -1;
    }

    if ((location.y > height) || (location.y < 0)) {
      speed.y = speed.y * -1;
    }
  }

  void avoidEnemies(Enemy enmy) {
    int minDist = r * 2;
    float d = dist(this.x, this.y, enmy.x, enmy.y); 
    println("displayHeight = ", displayHeight, " | r = ", r, " | minDist = ", minDist, " | d = ", d);
  }
}

blindfish

OK - here's an optimised collision detection loop (code untested so maybe fix the issues mentioned below first ;) ):

for (int i = 0; i < enemies.length-1; i++) {

    Enemy currentEnemy = enemies[i];

    for (int j = i+1; j < enemies.length; j++) {
        currentEnemy.avoidEnemies(enemies[j]);
    }
  }

Your avoidEnemies routine will need to apply change in direction to both enemies; but this is optimal since it means you don't have to calculate the same angle twice.

As for your problem with d. reduce the number of enemies to 2. Notice anything odd? Basically you need to clean out some cruft. Whilst you still have x and y properties lurking on your Enemy class these aren't actually being used to track the location <(hint) of your enemies... So they never change and therefore aren't good candidates for checking distance between them!

Come back when you've fixed that ;)

GoToLoop

Some online example w/ ellipse() collision: :D
http://studio.processingtogether.com/sp/pad/export/ro.989GaZC5t7EkE/latest

Pixels

Thanks GoToLoop, I'll check that out!

blindfish, I checked it with 2 enemies and I see what you mean, the values never change. I suspect my code uses the x and y at the time the enemies spawn, calculate the distance then and keeps it that way (or rather the variables hold just those values)... Does that mean I should try to get the distance using the vectors themselves rather than the x and y variables?

//Something like
float d = this.location.dist(enmy.location);
//or
float d = PVector.dist(this.location, enmy.location);

//rather than
float d = dist(this.x, this.y, enmy.x, enmy.y);

Edit: Hahahaha! Tried it and it works! Well, enemies still end up overlapping but I get decreasing and (much more) logical values! Hurray!

Now to get a code to tell enemies to re-calculate their vectors to avoid each other? Is that still using trigonometry as suggested previously?

blindfish

Good: my clues led you to the complete answer. In your enemy class x and y are redundant. You should assign the constructor parameters to the location vector and remove the random stuff there. That is if you want the class to accept these parameters (I think you do)... Obviously make sure sensible values are set in setup(): they weren't in your first code posting.

Yes enemies will overlap: you haven't done anything to stop that yet. Trig is certainly the approach I use for collision detection, though you may be able to use vector maths instead. I think trig may be simpler and it's not so bad. If you need a well written explanation I still keep touting ActionScript Animation (Keith Peters) as a good information source for this stuff, even though it's aimed at another language. There are obviously Processing references and a lot of resources online (try searching specifically for 'trigonometry for animation').

Also now may be the time to test that optimised loop I posted. I'm sure @GoToLoop would have mentioned if in, my current dreary state, I'd made an error...

blindfish

Actually the 'trig' isn't really trig and you've already applied it to get the distance between enemies. One crude approach - in this case - is you simply reverse the speed of both enemies when they collide. I suspect that'll have them bouncing around like crazy, but it's a start and it's easy ;)

Edit: oops. Just remembered something. Do as I suggested and you'll discover why - even with this simple approach - you need to do some extra work; probably with real trig...

Pixels

Thanks for the hints!

I tried reversing the speed using the same method as the void checkBounds() in my code: multiplying the speed.x and speed.y by -1. But it didn't do much, maybe slowed down the enemies overlapping each other. (see gif for reference)

I tried to up the factor (-4 and -10) and ended up with a bunch of static enemies having epileptic seizure. ^^ (again gif for reference)

I thought the x and y were used for the enemy spawn at the beginning. What would assigning the location vector in the parameters mean/do?

I've come across an article quite interesting and am trying to understand how to use it. But it uses "normal" Java, not the same as in Processing, which is a bit troubling for me.

Edit: My code so far

//Main sketch
//Declare array of Enemy objects
Enemy[] enemies = {};
int nbrEnemies = 5;

Hero hero;

void setup() {
  size(displayHeight, displayHeight);
  background(#2c3e50);

  //Initialize several enemies
  for (int i = 0; i < nbrEnemies; i++) {
    Enemy newEnemy = new Enemy(random(displayHeight), random(displayHeight), 255);
    enemies = (Enemy[]) append(enemies, newEnemy);
  }
}

void draw() {
  background(#2c3e50);

  //Call methods on each Enemy initialized
  for (int i = 0; i < enemies.length; i++) {
    enemies[i].update();
    enemies[i].display();
  }

  for (int i = 0; i < enemies.length; i++) {

    Enemy currentEnemy = enemies[i];

    for (int j = i+1; j < enemies.length; j++) {
      currentEnemy.avoidEnemies(enemies[j]);
    }
  }
}

//////////////////////////////////////////////////
//Enemy class
class Enemy {

  float x;
  float y;
  color c;

  PVector location;
  PVector speed;
  int r = displayHeight/20;

  Enemy[] otherEnemies = {};

  Enemy(float x, float y, color enmyC) {
    this.c = enmyC;
    location = new PVector(x, y);
    speed = new PVector(2, -2);
  }

  void update() {
    PVector target = new PVector(mouseX, mouseY);
    PVector steer = PVector.sub(target, location);
    speed.add(steer);
    speed.limit(3);
    //Updating the location of the enemy
    location.add(speed);
  }

  void display() {
    fill(c);
    noStroke();
    ellipse(location.x, location.y, r, r);

    checkBounds();
  }

  //Function to invert the velocity vector values
  void checkBounds() {
    if ((location.x > width) || (location.x < 0)) {
      speed.x = speed.x * -1;
    }

    if ((location.y > height) || (location.y < 0)) {
      speed.y = speed.y * -1;
    }
  }

  void avoidEnemies(Enemy enmy) {
    int minDist = r * 3;
    float d = this.location.dist(enmy.location); 
    println("displayHeight = ", displayHeight, " | r = ", r, " | minDist = ", minDist, " | d = ", d);

    if (d < minDist) {
//      Testing with colours
//      this.c = color(255, 0, 0);
//      enmy.c = color(0, 255, 0);

      this.speed.x = this.speed.x * -1;
      this.speed.y = this.speed.y * -1;
      enmy.speed.x = enmy.speed.x * -1;
      enmy.speed.y = enmy.speed.y * -1;
    }
  }
}

blindfish

Sorry: on reflection I realise my suggestion wasn't correct since you're making changes to speed elsewhere at the same time. The article you link to could be applied but looks like overkill. I might be able to post a code example later (as in over the weekend); but I think you want something more akin to inverted springing.

I recently posted a balls example that includes a routine for doing mass (as in 'weight') based avoidance but I think this again goes beyond what you need.

In the meantime a suggestion to simplify your setup routine:

//Main sketch
// moved in front of array declaration
int nbrEnemies = 2;
//Declare array of Enemy objects
Enemy[] enemies = new Enemy[nbrEnemies];


void setup() {
  size(800, 800);
  background(#2c3e50);

  //Initialize several enemies
  for (int i = 0; i < nbrEnemies; i++) {
    enemies[i] = new Enemy(random(0, width), random(0, height));
  }
}

By declaring nbrEnemies before the enemies array you can then set the array size and, since it now has a declared size, you can avoid the convoluted process you were previously using to add enemies to the array...

I thought the x and y were used for the enemy spawn at the beginning. What would assigning the location vector in the parameters mean/do?

In your previous code you passed x,y coordinates for where you want the enemy to start, but then ignored these and set a random value to 'location' So they weren't being used at all. By passing them to the location vector in the contructor you then have the choice to either position them randomly - as you do now - or based on any number set positions. So you might have a separate class to manage levels of your game and choose to position enemies at specific locations for each level. Using the parameters in location allows you to do this.

Pixels

Thanks again for the tips! Setup routine has been changed. I didn't even realize the nbrEnemies I created to simplify my tests was actually somewhat useful...

I checked your bouncing balls example when I visited your profile and it looks really neat! Probably more than I need but good inspiration nonetheless. Same for the article I linked, it's quite complex and I'd much rather find a more simple way that I can fully understand.

blindfish

Did you implement the movement code you use in update() based on an example or figure it out yourself? I must admit I haven't used vectors enough to be entirely comfortable with them; but from what I can see you're doing the following:

1. calculating the vector from location to mouse cursor
2. adding this raw value to speed
3. limiting the maximum speed
4. adding this to location to create movement

Unfortunately I think the current approach will make it difficult to do any kind of collision avoidance in a separate method. It's just a hunch but because the raw vector to the mouse location always generates a speed greater than your limit it is then almost always subject to the limit() constraint - i.e. enemies always have a constant speed. Applying changes to speed to try and get enemies to avoid each other then proves futile; since whatever you apply to speed gets normalised to the value in limit...

I'm having a play using PVector.div() to reduce the steer vector before adding to speed: that's what you usually do to spring to a point. It seems to work better; but still slightly flaky; but that might be because I don't understand the PVector methods well enough...

Pixels

The movement code was something we coded during one of our classes. It was slightly different as the aim was to have an object "orbit" around the mouse cursor instead of just following it. The current version may not be optimized as I tinkered with the vectors myself in order to have it do what I need.

Having a constant chasing speed kinda suits my needs, and my aim is "only" (how I wish it was this simple) to have them stay away from one another. Does having a constant speed prevent the Enemy objects to adjust their vectors' direction or is it that slowing down would be the best course of action?

If I understood correctly the article I found, the author was speaking about the object "seeing" in front of him: having a vector longer than the one used for the object movement that would tell if an obstacle was ahead thanks to hit testing/collision detection. Then adding another force (vector) to change the object's course. But then I didn't quite catch how he implemented it.

blindfish

A 'constant' speed shouldn't be a problem. Split your vectors into their constituent parts to see the problem you do have (pseudocode):

// variables to adjust speed in order to avoid collision
// these values will normally be relatively small
ax = 3;
ay = 2;
//speed (from steer):
vx = 130;
vy = 50;
// apply adjustment:
vx += ax;
vy += ay;
// apply limit. This isn't quite what limit() does,
// but it's essentially the problem you have
vx = min(vx, 30);
vy = min(vy, 30);

Since the initial input is almost always over the limit the adjustment will always be nullified...

Pixels

I see. Then rethinking the whole movement part seems necessary if I want to use avoidance methods. I'm going to work a bit on the other aspects of my sketch (hit testing mostly), and come back on that later today or tomorrow.

Thanks again for the explanations! (I wish I could +1 comments)

Edit: I have found a reserve solution if I can't manage the avoidance in time. I just "teleport" one of the objects that come too close to one another on a random spot in the window. It's not perfect but it kind of does the trick as my enemies don't overlap anymore. :-p

void avoidEnemies(Enemy enmy) {
    int minDist = r * 2;
    float d = this.location.dist(enmy.location); 

    if (d < minDist) {
      this.location.x = random(width);
      this.location.y = random(height);
    }
  }