Collision avoidance not only AI wrong

Question

I am trying to implement the game similar to Dota 2 or Warcraft 3. I want this: when user clicks the right mouse button I want to navigate to the click position. However if there is an obstacle in my way I want to go around it.

Here's what I've got so far:

// p - where user clicked
// stepSize - something like movement speed
// minDistance - not important for this problem
// objects - all the colliding objects
// shouldStepInto - not important for this problem
public boolean moveTowardsPoint(Point p, double stepSize, double minDistance, ArrayList<GameBodyObject> objects,  boolean shouldStepInto) {

    ArrayList<GameBodyObject> others = (ArrayList<GameBodyObject>) objects.clone();
    others.remove(this);


    double dx = p.getX() - getPosition().getX();
    double dy = p.getY() - getPosition().getY();

    boolean isClose = false;

    Point lastPosition = getPosition().clone();
    if (Math.sqrt(dx * dx + dy * dy) < Math.max(minDistance, stepSize)) {
        isClose = true;


    } else {
        setRotation(Math.atan2(dy, dx));

        // Though the sqrt is expensive operation
        // We check first without using sqrt
        if (shouldStepInto && Math.abs(dx) + Math.abs(dy) < stepSize) {
            if (Math.sqrt(dx * dx + dy * dy) < stepSize) {
                getPosition().setX(p.getX());
                getPosition().setY(p.getY());
            }
        } else {
            getPosition().setX(getPosition().getX() + (stepSize * Math.cos(getRotation())));
            getPosition().setY(getPosition().getY() + (stepSize * Math.sin(getRotation())));
        }
    }

    // -- COLLISION AVOIDANCE -- //

    ArrayList<Double> movements = new ArrayList<>();
    for (GameBodyObject obj : others) {
        // Check collision with all the other GameBodyObjects
        if (checkCollision(obj)) {
            // How much have I moved lastly
            double distanceMoved = getPosition().distance(lastPosition);
            if(!isStatic() && distanceMoved > 0.01) {
                // calculate vector between me and a collider
                Vector v = new Vector(getPosition().getX() - obj.getPosition().getX(), getPosition().getY() - obj.getPosition().getY());
                // Calculate 2 normal vectors
                Vector n1 = v.getNormal(stepSize, 1);
                Vector n2 = v.getNormal(stepSize, -1);
                Point p1 = getPosition().clone();
                Point p2 = getPosition().clone();
                // Try to move in the directions of two normal vectors
                p1.moveByVector(n1);
                p2.moveByVector(n2);
                double dist1 = p1.distance(p);
                double dist2 = p2.distance(p);
                // If I got closer with normal vector n1
                if (dist1 < dist2) {
                    // Store the angle
                    movements.add(n1.getAngle());
                // Otherwise if I got closer with normal vector n2
                } else {
                    // store the angle
                    movements.add(n2.getAngle());
                }
            };
        }
    }

    // If I have stored any angles:
    if(movements.size() > 0) {
        // Reset my position to where it was before moving
        setPosition(lastPosition.clone());
        // Calculate the sum of angles
        double totalAngle = 0;
        for (double angle : movements) {
            totalAngle += angle;
        }

        // Create a vector with total angle and step size.
        Vector v = Vector.createFromLengthAndAngle(stepSize, totalAngle);

        // Move in the direction of calculated vector
        Point newPos = getPosition().clone();
        newPos.moveByVector(v);
        setRotation(totalAngle);
        getPosition().moveByVector(v);
    }

    return isClose;

}

Simply I calculate two normal vectors (perpendicular to the vector) pointing from me to colliding element. Then I store angle and after all I create new vector with total of angles.

It works on collision between 2 elements. However when there are multiple elements it starts jiggling (bouncing) and sometimes it even breaks the collision constraints (rules) and walks into a tree.

What am I doing wrong here?

EDIT btw my colliders are all circles

What do you mean "when user clicks the RMB I want to navigate to the click position"? — clabe45
– clabe45, Commented Aug 2, 2017 at 14:48
@clabe45 I want to move this (GameBodyObject) to the position where the user clicked, like in Dota 2 or Warcraft 3 — durisvk10
– durisvk10, Commented Aug 2, 2017 at 17:14
Can you show us the code where you call this method? What objects do you set it to avoid? — clabe45
– clabe45, Commented Aug 2, 2017 at 22:58
@clabe45 I call this from many places and I use all the objects registered in Game object — durisvk10
– durisvk10, Commented Aug 3, 2017 at 10:56

durisvk10 · Accepted Answer · 2017-08-03 11:01:06Z

I found out logical mistake, I should do the sum of angles as totalAngle and then divide it by the count of angles so I get totalAngle / movements.size(). With that I get a middle vector (in the middle of all the normals). Another thing is that my checkCollision wasn't working properly so I had to change that. I also had to check if the collision occurs on the calculated points moved by normal. So my final code looks like this:

