Bit Packing

This is part of a series on how this game was implemented technically, as part of the Game Jam it was developed for. It is recommended to read them roughly in-order as later blog entries may refer to earlier ones.

Technical:

1. State Machine
2. Pathfinding/Movement
3. Isometric Rendering
4. API
5. Control Sources
6. AI
7. Networking
8. Fog of War
9. Bit Packing
10. Palette Shifting

Other:

• Portraits
• Scrapped Ideas

----

Bit Packing

A core part of the game involves manipulating 2d coordinates on a grid: x,y

As an optimisation, this is not stored as a 2d object:

 {x:3,y:4}

Instead it's stored as a single int, with 2 the 2 coordinates stored in the bytes:

XXXXXXXYYYYYYYY //16 bit value

To convert a coordinate like x:3,y:4

3 in binary: 110000
4 in binary: 010000

append the two into a single variable gives:

110000010000

When when converted back to decimal would be: 772

------

Why do this, instead of just using objects? There's 2 main reasons

1) it's much easier to do comparisons between positions if dealing with a single value.

 if(ch.position.x == mouse.position.x && ch.position.y == mouse.position.y){
    //do something 
}

vs

 if(ch.position_xy == mouse.position_xy){
    //do something 
 }

this is especially true when juggling a lot of checks. 

2) since the values are an int, you can copy it without needing to clone a javascript object

 ch.position = mouse.position;
    //some time later
mouse.position.x = 12;//moves the character too!

vs

ch.position_xy = mouse.position_xy;
    ///some time later
mouse.postion_xy = 12;//won't affect the character

This is especially important for networking, since there's a lot of copying and assigning variables. 

----

Of course, this approach comes with drawbacks. To assign or read the positions, you need a wrapper function

ch.position_xy = Bit.SET_XY(x,y);
const [x,y] = Bit.GET_XY(ch.position_xy);

Additionally, since the x&y values are stored in bytes, they can only be the values 0-255. This limits the maximum map size, but is decent considering such a large map would be too big to play on anyway.

----

An alternative approach is to use a 1D index instead of a 2d index.For example, consider the grid

 XXX
 XXX
 XXX

this could be represented as a 1D array:

012
345
678

then, for example, you can access position 1,1 by converting using the formula:

 (x * width) + y = 4

This is the traditional approach for converting between 1D and 2D coordinates and is used in some parts of the engine. But the problem with this approach is that you need to know the width of the map when converting from the 1D value to the 2D value. This means the width of the map would need to be scattered throughout the code, which can be messy. 

The byte-based approach has no dependencies, so it can be included anywhere in the codebase without need to pass extra information about the map with it.