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.
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 accepts 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, temporary 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 comparison 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 example, 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 confident 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 language you are learning.