Code Size

"ATmega328P" memory use summary [bytes]:

Segment   Begin    End      Code   Data   Used    Size   Use%
---------------------------------------------------------------
[.cseg] 0x000000 0x0003fe    960     62   1022   32768   3.1%
[.dseg] 0x000100 0x000600      0    459    459    2048  22.4%
[.eseg] 0x000000 0x000000      0      0      0    1024   0.0%

Assembly complete, 0 errors. 0 warnings

Playing The Game

Each player is represented by a red or blue tank positioned on a randomly generated terrain background. When it is your turn to fire, a white button will appear behind your tank. In addition, the aiming cursor (white cross hair) is displayed in the sky region. The relative position of the aiming cursor and firing point of your tank (top-center of the turret) is used to describe a vector of your projectile's initial velocity (remember this from physics class?)

The relative angle between the aiming cursor and turret describes the angle of fire. The distance between the two describes the amount of powder used to fire the shot. The further away from the turret, the larger the powder charge and the longer the projectile will fly. Touch the "sky" region of the screen to move the aiming cursor.

Once you are happy with where it is placed, press the white button (or your tank) to fire. The path of the projectile will be plotted in real time until it hits something or goes out of bounds. If you miss, the other player will be given a turn to fire on you. If you hit the other player, you are awarded a point and the terrain is regenerated. If you hit yourself, the other player is awarded your point.

Each player's score is displayed at the top of the screen as tally marks. Play continues until a player has scored 3 points, in which case he or she is the winner. A new game is immediately started.

Design Details

The code is broken into several modules located in the real/ subdirectory of the github repo:

At the top of main.asm, there are a number of constants defined. The most interesting are the SMOOTH_TERRAIN and FLASH_TANK constants. When both are enabled, the size of the code exceeds the 1024 byte limit. For the purpose of submission to the contest, I have chosen to enable SMOOTH_TERRAIN and disable FLASH_TANK. If you don't mind blocky terrain and want a cool flashing effect when a tank gets blown up, then you can change these constants to enable that. Also, you can turn them both on, but the game will no longer fit in 1KB!

The main game loop (in main.asm) is broken up into the ready, aim, and fire sections. Ready draws the board, aim handles manipulating the aiming cursor, and fire plots the projectile path. There is also a new_game section and labels for handling hits an misses. Several subroutines are also defined for generating the terrain.

The game is based on "real physics equations". Each pixel on the screen represents one meter of space. Obviously the tanks are oversized, to make the game possible to play. Position is computed using three vectors - acceleration, velocity, and position. Each vector consits of an X and Y coordinate, stored as 16-bit signed integers. Fixed-point math is used such that 1 meter = 64 units. A frame rate of 16 fps is used to plot the motion of the projectile. Every 16th of a second, the acceleration vector is added to the velocity and the velocity is added to the position. This is, in effect, a numerical integration of the 1/2at^2 equations we all learned in physics class.

The position vector is immediately scaled down into screen coordinates (1 meter = 1 pixel = 1 unit). The remainder of the calculations, such as hit tests and bounds checks are performed in this coordinate system.

The proto/ subdirectory contains an Arduino sketch that was used as a prototype for this game. This allowed me to try out new ideas and figure out how the hardware worked. It's fun to play too, but at 7.5KB is no where near meeting the requirements for this contest :-)

Making It All Fit

I used quite a number of techniques to make this code fit. First and foremost - scoping. There were quite a few features that I developed and later cut. In making these decisions, I tried to favor things that made the game interesting to play (random terrain, scoring) over eye-candy (animations, complex shapes, etc.).

Fixed point math

Obviously, 1KB does not leave much room for math routines, and a floating point library is out of the question. Instead, fixed point is used with 16-bit signed integers. These numbers are scaled such that 64 units = 1 meter = 1 pixel on the screen. 64 was chosen so that overflow would not occur (320 pixel screen width * 64 = 20480, which is less than 32767), but the gravity vector G still has a reasonably accurate value when truncated (9.8 * 64 / frame_rate / frame_rate = 2.45 => 2).

Used tally marks instead of fonts

Most games display scores numerically. However, a font table would count against my 1KB of code space, so I simply use an array of small rectangles to represent the scores of each player. In an extra bit of space-saving trickery, the scores are internally stored as the range 2 to 5, and are the number of rectangles to draw. The first two rectangles in the array are the tank body!

Graphical vectors instead of sine functions

The "textbook" version of these equations starts with a speed and angle, which are converted to X and Y components using sine and cosine functions. Instead of writing these functions, I took advantage of the graphical interface to trick the user into computing them for me by drawing out the vector. Turns out, humans are pretty good at this, even if they don't know they are doing it.

Avoid 32-bit instructions

The AVR is a RISC architecture and as such, most instructions are a single word (2 bytes). However, there are four instructions (call, jmp, lds, sts) that deal with absolute addresses, which take up two words (4 bytes). I avoided all usage of these instructions by using rcall, rjmp, and Y and Z register-based load and store instructions.

Data layout

The positions of variables were chosen carefully to allow maximum code density. Much of the state is stored as vectors, in which the X and Y coordinates are stored one after the other. By using auto-increment addressing and "call & fall" (see below) I was able to efficiently perform vector math. Furthermore, the vectors themselves were arranged by the order in which they were accessed, allowing me to eliminate a number of "ldi yl" instructions.

I also aligned the player-specific data into page boundaries, so that the low byte of the pointers are identical for both players and the high bytes correspond to the player number. This allowed the Y and Z pointers to be re-positioned with a single instruction.

Lastly, I included a number of "global" variables within the player-specific structure. This eliminated having to move the Y and Z pointers away from player-specific pages and allowed them to use common initialization code.

Call & Fall

This is an old assembly language technique for doing something 2-4 times. Instead of writing a loop, use a subroutine call as your first instruction and have it call the very next instruction. It will execute the bottom half of the routine, hit the ret call, and then fall through into itself again. In some cases, I have some extra code after the call to adjust pointers.

Static Initializers

Each AVR instruction is at least 2 bytes. However, instruction memory can be read byte-by-byte using the lpm instruction. So, quite a few variables are initialized by copying their values from program memory and are recopied on each turn.

Though the values in question are 16-bit integers, none of them initially exceed the range [-128, 127], so they are stored in program memory as 8-bit signed integers and expanded to 16-bit signed integers by the copyp routine. This cut their size in half!

Tail calls

Another classic old assembler trick. When the last thing a routine does is call another routine and then return, we can simply jump to the other routine and let its "ret" instruction return to our caller.

Global variables in registers

Due to the large number of registers available and the relative simplicity of this game, I was able to store several global variables in registers. Given the size of the lds and sts instructions, this turned out to save quite a few bytes. No interrupt handlers are used, so there is no danger of them changing unintentionally.

Use multiply and divide routines

OK, this one is counter-intuitive. Normally, assembly language programmers try everything in their power to use bit shifting rather than multiply and divide routines. However, the touch screen routines had to scale emperically derived ranges of values into 320x240, and there was no way to do this as powers of two. So, I had to bring in generic multiply and divide routines. Since they were "paid for" already, it was cheaper to just use them in other parts of the code rather than use more space to write bit shift versions. Remember, we're optimizing for space, not speed.