24 June 2013

Objective-C, Day 6 (Back from Dylan-land)

I've been a little sick -- maybe something in our water, because our tap water started tasting like hose water -- but it seems to be clearing up. There's nothing like having flu-like symptoms to celebrate the first couple of days of summer! But I'm more-or-less back on my feet, although still a little queasy. Yesterday the weather station closest to our home in Saginaw hit 93, "feels like 100" with the humidity. I know that's nothing compared to some of the folks out west, but it came on us pretty fast, and I'd happily trade 100 in the low-humidity desert for 90 in Saginaw. I've got the A/C unit set up in the home office, since we finally need it, and I'm pressing on with my re-engineering of the old Mac Polar game.

The Dylan implementation I discussed last time helped focus my thinking about, if not the optimal, at least a fairly clear model for implementing game piece behavior. It also clarified what I should do with game objects in Objective-C, and that is "nothing." The "model" class still deserves to live, but the tile pieces just don't derive any benefit from being classes. The two main reasons are (1) Objective-C doesn't really support static methods in the sense that C++ does, and (2) Objective-C's dispatch mechanism isn't sophisticated enough to help us significantly save on "code to find code." So the tiles will be represented by plain old data, and we'll dispatch on their "types" with plain old logic.

The Dylan code has a small infrastructure of helper functions for accessing, filling, and logging the board state. I won't include all of it, because most of what it does is pretty clear from the function name, but there are functions like this:

define method getTileAtPos( model :: <model>, pos :: <pos-or-false> ) =>
    ( tile :: <tile> )
    if ( pos )
        getTileAtXY( model, pos.y-idx, pos.x-idx );
    else
        $the-edge;
    end if;
end;