public boolean moveTowardsPoint(Point p, double stepSize, double minDistance, ArrayList<GameBodyObject> objects,  boolean shouldStepInto) {

    ArrayList<GameBodyObject> others = (ArrayList<GameBodyObject>) objects.clone();
    others.remove(this);

    // -- COLLISION AVOIDANCE -- //

    double dx = p.getX() - getPosition().getX();
    double dy = p.getY() - getPosition().getY();

    boolean isClose = false;

    Point lastPosition = getPosition().clone();
    if (Math.sqrt(dx * dx + dy * dy) < Math.max(minDistance, stepSize)) {
        isClose = true;


    } else {
        setRotation(Math.atan2(dy, dx));

        // Though the sqrt is expensive operation
        // We check first without using sqrt
        if (shouldStepInto && Math.abs(dx) + Math.abs(dy) < stepSize) {
            if (Math.sqrt(dx * dx + dy * dy) < stepSize) {
                getPosition().setX(p.getX());
                getPosition().setY(p.getY());
            }
        } else {
            getPosition().setX(getPosition().getX() + (stepSize * Math.cos(getRotation())));
            getPosition().setY(getPosition().getY() + (stepSize * Math.sin(getRotation())));
        }
    }

    ArrayList<Double> movements = new ArrayList<>();
    for (GameBodyObject obj : others) {
        if (checkCollision(obj)) {
            double distanceMoved = getPosition().distance(lastPosition);
            if(!isStatic() && distanceMoved > 0.01) {
                Vector v = new Vector(getPosition().getX() - obj.getPosition().getX(), getPosition().getY() - obj.getPosition().getY());
                int av = (int)(v.getAngle() * 180 / Math.PI);
                Vector n1 = v.getNormal(stepSize, 1);
                int an1 = (int)(n1.getAngle() * 180 / Math.PI);
                Vector n2 = v.getNormal(stepSize, -1);
                int an2 = (int)(n2.getAngle() * 180 / Math.PI);
                Point p1 = lastPosition.clone();
                Point p2 = lastPosition.clone();
                p1.moveByVector(n1);
                p2.moveByVector(n2);
                double dist1 = p1.distance(p);
                double dist2 = p2.distance(p);
                if (dist1 < dist2) {
                    movements.add(getAngleIfNotColliding(n1, p1, n2, p2, others));
                } else {
                    movements.add(getAngleIfNotColliding(n2, p2, n1, p1, others));
                }
            };
        }
    }
    movements.removeIf(Objects::isNull);
    if(movements != null && !movements.isEmpty()) {
        setPosition(lastPosition.clone());
        double totalAngle = 0;
        for (double angle : movements) {
            totalAngle += angle;
        }

        Vector v = Vector.createFromLengthAndAngle(stepSize, totalAngle/movements.size());
        Point newPos = getPosition().clone();
        newPos.moveByVector(v);
        setRotationWithMaxRotation(totalAngle/movements.size(), GameLogicConstants.MAX_ROTATION_ON_COLLISION);
        getPosition().moveByVector(v);

    }

    return isClose;

}

private boolean checkCollisionWithCircle(Point p, double radius, ArrayList<GameBodyObject> objects) {
    for(GameBodyObject obj : objects) {
        if(CircleCollider.collide(p, radius, obj.getPosition(), obj.getRadius())) {
            double dx = obj.getPosition().getX() - p.getX();
            double dy = obj.getPosition().getY() - p.getY();
            return true;
        }
    }
    return false;
}

private Double getAngleIfNotColliding(Vector n, Point p, Vector alternativeN, Point alternativeP, ArrayList<GameBodyObject> others) {
    if (!checkCollisionWithCircle(p, getRadius(), others)) {
        return n.getAngle();
    } else {
        if(!checkCollisionWithCircle(alternativeP, getRadius(), others)) {
            return alternativeN.getAngle();
        } else {
            return null;
        }
    }
}

Glad to hear you found the solution to your problem! Please mark your solution as the accepted answer to help others who may have similar problems. — Pikalek
– Pikalek, Commented May 5, 2018 at 14:10

coder_86 · Accepted Answer · 2017-08-02 17:39:32Z

0

You can use NavMesh for that purpose. Mark the objects that you want to bake in NavMesh as Navigation Static. Attach a NavMeshAgent component to the object you want to move. Bake the NavMesh for the scene.

To Move to a position on click first save the click position into a variable say clickPosition and use the SetDestination() method of NavMeshAgent class:

 GetComponent<AI.NavMeshAgent>().SetDestination(clickPosition);

It will automatically calculate the required path and will move to the click position.

for details read the documentation : https://docs.unity3d.com/Manual/Navigation.html

edited Aug 2, 2017 at 17:39

answered Aug 2, 2017 at 17:34

coder_86

1751 gold badge5 silver badges19 bronze badges

\$\begingroup\$ Sorry I am not using unity, I do it on serverside in Java using Spring boot \$\endgroup\$

durisvk10
– durisvk10

2017-08-02 18:29:55 +00:00
Commented Aug 2, 2017 at 18:29

Add a comment |

Stack Exchange Network

Collision avoidance not only AI wrong

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Collision avoidance not only AI wrong

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions