Part 14 Collisions

Graftgold Memories.

Once we ordered some Commodore monitors for our graphics artists to use with DPaint. When they came the quality was really bad compared to our existing Commodore monitors. The focus was poor, the colours were skewed and the sound was really tinny. Ok artists don't need sound but they also tested games and played in the lunch hour. We decided  to send them all back but the seller said they were ok.  I happened to meet the Commodore CEO to discuss writing for the cd version of the Amiga and he said that model of monitor was rubbish with less parts for cheapness and he would sort it out. Unfortunately Commodore shut up shop shortly afterwards and we were left with bad monitors and unsellable CD32 work.  Commodore always promoted its computers as business machines and did not seem to recognise until it was too late that they were fabulous games machines. They were on the whole good robust machines but the slowness of the C64 disk drive used to drive us mad, and it had its own computer in the box.

Deepest Blue Progress.

I had been doing loads of techy stuff the previous month so I thought I would get that all installed in the game and do a bit on the game play.  I installed the network stuff and changed the key input routines to cooperate with the network code. That's when I realised I would have to add more code to pass across the results of any ship controls altered by the player. I still needed to finalise the ship control panel so I shelved the network game for the moment.

"I often have disagreements with myself"

I played around honing the enemies flight routines to give an effective dogfight. Its a good job I haven't put the player damage in yet as they are pretty good at pasting me. I started work on an Ai system based on Avalon's meanie movement system. A table of random weightings is used to chose from several standard movement patterns. These are indexed by ship type and the morale of the pilot.

Thus a really frightened pilot runs away,  an uncertain pilot tries sporadic attacks, a gung ho pilot continually attacks.  Movement pattern primitives are things like chase, run away from, keep distance from,  keep side in line with target.  I decide to mull the design of this over for a bit before fully integrating it. I need to identify all the things I want ships to do. It may be better to write several high level move routines rather than one data driven routine. While working on my own I often have disagreements with myself.  You have to challenge your ideas to make sure they are sound.

I needed to add code to the shield routines. I had basic stubs using energy but not responding to hits.

This in turn needed code in my collision routines. I had  basic top level collision system in place. This was a 3d version of Graftgold's old collision system. This used an array for each axis. Each object has a bit place and marks its presence by setting its bit in the array at the appropriate place. To see if a collision has occurred the array contents for an objects position on each axis are Anded together. If any bits stay set they must be at the same position. The brilliant thing about this method is you are testing up to 32 objects a time with a couple of And instructions, so it beats most other methods for speed. Its downfall is that objects need to write in each axis a few times to represent their size. I decided that I would try a brand new system because I had big differences in the sizes of my spaceships. Normally I would choose the size of the step along each axis to be  about the length of the smallest object. However large ships or space stations would have to write and examine many steps.

I played about with designs on paper and a solution came to me as I woke up one day. I grabbed a pencil and scribbled it down on an old birthday card.  The new design can be summarised as:

A collision object for each game object that collects collision variables to minimise cache breaking.
A link list for each axis.
Each collision object to have a start and end position for each axis. These are kept in the link list for the matching axis. The link list pointers for an object all existing in the collision object.

The list is initiated by adding each of the objects start and ends to each axis. To add a start the list is scanned like an insertion sort. Every time a start is passed its overlap count is incremented. Every time an end is passed its overlap count is decremented. Thus passing both a start and end of the same object balances to zero as it doesn't overlap.  Then the end is adding scanning from the start. Every tine a start is  passed the inserted objects overlap count for the axis is incremented.  Thus overlaps are owned by front most object of the pair in the list to prevent double collision processing.

When the objects moved they have to adjust their position in the list and the counts.

To process collisions the plan was to scan the X list till I found an object with an overlap count.
If it also had a Y and Z overlap count I would scan the axis that had the least count from object start to end.  Any two axes could possible have a large amount of overlaps if the objects were in a line. Choosing the axis with the least number of overlaps prevents excessive processing.

