# Obstacle-avoiding AI

I have made a game in Java that involves two players to fight each other with spaceships. For one player mode, I have programmed a simple AI to avoid allies and asteroids and go straight towards the player. Unfortunately, the game lags quite a bit when there are 3 AIs at once. I think this is because of all the for loops. Is there a way to streamline this?

Note: this is only a snippet, not the whole thing.

Important: angle is in counterclockwise radians.

• player - AI body
• xLimit\yLimit - Boundaries
• asteroidField - ArrayList of asteroid bodies
• otherAllies - ArrayList of ally bodies
• findAng - returns angle from two positions

angle = player.getAngle();
position = player.getPosition();
mass = player.getMass();

if(position.x > xLimit){
position.x = xLimit;
}
if(position.x < -1 * xLimit){
position.x = -xLimit;
}
if(position.y > yLimit){
position.y = yLimit;
}
if(position.y < -1 * yLimit){
position.y = -yLimit;
}

float angToOther = findAng(position, otherPos);

while(angle<0){
angle += 2*Math.PI;
}
while(angle>2*Math.PI){
angle -= 2*Math.PI;
}

if(angle > 3 * Math.PI / 2 && angToOther < Math.PI / 2){
angToOther += 2 * Math.PI;
}
if(angle < Math.PI / 2 && angToOther > 3 * Math.PI / 2){
angToOther -= 2 * Math.PI;
}

boolean asteroidInWay = false;
float playerDist = (float) Math.sqrt(Math.pow(otherPos.x - position.x,2) +
Math.pow(otherPos.y - position.y, 2));

ArrayList<float[]> possiblePaths = new ArrayList<float[]>();
ArrayList<Float> goodPaths = new ArrayList<Float>();
ArrayList<Integer> toRemove = new ArrayList<Integer>();

for(Body ast: asteroidField){

float dist = (float) Math.sqrt(Math.pow(ast.getPosition().x - position.x,2) +
Math.pow(ast.getPosition().y - position.y, 2));

float angToAst = findAng(position, ast.getPosition());
float angToEdge = (float) Math.asin(radius / dist);

float side1 = angToAst+angToEdge+0.3f;
float side2 = angToAst-angToEdge-0.3f;

if(side1 > 3 * Math.PI / 2 && angToOther < Math.PI / 2){
side1 -= 2 * Math.PI;
}
if(side1 < Math.PI / 2 && angToOther > 3 * Math.PI / 2){
side1 += 2 * Math.PI;
}

if(side2 > 3 * Math.PI / 2 && angToOther < Math.PI / 2){
side2 -= 2 * Math.PI;
}
if(side2 < Math.PI / 2 && angToOther > 3 * Math.PI / 2){
side2 += 2 * Math.PI;
}

if(angToOther < side1 && angToOther > side2 && playerDist > dist){
asteroidInWay = true;
}

}

for(Vec2 ally: otherAllies){

float dist = (float) Math.sqrt(Math.pow(ally.x - position.x,2) +
Math.pow(ally.y - position.y, 2));

float angToAst = findAng(position, ally);
float angToEdge = (float) Math.asin(10 / dist);

float side1 = angToAst+angToEdge+0.3f;
float side2 = angToAst-angToEdge-0.3f;

if(side1 > 3 * Math.PI / 2 && angToOther < Math.PI / 2){
side1 -= 2 * Math.PI;
}
if(side1 < Math.PI / 2 && angToOther > 3 * Math.PI / 2){
side1 += 2 * Math.PI;
}

if(side2 > 3 * Math.PI / 2 && angToOther < Math.PI / 2){
side2 -= 2 * Math.PI;
}
if(side2 < Math.PI / 2 && angToOther > 3 * Math.PI / 2){
side2 += 2 * Math.PI;
}

if(angToOther < side1 && angToOther > side2 && playerDist > dist){
asteroidInWay = true;
}

}

if(asteroidInWay){

for(int pathGroup=0; pathGroup<possiblePaths.size(); pathGroup++){
for(int path=0; path<2; path++){

float pathAngle = possiblePaths.get(pathGroup)[path];

for(int pathGroupToCheck=0; pathGroupToCheck<possiblePaths.size(); pathGroupToCheck++){

if(pathAngle < possiblePaths.get(pathGroupToCheck)[0] &&
pathAngle > possiblePaths.get(pathGroupToCheck)[1] &&                               !toRemove.contains(pathGroup*2 + path)){

}

}
}
}

for(int pathGroup=0; pathGroup<possiblePaths.size(); pathGroup++){
for(int path=0; path<2; path++){

if(!toRemove.contains(pathGroup*2 + path)){
}

}
}

float bestPath = 100f;

for(int path=0; path<goodPaths.size(); path++){

float pathAngle = goodPaths.get(path);
if(Math.abs(angToOther-pathAngle) < Math.abs(angToOther-bestPath)){
bestPath = pathAngle;
}

}

angToOther = bestPath;

}

