Tutorial: Goal Seeking

Skill Level: Beginner

The bot included in the devkit is not at all intelligent. The problem with this bot is that it makes no attempt to reach the goal. If it does stumble into the goal it'll be entirely by accident. It doesn't even check where the goal is, even though it's possible to do that with this line of code:

Point goalPos = getGoalCorner();

But supposing the bot did obtain the goal's location, how could it use this information? A simple way is to always try to move nearer to the goal with each step. To do this the bot will have to calculate how far away it currently is from the goal, and then compare that with how far it would be if it were to move in various directions. To try the code presented here, use an empty maze. Click the "clear" button in the Maze Editor, and then save the maze. The system will reload the empty maze each time you run (until you change the maze).

To do the calculations, we'll need to know where we are currently located, and where we would be if we were to take one step in some particular direction. Let's assume that we have the direction we want to move stored in a Compass variable:

Compass direction = Compass.EAST;

Here's one way to find out where we would end up if we were to move in that direction:

Point pos = getPosition();
Point nextPos = addPoints(pos, direction.getVector());

The getPosition method is available in the BotBrain class, which your class derives from. It's not a free method, although the cost is only 1 unit of energy, which isn't much considering the battery starts with 10,000 units of energy. However the calls do add up quickly and in a competition it will make a difference. For now we'll use this, but another tutorial will consider a better approach to determining the bot's location.

Now that we have our current location, plus the location of the goal (technically the top-left cell of the 4×4 cell goal area, but let's ignore that for now), how do we determine the distances? The theorem of Pythagoras would serve, but we needn't implement it ourselves. Java provides an easier way:

double dist = pos.distance(goalPos);
double nextDist = nextPos.distance(goalPos);

Why are we using doubles here? Partially it's because that's what the distance method returns, but we do need those decimals. The difference between the goal-distances of two adjacent cells could be a fraction, and rounding to an integer would prevent us from comparing properly.

Now that we have the distances we can compare the two, and as long as the next position has the lesser distance to the goal, we proceed to move in the direction we had in mind.

if (nextDist < dist) move(direction);

If you were to use only this in your main loop, you'd find that the bot would move forward up to a certain point, and then get stuck in an infinite loop. The problem is that no code is given for the situation when the next distance is not less than the current distance. What should we do in such a case?

As suggested before we could check the cells in other directions, and then choose between them. For now let us take the simplest possible approach: just turn in some direction. It doesn't matter which direction, because on the next iteration of the main loop, if the cell in that direction isn't any closer to the goal the bot will turn again. The bot will keep turning until it has found a better direction to move in.

if (nextDist < dist) move(direction);
else direction = direction.getLeft();

This small amount of code should be enough to have the bot reach the goal on an empty maze, no matter where the goal is and no matter where and in which direction the bot starts. Here is the complete runBot method:

public void run()
{
    Point goalPos = getGoalCorner();
    Compass direction = Compass.EAST;

    while (true)
    {
        Point pos = getPosition();
        Point nextPos = addPoints(pos, direction.getVector());

        double dist = pos.distance(goalPos);
        double nextDist = nextPos.distance(goalPos);

        if (nextDist < dist) move(direction);
        else direction = direction.getLeft();
    }
}

By itself this isn't very useful of course—this bot is still foiled by any walls, since it completely ignores them and will blindly keep running into them until its energy is exhausted. But this is probably the simplest possible way of seeking the goal, which every bot must do in some fashion. There are other ways which are better; try discovering them!