Gravity Beam Source Code Documentation

9th November 2012


Style conventions

Variables for ingamey use are in lowercase with underscores for spaces. player_position_x. This is how I do my variables in C.

Constants are in uppercase with underscores for spaces. CARRYBOX_INITIAL_HEALTH... unless they interact with graphics, in which case they're probably camelcase too.

Labels are lowercase with underscores for spaces. game_init.

Variables that interact with the custom chipset are usually in camelcase and have a prefix indicating what they contain. Ptr_CopperlistData. This is usually because these are derived from the example code in the Abacus Amiga System Programmer's Guide. Constants related to the handling of graphics data are like this too.


Graphics modes

All the screens in Gravity Beam use a 6 bitplane, dual playfield mode: BPLCON0 = %0110011000000000. No hardware sprites are used. The game is timed to perform all graphical updates during the vertical blank. Usually works. Uuuusually.

The following settings are used to define a 320x240 screen, with DDFSTRT set to read an extra word to allow hardware horizontal scrolling.

DIWSTRT = $3081
DIWSTOP = $20c1
DDFSTRT = $0030
DDFSTOP = $00d0

Playfield 1 is the 'canvas layer', and is largely used for large scrolling static elements like the menu background, ingame Martian landscape and result screen blue screen.

Playfield 2 is the 'sprite layer', and is reserved for drawing small sprites and text using the blitter without affecting the contents of the canvas layer.

The sprite layer is slightly bigger than the visible area of the screen. The extra space is used to allow for drawing of sprites slightly off the sides of the screen. There are unwanted graphical artefacts produced by the blitter when trying to draw a shifted, masked sprite while omitting some number of leading words.

The sprite layer does not use hardware scrolling. The intention is that the contents of the sprite layer are erased and redrawn every frame.

Interleaved graphics

All graphics modes use interleaved bitplanes.

Interleaved in this context means that the first row of data contains the values for the first bit of the first pixel row, the second row contains the values for the second bit of the first pixels row, the third row contains the values for the third bit of the first pixel row. The fourth row of data then contains the values for the first bit of the second pixel row.

Interleaved bitplanes allow for the drawing of sprites using the blitter with a single invocation; to the blitter, the sprite layer appears as a 24 word by 720 bit-row array of bits. To request a sprite draw, you direct the blitter to draw (sprite height * no bitplanes) bit-rows of data.


Title screen

The Gravity Beam title screen constantly rewrites its copperlist to all for its palette changes and playfield scrolling. It uses double buffering for the copperlist.

The 'canvas' layer is used to display the Mars background only.

The 'sprite' layer is used to display the Gravity Beam logo, the cartoon Greenwing and then the Press Fire to Start caption. The bitplane image memory associated with the 'sprite' layer contains the Gravity Beam logo, the cartoon ship and the caption all adjacent to one another. It is the responsibility of the routine title_construct_copperlist to read the title_screen_* state variables and construct a copperlist which uses WAIT commands to start and stop the 'sprite' layer bitplane display at the appropriate screen positions, and initialise the bitplane data pointers appropriately.

It's simpler to think of the bitplane playfield display as two 'cursors' (or 'pens') running down the screen. When the beam reaches a certain point, the copperlist starts drawing the Beam logo, then stops, then draws the ship, then stops.

The routine is quite longwinded because it has to be perfectly aware of the order of the screen elements. The order is: set up screen, draw logo, palette changes for logo, draw Mars, stop logo, start ship, palette changes for ship, stop ship, draw caption, palette changes for caption, stop caption.


Helical memory layout for scrolling level

