Tuesday, January 9, 2007

Building a Game Engine with Cocoa, Part 2

we started the initial implementation for building a simple game engine with Cocoa. We finished with a working board that would draw itself and allow us to move pieces freely around on it. In this episode, we'll extend this work and add a little more pizzazz to the game board itself by introducing the logic for generating valid moves for Lines of Action, our sample game of choice. With a snazzy game board and move generation out of the way, we'll be poised nicely to dive right into the game tree search in the next installment.

User Interface Updates

There are a number of updates to the game board that can drastically increase the overall usability of our board game. One helpful change is to keep a game piece highlighted once it has been clicked, if it belongs to the player who is moving. This mechanism alerts the user that a piece has indeed been selected, and presumably, the next click designates where the piece should move. Another related change is to highlight squares on the board that correspond to valid move locations once a piece has been selected.

These two approaches in combination provide a great deal of clarity as to what's going on and increase the overall fun factor in a strategy game like Lines of Action; they allow you to spend more time strategizing and less time trying to make sure you haven't overlooked an obvious possibility for moving or capturing a piece. Plus, if you've never played before, they definitely facilitate the learning process.

The changes to get these effects in place are primarily reflected in mouseDown:, mouseMoved:, and drawBoardBackgroundInRect:. Here are the new versions of these methods with some of the most interesting portions highlighted. Ignore the self-descriptive macros, but only for the moment. We'll discuss them, along with the summary of the changes, later.

- (void)mouseDown:(NSEvent*)event {
//get the mouse position in view coordinates
NSPoint mouse;
mouse = [self convertPoint: [event locationInWindow] fromView: nil];

//if there was a previous click, save it
NSPoint previousPoint = selectedCoord;

//get the new board square that was clicked in.
selectedCoord = [self boardCoordForClickPoint:mouse];

//starting point for a move must be the player moving
if (
EQUAL_NSPOINTS(previousPoint, NIL_POINT) &&
board[(int)selectedCoord.x][(int)selectedCoord.y] != playerMoving
) {
selectedCoord = NIL_POINT;
return;
}
//ending point for a move must not be on the player moving
if (NOTEQUAL_NSPOINTS(previousPoint, NIL_POINT))
if (board[(int)selectedCoord.x][(int)selectedCoord.y] == playerMoving)
hoveredCoord = selectedCoord;
else if (![currentPlayerMoves
containsObject:[NSValue valueWithPoint:selectedCoord]]) {
//ignore it. it's not a valid move
if (NOTEQUAL_NSPOINTS(previousPoint, NIL_POINT)) {
selectedCoord = previousPoint;
return;
}
}

//generate moves here
if (currentPlayerMoves)
[currentPlayerMoves release];
currentPlayerMoves = [[self validMovesFromSpot:selectedCoord] retain];

if (
NOTEQUAL_NSPOINTS(previousPoint, NIL_POINT)
&& board[(int)selectedCoord.x][(int)selectedCoord.y] != playerMoving
) {


[self movePieceFromCoord:previousPoint toCoord:selectedCoord];
selectedCoord = NIL_POINT;
[currentPlayerMoves release];
currentPlayerMoves = nil;

if (playerMoving == PLAYER_1)
playerMoving = PLAYER_2;
else
playerMoving = PLAYER_1;
}


//set display now that currentPlayerMoves is populated
[self setNeedsDisplay:YES];

}

- (void)mouseMoved:(NSEvent *)event {
// get the mouse position in view coordinates
NSPoint mouse;
mouse = [self convertPoint: [event locationInWindow] fromView: nil];

//no need to redraw anything in this case, the piece is still highlighted
if (NOTEQUAL_NSPOINTS(hoveredCoord, NIL_POINT) &&
[piecesPaths[(int)hoveredCoord.x][(int)hoveredCoord.y] containsPoint: mouse])
return;

//otherwise, check to see if a piece is being moused over
int i; int j;
for (i = 0; i < DIMENSION; i++)
for (j = 0; j < DIMENSION; j++)
if (board[i][j] != EMPTY)
if ([piecesPaths[i][j] containsPoint: mouse] &&
EQUAL_NSPOINTS(selectedCoord, NIL_POINT)) {
hoveredCoord = NSMakePoint(i,j);
[self setNeedsDisplay:YES];
return;
}

//no pieces are being moused over if we've made it to here, so there's
//no need to redraw unless we need to un-highlight a piece, but only
//unhighlight if the piece is not unselected
if (NOTEQUAL_NSPOINTS(hoveredCoord, NIL_POINT) &&
EQUAL_NSPOINTS(selectedCoord, NIL_POINT)) {
[self setNeedsDisplay:YES];
hoveredCoord = NIL_POINT;
}
}

- (void)drawBoardBackgroundInRect:(NSRect)rect {
int i; int j;
for (i=0; i < DIMENSION; i++)
for (j=0; j < DIMENSION; j++) {
if (currentPlayerMoves && [currentPlayerMoves containsObject:
POINT_OBJECT(i,j)])
[self drawRectForBoardCoord:NSMakePoint(i,j) andHighlight:YES];
else
[self drawRectForBoardCoord:NSMakePoint(i,j) andHighlight:NO];
}
}

