💾 Archived View for thrig.me › blog › 2022 › 11 › 12 › pushing-pieces.gmi captured on 2023-09-08 at 16:35:14. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2023-04-19)
-=-=-=-=-=-=-
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)))))))
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
}
}
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.
Efficiency was something on the mind having recently stumbled across the following study, though drawing a huge SDL window with background art probably isn't the most efficient of things (and SBCL is not shy about using memory). A terminal implementation on the other hand is probably too minimal, and beyond that is breaking out some rocks to move around a marked field, or similar.
https://thenewstack.io/which-programming-languages-use-the-least-electricity/
A commentator wondered how much energy the JavaScript on that page has burned up. I only used w3m, but even then there will be excess costs from the bandwidth to transfer and memory to store the not-run JavaScript...
tags #lisp #perl #c