This algorithm was based on the documentation for 'Scroller_XLimited' from ScrollingTrick.lha by Georg Steger, available on Aminet (http://aminet.net/package/dev/src/ScrollingTrick).

It was later improved to reduce Chip memory requirements and as a result it's closer to the two-dimensional examples from the same archive.

Gravity Beam levels are composed of a grid of 16 pixel x 16 pixel tiles. Instead of storing the entire level image in memory at once, Gravity Beam uses a '2d-helical' memory block for the canvas layer.

The visible screen area is shown by the blue outine. With hardware sub-word pixel scrolling, we need to take into account an extra word of pixels, effectively extending the side of the visible screen by 16 pixels. This is shown by the green outline.

As the screen scrolls in one direction, the bitplane pointers into the canvas layer bitplane memory block are changed. This moves the 'visible frame' into this memory block around. As the visible frame moves along the screen, it will reach the limit of drawn tiles. When one of these boundaries is crossed, new blocks are blitted on the oncoming edge.

The image on the left shows what is displayed on screen when the camera has been moved to the right: the bitplane pointers have been increased and the world appears shifted to the left.

The image on the right shows the state of the canvas. Tiles on the left of the canvas have been drawn over. The colours of these new tiles appear distorted because the memory locations for the values for bitplane 2 of the left of the canvas are the same as those for bitplane 1 of tiles with X positions beyond the right of the canvas.

To move the camera to the right (scrolling the visible level to the left) by sixteen pixels, the bitplane pointers are increased by 2. To move the camera to the left (scrolling the visible level to the right) by sixteen pixels, the bitplane pointers are decreased by 2. Sub-word scrolling is achieved using the bitplane control registers.

If you keep increasing the pointers, the visible frame on the canvas will keep looping left to right across the canvas. The player only sees what's in the visible frame, and so it appears that the world is scrolling horizontally. Although it may appear from the diagram that the x-coordinate of the drawn tiles loop, the bitplane pointers are monotonically increasing as the memory is contiguous.

CanvasWidth is set to ScreenWidth + 32. This extra size means that there shouldn't be any need to worry about half-destroyed blocks as in Scroller_XLimited.

To move the camera vertically, the bitplane pointers are increased or decreased by the size of a horizontal row of pixels worth of data: ((16*CanvasWidth*BITPLANES)/8). This means that the canvas has to be as tall as the world, and have extra pixels reflecting the added 'vertical' part of the screen when the visible frame is scrolled all the way to the right.

As for the horizontal case, tiles are drawn at the advancing edge of the displayed screen as the camera moves. Unlike the horizontal case, the vertical position of the drawn tiles DOES loop; the vertical position of drawn tiles is modulo the height of the canvas bitmap data area.

This necessitates the use of the copper to split the screen into two horizontal slices, described below in 'Ingame copperlist generation'.

CanvasHeight is set to ScreenHeight + 32. This extra size means that there shouldn't be any need to worry about half-destroyed blocks as before.

After the blitter has been prepared by calling the routine preparetodrawcanvasblocks, the routines drawacanvasblockrow and drawacanvasblockcolumn draw multiple rows or columns of blocks to the canvas area.


Ingame copperlist generation

The ingame copperlist is the most complicated copperlist in Gravity Beam. It is re-generated algorithmically by the routine ingame_update_copperlist every frame based on the camera x and y position and the fade value for the canvas layer. The ingame copperlist has the following responsibilities:

In order to produce a copperlist with the above effects, ingame_update_copperlist does the following:

Because the copperlist can only function if all its commands are sorted in increasing vertical order, but the background gradient bars and the bitplane data split can occur at any location on the screen, I use an interim data structure that can be random-access populated with data representing the copperlist commands.

The interim data structure is an array of 16 [word-word] pairs representing the copperlist commands.

The most significant word (held in the lower two addressed bytes) holds the colour value that COLOR07 should be set to on this line, or $FFFF to trigger the bitplane data split.

The least significant word (held in the higher two addressed bytes) holds the y-coordinate that should trigger this action. $0000 represents 'skip this line' and $FFFF for 'end of list'.

The following table shows a sample interim data structure:

ValueLine
ingame_update_copperlist_interim_record_list:$0000$FFFFA line of $FFFF means 'end of list'.
$0000$0000
A)$0804$00E0
$0000$0000
B)$0703$00C0
$0000$0000
C)$0603$00A0
$0000$0000
D)$0502$0090
$0000$0000
E)$0402$0070
$0000$0000
F)$0301$0050
$0000$0000
G)$0201$0030
$0000$0000
ingame_update_copperlist_interim_record_list_high_address_end:

The list should be read backwards from ingame_update_copperlist_interim_record_list_high_address_end until the $FFFF at ingame_update_copperlist_interim_record_list is reached.

Rows G) through A) represent the background gradient bar commands. There are always seven commands and they are always located in these rows. Notice that the vertical position increases in value (the vertical beam moves down the screen) from G) to A). This series of commands places successively lighter shades of purple into COLOR07 every $20 pixels. The vertical postion value for these commands is based on the value of new_cam_y. As the player moves deeper down into the level, the bands rise upwards (their position values are decreased). The colour value part of these commands is also faded by the value of ingame_palette_fade_decay_value, similar to the rest of the canvas layer palette.

The rows interleaved between G) through A) are vacant rows into which the command for the copperlist split point can be placed.

The vertical location of the copperlist split point is independent of the location of any of the colour gradient commands. There may not even be a copper split point present at all. (This is the case if the resultant y coordinate of the camera is between 0 and 32: if this occurs, the screen can be displayed as one contiguous whole.)

If the copperlist split point is present, then the list is traversed from ingame_update_copperlist_interim_record_list_high_address_end backwards to find a vertical position greater than that of the copperlist split point. Then the cursor is wound backward (increased in memory) to the next vacant row and the copperlist split point command placed there.

The result is that a list of commands sorted in ascending vertical position is produced in linear time.

To translate the interim record list into copperlist commands, the list is parsed backwards in memory from ingame_update_copperlist_interim_record_list_high_address_end, and continues until the $FFFF at ingame_update_copperlist_interim_record_list is reached.

