Thinking in Grids

A grid is an extremely useful way to organize space. Post office boxes, closet organizers, spreadsheets, city blocks, and data tables all take advantage of grids. Games take clear advantage of grids as well - from platformers like Super Mario Bros. where the world is created from repeating tiles to Wolfenstein 3D, which used a grid-based layout to organize floor plans.

## Arrays

We have inherent grids in computer science as well, in two-dimensional arrays. Consider the following 5x3 array:

0 1 2 3 4
0 A B C D E
1 F G H I J
2 K L M N O

We tend to write out such arrays as grids as well. But that is not how we actually store them in the computer's memory. In memory, a 2-dimensional array is actually stored as a 1-dimensional array, i.e.:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
A B C D E F G H I J K L M N O

When we access 2d arrays, our 2d accessor, i.e. `array[1,2]`, is converted into an offset (i.e. an index) in this array. Consider how we would locate the cell in the 2d table above. We'd look at the second column and third row (the cell containing L). But if we are looking in the linear array, what do these correspond to?

We need an index from the start of the array. To reach the third row, we have to move across ten cells - twice the width of the table. We then have to move one more cell. So 2 rows and 1 column - the y and x coordinates we are accessing. This suggests a formula for converting our 2d coordinates into a 1d coordinate:

``````var index = y * width + x;
``````

Now what about going the other direction? Say we have an index and want to convert it into an x- and y-coordinate? Consider the relationship we saw between our width, x, and y in the formula above.

Multiplying the width by the y coordinate tells us how far into our 1-d array we need to move to reach the appropriate row. Then we have the x value to tell us how far to move into the next row - a partial distance that is not as big as a row... in other words, we want to remove all the whole rows, and see what remains. The remainder, which we can get with the modulo operator:

``````var x = index % width;
``````

If the remainder is our x coordinate, what about the whole portion? That would be the number of rows we need to move down. We can get this with integer division, which gives us the whole number and drops the fractional part, i.e.

``````var y = Math.floor(index / width);
``````

Because JavaScript doesn't have a distinct integer division operator, we need to wrap our division in a `Math.floor()` or `parseInt()` to convert the resulting float into an integer. Note: `Math.floor()` is not equivalent to integer division when dealing with negative numbers (which doesn't affect us when talking about array indices).

With these three formulas, then, we can move between 1-d and 2-d array representations easily.

One final note concerning JavaScript, it doesn't support 2d array notation - at least the kind we know from C# and similar languages. Instead, JavaScript uses jagged arrays, which are actually arrays of arrays. The secondary arrays don't have to be all the same size (hence the term jagged).

### 1d and 2d Arrays in Practice

So why is this important to us? One obvious reason is that JavaScript does not implement multi-dimensional arrays. Instead, JavaScript uses jagged arrays, which are actually arrays of arrays. The secondary arrays don't have to be all the same size (hence the term jagged). In fact, to set up a jagged array, we actually have to initialize each of the secondary arrays, i.e.:

``````var width = 10;
var height = 5;
var array = new Array(width);
for(i = 0; i < width; i++) {
array[i] = new Array(height);
}
``````

You may find it much easier to create a 1-d array instead:

``````var array = new Array(width * height);
``````

Shifting to other language implementations, understanding that a 2d array is stored in memory is also key to iterating effectively. Most of us would naturally gravitate to iterating through a 2d array like this:

``````for(int x = 0; x < width; x++) {
for(int y = 0; y < height; y++) {
doSomething(arr[x,y]);
}
}
``````

This certainly works, but it means that for each iteration through the inner loop, the next element in our array we access is width x the size of our array element bits away in memory. If you think back to when you learned about computer architecture, when accessing a specific memory address, a chunk as wide as our cache is loaded into the cache from RAM, and if the next address we access is cached, we can access it from there and not need to retrieve from RAM again right away.

Making such large leaps (especially if our array is large or our array elements are complex structures) means we'll have a number of cache misses - times we have to go to memory to load more data. If we instead swap our inner and outer loops, i.e.:

``````for(int y = 0; y < height; y++) {
for(int x = 0; x < width; x++) {
doSomething(arr[x,y]);
}
}
``````

We now will move smoothly from one element the next in memory - no jumping around, minimizing our cache misses. The benefits of this approach are so easy to obtain and can improve performance so much that you should always write nested loops for iterating though a 2d array this way.

## Arrays as Spatial Data structures

