Contents


Secrets from the Robocode masters

Anti-gravity movement

Comments

Anti-gravity movement is a highly flexible technique that can help you fool pattern-analysing robots by allowing you to define particular points (called gravity points) on the battle field to avoid. Each gravity point is assigned its own strength. By resolving the components of this strength in the directions of x and y, you can make a good attempt at avoiding all the enemy robots. (See the sidebar "Anti-gravity terminology" for help understanding the terms used in this tip.)

The first portion of this tip deals with a basic anti-gravity technique, and the later portion describes ideas for working around the limitations inherent with this basic code.

The math behind anti-gravity movement

The mathematics behind anti-gravity is actually quite simple if you have a working knowledge of trigonometry.

In Figure 1, the arrow labeled "F" shows the direction of the force from Crazy on AntiGravityBot. The force can be thought of as components in the x and y directions, as shown by the two other arrows. Resolving the forces allows us to simply add together all the forces from all of the gravity points in the x and y directions, producing total forces in the directions of x and y.

Figure 1. Resolving forces
Resolving forces
Resolving forces

To prevent our robot from being affected by robots that are far away, we must calculate the force on our robot from a gravity point using the function force = strength/Math.pow(distance,2) where strength is the power of the gravity point, and distance is the distance between the gravity point and our robot. The power value of 2 is not fixed; you can use a value of 3 to avoid a point only when you become very close to it.

The code

The listings that follow show you the code for a basic anti-gravity system. Listing 1 shows the main anti-gravity function. It loops through all the gravity points in a vector, resolves the forces, and moves the robot in the correct direction. I recommend assigning enemy robots to be the repulsion points. To do this, you must keep a fairly up-to-date picture of the battle field, which means spinning your radar fairly often.

Listing 1. The anti-gravity workhorse: antiGravMove()
void antiGravMove() {
    double xforce = 0;
    double yforce = 0;
    double force;
    double ang;
    GravPoint p;
    
    for(int i = 0;i<gravpoints.size();i++) {
        p = (GravPoint)gravpoints.elementAt(i);
        //Calculate the total force from this point on us
        force = p.power/Math.pow(getRange(getX(),getY(),p.x,p.y),2);
        //Find the bearing from the point to us
        ang = 
    normaliseBearing(Math.PI/2 - Math.atan2(getY() - p.y, getX() - p.x)); 
        //Add the components of this force to the total force in their 
        //respective directions
        xforce += Math.sin(ang) * force;
        yforce += Math.cos(ang) * force;
    }
    
    /**The following four lines add wall avoidance.  They will only 
    affect us if the bot is close to the walls due to the
    force from the walls decreasing at a power 3.**/
    xforce += 5000/Math.pow(getRange(getX(), 
      getY(), getBattleFieldWidth(), getY()), 3);
    xforce -= 5000/Math.pow(getRange(getX(), 
      getY(), 0, getY()), 3);
    yforce += 5000/Math.pow(getRange(getX(), 
      getY(), getX(), getBattleFieldHeight()), 3);
    yforce -= 5000/Math.pow(getRange(getX(), 
      getY(), getX(), 0), 3);
    
    //Move in the direction of our resolved force.
    goTo(getX()-xforce,getY()-yforce);
}

The helper methods shown in Listing 2 give us the ability to move to a point in the most efficient way possible and get the distance between our robot and the enemy.

Listing 2. Helper methods
/**Move in the direction of an x and y coordinate**/
void goTo(double x, double y) {
    double dist = 20; 
    double angle = Math.toDegrees(absbearing(getX(),getY(),x,y));
    double r = turnTo(angle);
    setAhead(dist * r);
}

/**Turns the shortest angle possible to come to a heading, then returns 
the direction the bot needs to move in.**/
int turnTo(double angle) {
    double ang;
    int dir;
    ang = normalisebearing(getHeading() - angle);
    if (ang > 90) {
        ang -= 180;
        dir = -1;
    }
    else if (ang < -90) {
        ang += 180;
        dir = -1;
    }
    else {
        dir = 1;
    }
    setTurnLeft(ang);
    return dir;
}

/**/Returns the distance between two points**/
double getRange(double x1,double y1, double x2,double y2) {
    double x = x2-x1;
    double y = y2-y1;
    double range = Math.sqrt(x*x + y*y);
    return range;	
}

Finally, in Listing 3, we see the GravPoint class, which holds all the data we need for a gravity point. Note that power must be negative to repel.

Listing 3. GravPoint class
class GravPoint {
    public double x,y,power;
    public GravPoint(double pX,double pY,double pPower) {
        x = pX;
        y = pY;
        power = pPower;
    }
}

The complete source for this tip is available for download from Download.

Improving the behaviour

The code in Listings 1 through 3 produces reasonable behaviour, but the battle performance is hardly breathtaking. While the bot generally stays away from other robots, it has a tendency to get stuck close to a wall. The reason for this is that once a robot reaches, say, the bottom wall there are no robots below it. Thus, there is no force to push it away from the wall except for the repulsion produced by the wall itself. Because the wall repulsion has a limited range, poor behaviour is produced.

To combat the problem, I use a system that totals all the forces on a series of points around the arena. I then assign repulsion values to points that have a greater-than-average total force on them (meaning that they have robots near them), and attraction values to those that have a lower-than-average total force on them. I then resolve the forces of these new points on my robot. When assigning attraction points, you must be extremely careful; if your robot gets close to an attraction point, it will hover over it and never leave. For this reason, I recommend randomly assigning the position of these intermediate points and changing their positions regularly.

I'll leave it to you to work out the code for this enhancement; be assured that it is only a slight adaptation of the code above, with exactly the same basic principles described. As a further tip, I recommend using force = strength/Math.pow(distance,1.5) for calculating the force of the intermediate points on your bot.

Additional enhancements

Anti-gravity is an incredibly flexible technique, so a discussion of the full range of behaviours you can produce with it is impractical. Here are, however, a few of the more interesting ones:

Target selection: By assigning lower repulsion values to targets that you are good at hitting or have low health, you can move closer to them and prey on the weak.

Randomisation: On a fairly regularly basis, you may want to add or subtract random amounts from your x and y forces to produce some more random movement, and even to stop occasionally, to fool enemy targeting systems. I encourage you to implement this behaviour.

Melee bullet dodging: If you know when an enemy is firing at you, you can model the bullet that's fired as an anti gravity point. If you assume that it was fired with, for example, linear targeting, you can update the position of that gravity point each turn and dodge the bullet. This enhancement, however, has yet to be perfected by any bot.

Follow the leader: This enhancement involves creating an attractive point for your robot to follow. You can thus produce any pattern that you want (within the the laws of robocode physics) by moving the point, all while leaving in the standard anti-gravity wall repulsion.


Downloadable resources


Related topics


Comments

Sign in or register to add and subscribe to comments.

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=1
Zone=Java development
ArticleID=242029
ArticleTitle=Secrets from the Robocode masters: Anti-gravity movement
publish-date=052002