The problem
Egg Savior currently has 30 levels. Each one of these levels include a generic background and a lot of bricks that act as platforms for the main character (the chicken). The bricks are all 64x64 pixels in size, and placed in a grid. The obvious yet inefficient way of rendering and interacting with bricks is to handle all of them one by one:for brick in brick_list: brick.render() character.detect_collision(brick)
This code is inefficient for two reasons:
- Renders the same bricks in the same way all the time, one by one.
- Forces to detect collisions with every single brick, even if they are stuck together creating a larget platform
Different backgrounds
The first version of Egg Savior had only 10 levels, and the approach was to have a different background image for each level, with the bricks already included into it. It worked really well, but as more levels were added, it proved not very scalable, because each new level added a lot of data to the APK. This approach meant brick objects to be just invisible rectangles, without render code, because they were already drawn into the background. This enabled a way to optimize also point 2, because there were no reason for defining each brick individually. If three bricks were stuck together in a row, they were defined as a single larger brick, thus enabling less time to process collisions.Run-time baking
The second iteration of the design, focused on solving the scalability problem with an algorithm that allowed baking the bricks above the background when loading a level. This also involved a way to easily define where to place the bricks. The solution was to use strings with spaces on empty cells and hashes on brick cells:String levelPattern[] = {
" ",
" ",
"# # ",
"## # # ",
" ## # # ",
"## ## # # #",
};With this language to define brick positions, we already know where to place the bricks on the background. Anyway, there is still a problem to solve: brick shape change depending on its neighbours. If a brick is the first or the last in a row, it has round corners, in other case, it has sharp corners in order to blend with the next or previous one. This leaves us with four cases to handle, depending on the previous, current, and next brick (the current brick is in the middle):
- [_#_]: The brick doesn't have neighbours.
- [##_]: The brick has only a neighbour on the left.
- [_##]: The brick has only a neighbour on the right.
- [###]: The brick has neighbours on both sides.
Four brick shapes with enhanced contrast.
The algorithm to generate the background with the tiles is as follows (I removed some obvious code to compute drawBitmap rectangles to enhance algorithm readability):
public static Bitmap bake(String[] rows, Bitmap baseBackground) {
int nRows = rows.length;
int nCols = rows[0].length();
Bitmap newBitmap = Bitmap.createBitmap(nCols * TILE_SIDE, nRows * TILE_SIDE, Bitmap.Config.ARGB_8888);
Canvas canvas = new Canvas(newBitmap);
canvas.drawBitmap(baseBackground, null, ..., null);
for (int row = 0; row < nRows; row++) {
for (int col = 0; col < nCols; col++) {
char left = '#';
char right = '#';
if (col > 0) {
left = rows[row].charAt(col-1);
}
if (col < nCols - 1) {
right = rows[row].charAt(col+1);
}
char c = rows[row].charAt(col);
Bitmap toRender = getTile(left, c, right);
if (toRender != null)
{
canvas.drawBitmap(toRender, null, ..., null);
}
}
}
return newBitmap;
} The getTile method just handles the four cases mentioned earlier, and returns the right bitmap from the app resources.
Automatic collision optimization
The baking of the bricks into the background solved the render part of the original problem (point 1). The bricks, which now consisted only in invisible rectangles, were defined by hand, looking at the hashes and chosing a smart way of arranging them in a minimum set of rectangles. This is a highly boring work that discouraged me to add more levels, and the perfect candidate for automatization.Finding the minimum set of rectangles that covers all the bricks is not an easy task, because there usually exists more than one way of covering all the bricks with rectangles. Sometimes the best way involves using overlapping rectangles. Even though finding the optimal solution was an interesting challenge, I realized that including complex (and maybe slow) code to reach perfection was not worth in this case. Having 10% more rectangles than the optimal solution didn't impacted the performance in a visible way. I decided to go with a simple algorithm that provided a good enough solution.
Original bricks
The basic idea of the algorithm is to process each row independently, looking for contiguous blocks which define single rectangles, and then try to mix rectangles from consecutive rows if possible. As I said, this doesn't find the optimal solution, it is just a greedy algorighm that provides a good enough one.
 |  |
| Column joins | Row Joins |
This is the pseudo-code:
previousRow = new Set[Rectangle]
currentRow = new Set[Rectangle]
rectangles = new List[Rectangle]
for row in rows:
currentRectangle = None
currentRow.clear()
for char in row:
if char == '#':
if currentRectangle == None:
currentRectangle = new Rectangle(colNum, rowNum)
else:
currentRectangle.grow()
if (char == ' ' or isRowEnd)
and currentRectangle != None:
if canMix(previousRow, currentRectangle):
mix(previousRow, currentRectangle)
else:
rectangles.add(currentRectangle)
currentRow.put(currentRectangle)
previousRow = currentRow
return rectangles
The algorithm already tries to mix rectangles with the previous row ones while they are generated, and does a pretty good job joining lots of bricks into big rectangles. Another optimization that I did to the algorithm is to encode the previousRow as an array with the same width as one row, where each position of the array has a pointer to the rectangle that covers this cell or to null if it is empty. This way, finding the right rectangle to mix with in the previous row runs in constant time. Actually, my implementation doesn't need a currentRow structure, I overwrite the previousRow one after reading it...
I will not go into the actual implementation to avoid making this article infinite, but if anyone has some doubt on how to implement it, feel free to leave a comment and ask.