• Don't think. Test. Break out that method into submethods. Spin up JVisualVM and see which submethod is causing the problem. Try to address that specific problem, either by yourself or by bringing it back here. – Eric Stein Jul 7 '15 at 14:53
• Agreed with @EricStein, rather than us guessing where time is consumed you should profile the code and see where it is consumed. If you need help improving it, post the code together with profiling information. – Emily L. Jul 8 '15 at 7:01

As noted in the comments, this would be better broken into methods. Not only would it make it easier to profile, it would make the code easier to understand.

angle = player.getAngle();


This seems a bad name. What is an angle and why does a player have one? My best guess is that this angle represents the direction of travel. If so, why not call it direction?

position = player.getPosition();
mass = player.getMass();

if(position.x > xLimit){
position.x = xLimit;
}
if(position.x < -1 * xLimit){
position.x = -xLimit;
}
if(position.y > yLimit){
position.y = yLimit;
}
if(position.y < -1 * yLimit){
position.y = -yLimit;
}


Are xLimit and yLimit always the same? If these are general limits, then they should probably be checked when the position is set or changed. Then you'd always get valid values from getPosition and wouldn't need to check them here.

This may or may not give a performance improvement. It depends on how this code is reached. Is it called from a loop itself? That context would make it easier to evaluate this code.

while(angle<0){
angle += 2*Math.PI;
}
while(angle>2*Math.PI){
angle -= 2*Math.PI;
}


Same objection. Why do this after fetching the angle? If you fetch the same angle multiple times, you'll do this multiple times.

You may also be able to get a small performance boost by defining a constant for the value 2*Math.PI. You use this frequently but your code has you calculating each time. Of course, your compiler may be smart enough to compile it out. Same thing for the two right angle values.

if(angle > 3 * Math.PI / 2 && angToOther < Math.PI / 2){
angToOther += 2 * Math.PI;
}
if(angle < Math.PI / 2 && angToOther > 3 * Math.PI / 2){
angToOther -= 2 * Math.PI;
}


This is confusing. Perhaps if I traced through the code enough, I could see the logic of this. But why should I need to do so? This would be a great place to comment and explain why angToOther should be no more than half a rotation from angle. We might be able to suggest a better way to get that same effect if it were clearer what this code was doing.

It's also worth noting that it would be helpful to know how angToOther is calculated and used. Perhaps that calculation could be adjusted to remove the need for this adjustment. Or later uses might be adjusted to not require this. That kind of context is often helpful.

boolean asteroidInWay = false;


This might better be named something like obstacleInWay, as it doesn't just get set for asteroids.

ArrayList<float[]> possiblePaths = new ArrayList<float[]>();
ArrayList<Float> goodPaths = new ArrayList<Float>();
ArrayList<Integer> toRemove = new ArrayList<Integer>();


As a general rule, on the left side you want to specify the type as the interface rather than the implementation.

List<float[]> possiblePaths = new ArrayList<float[]>();
List<Float> goodPaths = new ArrayList<Float>();
List<Integer> toRemove = new ArrayList<Integer>();


This makes it easier if you want to change the implementation later. Very occasionally there will be some method that only exists on the implementation that will require you to use the implementation. If that exists here, for all three, then you should comment saying so.

