If you have a project you’re working on which has memory constraints, you’ll probably consider data compression to some degree or another at some point in development. Memory constraints are usually due to limitations of hardware on your target system/architecture; for reasons, you’re probably looking at anything from cache sizes, to stack memory, or physical memory.

With my rover project, my constraint was stack memory. Developing a recursive algorithm you can easily run out of space, so it becomes almost a base requirement to compress your data. I could have fulfilled the concrete requirement of a functional recursive pathfinding algorithm without compressing my map data, but I didn’t know that with 100% certainty when I began designing. Furthermore, I just like compressing data plain and simple; not with dictionary compressions or however it is archive compressions work, but rather with bit twiddling. Yea, I have a special place in my heart for bit twiddling.

If you’re reading this I will just go ahead and assume you know what bit twiddling is, so I won’t bother with an introductory explanation.

In C++ bit twiddling usually means using a lot of bit operators. At the bare minimum you need the bit shift operators, ya you could hard code things. I am partial to using bit masks however.

For the Rover project I had requirements for my map size.

Width: 1024
Height: 1024
Tileset: At least 3 Tiles

---

1024 x 1024 = 1,048,576 (Tiles)
If you use 32bit integers to save each tile..
\[(32\frac{bits}{int}) \div (8\frac{bits}{Byte}) = 4 \frac{Bytes}{int}\]
1,048,576 x 4 Bytes = 4MiB

Four megabytes is a lot for just a tile map with 3 types of tiles. Even if I hadn’t been working on recursion, I’d need a compelling reason to leave that alone; a reason like time constraints on the project. Of course I could have cut that huge 4 down to 1 by using char variables, but CPUs don’t like chars. If I am gonna send 32 or 64 bits to the cpu, I might as well explicitly send that amount.

So enough talk, eh? Here’s how I did it. =)
Leave questions in the comments, if you got ’em.

#ifndef TILE_H
#define TILE_H

#include "sprite.h"
#include <mutex>

using uint32 = unsigned __int32;
#define regionWidth 4
#define regionHeight 4

class Region_Tile
{
private:
	uint32* Region;
	uint32 bitmask;
	__int8 bit_position;

public:
	Region_Tile( uint32* Region, __int8 index )
	{
		this->Region = Region;
		bit_position = index * 2;
		bitmask = 3 << bit_position;
	}
	//First two bits of assigned value are kept
	Region_Tile& operator=( __int8 tile_value )
	{
		*Region &= ~bitmask;
		*Region |= ( 3 & tile_value ) << bit_position;
		return *this;
	}
	__int8 Get_Tile_Value()
	{
		return ( ( *Region & bitmask ) >> bit_position );
	}
	bool canMove()
	{
		bitmask = 1 << ( bit_position + 1 );
		return bitmask & *Region;
	}
	bool haveBeenTo()
	{
		if ( Get_Tile_Value() == 3 )
		{
			return true;
		}
		return false;
	}
};

class Region
{
private:
	uint32 region_tiles = 2861864066; //Traversable NON-blank tile pattern =)

public:
	// Get_Tile() merely translates x,y to i (coordinates -> index)
	Region_Tile Get_Tile( ushort x, ushort y );
	uint32& Region_Tiles()
	{
		return region_tiles;
	}
};