AddThis Social Bookmark Button

Listen Print Discuss
Mac OS X > Excerpts >

Building a Game Engine with Cocoa, Part 2
Pages: 1, 2

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 3, when you're trying to reference the gameBoard from within AppController.

Setting gameBoard's outlet in Xcode
Figure 3. Don't forget to set gameBoard's outlet in 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.

Have fun tinkering around with what we have so far until next time. As always, feel free to leave your thoughts, feedback, and suggestions below.

Matthew Russell is a computer scientist from middle Tennessee; and serves Digital Reasoning Systems as the Director of Advanced Technology. Hacking and writing are two activities essential to his renaissance man regimen.

Return to the Mac DevCenter.