Star Duel

Allen Chang and Joran Siu

2. High Level Design
2.1  Rationale and Sources
2.2 Logical Structure
2.3 Tradeoffs
2.4 Relevant Standards

3. Gameplay Design
3.1 Code Organization
3.2 Polling for Inputs
3.3 Updating Ships
3.4 Updating Bullets
3.5 Collision-Explosion-Death

4. Graphics and Display
4.1 Zoom
4.2 Displaying Ships
4.3 Explosions and Bullets

5. Hardware Design

6. Results

7.  Conclusions
7.1 Ethics

Appendix A: Code

Appendix B: Schematics

Appendix C: Parts/Costs

Appendix D: Labor

References

A two-player spaceship dueling game featuring multiple unique ships, sophisticated physics-gaming engine, and a zooming battlefield camera.

1.1  Project Summary

Our project is a space dogfighting video game where two players attempt to destroy each other using a variety of ships and weapons.  The battlefield is a 128x100 pixel area on a TV, and a small planet resides in the middle, exerting gravitational forces on the ships and inviting them to certain death.  The input devices are Sega Genesis controllers, which were chosen because of their signal simplicity and sleek look (which makes Nintendo/SNES controllers look dorky in comparison). 

1.2  Motivation

We initially had some trouble thinking of an interesting project, and discarded several options that would have taken too much time or money.  Since we are both avid game players, we finally settled on the idea of making a video game, since this would be something we would enjoy working on for 4 weeks.  Next, we had to agree on which type of game to make; I proposed a 2-D dogfighting game because it is a time-honored but dying genre, as nearly all dogfighting games now are 3-D and aim for realism and complexity rather than straightforward fun.  Thus, we aimed to create a game that is simple to pick up and learn, yet entertaining and challenging to master. 

2.  High Level Design

2.1  Rationale and Idea Sources

For our inspiration, we drew upon a variety of old classics in the genre; Joran has had significant experience in playing the mutiplayer online shooter Subspace, and I have recently introduced him to one of my all-time favorites in the genre, Star Control II.  Both games featured the kind of top-down shooting action we were looking for, although SCII's melee mode was closer to what we envisioned our final project to be.  In addition, we saw that last year's ECE 476 projects featured a 3-player ship dueling game; however, its emphasis of that game was mainly on the impressive greyscale graphics scheme, and the actual gameplay elements were very simple.  We felt that we could take a step in the other direction, and create a game with deeper gameplay, but less impressive graphics.  Our goals were to implement several unique playable ships that had different handling characteristics and weapons, a planet that exerted gravitational forces upon the playing field, and a nifty zoom feature seen in SCII which would zoom in on the dueling ships if they were in close proximity.  The end result was StarDuel.

2.2  Logical Structure

The game consists of a state machine with 3 states:  Title, Menu, and Game.  The Title state simply shows a splash screen featuring our game name and logo, and prompts a user to press a button.  The Menu state is where the players select their ship type, and the Game state is where all the action takes place.  Below is a flowchart of the game setup logic:

In the Game state, time is either spent updating the graphics display or taking in user input and calculating what to display next.  We borrowed some of the display framework code from Lab 4, and modified it for our use.  The processor time is largely used to output the TV display lines 30-231, and afterwards we are free to use to remaining time for computations.  Here, we would execute 7 major tasks, each possibly split into several minor tasks.   The tasks were:

1.  Poll for player inputs
2.  Update ship information
3.  Update bullet information
4.  Update explosion information
5.  Check is zoom condition is met
6.  Detect collisions between objects and endgame detection
7.  Render everything on the TV output

Below is a flowchart of the gameplay logic.

Due to computational time constraints, we were forced to use an alternating scheme where all of Player 1's tasks would be executed in a frame, then Player 2's tasks would be executed in the next frame, and so on.  The gameplay is still quite smooth though, and the difference from executing everything once per frame is not noticeable.

2.3  Hardware/Software Tradeoffs

In the early design process, we considered several Atmel chips for the project. From our experiences with ATMega32 in Lab 4, we noticed the small amount of SRAM available. As a result, we spent some time studying other chip possibilities, such as ATMega162, which supports external memory. However, from discussion with various members of the course staff, we found out that external memory is not supported on STK500. We would have to switch to STK200, along with changing of clock crystals, etc. In summary, it would have taken at least a week just to get this hardware working. In the end, we decide to forgo the external memory support, and use the week for more software development. We saw the limitation of the SRAM as a challenge and motivation for better and more efficent coding.

