# Collision avoidance not only AI wrong

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
// Otherwise if I got closer with normal vector n2
} else {
// store the angle
}
};
}
}

// 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"? Aug 2 '17 at 14:48
• @clabe45 I want to move this (GameBodyObject) to the position where the user clicked, like in Dota 2 or Warcraft 3 Aug 2 '17 at 17:14
• Oh I see I guess that was obvious Aug 2 '17 at 22:50
• Can you show us the code where you call this method? What objects do you set it to avoid? Aug 2 '17 at 22:58
• @clabe45 I call this from many places and I use all the objects registered in Game object Aug 3 '17 at 10:56

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) {
} else {
}
};
}
}
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) {
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) {
return n.getAngle();
} else {
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. May 5 '18 at 14:10

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.