Collision Avoidance Example or Help

Question

I have been trying to find a collision avoidance example that I can adapt and use for a game I am working on. It will be used to model a skier's movements to avoid trees on the hill. I am basing the movement off of Steering Behaviors for Autonomous Characters and there are a lot of good examples for path following and flocking, but I can't find any good ones for collision avoidance. The Nature of Code website had awesome tutorials for steering but seemed to cover everything but obstacle avoidance.

I converted the code from here but it doesn't work as well as it should because collisions are found by projecting the obstacles center onto the velocity vector without taking into account when the obstacles center may be outside the limits of collision but the circle is still colliding. Here is the code I adapted (written in Processing (Java based)).

// Method to update location
void update() {
  // Update velocity
  vel.add(acc);
  // Limit speed
  vel.limit(maxspeed);
  loc.add(vel);
  // Reset accelertion to 0 each cycle
  acc.mult(0);
}

void obstacleAvoid() {
  float checkLength = 30*vel.mag();
  PVector forward,diff,ray,projection,force;
  float dotProd,dis;
  forward = vel.get();
  forward.normalize();
  ray = forward.get();
  ray.mult(checkLength);
  for ( int i = 0; i < obs.size(); i++ ) {
    Obstacle ob = (Obstacle)obs.get(i);
    diff = ob.pos.get();
    diff.sub(loc);
    PVector temp2 = forward.get();
    temp2.mult(ob.r);
    diff.sub(temp2);
    dotProd = diff.dot(forward);
    if ( dotProd > 0 ) {
      projection = forward.get();
      projection.mult(dotProd);
      dis = PVector.dist(projection,diff);
      if ( (dis < (ob.r + r)) && (projection.mag() < ray.mag()) ) {
        ob.hit = true;
        force = forward.get();
        force.mult(maxforce);
        if ( sign(diff,vel) == -1 ) { //CCW
          force.set(force.y,-force.x,0);
        }
        else { //CW
          force.set(-force.y,force.x,0);
        }
        force.mult(1-(projection.mag())/ray.mag());
        force.limit(maxforce);
        acc.add(force);
      }
    }
  }  
}

So to help me I was wondering if anyone knew of any complete examples of collision avoidance that follow the Steering Behaviors for Autonomous Characters way of doing things better. This Site is the example applet for the paper and is the exact example I wish I could see the code for. Sadly there is no code to come with it and I tried decompiling it but it just showed the main class so that wasn't very helpful. If someone has the code for this example or something like it, or a tutorial, I would appreciate it a lot.

Answer 1

Craig Reynolds cannot release the source code for the applets you're interested in. Similar source code is available in c++ at OpenSteer, which is maintained by Reynolds. Christian Schnellhammer and Thomas Feilkas worked to expand Reynolds original paper. Their paper is translated into english and contains a section on obstacle avoidance. The source code for their work is available in Java. However, I think Shiffman's code is a great starting point, and it sounds like you're pretty close to what you want already

One of my first Processing programs modified the Boids example to simulate a zombie apocalypse. Triangles chased circles that were avoiding them. Each survivor checks for other zombies in their vision, and averages the location vectors of threats in a function, PVector panic(ArrayList infected). After that, it was a matter of weighting the new vector negatively and adding it to the survivor's current vector like any other force. Something like:

void flock(ArrayList uninfected, ArrayList infected) {
  PVector sep = separate(uninfected);   // Separation
  PVector ali = align(uninfected);      // Alignment
  PVector coh = cohesion(uninfected);   // Cohesion
  PVector pan = panic(infected);        // Panic
  // Arbitrarily weight these forces
  sep.mult(4.0);
  ali.mult(1.0);
  coh.mult(2.0);
  pan.mult(-3.0);
  // Add the force vectors to acceleration
  acc.add(sep);
  acc.add(ali);
  acc.add(coh);
  acc.add(pan);
}

If your skier is successfully detecting the obstacles, then avoidance is the problem. Adding a stronger weight to the avoidance vector, increasing the radius the skier can 'see' to interact with objects, or even adding a method to the object that returns the location of the closest point to the skier could solve your problem. You could also add deceleration based on the distance from the skier to the nearest obstacle in front it.

Remember that even the applet you're interested in does not perfectly avoid obstacles. My solution may not be exactly what is happening in the applet, but by playing around with the forces determining you skier's direction, you can achieve a very similar (and possibly better) effect.

Answer 2

Checkout this link on NEHE game development site:

In this tutorial you will learn the basics of collision detection, collision response, and physically based modelling effects. This tutorial concentrates more on how collision detection works than on the actual code, although all of the important code is explained.

http://nehe.gamedev.net/data/lessons/lesson.asp?lesson=30

It is done using c++ and win32 API. Although you will find a link for Java Port using JOGL.

Also The Source code for http://www.red3d.com/cwr/steer/ is available here http://opensteer.sourceforge.net/ though in c++. Have you checked it??