define function getAdjacentPos( pos :: <pos>, dir :: <dir> )
    => ( pos-or-false :: <pos-or-false> )
    let y-offset :: <integer> = 0;
    let x-offset :: <integer> = 0;
    if ( dir == #"east" )
        x-offset := 1;
    elseif ( dir == #"south" )
        y-offset := 1;
    elseif ( dir == #"west" )
        x-offset := -1;
    elseif ( dir == #"north" )
        y-offset := -1;
    end if;
    let new-y-idx :: <integer> = pos.y-idx + y-offset;
    let new-x-idx :: <integer> = pos.x-idx + x-offset;
    if ( ( ( new-y-idx >= 0 ) & ( new-y-idx < $board-dim-y ) ) & 
         ( ( new-x-idx >= 0 ) & ( new-x-idx < $board-dim-x ) ) )
        make( <pos>, y-idx: new-y-idx, x-idx: new-x-idx );
    else
        #f
    end if;
end;

define method penguinPush( model :: <model> )
    => ( result :: <boolean> )
    let target-pos :: <pos-or-false> = 
        getAdjacentPos( model.penguin-pos, model.penguin-dir );
    let target-tile = getTileAtPos( model, target-pos );
    pushTile( model, model.penguin-dir, target-pos, target-tile );
end;

define method penguinMove( model :: <model>, dir :: <dir> )
    if ( model.penguin-dir ~= dir )
        model.penguin-dir := dir;
        format-out( "Penguin changed dir to %S\n", dir );
        force-output( *standard-output* );
    else
        if ( penguinPush( model ) )
            format-out ( "Penguin moved to %d, %d\n",
                model.penguin-pos.y-idx, model.penguin-pos.x-idx );
            force-output( *standard-output* );
        end if;
        if ( model.heart-count == 0 )
            format-out( "Heart count reached zero, level cleared!\n" );
            force-output( *standard-output* );
        end if;
    end if;
end;

define method penguinMoveTimes( model :: <model>, dir :: <dir>,
    times :: <integer> )
    for ( count from 1 to times )
        penguinMove( model, dir );
    end for;
end;

define method describe-tile( tile :: <tile> ) => ( str :: <string> )
    case
        ( tile == $the-empty     ) => "___ ";
        ( tile == $the-tree      ) => "tre ";
        ( tile == $the-mountain  ) => "mtn ";
        ( tile == $the-house     ) => "hou ";
        ( tile == $the-ice-block ) => "ice ";
        ( tile == $the-heart     ) => "hea ";
        ( tile == $the-bomb      ) => "bom ";
        otherwise                  => "??? ";
    end case;
end method;

define method describe-board( model :: <model> )
    for ( y-idx from 0 below $board-dim-y )
        for ( x-idx from 0 below $board-dim-x )
            format-out( "%S", 
                describe-tile( model.board[ y-idx, x-idx ]  ) );
        end for;
        format-out( "\n" );
    end for;
    force-output( *standard-output* );
end;

In Objective-C, I'm going to get rid of the singletons and tile classes altogether. They will live on in the comments, to clarify what the pseudo-object-dispatch is doing, and vestigially in the code. The board will have the same internal representation as the raw strings of data taken from the original Polar game resources. I'll keep my three main methods from the Dylan code -- pushing a tile, colliding, and sliding -- but these will be single Objective-C methods rather than multi-methods. The tiles are just chars:

#define POLAR_DATA_LEN_Y 4               // 4x24 grid
#define POLAR_DATA_LEN_X 24
#define POLAR_DATA_NUM_LEVELS 6          // In the original game

typedef char tile_t;

enum {
    polar_tile_empty = '0',
    polar_tile_tree,
    polar_tile_mountain,
    polar_tile_house,
    polar_tile_ice_block,
    polar_tile_heart,
    polar_tile_bomb,
    polar_tile_last = polar_tile_bomb
};

/*
    Not part of the level data; an extra flag value representing
    edge of board
*/
#define polar_tile_edge 'X'

typedef const char polar_level_array_t[POLAR_DATA_NUM_LEVELS]
                                      [POLAR_DATA_LEN_Y]
                                      [POLAR_DATA_LEN_X];

typedef char polar_board_array_t[POLAR_DATA_LEN_Y]
                                [POLAR_DATA_LEN_X];

extern polar_level_array_t polar_levels;

Why use #define for array indices and our tile pieces instead of const int and const char? Because using a const integral variable (yeah... a "const variable...") to dimension an array, or represent a case value for a switch statement, is still not standard C everywhere, although it is a common extension to allow the compiler to treat it as so in contexts like this. Enum works fine with characters. Oddly, I have a build issue when using enum values to define the array boundaries. I haven't figured out quite what that is all about -- I think it may be a Clang bug. But I'll worry about that later.

In the implementation file:

polar_level_array_t polar_levels =
{
    {
        "100000000000000100000400"
        "106020545000000000100100"
        "100000000000000050002300"
        "110000100000000000000000"
    },
    // Etc., for the other five levels
}

The model class gets one as a member:

@interface ArcticSlideModel : NSObject
{
    polar_level_array_t board;
    pos_t penguinPos;
    dir_e penguinDir;
    int heartCount;
}

We'll work ourselves down from the external API to the associated implementation:

// The external API
- (void)penguinMoveDue:(dir_e)dir;
- (void)penguinMoveNTimes:(int)n
                      due:(dir_e)dir;

penguinMoveNTimes:due: calls penguinMoveDue: which calls penguinPushDue:. In Dylan:

define method penguinPush( model :: <model> )
    => ( result :: <boolean> )
    let target-pos :: <pos-or-false> = 
        getAdjacentPos( model.penguin-pos, model.penguin-dir );
    let target-tile = getTileAtPos( model, target-pos );
    pushTile( model, model.penguin-dir, target-pos, target-tile );
end;

That's not strictly translatable to C, since we're taking advantage of a type-union to retrieve the position or #f with getAdjacentPos. This usage extends to the lower levels of the implementation, though, so for now we're going to continue to allow getAdjacentPos to return position values that are invalid, and explicitly check for them so we don't read or write at non-existent array indices.

pos_t getAdjacentPos( pos_t original_pos, dir_e dir )
{
    pos_t updated_pos = original_pos;
    int y_offset = 0;
    int x_offset = 0;
    switch ( dir )
    {
        case dir_east:
            x_offset = 1;
            break;
        case dir_south:
            y_offset = 1;
            break;
        case dir_west:
            x_offset = -1;
            break;
        case dir_north:
            y_offset = -1;
            break;
        default:
            NSLog( @"getAdjacentPos: invalid dir %d", dir );
    }
    updated_pos.y_idx += y_offset;
    updated_pos.x_idx += x_offset;;
    return updated_pos;
}

We rely on posValid to explicitly check for invalid tile cases:

BOOL posValid( pos_t pos )
{
    return ( ( ( pos.y_idx >= 0 ) &&
               ( pos.y_idx < POLAR_DATA_LEN_Y  ) ) &&
             ( ( pos.x_idx >= 0 ) &&
               ( pos.x_idx < POLAR_DATA_LEN_X ) ) );
}

That should be pretty non-controversial. Note that BOOL in Objective-C is not a real type; it's just a #define and a typedef based on char_t. So don't get a false sense of security -- it has the same problems that fake bool types always have, and always will have, in straight C.

Anyway, we can now implement our pushTile function. Here is the Dylan:

define generic pushTile( model :: <model>, dir :: <dir>,
    pos :: <pos-or-false>, target-tile :: <tile> );

// Handle walkable (empty or tree tile). The penguin
// is allowed to move onto this tile (indicated by
// returning #t).
define method pushTile( model :: <model>, dir :: <dir>,
    target-pos :: <pos>, target-tile :: <walkable> )
    => ( result :: <boolean> )
    model.penguin-pos := target-pos;
    #t;
end;

// Handle movable (bomb, heart, ice block) -- call
// collide which specializes in various combinations.
define method pushTile( model :: <model>, dir :: <dir>,
    target-pos :: <pos>, target-tile :: <movable> )
    => ( result :: <boolean> )
    let next-pos :: <pos-or-false>  = 
        getAdjacentPos( target-pos, dir );
    let next-tile = getTileAtPos ( model, next-pos );
    collide( model, dir, target-pos, target-tile,
        next-pos, next-tile );
    #f;
end;

// Handle fixed (house, mountain, edge) -- do nothing.
// The GUI might play a "fail" beep.
define method pushTile( model :: <model>, dir :: <dir>,
    target-pos :: <pos-or-false>, target-tile :: <fixed> )
    => ( result :: <boolean> )
    #f;
end;

Doing all our own dispatch logic, here is a single method in Objective-C:

- (BOOL)pushTile:(tile_t)target_tile
             due:(dir_e)dir
              at:(pos_t)target_pos
{
    switch ( target_tile )
    {
        /*
            Handle the "walkable" cases. The penguin is allowed to move
            onto these tiles, indicated by returning YES
        */
        case polar_tile_empty: /* FALL THROUGH */
        case polar_tile_tree:
            NSLog( @"pushTile: walkable\n" );
            self->penguinPos = target_pos;
            return YES;

        /*
            Handle "movable" cases. Call collide which specializes in
            various combinations.
        */
        case polar_tile_bomb:      /* FALL THROUGH */
        case polar_tile_heart:     /* FALL THROUGH */
        case polar_tile_ice_block:
            NSLog( @"pushTile: movable\n" );
            {
                pos_t next_pos = getAdjacentPos( target_pos, dir );
                /*
                    Note that next-pos can be invalid, which results
                    in the special "edge" tile value.
                */
                tile_t next_tile = [ self getTileAtPos:next_pos ];
                [ self collideTile:target_tile atPos:target_pos
                    due:dir withTile:next_tile
                    atSecondPos:next_pos ];
            }
            return NO;

        /*
            Handle "fixed" cases. Do nothing; the GUI might play
            a "fail" beep.
        */
        case polar_tile_mountain:   /* FALL THROUGH */
        case polar_tile_house:
            NSLog( @"pushTile: fixed\n" );
            return NO;

        default:
            NSLog( @"pushTile: unexpected tile value %d\n",
                   target_tile );
            return NO;
    }
}

And as in the Dylan version, for interesting interactions this method defers to another method:

- (void)collideTile:(tile_t)first_tile
              atPos:(pos_t)first_pos
                due:(dir_e)dir
           withTile:(tile_t)second_tile
        atSecondPos:(pos_t)second_pos
{
    BOOL empty = ( second_tile == polar_tile_empty );
    /* Blocking includes the special edge tile value */
    BOOL blocking = ( second_tile != polar_tile_empty );
    BOOL mountain = ( second_tile == polar_tile_mountain );
    BOOL house = ( second_tile == polar_tile_house );

    BOOL ice_block = ( first_tile == polar_tile_ice_block );
    BOOL bomb = ( first_tile == polar_tile_bomb );
    BOOL heart = ( first_tile == polar_tile_heart );
    BOOL movable = ( ice_block || bomb || heart );

    if ( bomb && mountain )
    {
        /*
            When a bomb meets a mountain, both bomb and mountain blow up
        */
        NSLog( @"collideTile: bomb / mountain\n" );
        [ self setTile:polar_tile_empty AtPos:first_pos ];
        [ self setTile:polar_tile_empty AtPos:second_pos ];
    }
    else if ( heart && house )
    {
        /*
            When a bomb heart meets a house, we are closer to winning
        */
        NSLog( @"collideTile: heart / house\n" );
        [ self setTile:polar_tile_empty AtPos:first_pos ];
        [ self decrementHeartCount ];
    }
    else if ( ice_block && blocking )
    {
        /*
            When an ice block is pushed directly against any
            blocking tile (including the board edge), it is destroyed.
        */
        NSLog( @"collideTile: ice block / blocking\n" );
        [ self setTile:polar_tile_empty AtPos:first_pos ];
    }
    else if ( movable )
    {
        if ( empty )
        {
            /*
                A movable tile pushed onto an empty tile will slide
            */
            NSLog( @"collideTile: movable / empty: start slide\n" );
            [ self slideTile:first_tile atPos:first_pos due:dir
                   toTile:second_tile atSecondPos:second_pos ];
        }
        else if ( blocking )
        {
            /*
                When a generic movable piece meets any other
                blocking pieces not handled by a special case
                above, nothig happens; it stops. Maybe play
                a "fail" beep.
            */
            NSLog( @"collideTile: movable / blocking\n" );
        }
    }
}

This could have been written with a bunch of ugly, redundant-looking switch statements, but the duplicated cases and defaults just don't seem as clear to me as making flags that precisely describe the nature of the "double dispatch" going on. In this program, having to spell out the logic (using code to find code) is not really onerous. But the problem comes, of course, in code where we keep having to add special cases. I could refactor this method to call some smaller methods but that doesn't seem like a real win. In the Dylan implementation if I wanted to add another special interaction, it might only require adding another generic function. That's assuming my whole class hierarchy didn't change.

Finally, the slide method:

- (void)slideTile:(tile_t)first_tile
            atPos:(pos_t)first_pos
              due:(dir_e)dir
           toTile:(tile_t)second_tile
      atSecondPos:(pos_t)second_pos
{
    BOOL empty = ( second_tile == polar_tile_empty );
    /* Blocking includes the special edge tile value */
    BOOL blocking = ( second_tile != polar_tile_empty );
    
    BOOL ice_block = ( first_tile == polar_tile_ice_block );
    BOOL movable = ( ice_block ||
                     first_tile == polar_tile_bomb ||
                     first_tile == polar_tile_heart );

    if ( ice_block && blocking )
    {
        // A specific movable tile, ice-block, meets a
        // blocking tile; don't call collide since the behavior
        // of a sliding ice block is different than a pushed ice
        // block. It just stops and doesn't break.
        NSLog( @"slideTile: ice block / blocking\n" );       
    }
    else if ( movable && empty )
    {
        // A movable tile interacting with an empty tile --
        // move forward on the board and call slide again.
        NSLog( @"slideTile: movable / empty\n" );
        pos_t third_pos = getAdjacentPos( second_pos, dir );
        tile_t third_tile = [ self getTileAtPos:third_pos ];
        [ self setTile:polar_tile_empty AtPos:first_pos ];
        [ self setTile:first_tile AtPos:second_pos ];
        [ self slideTile:first_tile atPos:second_pos due:dir
                  toTile:third_tile atSecondPos:third_pos ];
    }
    else if ( movable && blocking )
    {
        // A movable tile meets a blocking tile: call collide to
        // handle heart/house, bomb/mountain, edge of world, etc.
        NSLog( @"slideTile: movable / blocking\n" );
        [ self collideTile:first_tile atPos:first_pos due:dir
                  withTile:second_tile atSecondPos:second_pos ];
    }
}

That's the bulk of it. Here's an excerpt from the log as it finishes up the first level:

ArcticSlide[2279:c07] penguinPush: tile at 2, 5 pushed
ArcticSlide[2279:c07] pushTile: walkable
ArcticSlide[2279:c07] Penguin moved to: 2, 5
ArcticSlide[2279:c07] Penguin direction changed to EAST
ArcticSlide[2279:c07] Penguin moving EAST
ArcticSlide[2279:c07] penguinPush: tile at 2, 6 pushed
ArcticSlide[2279:c07] pushTile: movable
ArcticSlide[2279:c07] collideTile: movable / empty: start slide
ArcticSlide[2279:c07] slideTile: movable / empty
ArcticSlide[2279:c07] collideTile: heart / house
ArcticSlide[2279:c07] Heart count reached zero, level cleared!
ArcticSlide[2279:c07] ArcticSlideModel board state:
tre__________________________________________treice_____________________
tre_________mtn_______________________________________tre______tre______
tre____________________________________________________________hou______
tretre____________treice________________________________________________

I'll put in logic to play the remaining levels soon, as additional test cases.

Note that I kept the recursive call to slideTile. It's not an idiom commonly used in C and Objective-C. We only recurse when the moving tile traverses more than one empty tile, and so never more than 23 times. I like to write algorithms recursively when possible while sketching out code. If direct recursion like that is verboten, it can be removed. I don't think my compiler is optimizing it out. But the termination logic now starts to look redundant:

else if ( movable && empty )
    {
        while ( NO == blocking )
        {
            pos_t third_pos = getAdjacentPos( second_pos, dir );
            tile_t third_tile = [ self getTileAtPos:third_pos ];
            [ self setTile:polar_tile_empty AtPos:first_pos ];
            [ self setTile:first_tile AtPos:second_pos ];
            first_pos = second_pos;
            second_pos = third_pos;
            second_tile = third_tile;
            blocking = ( third_tile != polar_tile_empty );
        }
        if ( ice_block )
        {
            NSLog( @"slideTile: ice block / blocking\n" );
        }
        else
        {
            [ self collideTile:first_tile atPos:first_pos due:dir
                      withTile:second_tile atSecondPos:second_pos ];
        }
    }

And if I don't want to call back into methods in my own call chain at all -- that is, if I have to give up calling collideTile, well, I could do that but it would involve putting copying of the logic from collideTile into this method, and by that point this method will be badly breaking the "DRY" (Don't Repeat Yourself) axiom, so it might be clearer to turn collideTile and slideTile into one method.

Anyway, the heat is building up in my office and it is about dinnertime. I think it's time to move on to some user interface, so the app can actually be played on an untethered iOS device. I also am still struggling a bit to get going on a Haskell implementation. I know it can be done -- people describe Haskell as a good imperative language too, for modeling state as safely as possible -- but let's just say that the chapters and examples I'm reading haven't quite "gelled" in my brain. I still feel like someone studying a foreign language who can read it and understand it when spoken, but not speak it yet -- especially the Monadic dialects. But I'm still working on that.

UPDATE: I have put the source on GitHub, such as it is -- for now, ignore the license text; I need to pick an actual license. See: https://github.com/paulrpotts/arctic-slide-ios

No comments: