8
\$\begingroup\$

I making a small steering simulator using the Reynolds boid algorithm. Now I want to add a wall avoidance feature. My walls are in 3D and defined using two points like that:

   ---------. P2
   |        |
P1 .---------

My agents have a velocity, a position, etc...

Could you tell me how to make avoidance with my agents?

Vector2D ReynoldsSteeringModel::repulsionFromWalls()
{
    Vector2D force;
    vector<Wall *> wallsList = walls();
    Point2D pos = self()->position();
    Vector2D velocity = self()->velocity();

    for (unsigned i=0; i<wallsList.size(); i++)
    {
        //TODO
    }

    return force;
}

Then I use all the forces returned by my boid functions and I apply it to my agent.

I just need to know how to do that with my walls.

Thanks for your help.

\$\endgroup\$
  • 2
    \$\begingroup\$ did you look at the original Reynold's paper? If I recall correctly it has info on how to do obstacle avoidance and wall avoidance. I think this is the doc: red3d.com/cwr/steer/gdc99 \$\endgroup\$ – krolth Dec 11 '12 at 19:17
  • 1
    \$\begingroup\$ Thanks but it explains how to avoid circular obstacle, not rectangular. \$\endgroup\$ – Vodemki Dec 11 '12 at 19:21
  • 2
    \$\begingroup\$ Use the radial distance from the agent to the center of the circle (minus the radius of the circle wall). \$\endgroup\$ – bobobobo Dec 11 '12 at 19:33
14
\$\begingroup\$

Let each wall exert an influence on the velocity.

Try something like using the inverse distance (or inverse squared distance) from the wall to determine the magnitude of the force that each wall "exerts", and the normal of the wall to determine the direction of the force that the wall "exerts".

enter image description here

So here the boid interacts with 4 walls. Since the dot product of the red vectors (boid-to-wall-center) is greater than 0 for 3 of the 4 walls, those walls won't exert a force on the boid.

Only the wall with a blue vector (negative dot product) will have a force.

The magnitude of the force should be great with the boid gets too close to the wall, and the direction of the force should be in the direction of the black arrow on the wall (pointing directly away from the wall).

enter image description here

If you use 1 / (t+1) for the magnitude of the force, where t is the distance from the wall, then the force will be really strong when gets close to 0, but fade off to nothing when t gets higher (note the axis scale in the diagram, it is not 0 when t=5, it is 0.2). (The t+1 is so that you don't get an infinite force / divide by 0 if the boid happens to enter the wall).

If you use 1/(t^2+1), then the force is much sharper near the wall, and falls off faster/smoother.

enter image description here

Experiment with it and see what you like.

\$\endgroup\$
  • \$\begingroup\$ Thanks but how to deal with a 3D wall. For example, my wall has 4 edges, so I believe I need only a maximum of 2 forces (if agent's direction is in diagonal). \$\endgroup\$ – Vodemki Dec 11 '12 at 19:24
  • \$\begingroup\$ In 2D, every 2 points is a "wall." If it's a square pillar in the middle of a room, then you have 4 walls there. You can "cull" backfacing walls (so that backfacing walls don't "suck" the player) if the vector from the boid to the wall-center has a positive dot product with the wall normal. \$\endgroup\$ – bobobobo Dec 11 '12 at 19:32
  • \$\begingroup\$ So, Do you think this would do the job ? Vector2D distance(wallsList[i]->center(), pos); double dotProduct = distance * wallsList[i]->normal(); if (dotProduct > 0) { force += wallsList[i]->normal() / distance.length(); } \$\endgroup\$ – Vodemki Dec 11 '12 at 19:43
  • \$\begingroup\$ It looks reasonable, test it out! \$\endgroup\$ – bobobobo Dec 11 '12 at 19:45
  • \$\begingroup\$ A shortcoming of this approach is that steering is modeled as a repulsive force that is independent of the motion of the agent. That is it treats the agent as a charged particle in an electrostatic field. Consider the case where the agent is “flying” parallel to that top (blue) wall and slightly above it (on the page). In this case, no steering or obstacle avoidance is needed. The agent is simply passing by, and should not be pushed away from the wall. See for example “containment” in this GDC 99 paper. \$\endgroup\$ – Craig Reynolds May 7 '18 at 2:36
8
\$\begingroup\$

If someone needs the code, here it is, feel free to redistribute it. I've tried to comment it to be more understandable. Based on bobobobo's solution.

Vector2D ReynoldsSteeringModel::repulsionFromWalls(vector<Vector2D *> walls)
{
    Vector2D force; // My force will be stored here
    Point2D pos = self()->position(); // Position of the agent

    // For each wall
    for (unsigned j=0; j<walls->size(); j++)
    {
        // Get the center point of the wall
        Real coordX = (walls[j]->p1().x() + walls[j]->p1().y()) / 2.0;
        Real coordY = (walls[j]->p2().x() + walls[j]->p2().y()) / 2.0;
        Point2D center(coordX, coordY);

        // Create a new vector between my agent and the center of the current wall
        Vector2D distance(center, pos);

        // If the wall is visible, calculate the force to apply
        double dotProduct = distance * partsList[j]->normal();
        if (dotProduct < 0)
        {
            force +=  partsList[j]->normal() / (distance.length() * distance.length() + 1);
        }
    }

    // Returned the calculated force
    return force;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.