In games, arrays can serve an important role not ony in holding different data structures, but also as a way of modeling our game world. Consider the classic lightbikes game featured in the movie TRON. In it, we have multiple bikes driving around a 2D field, leaving a solid wall behind them. In building such a game, we need to both be able to render the bike and light trails, but also detect collisions between bikes and walls. In other words, we need a model of where the walls are in the world.

One simple technique that works well is to represent the world as a boolean array, i.e.:

``````var width = 760;
var height = 380;
var world = new Array(width * height);
for(var i = 0; i < world.length; i++) {
world[i] = false;
}
var bikes = [
{x: 20, y: 190},
{y: 740, y: 190}
]
``````

We can think of this array as a 2d grid, with bikes filling an entire grid cell, and moving one cell at a time. Moving is therefore a change in coordinates by 1 in an upward, downward, left, or right direction:

``````  // Move player one
switch(bikes[0].direction) {
case "up":
bikes[0].y--;
break;
case "down":
bikes[0].y++;
break;
case "left":
bikes[0].x--;
break;
case "right":
bikes[0].x++;
break;
}
// Move player two
switch(bikes[0].direction) {
case "up":
bikes[0].y--;
break;
case "down":
bikes[0].y++;
break;
case "left":
bikes[0].x--;
break;
case "right":
bikes[0].x++;
break;
}
}
``````

Collisions with such a model are trivial to test for, simply involving checking if our new position is occupied by a wall or another bike:

``````if(bikes[0].y * width + bikes[0].x) {
// Player 1 collided with a wall
}
if(bikes[1].y * width + bikes[1].x) {
// Player 1 collided with a wall
}
if(bikes[0].y == bikes[1].y && bikes[0].x == bikes[1].x) {
// The two players collided
}
``````

There is only one comparison between each bike and the world, and one between each bike. In other words, constant complexity per bike, or linear in terms of number of bikes O(bikes). This is clearly far more efficient than any scheme checking each wall segment individually against a bike's position.

We also need to write our new position to the world (which we do after checking for collisions, or our bike will collide with the trail it is now laying down):

``````world[bikes[0].y * width + bikes[0].x] = bikes[0].color;
world[bikes[1].y * width + bikes[1].x] = bikes[1].color;
``````

We could save a value of true to mark the trail, but using a color will work just as well in our tests (as any value not `false`,`undefined`, `null`, or `0`) will be evaluated as true). Moreover, if we save the color, we can render the world with colored trails corresponding to the bike.

Rendering the world can therefore be as simple as converting each cell to a pixel lit on our screen. But this leaves us with very small bikes, and very small trails. Instead, we can expand each cell by applying a scaling transformation to the model's coordinates. In this case, let's scale linearlly by 5 times, i.e. each cell will be five pixels on a side.

``````for(var y = 0; y < height; y++) {
for(var x = 0; x < width; x++) {
var color = world[y * width + x];
if(color) {
ctx.fillRect(x * 5, y * 5, 5, 5);
}
}
}
``````

### Optimizations

In JavaScript, Array objects are not traditional linear arrays, rather they are a kind of hybrid linked data structure. As such, their contents will not necessarily be located near one another in memory. This means that as we iterate over a JavaScript array, we will likely see many cache misses.

However, JavaScript does have a linear memory array in its typed array. These are initialized with a size and data type (signed or unsigned integers or floats with a specific size). A downside of the typed array is that it only supports a limited number of primitive data types - we cannot create one holding a user-defined structure (at least, not without some complex logic). But in this case, when we simply want to store a color value, which we typically represent with 24 bits (8 for the red channel, 8 for the blue channel, 8 for the green channel, and 8 for the alpha channel). We could convert this value into a 32-bit unsigned integer for storage, and convert it back into a color for rendering...

But consider that we probably won't have very many bike objects. Instead of storing the color, we could store an index standing in for the color - we'd only need as many indices as we have bikes. The smallest typed array we can sore is 8 bits, which can represent numbers from 0 to 255 - more than we would likely need for our bikes.

Creating the world array is even more straightforward than before, as we don't need to initialize it.

``````var world = new Uint8Array(width * height);
``````

To update the array, we simply store the bike's index. We can then render using that index:

``````for(var y = 0; y < height; y++) {
for(var x = 0; x < width; x++) {
var index = bikes[height * width + x];
var color = world[index];
if(color) {
ctx.fillRect(x * 5, y * 5, 5, 5);
}
}
}
``````

At the cost of some flexibility, we could further reduce the cost of this function by replacing our color look-up with a switch statement and hard-coded color values.