From: dbucklin@sdf.org
Date: 2019-08-10
Subject: Writing 2048 in Forth, or How I Spent My Summer Vacation
2048 is a casual puzzle game. Imagine a combination of Tetris and
sudoku. I've been spending far too much time playing 2048 lately
and I thought writing a version of the game in Forth would be a
good way to practice what I've learned about Forth so far [0].
The rules seem simple at first but, as with many things, they get
complicated. 2048 is played on a grid. How can I represent a grid
of numbers in linear blocks of memory? The standard grid is 4 by
4, so it seems reserving 16 cells of memory is a good starting
point. A cell, using gforth on a 64-bit system, is 8 bytes.
That's more than enough to store the largest possible grid cell
value, 2048.
Each segment of four cells represents a row in the grid. I need to
calculate a memory location based on a row and column in the grid.
The formula for this is straightforward:
offset = (rowlength * rownumber) + columnnumber
An important assumption is that the index origin is zero. Index
origin is where you start counting. Counting starting at zero is
an important convention in Forth as it is in many other programming
languages. This contrasts with, for example, BASIC and Awk that
use an index origin of one. Now I can navigate my logical grid.
I created a word, draw, that clears the screen, prints the score,
and draws the grid. In Forth parlance, a "word" is analogous to a
function or subroutine; it consumes input and produces a result.
At the beginning of each turn, the computer places a low-value
tile, a 2 or 4, in a random empty square in the grid. I needed a
word to generate a random number from 0 to 15. I ended up copying
the gforth-provided code to do this. I created a word, new, that
generates a random number among 0 and 15, inclusive. It then
checks to see if the cell value is zero and, if so, places a two in
the cell. If the cell value is not zero, it tries again. Now, I
can draw my grid and place values in random places.
Next, I needed to "finish the owl". During each turn, the game ac-
cepts a move from the user. The move can be one of up, down, left,
or right. The game recomputes the grid, condensing the tiles and
combining adjacent, equal tiles in the direction of the move.
I used my experience playing the game to intuit the rules for this
step. I tried and gave up on a few different ideas before settling
on an approach. One idea I liked initially was to scan the row or
column, apply the rules, and place the results in a separate, tem-
porary memory location. Because the compute process doesn't write
to the same memory location more than once during a compute cycle,
there really isn't any need to have a separate memory location to
store results; I can do it in-place.
After a fair amount of mental churning, I determined that I could
do everything using two pointers. I call them the "store" pointer
and the "look" pointer. The look pointer points to a cell in the
grid holding one of these numbers. The store pointer points to the
second number and also indicates where the result of the operation
will be stored.
Think of using two fingers to remember the locations of the two
numbers you are comparing. Each operation is essentially a compar-
ison of these two values in the grid. One of three actions will
result from that comparison: a number could be moved, values could
be combined, or nothing will happen. Depending on the specific
conditions, the look pointer will be advanced, the store pointer
will be advanced, or both will be advanced.
Initially, I wrote separate words to perform the computation for
each movement direction. This was an important exploratory step.
I determined that the chosen direction determines whether the
pointers are incremented or decremented and the order of row and
column operands when calculating the location of the box in memory.
I added a couple more words to account or this and then refactored
the four directional words into a single word, `compute`. The
`compute` word takes four arguments: the loop limit and index, the
vector which determines which direction the loop goes, and a flag
that indicates whether rows or columns are being condensed.
After much debugging and many facepalm moments, my game was
playable. It's still missing some important features. For exam-
ple, it doesn't know if you've won or lost, and it will eventually
get stuck in an infinite loop.
I've been reading about Forth for so long, it's helpful to have a
practical application to apply my skills. I feel a lot more confi-
dent in my knowledge of Forth after this exercise. I think casual
games like 2048 offer a good way to challenge yourself with a level
of complexity that would suit Goldilocks, regardless of the lan-
guage you are learning.
[0]: https://gitlab.com/davebucklin/2048