All Those Years Ago

By Kevin Ryan

Posted on March 13th, 2016

I worked on Zoo Master during my senior year the University of Oregon in 1983. It was written for the 48k Apple II Plus in 6502 machine language. The Apple II was 1 Mhz so you would want to do coding tricks like unroll your loops for speed. Most of the instructions took between 2 and 4 cycles.

I think I remember the resolution being 280×192. The Apple II also had a interesting way of specifying pixel colors. If two neighboring bits were set then the color would be white otherwise the color would be either red, green, blue, or purple depending upon if the pixel was on a even or odd screen pixel location and also whether the 8th bit was set or not. Three zero bits in a row would give you at least one black pixel.

zooMasterFront
www.topmeadow.com/plans/white720x4.jpg
At the time I did not have an assembler so I wrote it by typing in all the instructions in HEX code into the Apple. The branch instructions in 6502 were relative to the current instruction memory location. So if I wanted to branch forward to an instruction 10 bytes ahead I’d use $0A and for branching backwards I’d use a negative number like $F4. For forward branches I had to estimate how many bytes my code would need to jump over and then go back and fix the branch instruction if I got it wrong.

Since I wasn’t using an assembler everything ended up being hard coded to fixed memory locations on the Apple. The upshot of this was that I had to write bug-free code because they would be a pain to fix. I actually did have a couple bugs where I ended up I having to JMP to a free memory area do what I needed to do and then JMP back using some NOPs to clean up in the patch area. Went against my structured code college stuff, but what else could I do. I think there was an assembler available for the Apple back then, but it was beyond my college days budget.

Funny how I can still remember what hex values correspond with which 6502 instructions – for example:

$20 – JSR — jump subroutine

$4C – JMP  — jump

$60 – RTS — return subroutine

You had three 8 bit registers available to do computation with, but only the A register could be used for addition or subtraction. You could only increment (INX,INY) or decrement (DEX,DEY) the X and Y registers. There was an add with carry (ADC) instruction so you could do 16-bit computations easier.

I wrote this game for the technical fun of it. It was published by Earthware Computer Services, but never really sold. I actually played it online a few months ago somewhere online.

After Zoo Master came out I made my home town paper which made Mom and Dad proud.

zooMasterFresnoBee


Ropes in Contraption Maker

By Kevin Ryan

Posted on March 11th, 2016

Contraption Maker (CM) is a sandbox physics game that I developed along with Spotkin. It was built using a modified version of the Loom Engine, along with a few different libraries/components including cocos2dx and Chipmunk. After going through Steam’s early access program, the full game was released on Steam in the summer of 2014.

Getting realistic ropes working required tackling several different problems. It was mostly traveling development paths that others have already blazed and then making whatever adjustments were needed for my specific needs. This is just a quick overview of how I went about implementing them in CM and some of the potholes I hit along the way.

The Basics

The first decision made was exactly how much of a rope’s behavior I was going to model. Deciding exactly what elements or rope behavior to implement involved trade-offs affecting both performance and also design. For example, in their final incarnation, the ropes don’t collide with anything. So their only game play function is to transfer forces between the parts attached to either end. This was both a game design and a performance (speed of execution) decision. The performance was better because the code didn’t have to calculate all the collision and physics needed for the whole length of the rope cutting down drastically on the calculations needed.

This is fairly typical in the craft of game design and development in that you are always making various trade-offs. The relative sizes of the little guy, the dog, the mouse, and the soccer ball are game design decisions that bent reality for better game play possibilities.

Contraption Maker Characters

Contraption Maker Characters and Soccer Ball

I didn’t use the built-in ropes in the Chipmunk physics engine. The Chipmunk engine doesn’t have built-in ropes – easy decision. It does have a whole bunch of different types of constraints though, so my first thought was to use those to implement ropes. So browsing through the available constraints, using a slide joint for the two ends of the rope seems obvious. Maybe use the spring joint for all the points between the rope endpoints?

Speed of execution was a big concern. People playing CM are going to be able to create huge contraptions which could include ones with very many long ropes. Okay, first thoughts, rather than use Chipmunk’s general spring constraint, I’ll write a tighter custom spring-like routine specifically for our ropes with a focus on minimizing calculations needed and still simulate a rope in a way that looks and behaves realistically. I sketched out this fairly simple idea before writing any code.