"Then I spotted the fatal flaw"
I wrote and had almost finished testing the routines, then I spotted the fatal flaw.  An object may "own" the overlap on one axis but not necessarily the other two. In other words it may have the lowest X but a higher Y or Z.  Its really annoying when you spot a defect in design at a late stage. I reverted to just scanning the X axis from object start to end and testing the other two axis positions of any objects whose start I found. I have a plan to fix it properly letting objects include all overlaps in their counts.

Squadron of friendly scouts used for collision testing

My ships are made up of sub objects so my second level collision system refines the result of the first routine by considering the size and position of all the parts. When I know the parts that collided I can call the damage routine. Thus specific systems can be damaged by shooting the part of the ship that houses them. I already had a damage field in the parts of my ship. I decided to have a fraction that is just used as a multiplier. 0 means completely dead, 1 means fully functional. The damage repair system then gradually returns the fraction to 1.

I  decided on a 4 way shield system allowing an easy display of shield energy allocation. A square  will be divided diagonally into 4 to represent the 4 shields. The player can drag  the centre point to resize the shields, the bigger the more energy is allocated.  I wrote the code to maintain this but need to write the 4 way slider control.

"I gave up for a few days
To test all this I started dog fighting with the AI ships. I had a few too many issues to sort out so took out the enemies movement to check the collisions. I could then aim my ship at an enemy and see how it collided. I had added a rigid body bounce using the momentum of each ship so that large ships bounced less than small ships. Annoyingly ships seemed to collide when they were too close and the pass through each other. I traced the  code that calculated the result velocities and double checked the signs and tests. You must collide if you are already moving away for each XYZ component.  I gave up for a few days and when I went back realised my basic mistake. I had calculated relative velocity
by  taking object 2 from object 1 so I could use formula for hitting a stationery object and add back the object2 velocity at the end. I calculated relative position the same way by taking object2 position from object 1. However this reverses the signs. You need to take object 1 from object 2. So much for symmetry I was sure I had to do both the same way. Never assume, I should have checked the very first line of the routine rather than spending days going over all the complicated calculations.

Never mind, I spotted several ways of optimising the momentum calculations. Formulas tend to show results when object2 is stationery. You can just as well take off the velocity of object 1 , considering it to be the stationery object. Then write down a new set of equations. By using part of the first set and part of the new set I found I could use the same ratio derived from the masses of the objects rather than having to calculate two very different ratios.

At last ship ricocheted of each other properly. My collision sizes needed adjusting. They are part of the models 3d data. I keep a x,y,z  bounding box size and a max radius for quick checking. I need to look at the model creation code to correct these.  I could also add a square of the radius to save having to square it when comparing to the square of the distance.  (Distance between two points in 3d would involve a square root so its more efficient to use the distance squared for comparisons.)


"Sometimes I find it best to switch my laptop off "
It was a tough slog this month, progress was really slow at times and has ground to a halt as I try to work out how to apply angular momentum to my collisions. To fit in with the ships controls I need to decompose angular acceleration to Roll, Pitch and Yaw. This depends on the vector between the objects and the closing velocity.  I could use the difference between these to give me a turning vector but they need to be unit vectors , or at least the same scale and that involves a couple of square roots.
I want to have ships spinning  out of control like Darth Vader at the end of the first Star Wars.
Sometimes I find it best to switch my laptop off and get my notebook out and have a real think about something. I have an electronic drum kit and love to take my frustration out on it now and then.

Programming Tip.

When I code a complicated routine I consider how I am going to prove it works. I will often code a routine to perform health checks. For example I knew my link lists and overlap counts could easily go wrong as there were several complicated algorithms updating them. So I coded a list scan that recalculated all the counts and counted objects and checked the results against each axis. I then called this after each update finding many mistakes. I keep these test routines as they are often useful later on if a bug has been introduced.

I run a battery of tests while debugging  to check critical routines such as the memory allocation system. These detect and report on any corrupted memory blocks, unallocated blocks and give me a usage profile. These are invaluable when something goes really wrong. Catching memory corruptions at the earliest opportunity in a controlled way gives  a clue as to which routine was the culprit.