TREASURE HUNT OF
THE HIGH SEAS

 
PROGRAM DESIGN
 
    Main Goal:
    Create a wind direction detector with a laser assembly
    Design a sailboat simulator on the television screen that will react to the detected wind

    Secondary Goal:
    Use external inputs to adjust sail height, wind magnitude, and rudder position
    Turn and move sailboat on TV in a calculated speed depending on current wind, rudder position, and sail height

    Tertiary Goal:
    Allow sailboat to uncover and retrieve treasure troves
    Design pirate ship to protect treasure and fire upon sailboat
    Program cannon firing for sailboat to protect itself from pirates
 
  1. Atmel AVR Programmer Setup
  2. Television Signal
  3. User Interface
  4. Game Screen and Icon Drawing Instructions
  5. State machine determining background to display: opening screens, game screens, and in-game map
  6. Algorithms to display the correct ships and cannonballs for the present section of the map
  7. Algorithm to display sailing indicators on screen
  8. Algorithm to adjust sailboat direction and velocity based on wind direction, wind magnitude, and sail height
  9. Algorithm to adjust pirate’s direction along a preset course and velocity based on the wind direction
  10. Algorithm to create a cannonball that appears when demanded, moves, and disappears when it hits either land or another ship
  11. Algorithm to determine which direction an opposing ship is, so that the cannons fire from the correct side of the ship
  12. Treasure Algorithm
  Atmel AVR Programmer Setup
 
There are several options that must be selected or unselected for the Atmel AVR Programmer. Under the Project menu, choose C Configure. Under the Compiler tab, choose the Atmel Mega32 and 16MHz, set "Optimize for Speed", set the Data Stack size to 100 bytes, turn off the "char is unsigned" option, and set (s)printf to “int, width.” Under the After Make tab, turn off all Clk Select options and uncheck both verify and chip.
 
Television Signal
 
The TV signal is created by a timer 1 interrupt that runs every 63.625 ms. The interrupt generates a horizontal sync pulse of 5.125 µs to start each line. The stopwatch code runs once line 231 is reached. Starting at line 231 gives the code more than 3.8 ms to run. At line 248 the vertical sync pulse begins and lasts for three lines. We used a large character bitmap for lettering and indicators, and a small character bitmap for the ships.

Code for displaying a point, a character, a string, a line, or returning the value of a point were provided by Professor Land on the ECE 476 Video Generation with AVR page. The code was a combination of C and assembly written specifically for the Mega32. The code also generated the sync and raster. We did have to adjust the functions when we changed the size of the characters in the bitmaps. The main difficulty was that we had not used the Mega32 before. In labs, we had used the Atmel Mega163, which used an 8MHz crystal rather than a 16MHz crystal. The Mega32 also required a few different initializations including enabling sleep mode requiring MCUCR to equal 0b10000000 and the line time increasing to 1018. Since the Mega32 is twice as fast and has twice as much SRAM as the Mega163, we could double the width viewed on the television to 126 pixels wide. The height remained the maximum height for the screen at 100 lines.
 
User Interface
 
The user controls game conditions through debounced buttons and laser apparatus outputs. The code processing this is implemented at the beginning of a function that implements the ship movement (shipmovement), since this is an appropriate time to check the user commands. It runs twenty times per second, deemed sufficiently fast to catch button presses and slow enough to prevent button bouncing by checking to see if two successive checks register that a button is pressed. The buttons implemented are described in the hardware design section.

All buttons will register only one press when held down except for the cannon fire button, so that you can simply hold this button down when on a violent rampage. Naturally, rudder direction, sail magnitude, and wind magnitude cannot be adjusted past their game limits. The program must interpret the phototransistor outputs in order to determine the wind direction. The beam orders are: 0 = north; 1 = south; 2 = east; 3 = west. If beam 0 (corresponding to PINA.0) is blocked, for example, we know there is wind to the north. If beam 2 is also blocked, we know there is wind to the east as well, so the game wind direction is northeast. The last known wind direction is used if more than three beams are blocked.
 
Game Screen and Icon Drawing Instructions
 
We discovered during initial testing that adding more than four long lines or fourteen characters to the display in a single frame creates visual artifacts. In order to display complex maps and instruction screens, we created a counter (timer) which increments every frame while a map is being drawn and directs which section of the map to draw in the given frame. All aspects of the game are paused for as long as the map is drawing. After the map is drawn, normal game operation resumes.