Rope Design First Pass

Rope Design Ideas – First Pass

Constraining the Rope Ends

The slide joint constraint keeps two point-mass Chipmunk bodies within a specified range of each other. It is given the two bodies to constrain along with a minimum and maximum distance that the bodies should be from each other. Therefore each end of a rope is attached to a body – either to a body of a CM part or, in the case of an unattached rope end, to a physics body at end of the rope.

The slide joint is perfect for handling the behavior of the two endpoints of a rope. For ropes in CM the minimum distance is always set to zero and the maximum distance is the length of the rope. In the simple setup pictured below, a slide joint constraint is attached to the center of the static body of the hook and also attached to an offset of the center of dynamic body of the block.

Okay, great, first bit done, easiest code to write is code that someone else has already written. Now it’s time to take care of simulating the rope between the two endpoints – how it moves when it is slack. Note below that you can see how the rope passes right through the brick wall. As mentioned above, the ropes don’t collide with any other parts or with itself. My only concern with the internal rope movement was that it appear rope-like; it didn’t affect physics outside of itself. To do that I needed to break the rope into individual segments and then make move in a rope-like way. You can see each of the individual segments as purple dots in the picture below.

Purple dots for each segment

Purple dots for each segment

 

To make the display look like an actual rope it is then just a matter of replacing the purple dot artwork with rope segment artwork. The art is rotated to seamlessly join the individual segments. Here is the same setup with the purple dots replaced with rope segment art:

Artwork for rope segments

Artwork for rope segments

 

Details of Internal Rope Physics

Once I sat down and thought for a a while, I decided to go with verlet integration to take care of all the internal segments of the rope. It solves the problem very nicely and the code is very fast to execute. The process is:

  1. Use each segment’s current and previous location to determine velocity
  2. Add this velocity to current segment location to get new location
  3. Add in gravity (steps 1-3 are in first code excerpt below)
  4. Run multiple passes per time-step working towards getting neighboring rope segments a fixed distance apart. This is an iterative process where the more iterations the better the solution. A trade off between execution speed and robustness of solution. CM used seven iterations per time-step. (this is done in the second code segment below)

