Tutorial: Maze Mapping

Skill Level: Beginner

In the AMazeBot, all bots get knowledge of the goal location when they start, but they have no idea about the layout of the maze. They do have various means by which to determine the layout—that is, whether cells contain a wall or a floor. These means all consume some energy though, and it is important to minimize the amount of energy used. One way of doing this is having the bot remember where it's been, and where the walls and floors are. In addition to avoiding wasteful looking, this also becomes very useful for more intelligent pathfinding.

What we need to do is store in memory some information about each cell. Since the maze is arranged as a grid of cells, we should organize our memory in the same way, and the way to do that is to use a 2-dimensional array. The question becomes, what datatype should we use? To start with, let's use an integer, and use a code where certain numbers have certain meanings.

In Java arrays are not primitive types, and it's not enough to just declare the variable, as we could do with a plain (scalar) int:

int scalar;

We have to additionally instantiate arrays with the new keyword before we can use them. This is how we do it:

int[][] map = new int[29][29];

The square brackets are what indicate that this is an array; the fact that there are 2 of them indicates that this is a 2-dimensional array. Notice that the declaration doesn't specify the size of the array, just the number of dimensions. It's in the instantiation that the size of the array is specified. In this case we want an array that has 29 × 29 elements. Since in programming we generally start counting at 0, the rows and columns will be identified by numbers in the range 0 to 28 (just like coordinates on the maze itself).

Although it's not a problem to hardcode the value 29 here, since we know that the AMazeBot competition uses a maze of that size, it is good programming practice to not use literal values like this. Indeed, previous versions of the AMazeBot used a larger maze size of 44, so a bot written for a n earlier version with that number hardcoded would have more places in the code that need to be updated to work in the current version. The most robust way to create this array is like this:

int[][] map = new int[MAZE_SIZE][MAZE_SIZE];

Code like this wouldn't need to be changed in the future if the maze size were to change. Such things matter a lot when you're working on a huge codebase with a team of programmers, so better get into the habit now!

Now that we have the array, what information shall we store, and how shall we encode it? Well, a cell can be either a floor (open to the bot) or a wall (blocked). We could use 2 numbers to indicate those 2 states, but additionally we could use another number to indicate that we don't know what the cell is yet. Since in Java ints are by default initialized to the value 0, and we start out with most of the cells being unknown to us, it makes sense to let 0 represent "unknown". We could then use 1 for "open" and 2 for "wall", though this is arbitrary.

NOTEIt is very important that you do not use Strings in your map. Java's Strings are very slow compared to C's character arrays. Doing heavy calculations on your map would become extremely slow, and bots that take too long to run a maze during the competition will be disqualified.

When we start a maze, we know that the starting position is always a floor (otherwise how could the bot be there!). We could thus mark the starting cell as open right at the start:

Point start = getStartPosition();
map[start.x][start.y] = 1;

This code will work, but perhaps you see a problem here. If someone else (and that someone else could be you, a week later) were to look at this code, they wouldn't immediately know what the 1 represents. Comments could be added, but that has various issues of its own. This is another example of the principle of not using literals in your code when you can avoid it. Since we are making up this coding scheme ourselves, what we should do is explicitly define the values as constants.

final int UNKNOWN = 0;
final int OPEN    = 1;
final int WALL    = 2;

Point start = bot.getStartPosition();
map[start.x][start.y] = OPEN;

The final keyword is how we define constants in Java. The convention is that constants are written in uppercase to distinguish them from variables. Now the code is effectively self-commenting, and we're less likely to introduce accidental bugs. It's still possible though, because there's nothing to prevent us from doing something like this:

map[start.x][start.y] = 42;    // What does this mean?!

There is a way to deal with this issue, but that is a diversion that may be addressed in another tutorial (yes, the princess is always in another castle).

So now that we have a map of the maze, how do we use it? There are two things to be done: first, before we move or look into a cell, we check whether we already know its state. If we do know, then we don't need to waste energy doing a look, and can decide whether to move or not. Second, when the map says the state of the destination cell is UNKNOWN, we do do the look and then update our map (and move if desired) based on the results. Perhaps something like this:

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

if (map[nextpos.x][nextpos.y] == OPEN) move(direction);
else if (map[nextpos.x][nextpos.y] == UNKNOWN)
{
    if (look(direction))
    {
        map[nextpos.x][nextpos.y] = OPEN;
        move(direction);
    }
    else map[nextpos.x][nextpos.y] = WALL;
}

if (map[nextpos.x][nextpos.y] == WALL)
{
    // We'll have to find some other direction to move in.
}

Notice that the final if statement is standalone, not part of an else statement. The reason is that if the state was originally UNKNOWN, it could have been set to WALL after a look. By making that last if statement independent we can take the same action whether the state was originally WALL or changed to WALL, and only have the code in one place.