If a special 'Line' value is encountered, the row is either skipped or translation terminates.

Else (if a non-special 'Line' value is encountered), the Line value is compared against the recorded previous Line value to determine whether a new copperlist WAIT command needs to be constructed. If a WAIT is necessary, then a (line&$ff)+1,$fffe WAIT is appended, with a one-time $ffe1fffe WAIT also inserted when the Line counter exceeds line 256 for the first time as this is necessary to schedule WAIT commands beyond line 256.

Then the 'Value' is checked. If 'Value' is not $FFFF, then the row is interpreted as a background gradient colour change and a COLOR07, value pair is appended to the end of the current copperlist.

If 'Value' is $FFFF, a series of commands is appended that alter the bitplane data pointers for the canvas layer playfield to point a new value. Regardless of the value of new_cam_y, these pointers always take the value of Ptr_CanvasData plus ONLY the horizontal contribution to the bitplane pointer. This is because the second half of a split screen will always begin on line 0 of the canvas data area.

The copperlist must finally be terminated with $FFFFFFFE.


Polygon collision detection

Summary

Gravity Beam levels use a list of convex polygons to define where the 'interior' of the level mass is.

The image on the left shows the physical layout of the level from the tilemap. The image on the right shows the collision mass. The different colours indicate where the different convex polygons lie on top of each other.

There is one collision query used in Gravity Beam: 'is the given point within any one of a list of convex polygons?'. The order of the polygons in the list does not matter. The routine considers the polygon list as a jagged mass with an outside where the ship and box may freely move (the black) and an inside where no object can go (the colours).

Every frame, for each object (just the ship and the box), a new potential position is calculated by adding a multiple of the current velocity (implicity first-order integration) to the current position. This new position is then tested for collision using the routine. If the new position is outside the collision mass, then the object can be moved to the new position. If the new position is inside the collision mass, the object's position is not updated that frame. For the ship, a collision sets the velocity to zero. For the box, the velocity is inverted.

Maths

To determine whether or not a point is inside a convex polygon is really easy.

Say you've got a function d(p, A, B) that takes a point p and a directed line defined by two input points A and B, gives you the distance from P to the line AB as a signed real value:

If your point is above the line, it's in the white area and d is positive. If your point is below the line, it's in the red area and d is negative. If the point lies on the line d is equal to zero.

The line divides the infinite space into two halves. If you were to stand at A and walk towards B, the red area is defined as the area on your right.

For a convex polygon made of multiple lines, each line defines a new coloured half space. The area where all three different colours coincide, is the interior of the polygon defined by the lines!

For a triangle A, B, C where the vertices are ordered clockwise, you can use the following to determine if a point is inside the triangle.

If d(p, A, B) is negative
AND d(p, B, C) is negative
AND d(p, C, A) is negative
then point P is inside the polygon.

This works for a convex polygon with any number of vertices.

If you invert everything, the test becomes even more straightforward:

For each line of the polygon:
  If the point p is on my white side, it's outside this polygon.
If point p is not outside any of the lines of this polygon, then it must be inside this polygon.

The formula for d is:

d = det(B-A A-P) / | B - A |

If the distance B-A is unit length, then we can forget about the division. d is now the distance squared but it's still got the right sign. I replace B with B', which is a unit distance from A in the direction AB. Now the calculation can be unvectored and looks like this:

d = (B'.x - A.x)(A.y - p.y) - (A.x - p.x)(B'.y - A.y)

But that's a lot of work! Asking the Amiga to do all that is too much.

The calculation for d can be simplified if it's restated in the form d = (1) + (2)*p.y + (3)*p.x, where the three constants (1), (2) and (3) are fixed for a given line AB.

(1) = A.y(B'.x - A.x) + A.x(A.y - B'.y)
(2) = A.x - B'.x
(3) = B'.y - A.y

(1) can take any value. (2) and (3) are always going to be in the range -1 to 1 because AB is unit magnitude.

I precalculate these values for every polygon in the level.