All of the macros you see are defined at the top of GameBoard.m and are intended to be more self-descriptive and readable than their encompassing logic appears. A motivator for defining these macros was the repetitiveness involved in much of the conditional logic that was introduced with move generation, as well as the repetitive casting of NSPoint's .x and .y components to int values. (A useful exercise in refactoring the code base before next time would be to replace all of the NSPoint references with a custom struct that holds two integer values.) A summary of the macros introduced follows, along with introductory comments.

//a way of designating an undefined point on the board
#define NIL_POINT NSMakePoint(-1,-1)

//ways for checking if two NSPoints are equal or not
#define EQUAL_NSPOINTS(p1,p2) (p1.x == p2.x && p1.y == p2.y)
#define NOTEQUAL_NSPOINTS(p1,p2) (p1.x != p2.x || p1.y != p2.y)

//descriptive shortcuts for checking board conditions
#define PLAYER_MOVING_NOT_AT(x,y) (board[(int)(x)][(int)(y)] != playerMoving)
#define OPPONENT_NOT_BLOCKING(c1,p1,p2) (![self opponentInLineBetweenCoord:(c1) \
andCoord:NSMakePoint((p1),(p2))])
#define OPPONENT_AT(x,y) ( (board[(int)(x)][(int)(y)] != EMPTY && \
board[(int)(x)][(int)(y)] != playerMoving) )

//NSPoints (structs) can't be loaded into arrays, so wrap/retrieve them via NSValue
#define POINT_OBJECT(x,y) ([NSValue valueWithPoint:NSMakePoint((x),(y))])

Getting back to the actual changes that are related to the highlighted pieces, you see in mouseDown: that we're still tracking where the user clicks on the board. However, we're also keeping track of whose turn it is to move, via a new instance variable called playerMoving, so that we can always highlight the most recent piece the player moving has clicked and force him to make a valid move based upon the array of results returned by a method called validMovesFromSpot: (more on this shortly). A small change in mouseMoved: now results in the selected piece remaining highlighted if it was clicked and belongs to the player moving.

