Gorilla Warfare - Map datastructures and their memory footprint
For Gorilla Warfare, we had to come up with a convenient way of storing the map. The map has a few requirements:
- It has to have a small memory footprint. Although Android phones nowadays have a lot of memory, Android still limits the amount of memory used per application. The lower bound for this maximum is 16MB, and still a common setting on a lot of phones.
- It has to be fast: during gameplay, the map constantly changes. These changes have to be processed in realtime.
The first and most simple idea we came up with was a two-dimensional bit array. The array is generated at a certain resolution (most ideally equal to the resolution of the entire drawn bitmap when fully zoomed in), every bit represents a small piece of the map. When the bit is set to 1, this piece is land, when the bit is set to 0, it is empty.
This looked reasonable, but after some thinking we realised this would consume quite some memory. Why? Consider a modern average Android phone, e.g. the HTC Desire. It has a resolution of 800×480 in landscape mode, a very common resolution at the moment of writing. In our game, we want our players to be able to zoom and pan, so lets say the phone display covers 1/4th of the map when fully zoomed in. This would come down to a bitmap resolution of 1600×960. The number of cells can be calculated by multiplying the width and height of the map, and a boolean is a fancy name for a single bit, so this formula should give us the memory footprint of the bitmap:
nbytes = width * height / 8.
Which in our case gives:
1600 * 960 / 8 = 192000 B ≈ 0,18 MB.
That’s not too bad! But hold on a second. How does java store booleans? Well, from the java documentation we learn that “This data type represents one bit of information, but its “size” isn’t something that’s precisely defined.”. Basically, what they mean is: it depends on your VM. In most VMs it comes down to 1 byte, and from some experiments we suspect the same to be happening in Dalvik. So, let’s take the “/ 8” part out and calculate again.
1600 * 960 = 1536000 B ≈ 1,46 MB.
Taking into account that the maximum memory footprint of our application is 16MB, this is almost 10% of our memory, quite a lot if you also want to store high-quality graphics and sound.
The next property our map implementation needed to have is good performance. Imagine a projectile strikes into a piece of land. The map then needs to update itself and create a crater with a certain size on the map. This means that from the center of impact, all cells in a certain radius have to be set to zero. Since we have a simple bitmap, the number of cells that have to be set is approximately equal to the area of the circle. It is not exactly equal since some rounding will occur: we do not have half cells. For those of you who don’t remember their geometrics classes anymore, here is the formula:
noperations ≈ π * (r^2).
So, a crater with a radius of 100 units results in approximately 31400 memory operations.
Although that is still doable, we thought we could come up with a better alternative. So we created the vector map. The vector map is an array of lists of vectors. The lists of vectors represent one column/row of the map.
Let’s look at the memory footprint of a vector map. It can be defined as
nbytes = width * vAverage * 2 * 8
Of course, switching the dimensions is also possible. vAverage represents the average number of vectors per row/column. The vector map consumes the most space when a map is very partitioned, since vAverage is very high in such a case. To calculate a comparable footprint to our bitmap scenario, let’s take a very high average value, let’s say that vAverage = 20. Note that in most cases, vAverage will be below 10. Anyhow, let’s calculate the footprint:
1600 * 20 * 2 * 8 = 512000 B ≈ 0,49 MB
If we want to, we can still halve this footprint by using short integers instead of integers, limiting our map to a size of 65536 in both directions. It is pretty clear that this is a huge improvement on the regular bitmap.
The other issue we were looking in to was performance. To create a crater in the vector map, vectors have to be removed, edited or added. This might sound like more work than in the bitmap, but it isn’t. For every row/column in the map, the maximum number of vectors that can be populating the area to be destroyed is half of the cells that will be modified in the bitmap. We conclude this from the fact that vectors need at least one “cell” in between themselves to be separate vectors. Therefore, in a worst case scenario,
noperations ≈ (π * (r^2)) / 2.
In most cases however, a crater will affect less than 5 vectors. The number of operations will then be something like this
noperations = 2 * r * vAverage
With vAverage being the average number of vectors per row/column in the crater. Thus, with crater radius 100 and a high vector average of 10, we get:
2 * 100 * 10 = 2000
Which still is way less than the 31400 operations we calculated for the bitmap.
All in all, we are pretty content with our vector map. We will try to do some performance tests in the upcoming weeks. If we do, you will find the results on this blog.
