Blogs - kevryan

The Incredible Machine (TIM) is a computer game released in 1992 that is driven by custom physics and is very similar to Rube Goldberg and Heath Robinson machines. There were a few games in the series and it got a surprisingly large and loyal following. We won an “Honored Developer” award at the 1993 Game Developers Conference for it which I think was the first year that they gave out any sort of awards. I think I still have it somewhere - it was a pin or something like that. Later on TIM was inducted into Computer Gaming World's Hall of Fame which was a very pleasant surprise.

Oh this looks neat!

In the summer of 1992 when I was partway through implementing the original group of parts in The Incredible Machine, I read about Edward Fredkin and Tommaso Toffoli's Billiard Ball Computer. Roger Penrose also discussed it in his book The Emperor's New Mind which I was reading at the time. Along with a technical description it had a nifty graphic showing a billiard ball model for an AND gate similar to the one pictured below.

[caption id="attachment_387" align="aligncenter" width="400"] Modeling an AND gate with Billiard Balls[/caption]

Wow, that would be cool to implement! I realized that I already had the basic physics and collision frameworks in place and I could implement the needed parts in TIM without too much effort. Walls, incline, and balls were already working. Finding enough free time before shipping would be the constraint on whether I could get it done in time by the ship date or not. TIM had a very tight development schedule.

Coding The Incredible Machine

Coding on TIM started on March 26, 1992. I know that exact date from the title page of my design. On the day that I finished the design, I wrote the date on the title page, printed it out, went “whew, finally” and then immediately started coding in the unheated and unfinished basement of my home in Eugene. Note: this was not my parents' basement – I was married and had three young kids at the time. Once I week I'd walk over to Jeff Tunnell's office with the latest build on a floppy disk and show the build to everyone.

[caption id="attachment_388" align="aligncenter" width="500"] Title page of the original design.[/caption]

Collision System

The first order of business when I started coding was getting a collision system in place. No Google, no big Internet search space, so I ended up writing the collision code from scratch. I decided to go with polygon borders for all the parts. Everything had to be integers because at the time the speed of floating point operations on CPUs was slow.

The conversion factor for the 16-bit integers was: 1,024 in the physics space was equal to 1 in the screen space. A shift of 10 bits left or right would convert between the two coordinate systems. The 360 degrees of a circle were covered by 16-bits and went from 0 (0 degrees) to 65536 (360 degrees). In hex it came out as: 0x0000 flat facing up, 0x4000 vertical on left, 0x08000 flat facing down, and 0xc0000 vertical facing left.

All the parts collision shapes were defined by polygons which could be either concave or convex. The collision checks were line segment to line segment – projecting each point of the polygon to where the new position would be based upon the velocity, creating a line segment, and checking for collisions with other polygons. If a collision was found, then the projected line would be adjusted to the point of first collision.

As an aside, there are now terms for most all of this stuff which in many cases didn't exist at the time. Lots of ad-hoc development here – making it up as I went along. So the segment-to-segment check would be what is now called swept collisions. There was also a broad-phase collision check. The way collisions were implemented allowed me to do a bit check on the high bit and reject roughly half the checks – less calculations – important because frame rate was a big concern. The fastest code is the code that isn't executed.

The collision polygons for the Balloon and Birdcage became my debug test cases. I created graph paper version that exactly matched how they were represented in the game data. I would move the paper cutouts around by hand in various collision scenarios to verify that the code was working correctly. The hex values in the balloon and birdcage photos are the slopes of the line.

[caption id="attachment_391" align="aligncenter" width="549"] Balloon and Birdcage. Testing models and how they appeared in game.[/caption]

Physics Code

Written in parallel with the collision code was the physics code to apply forces to resolve collisions. Every part was a point mass with some parts being static and some dynamic. Each part had a density, mass, elasticity, friction, terminal velocity, and various other parameters. Sir Isaac Newton wrote the physics code for me roughly 300 years before TIM. I just had to put it in modern C code and make it fast and use only integers.

The structure for how the basic properties of the parts were defined is listed below. (Ugh, I don't like the code style I used back then). Those last elements in the struct are function pointers. They pointed to general routines for the parts and I would override them with pointers to specific functions for parts that needed them. TIM was written in C and this is similar to overridable methods in C++ although I wasn't familiar with C++ at the time.

struct part_elements
{
   short          density;
   short          mass;
   short          elasticity;
   short          friction;
   short          acel;
   short          terminal_velocity;
   TIM_VEC        max_size;
   TIM_VEC        min_size;
   struct shape   **part_shapes;
   SSHAPE         **super_shapes;
   TIM_SCVEC      *shp_offset;
   TIM_VEC        *shape_size;
   unsigned char  plane_num[2];
   short          num_borders;
   short          part_bin_order;
   VOID_BPARTFPTR bounce_func;
   VOID_PARTFPTR  internal_func;
   VOID_PARTFPTR  reinit_func;
   VOID_FPARTFPTR flip_func;
   VOID_PARTFPTR  resize_func;
   VOID_RPARTFPTR rope_func;
};

 

So Where is the Billiard Ball Gate in TIM

Short answer: It's not there. I ran out of time.

Slightly longer answer: I really wanted to make an adder just like the picture below instead of just making an AND gate. Defining the elasticity and borders needed for the billiard balls would have been very quick and easy, but getting all the parts lined up correctly even for just the simpler AND gate would have been more time consuming than defining the needed parts.

[caption id="attachment_393" align="aligncenter" width="620"] Diagram of an adder circuit.[/caption]

Game Dev Weight Loss Program

As best as I can remember, we shipped the first version of The Incredible Machine in mid-November of 1992. I remember that at the time getting to gold by mid-September was important for the Christmas season. Big orders by the distributors and stores were being made in September and then they'd duplicate a whole bunch of floppies and print up all the boxes. There was a lead time for all this so we would usually be shooting for mid-September to have a gold disk ready for shipment. It was a very bad thing to have bugs in the shipping floppy disk version because there was no simple way to get out an update.

So the summer of 1992 was a mix of implementing all the parts, tweaking the collision and physics code, and creating all the puzzles that would ship with the game. Creating new puzzles started becoming harder and harder. I was very busy and over that summer my weight dropped from 155 to a little below 140. It was fun! Really! I wouldn't still be doing games for all these years if it wasn't fun. But it was tiring too. Near the end of TIM development I started referring to it as a 6 month sprint.

[caption id="attachment_395" align="aligncenter" width="620"] Some of the puzzles from TIM. I would go through them all and reorder how they showed up in game to gradually increase difficulty for the end users.[/caption]

I just played the first version of TIM for the first time in a long time – a very long time. I had to buy it from the Good Old Games website because I don't have a running copy here. I see that Billiard Balls aren't even in the first version, but they did make it into the “Even More'” version where more parts and puzzles were added. And they aren't affected by gravity and are perfectly elastic so they had the correct physics attributes to implement the AND gate. But they would have still needed work to give each of them the exact same initial velocity when entering the gate and then there would have been lots of tweaking of position to get them working correctly.

Over the last year few of years I've been working on Contraption Maker with Spotkin. It is published on Steam and we continue to make updates for it. There is a different publishing paradigm in place. Now it is easy to do updates seamlessly to the end user. A Billiard Ball Computer is on my to-do list for Contraption Maker although the physics system being used would make it just a little harder because it doesn't use swept collisions. Maybe someday in an update I'll get it in there.

More Reading:

Conservative Logic a paper by Edward Fredkin and Tommaso Toffoli.

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.

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.

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: Gafferongames.com

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.

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.