To produce a convincing image of ship movement, eight different bitmaps were created to represent the ship oriented in eight different directions. These can be found in shipbitmap. Bitmaps were also created for displaying status indicators and are in bitmap. Since the sailboat direction is stored as a variable sailD with range 0-15, this is simply shifted once to select one of the eight possible bitmaps. Similarly, the pirate ship direction pirsailD is shifted once to choose the pirate’s bitmap.
 
 
State machine determining background to display: opening screens, game screens, and in-game map
 
The section of main that runs when line 231 of the TV is being displayed contains a state machine (gamescreen) that organizes the game (its dependencies on game situations make it too complex to draw). It contains states for the opening screen, rules screen, indicators screen, four map section screens, a screen for viewing the entire map, two different game over screens (victory and defeat), and a screen for updating the loot indicator. The various functions of the game change the overall state when required by game conditions and user controls.
 
Algorithms to display the correct ships and cannonballs for the present section of the map
 
Due to considerations discussed below, both the ships and the cannonballs travel over a map that is about four times larger than the actual screen. In the shipmovement function, when the ship is to be displayed on the screen, its coordinates are adjusted down to the coordinates for the TV screen (see below). When the ship moves onto a different screen, pirate is set to either turn all pirates off (if you move into the southwest quadrant) or turn pirate 1, 2, or 3 on. When the pirate movement function piratemove is next run, only the pirate dictated by pirate will be displayed on the screen, so it will be appropriate to the map since the map is changed as well when the ship changes screens. The cannonballs of shipcannon and pircannon are initially created in the same place as the ship that fires them, and follow the same procedure for reduction to the TV screen coordinates. The cannonballs are restricted from moving off the screen because they are destroyed when they hit any pixel of the screen that is on, and the screen is always bordered by lit pixels.
 
Algorithm to display sailing indicators on screen
 
Every frame before the ship is moved in shipmovement, the sail magnitude, wind magnitude, rudder direction, and wind direction are displayed (this uses shipspeed as its counter). This takes place in the frame before the ship is moved to ensure that the indicators do not have to compete with complicated ship movement calculations for processing time. The indicators appear in a 124x9 pixel region at the bottom of the screen. They use bitmaps that are 7 pixels tall, so there is one pixel of black space between the indicators and the two horizontal lines used to create the indicator bar. The code is near the beginning of the shipmovement function.
 
 
Algorithm to adjust sailboat direction and velocity based on wind direction, wind magnitude, and sail height
 
This algorithm is necessarily complicated because it needs to simulate sailing conditions without using long multiply or divide operations. It is further complicated because we wanted 16 different directions of ship movement while only having eight adjacent pixels to move the ship to. Moving the ship several pixels at a time would have wasted resolution, so we chose a different option. Our solution was to create a map for the ship to travel on with more coordinates than the TV screen has. Sailing calculations are made on this map, and the sailboat’s location is then mapped down to TV screen coordinates. So that the coordinate reduction does not require hundreds of divides, we made the ratio 2:1 for true map pixels to screen pixels. This allows a simple right shift. The true map is more than just twice the width of the screen, however, because the true map takes into account all four quadrants of the game map. This results in a true map size of 498x350 pixels. The true map is not eight times the TV screen size (100x126 pixels) since the indicator bar and screen borders take up a decent portion of the screen (1666 pixels’ worth to be precise). The code for the coordinates is not located in a single place, since it is inherent in the design throughout all the functions. Both the pirate ship and the cannonballs move on the true map and are mapped down when needed for display.

There are two factors affecting the sailboat direction: its previous direction and the direction of its rudder. In sailing this is roughly true as well; the wind changes your speed based on your direction, but it doesn’t keep you from pointing toward or away from it. Every time the sailboat moves, the sailboat direction increases or decreases by one or two (depending on whether the rudder is pulled hard or lightly) around a circle of 16 points. On the true map, the sailboat moves in each of the x and y directions by 1 or 2 depending on which of the 16 directions you are going. This code can be found near the beginning of shipmovement, and the velocity calculations comprise almost all the rest of the function.

Calculating the ship velocity is much more complicated. It is a function of the sailing direction, the wind direction, the wind magnitude, and the sail height. First, we reduce the first two variables down to one because all that matters is the difference between the ship direction and the wind direction. This gives a value between 0 (ship moving with the wind) and 8 (ship headed against the wind). Since you will be drifting slowly if the sails are down, wind is zero, or you are heading into the wind, we can quickly eliminate a lot of cases that we would have to calculate the velocity for. We are left with 2 possibilities for the sail height, 2 for the wind magnitude, and 7 for the difference in direction between the ship and the wind. This gives 28 possible speeds, which is well within feasibility for case statements. This eliminates the need for multiplication.