On the software aspect, based on our past experiences, we decided to break up the code, so that the code would actually be maintainable. Breaking up the code into modules will also allow concurrent development by both game creators, and reduce the time spent to merge code together. Furthermore, we also decided to try to program as much in C, and only program in assembly for video and time critical sections. This decision was based on the fact that C code is easier to read and easier to debug. We rather spend more time implementing features, instead of taking on the job of a compiler as well.

2.4  Relevant Standards and Copyrights

The display that we used was a black and white television, which follows the RS170 and NTSC video standards.  RS170 specifies the voltage levels required to generate white, black, and sync signals as well as synchronization pulses in the horizontal and vertical direction.  It specifies three different voltage levels (sync, black, and white) along with two sync pulses for horizontal and vertical alignment.  The NTSC standard specifies that we need 525 lines per frame, 30 frames per second, with odd lines rendered separately from the even ones (interlacing).  Instead of interlacing, we just repeated lines twice as done in lab, which cuts down on processing time but halves the potential resolution. 
We based the design of our game on various classical spaceship fighter games, including Star Control II which has been publicly release under the GNU license. We give full credit to the Pam Levins and his programming team, as well as all contributors in the 3DO and sourceforge versions of the game.
 

3.  Gameplay Design

3.1 Gameplay Code Organization

We implemented three types of ships, 3 primary weapons, and 3 secondary weapons/specialities.  Each player's ship is represented by a structure containing many variables, and at upon entering the gameplay state, we initialize most of the variables based on what ship type was chosen.  Variables include ship x/y position, velocity, direction, ship type, weapon fire delays, and life remaining.  In addition the the single variables, we also maintain arrays containing information about the ship's bullets (at most 4 onscreen at a time for each ship) and explosions caused by these bullets.  The index (0-3) represents the bullet, and the arrays contain information such as x/y position, direction, time left till self detonation, whether it is active or not, etc.  The explosions have a similar setup within the structure as well.

Aside from these constantly changing variables, we maintain flash tables that store static information about the various ship and bullet characteristics such as turning rate, damage, max life, max velocities, collision radius, etc.  Simply by knowing the ship or weapon type, a function could quickly look up the value of a certain characteristic from these tables.  Of particular note is that the x and y accelerations for the ships (corresponding to each direction) have also been hardcoded into flash, since we didn't want to do any intensive sine/cosine calculations.  Bullet x/y velocities have been hardcoded similarly (we viewed them as massless, and thus didn't account for their acceleration). 

The bitmaps for all objects are stored in flash.  This includes the planet, explosion animations, and ships/bullets.  Our ships and bullets only can face in 8 directions (cardinal and sub-cardinal), so we created bitmaps for each direction.

The details of the structure and variable organization can be found within our code, which we have commented heavily.  In particular, game.c, flash.c, and ships.h should be referred to. 

3.2  Polling for Inputs