Knowing which piece is currently selected (as you're no doubt thinking by now) also allows us to highlight spaces on the board, which is the other change we'd like to make to the user interface. The method drawBoardBackgroundInRect: handles this change by inspecting the contents of another instance variable, currentPlayerMoves, whenever it is asked to draw the board. But when is drawBoardBackgroundInRect: called? It is called first thing, back in drawRect:, which we trigger at the very end of mouseDown: with the [self setNeedsDisplay:YES] call.

Overall, there's not a ton of work involved with these changes, and yet they pack a significant punch with respect to overall usability and enjoyment. We'll get to the details of the move generation next, but go ahead and take a look at Figures 1 and 2 to see how our new game board shows you which moves you have available when you're trying to move.

Generating Moves

With a spiffier user interface in place, we'll now turn our attention to generating moves for our game. What appears to be the official Lines of Action page lists a few basic rules:

* Black moves first.
* Each turn, the player moves one of his pieces, in a straight line, exactly as many squares as there are pieces of either color anywhere along the line of movement. (These are the "lines of action").
* You may jump over your own pieces.
* You may not jump over your opponent's pieces, but you can capture them by landing on them.

We'll implement a move generator for these rules, but wait until next time when we develop a routine to check for "gameover" to handle the corner cases that may arise.

To get started with move generation, we'll implement a routine that computes the total number of pieces in each "line of action," given a spot on the board. For any given board position, we'll inspect the board from the starting spot in the following manner: up/down, left/right, up/right, then down/left, and finally, up/left, then down/right. Remember, all that matters is the total number of pieces in each of those four lines, so we'll only be returning a total of four values.

To make our lives a little easier, we'll introduce a helper struct to encapsulate these four values, which we can pass off to another routine that will use this information to help generate the actual moves. Here are the necessary additions so far:

typedef struct {
int up_down;
int left_right;
int up_right_down_left;
int up_left_down_right;
} LineCounts;

- (LineCounts)lineCountsForSpot:(NSPoint)spot {

//up down
int up_down = 0;
int y;
for (y=0; y < DIMENSION; y++)
if (board[(int)spot.x][y] != EMPTY)
up_down++;

//left right
int left_right = 0;
int x;
for (x=0; x < DIMENSION; x++)
if (board[x][(int)spot.y] != EMPTY)
left_right++;

//up right, then down left
int up_right_down_left = 0;
x=spot.x; y=spot.y;
while (x < DIMENSION && y < DIMENSION) {
if (board[x][y] != EMPTY)
up_right_down_left++;
x++; y++;
}

x=spot.x; y=spot.y;
while (x >= 0 && y >= 0) {
if (board[x][y] != EMPTY)
up_right_down_left++;
x--; y--;
}

//remove duplicate count
if (board[(int)spot.x][(int)spot.y] != EMPTY)
up_right_down_left--;

//up left, then down right
int up_left_down_right = 0;
x=spot.x; y=spot.y;
while (x >= 0 && y < DIMENSION) {
if (board[x][y] != EMPTY)
up_left_down_right++;
x--; y++;
}

x=spot.x; y=spot.y;
while (x < DIMENSION && y >= 0) {
if (board[x][y] != EMPTY)
up_left_down_right++;
x++; y--;
}

//remove duplicate count
if (board[(int)spot.x][(int)spot.y] != EMPTY)
up_left_down_right--;

LineCounts lc = {
.up_down = up_down,
.left_right = left_right,
.up_left_down_right = up_left_down_right,
.up_right_down_left = up_right_down_left
};

return lc;
}

Using the information provided by the LineCounts struct and the board, we can easily start at a given spot and search in each of the eight possible directions to determine if any moves are available. For each direction, we only need to ensure a few conditions:

* We don't go off of the edge of the board
* The opponent doesn't stand between a piece and its destination
* The piece doesn't land on one of its own pieces when moving

Each of these conditions can be wrapped up as a piece of a large conditional logic statement; in our case, we even use some of the recently discussed macros to make the code a bit tidier and readable. The only remotely challenging of these three conditions is detecting when opponents stand between a piece and its destination, so it's nice to wrap this one up in its own routine. A snippet of one possible approach, opponentInLineBetweenCoord:andCoord:, is shown below and illustrates vertical detection of an opponent. All seven of the other directions work exactly the same way.

if (c1.x == c2.x) {
if ((int)(c2.y-c1.y) > 0) { //up
int dy;
for (dy=c1.y; dy < c2.y; dy++)
if (OPPONENT_AT(c1.x,dy))
return YES;
}
else {
int dy;
for (dy=c1.y; dy > c2.y; dy--)
if (OPPONENT_AT(c1.x,dy))
return YES;
}

}

One other detail associated with move generation involves the desire to pass back the NSArray from the validMovesFromSpot: function. Since NSArrays only house objects descended from NSObject, we won't be able to directly add our NSPoint structs to it. Apple, however, realized the convenience of passing around some of the most common structs and provides another class, NSValue, which we can use to wrap NSPoints whenever we'd like to add them to an array. This is precisely what we do inside of the POINT_OBJECT macro, and it works like a charm.

Without further ado, meet validMovesFromSpot:. Like other functions we've encountered so far, the same basic logic is in place for checking all eight directions, so a portion of the code is omitted inline below. The sample project, of course, contains all of the code for the entire project.

-(NSArray*)validMovesFromSpot:(NSPoint)spot {
//make sure spot is occupied or else there's no move
if (board[(int)spot.x][(int)spot.y] == EMPTY)
return [NSArray array];

LineCounts lc;
lc = [self lineCountsForSpot:spot];

NSMutableArray *moves = [NSMutableArray arrayWithCapacity:8];

//up
if (
spot.y + lc.up_down < DIMENSION &&
PLAYER_MOVING_NOT_AT(spot.x,spot.y+lc.up_down) &&
OPPONENT_NOT_BLOCKING(spot,spot.x,spot.y+lc.up_down)
)
[moves addObject:POINT_OBJECT(spot.x,spot.y+lc.up_down)];


//down
if (
spot.y - lc.up_down >= 0 &&
PLAYER_MOVING_NOT_AT(spot.x, spot.y-lc.up_down) &&
OPPONENT_NOT_BLOCKING(spot,spot.x, spot.y-lc.up_down)
)
[moves addObject:POINT_OBJECT(spot.x, spot.y-lc.up_down)];

//snip...
//left,right,up right, down left, up left, down right
//snip...

return (NSArray*)moves;

Recalling that validMovesFromSpot was called all the way back in mouseDown:, we've now completed the circuit and grown the project to the point that two users could sit down at the keyboard and take turns moving until one of them identifies a gameover condition. Next time, we'll implement gameover checking and a few final details before delving head first into a game tree search where we will develop an AI opponent using some custom heuristics.

To prepare you for next time, the sample project already includes a hook in AppController's called validMovesFromSpot:withBoard:, which we'll be able to use for querying the game board about particular moves that are available from our game tree search. The implementation details are fairly straightforward and totally reuse existing code by temporarily swapping out the GameBoard's instance variables board and playerMoving whenever it is invoked. Since all move generation logic depends on these two values, they're all we need to modify in order to produce a list of moves.

If you prefer to work on your own copy instead of using the sample project provided, be sure to remember to set the outlet for AppController's gameBoard, as shown in Figure, when you're trying to reference the gameBoard from within AppController.


And while we're at it, there's also a method in GameBoard called board that simply returns a lightweight wrapper around the actual 2D integer array used to keep track of pieces. An illustration of this method is also in AppController's awakeFromNib method. In the next episode, the plan is to use this data board to feed our game tree search.