This is an experiment to find out how much action gameplay can be packed into a game for the Ardunio-based Gamebuino. Programming this neat little device means that we have to deal with few resources: There’s just 2 kb of RAM and 32 k of flash memory for the program code. Everything that should happen in the game must be crammed into this space. However, we’re lucky because there’s a powerful CPU in the device, chugging along at a blazing speed of 16 MHz. Let’s have a moment of silence for the poor souls that have to deal with a 1 MHz CPU.
Here’s a small demo (time used per frame is shown in the upper left corner):
And this is what the corresponding level looks like:
Just load the cruiser.ino into your Arduino IDE, upload to the Gamebuino and you’re ready to kick ass and chew bubblegum!
Portal engine
The engine implemented is a portal engine. A level consists of convex segments which are connected to each other. Each segment is defined by a 2D outline in the X/Z dimension and may have different floor and ceiling heights.
We always keep track of the segment the camera is currently in and render that segment. If we encounter a transparent wall which leads to an adjacent segment, we render the segment behind that, and so on.
Clipping
Sutherland-Hodgman clipping is used to clip segments to the viewing frustum.
An in-place version of the clipping algorithm is used to minimize the memory footprint: the clipped target polygon can be written to the same memory location the unclipped, source polygon is being read from.
Player movement
Player movement is done using accelleration and attenuation, resulting in smooth movements. Strafing is possible but there’s only so many buttons on the Gamebuino…
Hidden surface removal
The first segment is clipped against a viewing frustum defined by the four screen edges. When an adjacent segment is rendered, this viewing frustum is clipped against the wall through which the adjacent segment is visible, thus taking care of clipping.
Because clipping is performed in view space with the camera at the origin and pointing towards (0, 0, -1), frustum planes can be defined using a normal vector only.
To further save precious RAM, frustum plane normal vectors are currently stored with 16 bits per coordinate.
Building levels
Levels are defined in map.rb, using a Ruby DSL. The script connects all adjacent segments automatically and creates a header file containing the level definition (map.h) plus a visualization of the level (level.png).
Fixed point arithmetic
This game only uses floats when calculating sine and cosine values. It doesn’t use lookup tables for this because the CPU is fast and there’s no space for fancy lookup tables. In all other places, fixed point arithmetic is used.
Lasers!
This game has lasers. They’re fun but they require a lot of memory (10 bytes per shot as of now).
Sub-pixel accuracy
Lines are rendered using the Bresenham algorithm, but here it’s implemented in a way which allows for sub-pixel accuracy. Even with a small resolution of 84×48 and only black and white pixels, subpixel accuracy makes a difference when things get animated.
Here’s a comparison of both modes (pixel accuracy on the left, subpixel accuracy on the right):
It’s the same scene but in the left animation, pixel coordinates are rounded to integers before line drawing, whereas in the right animation, 4 fractional bits are left in the numbers which are then picked up by the Bresenham line drawing function. There’s not much of a difference in terms of speed, it’s just a matter of calculating the both the initial error and error delta in such a way that the fractional parts of the given coordinates are taken into account.
Debugging
Debugging a Gamebuino game is hard when space is an issue because the Serial library has a non-trivial memory footprint. Luckily the language used is C so this means that the game can just be compiled on a Linux machine with some minimal framework.
Hint: Run ./compile.sh and ./cruiser in the port directory to see LOG messages everywhichway. Oh, and if this crashes, comment out the #define MONITOR_RAM line, you don’t just paint the stack on a Linux machine like that. :-)
Here is a demo video showing the debugging version at work:
Rendering is done via OpenGL, and the resolution is much higher which helps in debugging strange artifacts. In addition, you get lots of LOG messages to the console which can be really helpful as well.
Doors
Doors are fun and besides that, they also minimize the amount of geometry that needs to be rendered when they’re closed, so that’s a good thing. Win-win. But doors need fancy animations and at the same time the see-through hole resulting from the animation should have as few vertices as possible, because more vertices mean more frustum planes to clip against. I tried different designs and came up with a version that has never more than 4 vertices.
Objects
When you have doors, you need to have keys. I’m currently experimenting with texture mapping and filled polygons.
Shots
Shots currently use 10 bytes per shot:
- 6 bytes for the position (16-bit vector)
- 3 bytes for the direction (8-bit vector)
- 1 byte for the current segment
Ideas:
- encode the position relative to segment position, thus saving bits
- encode the direction not as a xyz vector which may contain every point in a cube, but rather encode the principal direction with 3 bits and encode the rest using two coordinates with a resolution of 6 bits each, this would save one byte
- because two shots are always fired at the same time, they can share the starting position and direction
Clipping planes
Clipping planes currently are defined using a 16-bit normal vector which looks worse than using 32-bit normal vectors, especially in the center of the screen where accuracy is low.
Idea:
- define a clipping plane normal vector in screen space using fixed point coordinates with 4 fractional bits, thus we need 11 bits for x and 10 bits for y, so thats 21 * 2 = 42 bits for two points, which amounts to 5.25 bytes instead of the 6 we use now, so the memory stays the same, but it should look just perfect.