Java Game Programming For Dummies - W. Holder, D. Bell

Chapter 7: 2-D Maze 155

Assuming that the first test beats the odds and i s 0 p e n ( ) returns f a 1 s e, the next check i s 0 p e n ( x , y -1 , s i d e ) looks to see whether the square to the top (square 4 in Figure 7-3) is open. The s i d e probability is 80 percent, but because square 4 is a wall, i s o p e n ( ) returns f a 1 s e regardless of the results of the probability test. The next check is for the other side at the bottom (square 5); square 5 is also a wall square, so i s0pen ( ) again returns f a 1 s e.

The last two checks are looking to see whether using square 2 creates two diagonally opposed open squares, as shown in Figure 7-4.

The test n o D i a g ( x , y , 1 , -1) checks to see whether using square 2 creates diagonally opposed open squares between squares 2 and 6 in Figure 7-3. The test is

private boolean noDiag (int x, int y, int dx, int dy) I return blocked(x + dx, y) && blocked(x, y + dy) &&

i sOpen(x + dx, y + dy, diag):

noDi ag( ) first checks that both of the other opposing corners (squares 4 and 3 from Figure 7-3 in this case) are wall squares. If they are, it checks whether the diagonal square (square 6) is open. However, because

B 1 o c k M a z e sets the d i a g probability to 100, t ry D i r ( ) never uses a square that creates diagonally opposed open squares.

Although diagonally opposed open squares don't create a faulty maze, they are aesthetically undesirable, at least when viewed from overhead.

Table 7-1 shows all the settings that you can tinker with to change the characteristics of the maze that B 1 o c k M a z e generates. You change the settings by changing the initialization values of the private fields in the

class.

56 Part II: Up to Speed

sowing Mazes

You solve a maze by finding a path between two points in the maze. Games need to solve mazes in order to allow computer adversaries to navigate through the maze. This section shows how to implement algorithms to find a path through the maze. Chapter 8 discusses how to use the capability to navigate through mazes to instill "artificial intelligence" in your computer opponents.

Representing the solution

You declare the following two-dimensional array of bytes in the Maze class to keep track of a maze solution:

protected byte[][] path;

Each entry in the array records the sides of the corresponding maze square through which the solution passes. You mark a path in the array by setting the bit for the corresponding side. The static final fields L E FT, R I GHT, TOP, and BOTTOM in the Maze class define the bits. For example, if the path enters the left side of the square and exits out the top, the entry in p a

( LEFT I TOP).

You add the following methods to the M a z e class to define the methods for traversing the maze:

Chapter 7:2-D Maze 15 7

abstract boolean traverse (int startX, int startY, int finishX, int finishY, boolean displaySearch);

public boolean traverse (boolean displaySearch) I return traverse(startX, startY, finishX, finishY,

displaySearch);

The classes that extend Ma z e must implement the abstract method

traverse(). You declare the overloaded traverse( bool can

d i s p 1 a y S e a r c h ) method to use as a shortcut for traversing from the start and finish squares of the maze.

Keeping your !eft hand on the wa!!

A relatively simple yet effective strategy for traversing a maze is to keep your left or right hand in contact with the wall as you move through the maze. Keeping your left hand on the wall causes you to take all the left-hand branches. When you reach a dead end, your hand sweeps along the deadend wall and you start walking back down the path. Figure 7-5 shows traversing a maze while keeping the left hand on the wall.

dlpe 7-5:

Reverse

maze

using the

left-hand

rule.

The left-hand (or right-hand) rule only works reliably for mazes with a single solution between any two points. If a maze has more than one solution, you can end up traveling in an endless circle if you follow the left-hand rule. To see why you can move in an endless circle, consider a hallway with a column in the middle. Your objective in this simple maze is to get from one end of the hall to the other with two solutions: You can go around the column to the left or to the right. If you happen to start your search with your hand on the column, you perpetually walk around the column; your hand never leaves the column, and you never reach the goal of the maze.

58 Part II: Up to Speed

The W a 1 1 M a z e class implements the left-hand rule traversal algorithm like this:

public synchronized boolean traverse

(int xx, int yy, int fx, int fy, boolean displaySearch)

resetpath();