If you test d against a constant rather than zero (remembering it's signed squared distance), you can expand or contract the outer border of the interior polygon collision mass arbitarily. One way of considering this is you're giving point p a radius (squared) equal to the size of the constant.

Note that a video graphics universe will have positive y values downwards and negative y values upwards. If you implemented this algorithm as described above and didn't take this into account, the test would always return false (point p cannot be in all the external zones simultaneously). To account for the flipped y coordinate, you can either negate all the Y coordinates in the calculations or use anti-clockwise winding on all your polygons.

What happens if you don't specify a closed polygon? If you don't close the polygon (you make a 'two sided triangle), you define a wedge-shaped region that extends infinitely in the direction of the missing line. I use this a lot to define regions that should extend infinitely: a single line polygon defines a half-space as interior (like the very lowest floor part of a level), a two-line polygon with a right angle defines a 'box corner' shape as interior (like a sticking out corner that extends infinitely towards the sides of the level).

File format

The polygon data for level x is stored in levelx_polygonbinary_v2.bin. It has the following file format:

for every polygon
  length of polygon entry in bytes  : 16 bits  {  polygon prefix = 1 longword
  split-space bitmask               : 16 bits  {

  for every edge in the polygon                
    constant1                       : 32 bits  {  set of constants = 2 longwords
    constant2                       : 16 bits  {
    constant3                       : 16 bits  {

  0x80808080                        : 32 bits ; this is the end of current polygon marker.

0xf0f0f0f0                          : 32 bits ; this is the end of entire polygon list marker.

The polygon length entry gives the length of the entire polygon in bytes, including the end of polygon marker.

The split-space bitmask is a precalculated quadtree-like bitmask indicating what sub-spaces this polygon overlaps.

constant1 is stored as 24.8 signed fixed point.

constant2 and constant3 are stored as 8.8 signed fixed point. They are used directly in a MULS calculation, so they have to be 16 bits. By MULSing these 8.8 fixed point values with point p's position in whole-number pixels, the result is in 24.8.

split-space bitmask

Gravity Beam levels are always 1600 pixels wide by 1600 pixels tall.

The split-space bitmask considers the world as 16 equal square cells, with 0, 1, 2 and 3 along the top row, 4, 5, 6 and 7 along the next row and so on.

Each polygon is tested for the cells it overlaps. If the polygon overlaps a cell, that bit is set to 1 in the bitmask.

The large blue triangle occupies cells 2, 3, 5, 6, 7, 8, 9, 10, 11 and 15 and therefore has a split-space bitmask of $37F1. The small blue triangle occupies cells 12 and 13 and therefore has a split-space bitmask of $000C.

The polygon collision detection routine determines the cell point p currently occupies and bit tests against the bitmask. If the test sets flags to equal then the point p cannot be inside the polygon because it's not inside any of the cells in which the polygon resides. The entire polygon can be skipped.

Testing against all of the edges of the red triangle using multiplications is fruitless if you know already that the object is in any one of the many unshaded cells. The bit test is considerably faster than entering the edge test loop.

Assembly routine: polygon_collision_detection

The routine polygon_collision_detection detects whether the point (d0,d1) given in whole pixels is inside any of the polygons defined by the current level's collision list. d2 is 1 if there's a collision, 0 if not.


Game screens and phases

Overview

There are four screens in Gravity Beam: the title screen, the level select screen, the ingame screen and the results screen.

Each game screen has an entry point label ending in _init: and a frame advance label ending in _frame:.

Each game screen has its own set of (global) variables.

The game program transfers control to a screen by directly jumping to its _init: label. From there, the screen now directly owns the program flow. There is no stack of screens, no 'frametick' or 'render' subroutines or variable indicating the current screen.

The game screens transfer control to one another by jumping to the new screen's _init: label. Almost all of the game runtime is spent within by a screen (the exceptions are the entry point and the cleanup code).


Source file list

maingame.asm

Contains the main game! All of the different screens are smooshed together... roughly in the order 'title', 'level select', 'ingame', 'results fade', 'results'.

protracker.asm

This is the Protracker V2.3A Playroutine VBlank Version 2. Modified with a safety feature for null pointers.

joystick_mouse.asm

Contains routines allowing for reading of a standard Port 2 Joystick and mouse combination. These routines are designed to use a 'poll and store state' type of input.

routines_maths.asm

Contains routines for the following:

sinetable.bin

Contains a 256-entry table of sine values in 2.14 signed fixed point.

chipsetconstants.i

Include file containing a list of all the necessary Amiga custom chipset hardware memory locations.

As I built Gravity Beam out of the bitplane example code in the Abacus Amiga System Programmer's Guide, the chipset constants started off as a small number of lines at the start of the .asm file, which was then added to constantly until I moved it to its own file.

As a result, I've got yet another incomplete chipset constants file, hooray! But it does the job, and that's what's important.

level_manufact\

level_manufact\ is where the levels are converted from their .asm intermediate forms into the final forms compatible with the game. It contains make_levels.bat, a match file used to create the original Gravity Beam level set.

Creating a Gravity Beam diskette

During development, the directory gravity_beam\ should be mounted within WinUAE as as a hard drive DH0: named beam:.

From this point, open a shell and navigate to the beam: directory. Type GravityBeam to play the game.

To convert this directory tree into a bootable Gravity Beam diskette, use the following method:

The GravityBeam: disk should now be a perfectly standard bootable disk containing the GravityBeam executable, all the necessary game files, all the AmigaDOS-y environment and boot files and all the Workbench-friendly launcher files.

Game disk file list