Software
Program Details
Rather than describing every line of the program, this section will focus on the more difficult parts to implement. Readers interested in understanding the other sections can refer to the commented source code in the Appendix section.
The Task refers to the effect we wished to implement. Motivation explains the reason for wanting that effect. The Function(s) refers to the functions that used the algorithm we implemented. Description describes the algorithm conceptually, with specific details where relevant. Notes offers miscellaneous information, if relevant.
___________________________________________
Sprite Motion
Task:
Pixel-by-pixel movement in the x-direction for the Digger and Nobbins, without having to redraw the Digger/Nobbins pixel-by-pixel each time
Motivation:
Firstly, the Digger/Nobbin has to be able to move pixel-by-pixel because the movement would seem choppy otherwise (e.g. if we had made the movement occur byte-by-byte). Secondly, we felt that this algorithm would make our code faster since it required far less memory accesses to the screen array than redrawing the Digger pixel-by-pixel would. Lastly, we didn’t want to suffer through the coding of the brute-force approach of redrawing it that way.
Function(s):
initDigger/Nobbin/Left/Right, moveDigger/Nobbin/Left/Right, placeDigger/NobbinHoriz
Description:
To describe this algorithm conceptually, we take the specific case of the Digger moving right. There are three main steps to this algorithm:
Function: moveDigger/Nobbin/Left/Right
Placing the Digger correctly within the grid
Firstly, the Digger’s horizontal bitmap is placed in int array of size 6. This array can be thought of as a 16 bit x 6 row grid, with the tail end of the Digger placed to the left most position, and its mouth facing right. Then, based on the modulus 16 value of the x-coordinate of the Digger, the Digger is shifted the appropriate number of bits to the right.
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
One row of the 16-bit x 6 row grid
To determine the appropriate number of bits, the modulus 16 value of the absolute x-coordinate of the Digger’s mouth is taken. A result of 6 to 13 corresponds to a bit location of 6 to 13 within the temporary array. A result of 14 to 15 corresponds to a bit location of 6 to 7 in the temporary array. Finally, a result of 0 to 5 corresponds to a location of 8 to 13 in the temporary array. The shift is then made from bit location 5 to whichever bit location results from the mapping above.
The reason for this seemingly odd mapping is that placing the Digger’s mouth at bit location 6 in the temporary array is graphically equivalent to placing its mouth at bit location 14. Therefore, by mapping the result of the modulus 16 value to the bit location within the temporary array this way, we can use this temporary array for any pixel location on-screen.
Filling the remaining space with the appropriate land mask
The remaining bits in this grid have to be filled with a “land mask”. A land mask is simply a bit pattern that preserves the existing bit values in the screen array later on. This land mask is obtained by shifting the 0xff pattern of bits the appropriate number of positions right, shifting another 0xff pattern the appropriate bits to the left, and OR-ing them together. Finally, the final combined land mask must be OR-ed into the grid.
This land mask is important because the landscape in this land is not a simple black landscape. It is a pattern of bits that represents land that can be dug out by the Digger (but not by the Nobbin). Hence, as the Nobbins and Digger move throughout the landscape, un-dug land must maintain their pattern, and dug out land must remain black. Also, the land mask is used to erase the last vertical slice of bits behind the moving Digger/Nobbin (otherwise, their horizontal lengths would grow indefinitely).
Functions: placeDigger/NobbinHoriz
Placing the Digger/Nobbins at the appropriate byte location in the screen array
The last step in this algorithm is to place the 16 bit x 6 row grid (essentially 6 ints) into the screen array at the proper byte location. Referring back to the mapping scheme above, note that a modulus 16 result of 14, 15, 0 … 5 implies that the tail end of the Digger has now moved to the next byte in the screen array. Therefore, when placing to the screen array, we must be sure to reference the correct 2 bytes, based on the tail end of the Digger. This is done based on the mapping scheme.
Notes:
No such algorithm was required for vertical pixel-by-pixel movement. This is because vertical movement can be very easily achieved by offsetting the index into the screen array by 16.
___________________________________________
Digger Control
Task:
Orienting the Digger correctly after turns, especially from horizontal to vertical positions
Motivation:
The Digger has wheels on the bottom of its carriage. Hence, if the Digger were previously going left and then went up, we would expect the wheels of the Digger to be touching the left wall of the column. On the other hand, the wheels of the Digger would be on the right wall of the column if it had approached from the right (imagine a car driving up the wall after having approached it from the left, versus driving up a wall after having approached it from the right). The same concept applies when going from a horizontal direction to a downwards direction. Lastly, when the Digger reverses its vertical direction (e.g. up to down), we would want the wheels to remain on the same side.
Function(s):
checkDiggerDir
Description:
To achieve this effect, we declared 6 direction constants for the Digger, instead of just four (up, down, left, right). Instead of an up constant, the digger now has upleft (meaning wheels on the left wall of the column) and upright. The other two are downleft and downright.
We also declared a prevDiggerDir variable (previous direction of Digger) and ctrlDiggerDir variable (next intended direction). By matching the appropriate previous direction to the intended direction, we were able to achieve this effect reasonably easily. For example, if the previous direction was left, and the player pressed the ‘up’ button, prevDiggerDir would be left and ctrlDiggerDir would be set to upleft.
Notes:
The Nobbin did not require the use of this algorithm, since its legs are always oriented downwards, as based on the original game.
___________________________________________
Nobbin Control
Task:
Land checking for the Nobbins to prevent it from moving to land-filled locations, without using flags of any sort – while allowing it to still catch the Digger
Motivation:
As mentioned before in the discussion about land masks, and less explicitly in the summary, only the Digger can dig its way through existing land or dirt. The Nobbins have no such ability. Therefore, the Nobbins must be made stationary if the player or the AI attempts to move them to some land-filled location.
We did not want to use flags to determine whether or not the location was land-filled for one major reason. It would consume far too much SRAM memory to assign a flag to each pixel on the screen. Also, since the Digger and Nobbins can move pixel-by-pixel horizontally and vertically, there was no way to assign flags to groups of pixels.
Although the Nobbin was to be made stationary if it were to move to a land-filled location, it must still be allowed to move to the Digger. Otherwise, it would never be able to catch the Digger.
Function(s):
checkNobbinDir, checkAINobbinDir
Description:
The coordinates of the Nobbin refer to different parts of the Nobbin, depending on which direction the Nobbin is moving in. If the Nobbin is headed left or up, the coordinates refer to the upper-left most pixel of the Nobbin. If the Nobbin is headed down, the coordinates refer to the lower-left most pixel. Lastly, if the Nobbin is headed right, they refer to the upper-right most pixel.
Therefore, based on the previous direction of the Nobbin, different offsets would be added to the coordinates of the Nobbin to determine if the next pixels it wishes to occupy are land-filled or not. To check this, we used the video_set function written by Professor Land. Note that the coordinates here refer to the coordinates of the current location of the Nobbin, not the location the Nobbin intends to move to. The reason is that the Nobbin cannot be allowed to move there (and hence the coordinate variables cannot be updated) until that location has been proven to be free of any land.
To ensure that the Nobbin only stopped upon detecting land (and not the Digger), we checked two pixels side-by-side. If one pixel was black, and the other white, then land was detected. Unfortunately, the wheels of the Digger also follow this pattern. Therefore, when approaching some location from below, the Nobbin must check for 6 adjacent bits.
___________________________________________
Nobbin-Digger Clash
Task:
Detecting a clash between Nobbins and a Digger in 16 possible ways
Motivation:
A clash between the Nobbins and the Digger must be detected because that is an end game condition. The clash detection must work for each of the 16 ways in which the Nobbins and Digger could possibly clash, because otherwise, game play would be significantly affected. Also, the clash detection can only give a positive result if the Digger and Nobbin are no greater than some reasonable distance of each other (1 pixel). Otherwise, the Nobbin would be able to catch the Digger from too far away. These requirements complicate the code sufficiently.
Function(s):
computeDigger/NobbinCoord, checkClash
Description:
The algorithm is described for a single Digger and Nobbin. Clashes are checked in turn.
There are 16 ways in which a Nobbin and a Digger could clash. Either one of the Digger’s four corners could be touched by the Nobbin, a “corner” contact. Either one of the Digger’s four sides could be ‘face on’ with one of the Nobbin’s sides, called an “aligned” contact. Lastly, there are eight ways in which an “unaligned” contact could occur (e.g. half the length of a Nobbin’s side touches half the length of the Digger’s side).
To identify all 16 possible clashes, we used four local variables (xDiggerLeft/Right, yDiggerLeft/Right) to define the four corners of the Digger and another four for the corners of the Nobbin. When comparing the x (or y) coordinates of the Digger and Nobbin, this gives four possible combinations, although some of these combinations are mutually exclusive. If a x (or y) combination matches within a margin of 1 pixel, then a x-counter (or y-counter) is incremented.
Thus, to positively identify a corner contact, the sum of the x-counter and y-counter after all checks are completed must be at least 2. To positively identify an aligned contact, the sum must be at least 3.
The margin of detection had to be chosen to be 1 pixel, otherwise, a corner contact would look too odd, because the Nobbin and Digger would be too far away from one another. Therefore, the algorithm described up till this point would not work for an unaligned contact (the corners of the Digger and Nobbin are a distance of 2 pixels apart when an unaligned contact occurs).
Therefore, unaligned contacts are detected by checking to see if the corner of the Nobbin is within two corners of the Digger and vice versa. This constitutes another 8 possible combinations, implemented through a series of if and nested if statements.
Notes:
One could probably think of other algorithms that would have been simpler to implement.
An example would be to simply identify the center of the Nobbin and Digger and check if they are within some margin of each other. Unfortunately, due to the dimensions of the Nobbin and Digger, there is no true center to them. Hence, this algorithm would either result in the detection margin being too great (catching from too far away), or the Nobbin and Digger overlapping before detection occurs. This is the case since clashes from different directions would require different detection margins, which would require algorithms that are equally complex and less intuitive to implement.
Another algorithm would be to use variables to save the centers of each side of the Digger and Nobbin. However, this would consume even more SRAM. At the time of writing this code, we had approximately 70 bytes of SRAM left, and we were unsure of how much more we would need for other functions. Hence, we felt it best to save memory where possible.
Lastly, to save SRAM, we could have recomputed variable values every where there are used. But this would slow down the code, and we had to be mindful of speed, since we were executing the code in between frames.
___________________________________________
Nobbin-Nobbin Clash
Task:
Detecting a clash between Nobbins in 16 possible ways.
Motivation:
It is necessary to detect a clash between Nobbins because they should not be able to pass each other. In the event that their next positions (as selected by the AI or player) should cause them to clash, they should not be allowed to move there. While there are still 16 possible ways in which a clash could happen, the code for this was much shorter and simpler, because it did not matter if the clash was detected from a greater distance than 1 pixel.
Function(s):
checkNobbinClash
Description:
This algorithm uses the centers of the Nobbins for checking. Using the centers, it determines if the two Nobbins are x-aligned or y-aligned within 2-3 pixels. Note that alignment does not necessarily mean that they are close to each other. Alignment simply means that two sides are “facing” each other.
Then, using the coordinates of the centers, the Nobbins are checked to see if one Nobbin is to the left, right, top or bottom of another reference Nobbin within 2-3 pixels. Note that this does not necessarily imply that they are close to each other. This simply means that they are close to each other in one direction (y or x).
Finally, the combination of these 2 conditions implies that the Nobbins are close enough for it to be considered a clash.
___________________________________________
Bonus Emerald
Task:
Every 5 seconds, a randomly selected, specially marked emerald grants a temporary speed boost when consumed by the Digger (i.e. only one emerald is marked at a time)
Motivation:
We wanted to add a feature to the game that we felt would make it more interesting.
Function(s):
selectEmerald
Description:
Every 5 seconds, a randomly selected uneaten emerald is marked with 4 dots using function video_pt by Professor Land. If the time that the game has been running is 5 seconds or greater (i.e. at least one emerald has been marked already), the previously marked emerald is unmarked first. The emerald is randomly selected by using the rand function to randomly generate an index into a switch statement. If the chosen emerald is still uneaten, it is marked and the function exits. If it has been eaten, the loop repeats until an uneaten emerald is found or 5 iterations have been made, whichever comes first.
In the In-Game loop, the presence of the specially selected emerald is checked. If the Digger ate it while it was still marked, the Digger is granted a temporary speed boost.
__________________________________________
Artificial Intelligence
Task:
Computer controlled (or AI) Nobbins that would be intelligent enough to give a human player a reasonable challenge.
Motivation:
We wanted to add another level of complexity to our project. We also felt that a reasonably intelligent AI Nobbin would be an impressive feature to have.
Function(s):
checkAINobbinDir
Description:
This algorithm essentially serves to replace the human player in providing a selection of a direction to move for the Nobbins. The algorithm is written for a single Nobbin pursuing a single Digger, and is called as many times as there are Nobbins.
The first step in the algorithm is to compute the centers of the Nobbin and the Digger respectively. Then, the Nobbin center is used as a reference point and the Digger center is located within one of eight octants with respect to the Nobbin center. The octants are numbered from 1 to 8, clockwise. Depending on which octant the Digger is in, the four possible directions for the Nobbin (up, down, left, right) are assigned priorities. Then, the algorithm loops through each direction, starting from the highest priority, and takes that direction if it is available. As soon as the highest priority direction is found, the loop is broken out of.
Availability here means that the direction it wishes to take is not land-filled or “failed”. The first condition is self-explanatory. The second condition means that the Nobbin did not attempt to take that direction before, and could not because it was land-filled. The second condition is important because without it the Nobbin would constantly be moving one pixel away and towards a land-filled location, for as long as the priority list of directions did not change.
Notes:
Our algorithm allows the Nobbin to mimic the direction of the Digger very well if they are separated by some land, and if the mimicking movement is possible (i.e. the Nobbin is not land-blocked). For example, imagine the Digger and Nobbin separated only by a long thin vertical strip of land, with free vertical movement for the Nobbin. In fact, this mimicking is so good that we were required to freeze the Nobbin by several frames every time it attempts to reverse its direction. Otherwise, the situation described above would result in certain “death” for the Digger.
If the Nobbin is close to the Digger (within several pixels and not blocked by any land), it trails the Digger very well as it simply follows the path the Digger tunnels out and hence, will not be blocked. The Digger can shake off the trailing Nobbin provided there is sufficient distance between them, and it makes sudden turns, such that the Nobbin is forced to mimic its movements again.
Unfortunately, the Nobbin is unable to find its way to the Digger from a long distance away and via an indirect path. Ideas that we had for implementing this would have required the placement of nodes at certain points on the screen to form a reasonably large graph. This was not feasible due to SRAM (variables) and flash memory (code size) limitations.
__________________________________________
Code Size Optimization
Task:
Minimize flash memory usage (using pointers and for loops)
Motivation:
Mid-way through the project, we found that our program size had exceeded 90% of flash memory usage. Without additional flash memory, we could not have continued our work.
Function(s):
None
Description:
The first thing we did was to combine similar functions into one using pointers. This was particularly useful for the Nobbin functions since they were essentially duplicates of one another with the difference that different Nobbins needed to pass and modify different variables. In order to allow the function to modify variables that are usually passed by reference, we passed the variables in as pointers and dereferenced them. Without this, the implementation of the second Nobbin would not have been feasible.
The second thing we did was to replace repeated memory accesses (e.g. to the screen array) with for loops. This saved us approximately 30% of flash memory. Without it, we would not have been able to implement the AI, and other features.