i f (solve) ( // mark path to enter maze

while ((sq & side) != 0) // search for direction to try

if ((side <f= 1) > BLOCKED)

side = TOP;

path[xx][yy] ^= side; // set exit from current square dirtySquare(xx, yy);

switch (side) f // set entrance to new square

sq = dirtySquare(xx, yy):

i f (xx == sx && yy == sy && side ==

// we ve searched the entire maze and we re back at II the starting square, so there s no solution resetPath():

i f (displayPath) repaint();

return false;

i f (displaySearch) showMaze(false);

else if ((++count & OxFF) == 0) Thread.yield();

dirtySquare(xx, yy);

I

i f (displayPath) repaint();

return true;

} ll traverse()

Notice that t r a v e r s e ( ) marks a square in the path using the exclusive-or

operator (^=). Remember that you use the exclusive-or operator to toggle bits: A zero bit becomes a one and a one becomes a zero. This toggling

means that the first time t r a v e r s e ( ) marks a path in a square, the code sets the bit for the path to one. As t r a v e r s e ( ) backtracks down a dead-end path, this same instruction toggles the one and clears the path to zero, effectively erasing the dead-end path from the p a t h [ ] [ ] array.

Using breadth-first searching to find the shortest path

You use a breadth-first search to find the shortest path between two points in a maze. Unlike the left-hand rule, a breadth-first search is designed to find the optimal solution in a maze with multiple paths between two squares. Breadth-first searching works by taking one step at a time on each possible path before taking a second step on any path. The search proceeds simultaneously along all paths that have not been pruned. You prune a path (eliminate it from future searching) when the search reaches a dead end or a square that has already been searched. Because all search paths are the same length, you know that when you find the destination square, you've also found the shortest path.

You use a two-dimensional array the same size as the maze grid to keep track of which squares have been searched. You declare and allocate the array like this:

byte[][] graph = new byte[mzWid][mzHyt];

First, you initialize each entry in the g r a p h [ ] [ ] array to zero. Next, set the entry in g r a p h [ ] [ ] for the square where the search starts to -1. As you search, you record in g r a p h [ ] [ ] the direction to move in order to return to the previous square on the path. This record creates a backwards-pointing graph that you can follow to get back to the square where the search was begun. Figure 7-6 shows the breadth-first search path through a maze and the resulting g r a p h [ ] [ ] array.

160 Part II: Up to Speed

Figure 7-6:

A breadth-

first search

path and

corresponding graph array.

While searching, you maintain a queue of squares waiting to be searches. After you add a square to the search path and set the corresponding erao , in g r a p h [ ] [ ] , you add the square to the queue. Each iteration of the pulls the next square out of the queue and checks each direction to see whether the search path can be extended to the square in that direction You add any squares you find to the search path, set the corresponding

entry in g r a p h [ ] [], and place them in the queue. This cycle continues UN either you find the destination square, in which case you've solved the maze, or the queue is empty, in which case the maze has no solution.

A queue is a first in, first out (FIFO) data structure, which means that the first item put into the queue is the first item removed from the queue and that you add items to the queue at one end and take them out at the oth® The term queue means "a waiting line," and like a line at the Department 4 Motor Vehicles, the first person in line is the first person served.

Here is the breadth-first t r a v e r s e ( ) method for the B 1 o c k M a z e class:

public synchronized boolean traverse

(int sx, int sy, int fx, int fy, boolean displaySearch)

short[][] queue = new short[gsize][21; // 0 = x, 1 = y

if (displaySearch) l resetPath();

i f (solve) 1 path[sx][sy] = LEFT; dirtySquare(sx, sy);

showMaze(false);

2 Part II: Up to Speed

(continued)

switch (graph[xx][yy]) I

1

dirtySquare(xx, yy);

1

if (solve)

path[fx][fy] y= LEFT;

if (displayPath) repaint();

return true;

Chapter 7: 2-D Maze 163

Notice in the preceding code that after you find a solution, you reconstruct the path by following g r a p h [ ] [ ] from the destination square to the starting square.

The M a z e class extends j a v a . a wt . C a n v a s to give it a display area. You draw the maze by overriding the p a i n t ( ) method inherited from C a n v a s.

Because most of the work to draw a wall maze or a block maze is the same, the M a z e class overrides p a i n t ( ) to do the drawing. As far as the p a i n t ( ) method is concerned, the only difference between the two Maze subclasses, Bl ockMaze and Wal l Maze, is in the actual drawing of a square. paint( ) calls d raw Squa re ( ) to draw a single maze square. You have to implement the abstract method d r a w S q u a r e ( ) that Maze defines and that p a i nt( ) calls in the classes that extend M a z e. B 1 o c k M a z e draws its squares as solid blocks. Wa 1 1 Maze draws walls between squares and leaves the middle of the squares open, except that W a 1 1 M a z e draws squares with walls on all four sides (BLOCKED squares) as solid blocks.

I mplementing a circular queue

Part II: Up to Speed

Using the p a i n t ( ) method

You draw the maze to an offscreen image and then copy this image to the screen. (Chapter I shows how to use an offscreen image and override

u p d a t e ( ) for smooth screen updates.) You add the following p a i n t (: method and supporting fields to the Maze class:

public synchronized void paint (Graphics g) { paintOffscreenImage(); g.drawImage(offscreenImage. 0, 0, this); notifyAll();

paint() calls pai ntOffscreenlmage( ) (another method in the Maze

to do the work of creating the maze image in an offscreen image. You do the

pa i ntOffscreen Image( ). Keeping the offscreen image code out of

pa i nt ( ) allows the subclasses to modify how pa i nt ( ) works and still reuse the code in p a i n t 0 f f s c r e e n I m a g e ( ) to generate the maze display- (Chapter 8 shows an example of overriding p a i n t ( ) to display sprites on top of the offscreen maze image.)

The first thing paintOffscreenImage() does is check whether it needs to create the offscreen image and then creates it if necessary.

You allocate the offscreen image from pa i nt ( ) rather than in the Ma ze ( ) constructor because c r e a t e Image ( ) can't create the offscreen image unto you place the maze canvas on the screen by adding it to a container. And because you can't place the canvas on the screen until you create it, you port the code that allocates the offscreen image in pa i nt ( ). The Abstract Window Toolkit (AWT) can't call pa i nt ( ) until you add the component to the screen hierarchy, so c r e a t e I m a g e () is guaranteed to work when

paint( ) calls it.

Next, p a i n t O f f s c r e e n I m a g e ( ) loops through all the squares in the range of dirty squares and draws any squares that have the D I RTY bit set in the square. For each DIRTY square, pa i ntOffscreenImage( ) calls drawSquare( ) to draw the maze square and then calls draw Path Square to draw any path through the square. (The "Displaying a solution" section later in this chapter shows how to implement d r a w P a t h S q u a r e ( ).) If the square is the maze's start or finish square, p a i n t O f f s c r e e n I m a g e ( ) calls d r a wT a r g e t ( ) to draw colored circles to mark it.