Development
Fitting 100s of Puzzles in Memory
Right, so we have an idea and the graphics sorted out. Now we need to consider how we will store the hundreds of puzzles in the limited memory that the Pokitto offers. In the accompanying article Program Memory vs RAM, I discuss the two different types of memory that the Pokitto has. As the puzzle definitions are static and will be large, we will store them in the ‘program memory’ however even this is limited so any memory savings we can make are gold!
Consider a simple puzzle like the one shown below:
The numbers represent the nodes and (obviously) they come in pairs. The puzzle is 5 columns wide and 5 rows deep equalling 25 cells. We could store this in an array that looks something like this:
const uint8_t puzzles_5x5[] = {
1, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 4, 0, 0,
2, 4, 3, 0, 1,
3, 0, 0, 0, 0
};
if you are not familiar with arrays, refer to the article What is an Array?.
As we know there are, at most, 10 different node types on a 9x9 puzzle so we can compress the arrays a little using a hexadecimal notation. If we group the numbers in pairs we store two values into a single byte – effective halving our storage requirements. Unfortunately, our puzzle has an odd number of columns so we cannot fully realize this saving and have to be content storing each row using three bytes rather than the original five bytes. Still this is a 40% saving!
The array can now be expressed as shown below – in 15 bytes! Note how the hexadecimal values are expressed using the prefix ‘0x’. The first element, the 0x10, corresponds to the two yellow cells at the top left of the puzzle and the final 0x20 relates to the bottom-right corner. Remember that as the puzzle only has 5 columns, the ‘2’ relates to the right-most column and the ‘0’ is not used.
If you are not familiar with Hexadecimal numbers, refer to the article Decimal vs Binary vs Hexadecimal Numbers.
const uint8_t puzzles_5x5[] = {
0x10, 0x00, 0x00,
0x00, 0x00, 0x00,
0x00, 0x40, 0x00,
0x24, 0x30, 0x10,
0x30, 0x00, 0x20,
};
Additional puzzles can be added to the same array. The example below shows two puzzles and I have simply formatted the array to visually separate the puzzles. The array is a contiguous 30 bytes long where the first puzzle occupies bytes 0 through 14 with the second puzzle occupying bytes 15 to 29. Note that we – and the Pokitto and most other computers - refer to the first byte as the 0th position.
const uint8_t puzzles_5x5[] = {
0x10, 0x00, 0x00,
0x00, 0x00, 0x00,
0x00, 0x40, 0x00,
0x24, 0x30, 0x10,
0x30, 0x00, 0x20,
0x10, 0x20, 0x40,
0x00, 0x30, 0x50,
0x00, 0x00, 0x00,
0x02, 0x04, 0x00,
0x01, 0x35, 0x00,
};
Reading a puzzle into Memory
Whereas we stored the puzzles in a single dimensional array in memory, it is much easier for us to visualize and manipulate the puzzle if it is represented as a two-dimensional array. The snippet of code below shows a declaration of a multidimensional array of five columns and rows.
uint8_t board[5][5];
The declaration of two-dimensional arrays in C / C++ is a little counter-intuitive (for me anyway!) as you specify the number of columns before the rows. When visualizing a puzzle, the cell in the top right-hand corner of a 5 x 5 grid can be described as x = 4 and y = 0. However, when referencing the same cell in the array it must be referred to as board[0][4] or board[y][x]. Of course, our puzzles all have equal dimensions so this is a little academic.
As this tutorial progresses, we will end up with an array for each of the puzzle sizes – 5x5, 6x6, 7x7, 8x8 and 9x9.
The code below repeats our puzzle array and shows how to read the first element of it. If you are unfamiliar with C++ (and most other languages), the first element in an array is index zero so the expression puzzles_5x5[0] retrieves the first element. The expression puzzles_5x5[14] would retrieve the last element of the below array as it has 15 elements.
const uint8_t puzzles_5x5[] = {
0x10, 0x00, 0x00,
0x00, 0x00, 0x00,
0x00, 0x40, 0x00,
0x24, 0x30, 0x10,
0x30, 0x00, 0x20,
};
uint8_t byteRead = puzzles_5x5[0];
The previous code would read the first element from the array, 0x10. Once the value has been retrieved, we need to split the value into two using two functions whose operation is described in the supporting article Bit Manipulation. Shown below, they simply return the left and right values of a two-digit hexadecimal number.
uint8_t leftValue(uint8_t val) {
return val >> 4;
}
uint8_t rightValue(uint8_t val) {
return val & 0x0F;
}
With these two functions in play, we can now render an entire puzzle. The initBoard() function accepts a parameter that defines which puzzle in the array of puzzles to retrieve. A value of 0 (the first puzzle) will result in the function reading the first 15 elements from the puzzles_5x5 array and populate our two-dimensional board[][] array. Passing a value of 1 for the puzzle number will result in the function reading bytes 15 to 29 of the puzzles_5x5 array and so on.
The code is a little convoluted for a simple 5 x 5 puzzle but you will see in later articles that we will flesh it out to handle any puzzle size. The main complexity of the code is due to it compensating for puzzles with odd number indices (5x5, 7x7 and 9x9) where the last byte on each row of the array is discarded.
#define PUZZLE_X 5
#define PUZZLE_Y 5
void initBoard(uint8_t puzzleNumber) {
uint8_t x = 0;
uint8_t y = 0;
uint8_t byteRead = 0;
for (uint8_t i = (puzzleNumber * 15); i < (puzzleNumber + 1) * 15; i++) {
byteRead = puzzles_5x5[i];
// Load up the left hand value ..
board[y][x] = 0;
if (leftValue(byteRead) > 0) {
board[y][x] = 0xF0 | leftValue(byteRead);
}
x++;
// Are we still in the confines of the board?
if (x <= PUZZLE_X) {
board[y][x] = 0;
if (rightValue(byteRead) > 0) {
board[y][x] = 0xF0 | rightValue(byteRead);
}
}
x++;
if (x >= PUZZLE_X) { y++; x = 0; }
}
}
I have purposely neglected to point out the little bit of code that logically ORs the retrieved value with the hexadecimal constant 0xF0. Take it for granted that there is a cunning plan for this later and that it will be revealed when we start actually laying pipe.