1 About this module

• Prerequisites:
• Objectives: This module discusses a storage efficient method to store a maze map.

2 The problem

Although there are many methods to represent wall partitions in a maze, most popular methods involve memory-wasteful data structures. When a microcontroller unit only has thousands of bytes of RAM, a program cannot afford to waste memory resources.

3 The representation

The representation uses one bit per configurable partition. This means we do not waste any resources to represent the perimeter of a maze. For the rest of our discussion, we assume there are 16 rows and 16 columns of cells.

Given this configuration, there are 15 columns of vertical walls (aligned in a north-south orientation). Each column of walls has 16 partitions. Likewise, there are 15 rows of east-west (horizontal) walls. Each row has 16 partitions. This means there are $15\cdot 16\cdot 2=480$ configurable partitions. Because the existence of each partition is independent of that of the others, we need 480 individual bits to represent all the partitions.

In C++, there is a bool type. Unfortunately, each bool object takes one byte. Each partition should require only one bit. We need to pack the representation of 8 partitions in one byte. This means that we only need a total of 60 bytes to represent all the partitions.

4 Partition serialization

It is best to separate the partitions into two groups, the north-south (vertical) and the east-west (horizontal). Within each group, we need to serialize the partitions.

For the north-south partitions, let us serialize as follows. The eastmost column, from south to north, are numbered 0 to 15, then the second eastmost column, from south to north, are numbered 16 to 31, and etc.

For the east-west partitions, let us serialize in a similar fashion. The southmost row, from east to west, are numbered 0 to 15, then the second southmost row, from east to west, are numbered 16 to 31, and etc.

Using this representation, we have two arrays of bytes, as follows:

We also need to come up with a standard to name cells. Let $\left(c,r\right)$ represent the coordinate of a cell. $c$ is the column number, with the eastmost column being 0. $r$ is the row number, with the southmost row being 0.

5 Primary Interface

Now, let us define the basic interface to use the map.

5.1 Map changing

We define the following interface:

This subroutine adds or removes a partition to the south of the cell at the intersection of column c and row r.

The implementation is as follows:

Of course, this implementation is not exactly efficient, as the temporary variables byteIndex and bitMask are not exactly necessary. However, a good compiler should optimize the temporary variables out.

You can follow this template and implement the other three subroutines:

• Wall_setNorth
• Wall_setEast
• Wall_setWest

5.2 Map reading

Just as we have subroutines to change a map, we also have subroutines to read a map. Here is an example:

You can follow this template and implement the other three subroutines:

• Wall_getNorth
• Wall_getEast
• Wall_getWest

6 Orientation independent approach