We created separate functions named acquireCommandsP1() and acquireCommandsP2() to poll for inputs from each player.  The input devices we used were Sega Genesis controllers, which we hooked up to the interface ports of the STK-500.  Each button corresponds to a certain pin, and they are active-low.  In the acquireCommands() functions, we examine the activity of each pin, and take appropriate action depending on which button was pressed.  The up button set the acceleration flag (which indicates to the updateShip() function that the ship's characteristic acceleration is to be added to the velocity), the left button increments the direction (a number ranging from 0 to 255 representing the angle from north), and the right button decrements the direction variable.  If the B button (weapon 1 fire) is pressed, we first check if the ship has less than 4 active bullets at the moment, and if so we parse through the bullet activity array to find the index of an inactive bullet, make it active, and initialize the corresponding elements in the position/direction/weapon type/lifetime arrays based on the bullet type. A press of button C does something similar, except this is for the ship's secondary weapon.  Secondary weapons may or may not be projectiles; for two of the ships, they are actually special abilities that don't fire anything (afterburner and self-repair), so a check for these types of "weapons" is done first, and the corresponding action is taken (acceleration doubled temporarily or life incremented by fixed amount). 

3.3 Updating Ships

We created a function updateShips() that operates on a ship structure, and updates its position based on current variable values.  This function is basically our physics engine, and incorporates the effect of the planetary gravity field into ship movement.  We first update the x/y velocity by augmenting them by the corresponding x/y acceleration (hardcoded in flash) as well as the corresponding x/y gravitational force at the ship's position (also hardcoded in flash).  Of note is that each ship is also limited by a unique maximum velocity in the x and y directions, and this condition is enforced after taking the acceleration and gravity into account.

We determined the values of the acceleration for each angle outside of the program by first deciding on a fixed  acceleration value, and then multiplying this by the cosine or sine of the current angle (which can only be a multiple of 0, 45, or 90 degrees).  We truncated the decimal portion, since our accelerations were represented by signed integers.

The gravity field was also generated outside of the program.  Since the field is quite large (encompassing a 40x40 area around the planet), we had to use a C script gravity.c to generate the flash code for it.  We determined the x and y forces at a particular position by subtracting its x and y coordinates with the planet's coordinates to find the distances relative to the planet.  Then, we use the distance formula:
                          distance² = xdist² + ydist²
which gives us the radial distance squared from the position to the planet.  Next we found the angle from the x-axis by taking the inverse tangent of the magnitude of the y-distance over the magnitude of the x-distance, or:
                          theta = tan^-1 (|ydist| / |xdist|) or Pi/2 if the x-distance is 0 (which avoids a divide by 0)
Then, given a maximum gravitation force, we can extract the components thru:
                          Xgrav = MaxGrav*Cos(theta) /distance²
                          Ygrav = MaxGrav*Sin(theta) /distance²  

Note that gravitational force falls off by the square of the distance, which is why we didn't bother taking a square root to find the actual distance.  Finally, we determine the correct signs of the forces by noting that it should be the opposite of the distance's sign, i.e. if you are a positive x-distance away from the planet, the force should be pulling you back towards the planet (negative force). 

Next, we determine how many pixels were moved in the x and y directions.  Here we note that the velocity is not in terms of pixels per time unit, since that degree of granularity is too coarse for such a small playing field (128x100).  Thus, we used an idea that last year's Grayscale Ships implemented: fractional distance.  We can consider each pixel as being a 256x256 area, and thus each ship has a whole pixel position as well as a fractional pixel position.  Velocities can thus be in terms of fractional distance per time, allowing us a finer degree of granularity.  We first find how many whole pixels were moved, and then augment/decrement the fractional position by the fractional velocity and determine is this caused an additional unit of pixel movement (based on whether a boundary was crossed).  The way this was done is somewhat confusing, and a look at the physics.c code may help clarify things. 

3.4 Updating Bullets

There are many bullet-related arrays of length 4 (the max number of bullets a ship can have out at a time) within the ship structure, and one of these, bulletActive[], tells us whether a certain bullet has expired (either collided or died out after a specified amount of time) and is free to be replaced by a new bullet.  During each player's turn, we update the values in the bullet x/y position, lifetime, and type by first parsing through the activity array and checking to see if a certain index is active.  If so, we use a modified version of our updateShip() code to determine the new position, given that bullets have no acceleration and fixed velocities specified in the flash tables.  Then we decrement the entry's lifetime remaining in the appropriate array, and if the lifetime becomes 0, we set it's activity flag low.  Of note is before we calculate the new positions, we first check if the bullet type is one of the homing projectiles.  If so, then we enter a special homing() routine that will alter the direction of the projectile, which may result in a different position than a normal straight-line projectile.  The homing() routine makes the bullet increment/decrement its direction variable depending on the bullet's relative position from the opponent, and the bullet's current direction.  The way this is implemented can be better understood with a look at our physics code, which we have commented heavily.

3.5 Collision Detection, Explosion Updating, Endgame Detection

These three tasks are interrelated, and are thus executed together within a function hitOpponent() that takes in the current player's ship and the opponent ship as arguments during a player's turn.  We first defined a function distanceSQ, which takes in two sets of x-y coordinates and determines the distance between them.  Next, we detect if the current ship has collided with the planet if the distance squared between their positions is less than the ship's radius plus the planet radius, squared.  If so, the ship's life goes to zero.  Next, we parse through the current ship's bullet arrays and find active bullets.  If these bullets' positions are within the radius of the opponent's ship, we decrement the opponent's life by the bullet's damage value (found within the flash tables), and place an explosion at that position.  Explosions are handled similar to bullets - in fact, they are highly correlated since each bullet can produce a corresponding explosion.  Like bullets, explosions have arrays detailing their active state, lifetime, and x/y position. 

Finally, we determine if the game is over if either ship's life is zero.  In that case, we zoom onto the dead ship (which should be exploding), and declare the winner of the round.  Then, we move back to the menu state in preparation for another round. 

4.  Graphics and Display

After all computations are completed and values updated, we can determine what to draw on the screen.

4.1 Zoom Condition Checking

As an essential and fun aspect of gameplay, our graphics engine has a built-in zooming system, which automatically provides close-up perspectives during battle sequences. The zoom feature enlarges both the x and y directions by a factor of 2x, thus, magnifies a quadrant of our battlefield. The zoom is triggered when the ships close enough to each other, such that both ships can comfortably fit within a bounding quadrant box. Upon detection of this proximity, we determine to coordinates of the zoom quadrant/box while also ensuring that the box does not fall off the edge of the battlefield. The actual zooming is performed by a separate rastor output assembly code. Similar to the normal video output code, the zoom code determines the indices of the screen buffer array from which to load, based on lineCount as well as an xOffset defined by the left edge/coordinate of the bounding box. To achieve the 2x zoom factor, each bit in the line is outputted twice, and each line of our array is outputted four times (compared to the normal two). The resulting effect is a dynamic and flexible zoom feature, which allows us to easily switch between the two modes without much computation, artifacts or flickering.

4.2 Displaying Ships

The most important role of the graphics engine is the capability to draw and redraw ships without any flickering or video artifacts. Each ship is a 7x7 bitmap, and requires pixel accuracy in its position (for compatibility with physics engine). As a result, given the center coordinates and orientation of a ship, the drawing code will have to erase the previously drawn ship image, and replace it with an updated version of the ship. The pixel accuracy requirement further complicates matters by preventing us to align the render of our bitmaps to every 8 pixels (or a char on our field). As a result, the ship bitmap might span between two consecutive char elements in the screen buffer array. Several techniques were developed to handle this mapping to two array elements, which includes rotation of bits in a line of the ship bitmap, as well as efficient index calculation for mapping to the screen buffer. Additional complications resulted in handling of the mapping at the edges and corners of the screen. Simple oversights, such as using unsigned char instead of signed char in the render code will often leave artifacts behind at the edge of the playing field. In summary, the general flow of the ship display code is as follows:

1. Given ship center coordinates, orientation and type, compute the top left corner for the ship mapping.
2. Erase the old ship image from screen buffer.
3. Acquire the 7x7 ship bitmap correspoinding to the given orientation and ship type line-by-line from flash.
4. For each line, based on the 8-bit alignment offset, rotate the 7-bit line element.
5. If the ship map spans two elements of the screen buffer, we map the appropriate parts of the 7-pixel image to the corresponding element.
6. Repeat the above for each of the 7 lines of the ship image.

4.3 Displaying Bullets/Explosions

Similar to displaying ships, drawing of bullets and explosions require very similar steps. Bullet and explosion coordinates are provided by the physics engine, from which we have to erase the old graphics, and remap the new bitmaps to the screen buffer. The only new complexity is the rendering of explosions on top of ships. Since we only have black-and-white, drawing both the ship and an explosion together would result a big blob of indistinguishable white pixels. In order to allow people to visually distinguish and explosion apart from a ship, we actually perform explosion and bullet rendering on separate frames, such that for one frame, you see the explosion, while on the other, you see the ship. This technique allows the game player to visually distinguish these separate, overlapping components.

5.  Hardware Design

Since our project was a video game, we didn't have much hardware.  We used two Genesis controllers as input devices, which feature DB9 connections.  We bought some DB9 connectors at the Clark Hall stockroom,   soldered wires onto the connectors, and attached them to the breadboard to make easy-to-use plug-in ports for our controllers. 

Our other main piece of hardware was our video DAC, which we had previously used in the Digital Oscilloscope lab for ECE 476.  A schematic of this and the controller hookups can be found in Appendix B.

6.  Results

We achieve all primary and most of our secondary objectives of this project, which was to create a two-player spaceship shooting game that features multiple unique ships, a sophisticated physics engine, and a scaling battlefield camera. We have both ships moving fluidly in reponse to user commands, three unqiue ship models with a variety of weapons, advanced physics engine which incorporates acceleration, velocity, and ship collisions, scaling battle field camera. Among our secondary goals which were accomplished were the planet which exerted a gravity field, as well as ending explosion sequence for death scenes. There were no flickering or artifacts issues, as the video timings were always accurate, since we divided up the drawing, physical simulations and collision detection sequences into separate frame. Our video game can be played on any TV which supports composite video input.

7.  Conclusions

We achieved most of our goals through careful planning and design of the game. From the code architecture to the various physical equations used for simulation, our planning-before-coding saved us a lot of time, both in development and debugging. We decided to use Genesis controllers after sampling several options from old gaming systems, and were very statisfied with our choice. On the software aspect, our sepearation of functional units into separate modules allowed for concurrent development of both the physics engine and display code. Our early definition of the interface functions was a primary reason why our project was completed on time. We reached nearly the capacity of our AMega32, both in SRAM, flash and data capacity, which was a limiting factor to additional features. Given more development time, we may have been able to optimize our code further, and perhaps convert more sections of it into assembly for higher performance. Several out-of-the-world objectives were removed due to other limitations. For example, our dream of having moving asteroids would have cluttered up the screen and taken away some gameplaying enjoyment. The planet is a big death machine already, considering its small size.

Additional Features that we would have liked to include in the game:

• Powerups for ships and weapons.
• Sound Effects.
• Randomize battlefields.

7.1 Ethical Considerations

In this project,we abide by the IEEE Code of Ethics:

1. "...to accept responsibility in making engineering decisions consistent with the safety, health and welfare of the public..." We accounted for repetitive stress injuries arising from prolonged button pressing, and epileptic seizures arising from onscreen flashes at a certain frequency. As a result, we used a gaming device (Genesis Controller) that has been tested by millions of game players around the world. Our project did not have any flashing, so that latter issue is not a concern.
2. "...to reject bribery in all its forms..."We did not expect and have not received any form of monetary donations or gifts from anyone in the development of this game.
3. "...to maintain and improve our technical competence ..." Both of us learned a lot about the C, assembly programming for microcontrollers. We learned how to handle and debug (very important) timing problems that arose during the course of development.
4. "...to treat fairly all persons regardless of such factors as race, religion, gender, disability, age, or national origin..." This game does not discriminate against any persons in the development of this project. Both Allen and Joran accepted the input of all people in developing this game, as well as freely gave our input and ideas to fellow colleagues on their projects.
5. "...to avoid injuring others, their property, reputation, or employment by false or malicious action..." During the development of this project, we were careful in maintaining safety precautions in and around our lab bench. We made sure systems (ie. TV) were off when not in use, that extraneous wires were either removed, or tucked away, so that our game is safe for us, and others.
6. "...to be honest and realistic in stating claims or estimates based on available data..." We attest to the accuracy and completeness of all information provided on this website and during the demo.

Appendix A: Code Files:

game.c: Main Game File
game.h
physics.c: Physics Engine
physics.h
ships.h: Hardcoded Constants
ports.h: Port Definitions
flash.h: Flash Tables and Bitmaps
global.h: Global Parameters
gravity.c: Gravity Script
gravity.h
display.c: Display Code
display.h
letter.c: Letter Code
letter.h
letterflash.h: Letter Bitmaps
menu.c: Main Menu Code
menu.h
 

Appendix B: Schematics

Figure 1. Video DAC

Figure 2.  Controller Connection and Pinout (graphics taken from Lab 1 and Cantneroid from SP 2003

Figure 3. Global Setup

Appendix C: Parts and Costs

Our major hardware components included:

• 1 AMega32 chip ($8.00)
• 3 Resistors (Free)
• 2 Genesis Controllers (Free)
• 2 DB9 Connectors ($0.45 each)
• 1 Breadboard ($5.00 each)

Appendix D: Labor Division

Allen wrote and debugged the physics engine, collision detection and weapons system, as well as created all the bitmaps for ships, bullets and explosions. Joran worked on developing the backend display functions, and the menu selection system. Both of us took part in the design of the code architecture, and other high-level decisions.

References:

Ideas from: The Ur-Quan Masters - Star Control II Video Game

Ideas from: Gray-scale Graphics: Dueling Ships from SP 2003 by F.Woodland and J. Yuen

Technical Reference from: TV Oscilloscope Basis Code from ECE 476 SP 2004 Lab 4 - by Prof. B. Land

Technical Reference from: ATMega32 Full Data Sheet

Techical Reference from: Cantneroid from SP 2003 by C. Moschner & M. Cantlon