for(Body ast: asteroidField){


Most would put more spacing here and elsewhere.

for (Body asteroid: asteroidField) {


This makes it easier to see that for and Body are separate keywords. And that ) and { are not one multi-character symbol.

Also, why call it ast rather than write out asteroid? Similarly, why call a list of asteroids an asteroid field? Generally an asteroid field would be a section of space, not a collection of asteroids. I'd probably call that either asteroids or asteroidsInField.

    float radius = ast.getFixtureList().m_shape.m_radius;

float dist = (float) Math.sqrt(Math.pow(ast.getPosition().x - position.x,2) +
Math.pow(ast.getPosition().y - position.y, 2));

float angToAst = findAng(position, ast.getPosition());
float angToEdge = (float) Math.asin(radius / dist);

float side1 = angToAst+angToEdge+0.3f;
float side2 = angToAst-angToEdge-0.3f;


What is .3? You should probably declare a constant for this. Or comment on what it does.

    final float distance = (float) Math.sqrt(Math.pow(ast.getPosition().x - position.x,2)
+ Math.pow(asteroid.getPosition().y - position.y, 2));

final float deviation = (float) Math.asin(asteroid.getFixtureList().m_shape.m_radius / distance) + .3f;
final float asteroidDirection = findAng(position, asteroid.getPosition());

float farEdge = asteroidDirection + deviation;
float nearEdge = asteroidDirection - deviation;


If they aren't going to change, you should declare these as final.

You can actually get rid of the radius variable entirely, as you only use it the once.

Writing out the names makes it easier to read the code and understand what it's doing.

Changing the order can make it easier to see that you just declared distance when you use it to calculate the deviation.

Moving the addition of .3 to the deviation calculation saves a subtraction.

    if(side1 > 3 * Math.PI / 2 && angToOther < Math.PI / 2){
side1 -= 2 * Math.PI;
}
if(side1 < Math.PI / 2 && angToOther > 3 * Math.PI / 2){
side1 += 2 * Math.PI;
}

if(side2 > 3 * Math.PI / 2 && angToOther < Math.PI / 2){
side2 -= 2 * Math.PI;
}
if(side2 < Math.PI / 2 && angToOther > 3 * Math.PI / 2){
side2 += 2 * Math.PI;
}


The logic here can be simplified.

    if (angToOther < Math.PI / 2) {
if (nearEdge > 3 * Math.PI / 2) {
nearEdge -= 2 * Math.PI;
farEdge -= 2 * Math.PI;
} else if (farEdge > 3 * Math.PI / 2) {
farEdge -= 2 * Math.PI;
}
} else if (angToOther > 3 * Math.PI / 2) {
if (farEdge < Math.PI / 2) {
farEdge += 2 * Math.PI;
nearEdge += 2 * Math.PI;
} else if (nearEdge < Math.PI / 2) {
nearEdge += 2 * Math.PI;
}
}


This will do fewer comparisons per iteration. It takes advantage of several things that we know: angToOther can't be in both the fourth and the first quadrants at once. The nearEdge is less than the farEdge. So if the nearEdge is greater than something, so will the farEdge be. And vice versa if farEdge is less than something. So we do two to four comparisons per iteration rather than four to six.

    if(angToOther < side1 && angToOther > side2 && playerDist > dist){
asteroidInWay = true;
}


I would find this easier to read as

    if (farEdge > angToOther && angToOther > nearEdge && playerDist > dist) {
asteroidInWay = true;
}


This finishes

    float[] toAdd = {side1, side2};



Note that it is advantageous to be able to find paths quickly. In your current form, this is difficult. You have to iterate through the entire collection. If you change possiblePaths from an ArrayList to something that tracks order, e.g. a NavigableMap, you will be able to better store where you can and can't go. This may need to be a new type. I'd tend to store this in a tree structure (a TreeMap may work for you if you change the float[] to a custom type).

Also consider changing the name possiblePaths to something like blockages. A path just needs a single number, as it is just a direction. This needs two numbers because it is telling you the range that is blocked.

Note that overlapping blockages can be merged as you generate the set. This should be accomplishable in $O(n\log n)$ time. Your current method is an $O(n)$ insertion followed by an $O(n^3)$ check if there is an obstacle.

    for(int pathGroup=0; pathGroup<possiblePaths.size(); pathGroup++){
for(int path=0; path<2; path++){

float pathAngle = possiblePaths.get(pathGroup)[path];

for(int pathGroupToCheck=0; pathGroupToCheck<possiblePaths.size(); pathGroupToCheck++){

if(pathAngle < possiblePaths.get(pathGroupToCheck)[0] &&
pathAngle > possiblePaths.get(pathGroupToCheck)[1] &&                               !toRemove.contains(pathGroup*2 + path)){

}

}
}
}


Note that you do an $O(n)$ operation (contains) inside an $O(n)$ loop instead a constant loop inside another $O(n)$ loop. That's $O(n^3)$.

Incidentally, this would be easier if you could provide a runnable version of the code. Either add a link with more context or write a wrapper that exercises this code that is small enough to fit in the question. For the latter option, you should probably ask a new question and link back to this one.

• You do make a good point about the position and angle at the beginning, but unfortunately I don't control those. I am using jbox2d to get positions and angles. And no, xLimit and yLimit aren't constant. – Blue Jul 9 '15 at 0:56

In addition to @mdfst13's excellent answer I just want to point out one small thing.

When you are comparing euclidian distances or radii of objects you can do the comparison squared and get the same result.

Formally, $d \gt \ell \Leftrightarrow f\left( d\right) \gt f\left(\ell\right)$ for any monotonic function $f$. The same is true for other inequalities such as $\lt, \ge, =$ etc.

Which means that:

$\sqrt{s_x^2 + s_y^2} < \sqrt{v_x^2 + v_y^2} \Leftrightarrow s_x^2 + s_y^2 < v_x^2 + v_y^2$ for two vectors $s$ and $v$.

In short, when comparing distances you can always compare the squared distance for the same result, as squaring is a monotonic functions iff the argument is larger than zero, but this is rarely a problem when comparing distances (or radiuses). This means you can avoid doing a costly square root operation in tight loops in many game related applications.

Also I do believe that Math.pow(x, 2) is slower than x*x because Math.pow is much more general and handles non integer powers.