Introduction
Maze in a Box is a portable game in which you tilt a TV to navigate your way around a 3D maze as though you were in it.
We created Maze in a Box as a challenge to generate 3D looking graphics using the Atmel Mega32. We also looked to implement the game in a manner that was completely easy and intuitive to play. Most importantly, it was way cooler than any other idea we could think of.
High Level Design
The original idea for the project was to recreate something resembling the classic video game ‘Doom’.
After some discussion, we decided to settle with something simpler, like the ubiquitous windows screensaver.
The finalized idea was a maze in which a person could walk within by holding up a completely portable game unit.
The general schematic is as follows: The Atmel Mega32 generates a video signal to the TV showing the user’s current view of the maze. The user understands the information moves in a real space to modify his position within the maze. The accelerometers picks up these values and passes it to the analog to digital converter on the processor, which then interprets the changes in acceleration and modify’s the user’s position within the maze accordingly. This continues until the person reaches the end of the maze, which is marked by a corridor with a diamond at the end of it.
It was realized early on that there would be two main tasks involved in the project– creating the drawing system and interfacing with accelerometers. We started off with the former by exploring different ideas for creating 3D images for the game.
Performance, performance, performance.
The biggest compromises we had to make in the project involved performance, storage space and programming complexity. Since we are programming on the Atmel Mega32, performance and space are both scarce resources. Thankfully, we managed to come up with a good compromised that managed to achieve reasonable framerates, kept within the storage space and that was tenable to code within the allotted time frame.
How much real 3D calculations should there be?
Performing 3D calculations requires significant resources in terms of matrix multiplications. From our initial research, we found that true 3D required 4 4-D matrix calculations per point (which translates to 64 multiplications). This was unacceptable. In order to simplify the math and reduce the number of calculations, we could constrain the viewport. It was soon decided that for the best processor efficiency, we could execute the entire task without any real math and still conform to a reasonably realistic display specification.
One processor, or two?
When choosing how the drawing system should work, an important consideration was whether we should use one processor or two. One processor would be cheaper and more elegant. A couple of interesting schemes were conceptualized in order to try to squeeze as many clock cycles as possible out of the processor while it was generating video output. Interestingly enough, one of the schemes made it into the final build even though we finally opted for the two processor configuration. The eventual reason for using two processors was so we could work on the drawing system without having to worry about timing issues. This turned out to be a very fortunate decision.
Full frame updates, or incremental screen updates?
We had two options for the drawing system with very different implications. The first one was to update the entire video buffer on every iteration. The problem with this approach was that it was prohibitively slow due to the large size of the video buffer. On the up side, it produces a very elegant result, whence each frame can be drawn solely based on the current position the user is in the maze. Incremental screen updates would be much faster in updating the video buffer, however the screen updates would have to be a function of both the current user position and the next user position, which seemed much more complicated and prone to bugs that would be debugged by painful pixel counting. For this reason, we opted with full frame updates.
Random access updates, or serial updates?
When we inspected the video code from Lab 4, we realized that the code uses random access to update the video buffer, which would have been criminally inefficient for drawing solid shapes like in our game. We had to create our own system for drawing polygons, and the important question was whether we were going to draw using a ‘random access’ approach which would allowed us to draw polygons by specifying pixel values, or whether we should use a ‘serial’ approach, updating the video buffer sequentially. The trade off here is between programming complexity and execution time, and we eventually opted for serial updates in order to improve performance.
Discrete or continuous?
In order to create a compelling game, we needed to decide on how fine grained movements would be. For walking forward and backward, creating fluid movement seemed feasible enough. However, we had a long list of problems with performing continuous turning (since we had opted for no 3D math). By preliminary tests, we realized that 90-degree snap turning would be completely counter intuitive. With this in mind, we decided to implement as much as we could, with the contigency of defaulting to discrete movements if we could not work out the code in time. Thankfully, we did not have to revert to that.
After the drawing system was completed, we moved our attention to the accelerometer input. We started off with a X-Y accelerometer, taking in values and trying to deduce two kinds of movement– walking and turning. After a long series of particularly faulty inputs, the accelerometer stopped working. At Bruce’s suggestion, we switched to two Z accelerometers perpendicular to each other. This worked much better, but still after much work, we were still unable to devise any heuristics that deduced movement in an accurate enough fashion for it to be intuitive. We eventually gave up on trying to detect walking and turning and switched to a tilt based system which worked quite well.
Standards
We conformed to NTSC standard for video generation.
Program Design
Processor Communication System
Since we decided to work with two processors in this project, the first part of the project was spent working on the communication system between the two Amtel Mega32’s, which we shall name master and slave.
Parts List:
Cost Details:
| Quantity | Item | Cost |
|---|---|---|
| 2 | Atmel Mega32 | $8 |
| 2 | Custom PC Board | $5 |
| 1 | Small Solder Board | $1 |
| 1 | 9V Battery | $2 |
| 12 | 1.5V C Battery | $1 |
| 1 | 9V Battery Board | sampled |
| 2 | MMA1260D Accelerometer | sampled |
| 1 | B/W TV | $5 |
| Total: | $46 |
For more detail: 3D Maze in a Box video game Using Atmega32