These four steps are explained and illustrated very well here: (http://blog.2and2.com.au/?p=883).

This is the code that applies velocity and gravity to each rope segment once per time-step.

IMPORTANT CODE NOTE: For reasons I mentioned in The Butterfly Effect, all the physics calculations are done using integers instead of floats so the code listed above is using int(s) instead of floats. There is some bit-shifting going on to keep the numbers within my fixed point number system where 65536 is equal to 1. The code is very simple:

 for (int i=0;i<=lastIndex;i++)
 {
    // Gravity (assuming only in y axis)
    CMRopeSegment *seg = static_cast<CMRopeSegment*>(mSegments->objectAtIndex(i));
    seg->mY -= gravityY;

    // Verlet
    int temp = seg->mX;
    seg->mX += (seg->mX - seg->mOldX);
    seg->mOldX = temp;
    temp = seg->mY;
    seg->mY += (seg->mY - seg->mOldY);
    seg->mOldY = temp;
 }

 

And here is the code that makes multiple passes per time-step through all of the rope segments:

// Run a few iterations to process all the links (defaults to 7 steps)
 for (int step=0;step<mIntegrationSteps;step++)
 {
    CMRopeSegment *prevSeg = static_cast<CMRopeSegment*>(mSegments->objectAtIndex(0));
    for (int i=1;i<mNumSegments;i++)
    {
       CMRopeSegment *seg = static_cast<CMRopeSegment*>(mSegments->objectAtIndex(i));
       int dx = seg->mX - prevSeg->mX;
       int dy = seg->mY - prevSeg->mY;
       int dist = tmSqrtShiftedInt32(dx * (tmInt64)dx + dy * (tmInt64)dy);

      // Keep in a sane range to prevent divide by zero from happening
      if (dist < 128)
         dist = 128;

      seg->mLength = dist;
      int delta = seg-mAdjustedLength - dist;
      tmInt64 percent = (delta * FLOAT_TO_INT64(0.7f)) / dist;
      int offsetX = (int)INT64_SHIFT_DOWN(dx * percent);
      int offsetY = (int)INT64_SHIFT_DOWN(dy * percent);
      if (i == 1 && firstIndex != 0)
      {
         seg->mX += offsetX;
         seg->mY += offsetY;
      }
      else if (i != 1 || firstIndex == 0)
      {
         prevSeg->mX -= offsetX;
         prevSeg->mY -= offsetY;
      }
      else if (i != (mNumSegments-1) || lastIndex == (mNumSegments-1))
      {
         seg->mX += offsetX;
         seg->mY += offsetY;
      }
      prevSeg = seg;
   }
}

Before the verlet integration is run, the slide joint constraint first adjusts the locations of the bodies on either end of the rope. The first and last rope segments are then set to the locations taken from where the slide joint has computed the bodies’ locations. These first and last segments are not changed by the verlet integration, only all the segments between these two are changed. The verlet code above is run adjusting all the positions of the interior rope segments and giving us nice rope-like movement, but they transfer no force to the bodies on each end of the rope.

Verlets give “springy” results which can be minimized by increasing the number of iterations run per time-step. Contraption Maker uses 7 iterations per time-step. You can see the difference below using two different iterations. Not really obvious here, but enough of a problem to be noticeable in the game is integration steps are too small.

 

intergationDif

Two integration steps takes longer to come to rest than the 21 step version. This is an example of “springy” verlet method.

Pulleys

The physics of direct rope attachments between two parts is now done. Next up was adding pulleys. There is no pulley support in Chipmunk, but I did find some code written for Chipmunk by Robert Blackwood that was based upon Box2d’s pulleys. I took that, modified it to work well with our system and eventually had pulleys working, albeit with some problems I’ll mention below. All the physics happens on the two rope segments hanging off of the first and last pulleys. All the parts of a rope that is between two pulleys is treated as a straight line with no physics processed for them. Any slack in the rope will only occur on the parts of the rope off either end of the pulleys.

The pulleys almost completely worked, but there was a problem that became very obvious when the bodies on each end of the rope have very disparate masses. This is a typical problem in physics engines where if you have two bodies where the ratio between the two masses is very great the physics can break down. And I mean break down in a very spectacular ways like this:

 

The Disparate Mass Problem

Problem with Disparate Mass

That is a fairly obvious problem, but there were also problems when the differences in masses were not as great – not as visible as above but still there. The system could get in a state where the forces acting on the bodies were oscillating back and forth causing jitters or slow rope stretching on one end of the pulley system. Problems like this are very hard to track down and fix because there is so much math calculations going on with different forces being applied at different places. Here is an example of the the log output that I would use to track down physics problems:

debugging

 

Using the balloon/wrecking ball as a good test case and tracking through what was happening with impulses and cached impulses, it looked like energy was not being lost when the balloon hit the pulley – ah, guess what – it was because the balloon wasn’t hitting the pulley – no collision shapes on the pulley. Problem identified – next step problem solution.

In Contraption Maker the pulleys did not collide with anything because this allowed them to be placed so they could overlap with walls and other parts. But this did not correctly resolve the situation like that pictured above where the length of the rope on one end of the pulleys goes to zero. To solve this I added a special collision shape at the point where the rope attaches to the pulley. This ad hoc collision shape on the pulley would then only collide with another ad hoc collision shape at the location where the rope was attached to a part.

Now the part collides with the pulley and the physics system can apply the correct forces on the bodies. Here’s the same pulleys system as above but now the balloon correctly collides with pulley. You can see how the balloon bounces off the pulley. Success. All is well in the CM world.

Disparate Mass Problem Solved!

Disparate Mass Problem Fixed!


The Butterfly Effect

By Kevin Ryan

Posted on February 29th, 2016

Chaos Theory

I have been reading Nate Silver’s The Signal and the Noise and in one of his chapters he discusses weather forecasting and chaos theory. Chaos theory is where very small differences in the starting conditions of a dynamic system can result in completely different final results.

He writes about Edward Lorenz, the man who coined the term “butterfly effect”. When Lorenz was working on a weather forecasting program on a computer they were getting widely divergent results. This was when running through the exact same code using what they thought was the exact same data. According to Silver sometimes the forecast would be clear skies over Kansas and sometimes thunderstorms.

They spent quite a while trying to figure out what the problem was. Eventually they tracked it down to the setting of barometric pressure in one area of the grid where the floating point number was being rounded differently. A difference of just 0.0002 in the barometric pressures caused huge changes in the final results.

Edward Lorenz: “Chaos: When the present determines the future, but the approximate present does not approximately determine the future.” – quoted from here

A second thing that Silver writes about is a European weather model. In December 1999 they were trying to make a prediction of the storm Lothar for Germany and France. The model was completely deterministic. They ran many simulations, in some modifying the barometric pressure in Hanover slightly and in others making a tiny change in wind in Stuttgart. The results would sometimes show clear weather in Paris and in others a huge storm. The fifty different forecasts from this model are pictured below.

European Weather Forecast

Contraption Maker

Now this discussion hit home for me because I’ve been working on Contraption Maker (CM) recently and had to deal with many of these same issues. Contraption Maker is a sand box physics game in the same vein as The Incredible Machine and is currently available on Steam. I’ve been working on it with Spotkin which is made up of my old Dynamix business partner Jeff Tunnell, his son Jonathon, and Keith Johnston. I was responsible for getting the physics right. To get a sense of the game, here is a user created perpetual motion machine.

A user created perpetual motion machine running in Contraption Maker.

When you have a contraption made up of possible hundreds of parts that are interacting with each other for hundreds or thousands of frames then the butterfly effect becomes very obvious. Move a tennis ball over by just 0.0001 units and it may bounce off a teeter-totter a fraction of a second later and then make something else bounce left instead of right and divergence is off to the races.

Floating Point

But as long as the initial starting positions of all the parts were the same then the contraption should always run exactly the same. This is where the floating point problem came into play. Contraption Maker is cross platform. It runs on Windows machines, Macs, mobile devices (very soon), and who knows what future devices. Is the CPU within all these different devices going to calculate floating point results exactly the same? One small difference messes everything up.

After some research online the answer I got was that if you set up things right then the answer was maybe “yes” and maybe “no”. There were also indications that some things like like sin, cos, sqrt, and others could be a problem.

I found this page which summaries a lot of what I found scattered across the Internet: http://gafferongames.com/networking-for-game-programmers/floating-point-determinism/

This wasn’t the completely definitive answer that I was looking for, but I got the sense that if I set up the compiler settings correctly it would probably work. Probably… made me a little uneasy. So I wrote our own routines for sin, cos, etc so that I knew that they would give the same results no matter what computer/mobile-device CM was running on.

At this point everything was going along fine. Contraptions were running exactly the same on Windows and Macs. Development was cruising along. Parts were being implemented. Floating point didn’t seem to be causing a divergence to occur. Some minor changes were needed to handle adding new parts to an already existing Contraption so that all the parts were still processed in the exact same order. A few minor bumps that were easily solved. And then the copy/paste problem reared its head.

The problem was that there would be a group of parts that did something neat and then you’d want to copy and paste that whole group of parts to another area in the world. With floating point you could not guarantee that they would run exactly the same. Floating point has that weird thing – the point floats. You have more resolution close to zero than you do farther out. So a group of parts close to the origin are not going to have the same floating point results as the same group farther away from the origin.

Argh… Integers

Argh, sigh… At this point the simplest solution was to just convert everything to be an integer physics engine. And do the same with the trig routines. I had had to do the same for The Incredible Machine because floating point just wasn’t fast enough back then. So that is what I painfully did. Here is a group of parts that have been copied and pasted and are running the same.

Copy and Paste group of parts running exactly the same.

Keith set up an automated determinism check where we have generated hash values for a few hundred contraptions that are calculated after each one has run for a thousand frames or so. This way we can just run “testcompat” and it then runs each of those contraptions and then compares their hash values with the saved hash values to verify that everything is running the same on all different machines.

So far so good – physics are matching as we start building mobile versions on new devices- and the hash value checks have also caught a few times where code changes made earlier contraptions run differently. Our goal was to never have an update make a preexisting contraption have a different result when run. The hash check let us find and fix these problems before an update was released.