Pushing Pieces

Pushing pieces around a game board can be done in a number of different ways. The first attempt was recursive, though I did have vague notions of how to do a better job of it. Up to N moves are made, swapping the piece being moved with an empty cell, or recursing if there is something in the way, in which case there's a conga line of swaps. With a callback or by building a list this could in theory give an animation routine something to do, but I have no idea how to implement animations, so that might all be wrong.

    (defun move-pushing (board moves srcx srcy stepx stepy)
      (labels ((swap (a b x z)
                 (board-set-flag +board-moved+ (aref board b a))
                 (rotatef (aref board b a) (aref board z x)))
               (stepwise (a b)
                 (if (array-in-bounds-p board b a)
                   (if (plusp (aref board b a))
                     (let* ((newa (+ a stepx)) (newb (+ b stepy))
                            (result (stepwise newa newb)))
                       (ecase result
                         (:stop :stop)
                         (:move (swap a b newa newb) :move)))
                     :move)
                   :stop)))
        (loop with nextx = (+ srcx stepx) and nexty = (+ srcy stepy)
              repeat moves do
              (let ((result (stepwise nextx nexty)))
                (ecase result
                  (:stop (return))
                  (:move (swap srcx srcy nextx nexty)
                         (psetf srcx nextx srcy nexty)
                         (incf nextx stepx)
                         (incf nexty stepy)))))))

Take Two

The second implementation is non-recursive, though still is prone to making a lot of swaps. It, too, could support animation via a callback or list-building. Probably. This pushes points to move onto a stack, then drains them when there's an empty cell found.

    # moves stuff with less recursion than in prior versions (before 0.05)
    sub _move_stack ( $grid, $moves, $srcx, $srcy, $stepx, $stepy ) {
        my $point = [];
        $point->@[XX,YY] = ($srcx, $srcy);
        my @stack = $point;
        while ( $moves > 0 ) {
            my $point = [];
            $point->@[ XX, YY ] = ( $stack[-1][XX] + $stepx, $stack[-1][YY] + $stepy );
            # edge: ran out of space for pushing
            last
              if $point->[XX] < 0
              or $point->[XX] >= BOARD_SIZE
              or $point->[YY] < 0
              or $point->[YY] >= BOARD_SIZE;
            push @stack, $point;
            # empty cell: swap along the stack to advance the pieces
            if ( $grid->[ $stack[-1][YY] ][ $stack[-1][XX] ] == PIECE_EMPTY ) {
                for my $i ( reverse 0 .. ( $#stack - 1 ) ) {
                    # downside: this may happen more than it needs to
                    $grid->[ $stack[$i][YY] ][ $stack[$i][XX] ] |= MOVED_MASK;
                    my $j = $i + 1;
                    (   $grid->[ $stack[$i][YY] ][ $stack[$i][XX] ],
                        $grid->[ $stack[$j][YY] ][ $stack[$j][XX] ]
                      )
                      = (
                        $grid->[ $stack[$j][YY] ][ $stack[$j][XX] ],
                        $grid->[ $stack[$i][YY] ][ $stack[$i][XX] ]
                      );
                    # in theory one could collect a list of moves for use by
                    # an animation routine, or have a callback for that. but
                    # that would use more CPU and memory
                }
                shift @stack;
                $moves--;
            }
            # non-empty cell: put it onto the stack next time around
        }
    }

Third

Yet another method also uses a stack, though only saves the piece values. When the place to move the pieces to is found--which may not happen, or may only be partially through the stack of pieces--everything in the stack is copied out, once. Efficient, but not really compatible with any sort of animation.

    inline static void
    domoves(struct marad *game, int moves, int srcx, int srcy, int stepx, int stepy)
    {
        int bi, newx, newy, targetx, targety, target_bi, where;
        uint8_t buf[MARAD_BOARD_SIZE];
        bi        = 0;
        newx      = srcx;
        newy      = srcy;
        target_bi = -1;

        buf[bi] = game->board[MARAD_COORD(srcx, srcy)];

        // find where the pieces are to be moved to and buffer any
        // to be moved
        while (moves > 0) {
            newx += stepx;
            newy += stepy;
            if (newx < 0 || newx >= MARAD_BOARD_SIZE || newy < 0 ||
                newy >= MARAD_BOARD_SIZE)
                break;
            where = MARAD_COORD(newx, newy);
            if (game->board[where] == NOTHING) {
                // empty cell: one less move to make, and maybe
                // this is our target
                targetx   = newx;
                targety   = newy;
                target_bi = bi;
                moves--;
            } else {
                // occupied cell: record a piece to (maybe) be moved
                buf[++bi] = game->board[where];
            }
        }

        // if there are things to move, copy them, then fill any
        // remainder with empty cells
        if (target_bi >= 0) {
            while (target_bi >= 0) {
                where              = MARAD_COORD(targetx, targety);
                game->board[where] = buf[target_bi--];
                game->board[where] |= MOVED_MASK;
                targetx -= stepx;
                targety -= stepy;
            }
            while (targetx != srcx && targety != srcy) {
                where              = MARAD_COORD(targetx, targety);
                game->board[where] = NOTHING;
                targetx -= stepx;
                targety -= stepy;
            }
            where              = MARAD_COORD(srcx, srcy);
            game->board[where] = NOTHING;
        }
    }

The more efficient ones are also the least tested, though it would not be too hard to set them through various edge cases, and the Perl version does have not terrible code coverage.

Pushing Pieces

Take Two

Third

See Also