The variable shipspeed that will correspond to the velocity controls the ship’s speed in the game by determining how frequently the ship moves. Every time the ship moves, this variable is decremented. Only once it reaches zero are the ship’s direction and velocity re-calculated. Because of this, a lower value of shipspeed increases the velocity of the ship. We found when we tested the code that lower values of shipspeed increase the velocity exponentially. We could have figured this out beforehand, but didn’t really think about it too much. As a result, we changed the code so that incremental increases in the velocity correspond to logarithmic decreases in shipspeed. This fixed the problem. The values were also set with sailing in mind, in that going not-quite-with-the-wind will give you the highest velocity.
 
Algorithm to adjust pirate’s direction along a preset course and velocity based on the wind direction
 
The pirate’s movement calculations are much simpler. The piratemove function checks to see which pirate, if any, is supposed to be active on the screen and places a pirate ship at given starting coordinates. The pirate follows a set course that is designed to “guard” treasure. When the course is finished, the pirate returns to his starting position and the cycle repeats. The pirate moves on the same true map as your ship and uses the same method to move on it based on the preprogrammed sail directions. Its velocity is controlled in the exact same manner as your ship.
 
Algorithm to create a cannonball that appears when demanded, moves, and disappears when it hits either land or another ship
 
The cannonball is triggered in one way for your ship and a completely different way for the pirate ship. Your cannon is controlled by button 5; if you do not presently have a cannonball in the air and are pressing button 5, a cannonball will fire from your ship. The 1-pixel cannonball updates its movement in a straight line every frame until it has moved a preset distance (default is 20 pixels) or hits something. This is twice the maximum speed of either ship. If at any time your cannonball is located within the 5x5 square a pirate ship occupies, the pirate ship and cannonball both disappear. If it hits land or the screen borders, the cannonball is turned off (scannon = 0). This cannon is operated by the shipcannon function.

The pirate ship decides when to fire based on a crude, but computationally simple procedure in the pircannon function. It checks to see if the absolute difference in the x+y values for your ship is less than a certain number. As long as this number is greater than the maximum cannon distance times the square root of 2, the pirate will always fire when he could possibly hit you, unless you happen to be moving toward him in which case he will be a bit late. He will sometimes fire when he has no chance of hitting you at all, but since no actual metal is wasted in the cannonballs we figured the processor time savings was worth it, and warning shots will give you an idea of the pirate’s range. The pirate’s cannonballs disappear when they hit land or the screen borders. If at any time the pirate’s cannonball is located within the 5x5 square your ship occupies, the game over screen appears leaving the sea battle frozen in time so you can see what sank you.
 
Algorithm to determine which direction an opposing ship is, so that the cannons fire from the correct side of the ship
 
No self-respecting crewman would fire a cannon in the opposite direction of his target so an algorithm was necessary to prevent this. It follows a reasonably straightforward approach, basically a binary search to narrow the opposing ship’s location down to one of eight sections where each section is one half of a quadrant with the ship as its center. Explaining the algorithm further would take more space than the algorithm itself, which is incidentally identical for your ship and the pirate ship. See the well-commented code toward the end of either the shipcannon or pircannon functions.
 
Treasure Algorithm
 
Treasure appears on a different screen when your ship crosses key areas. There are a total of six possible treasures, each having its own area of the map in order to make it available. The ship must cross somewhere in an area of 21x21 pixels in order to activate a treasure. When a treasure is made available, one of three possible treasure indicators appears along with the direction of the now available treasure in the indicators section. When the sailboat retrieves all six treasures, the game is won and “You Found All The Loot” is displayed across the screen. In order to make the game slightly easier, the same treasure location can be activated multiple times rather than having to find all six possible treasures. Only one treasure is available at a time. Once that treasure has been retrieved, the sailboat can activate another treasure. The sailboat must sail over an area of 11x11 pixels over the treasure figure in order to retrieve treasure. So that the ship will not collide with its treasure, the collision algorithm is skipped when treasure is retrieved. When treasure is retrieved, the treasure figure is erased, the “Loot” or score is increased by one, and the next treasure can be activated.