Thursday, July 19, 2012

Classic Plasma Effect (1998)

In 1998 hardware acceleration for rasterization was gaining rapid ground, but many demos were still made using CPU-only approaches.  Though I was late to the party, and sort of alone in my basement, I wanted to try my hand at coding a few effects.

Here is a plasma effect I came up with (though I recall reading about the general principle somewhere, perhaps in a document found on a BBS).  It uses a precomputed height map; two 320x200 windows slide around over this heightmap in a lissajous pattern.  Every frame, the contents of both sliding windows are sampled from the underlying heightmap and summed into the framebuffer.  (You can picture this as two copies of the same heightmap sliding atop one another, with the computer screen displaying a screen-sized region of the result.)  The VGA color palette is setup as a smooth color ramp, and every frame the palette is rotated a bit to change the look of the plasma.


Friday, July 13, 2012

Jewels of the Oracle - Horse Puzzle Solver (1999)

For a programmer, there are always two games - the game, and the metagame. Often it's much more fun writing software to play the game for you. This is a post about a project I wrote in winter 1999.

I remember first trying the horse puzzle from Jewels of the Oracle. It is a puzzle where one must arrange nine squares by positioning and turning them such that each adjacent pair of edges matches properly. It seemed to me like a fun, straightforward programming challenge. You can see a screenshot of it here.

I threw a brute-force solver together using Turbo Pascal and ran it on our 486DX2/66, but that wasn't quite enough power for the task. Fortunately, my dad had just taken delivery of a Pentium II/366 laptop, which happened to be wasting cycles just then. I transferred the program over and my dad ran it in the background. After about a minute, the computer started emitting a loud hissing noise. Worried, we examined the situation closer and realized that the laptop's fans had kicked into overdrive, due to high and constant processor load... which yielded a solution in only a few minutes.

I never sat down to think about it seriously, but although the problem space of that particular puzzle is very large, I reckon the number of solutions is fairly large as well. Or it could just be that I got really, really, really lucky and that my encoding of the problem results in finding a solution so "low" in the problem space index.

The solver doing its thing.  Solutions flash by quite fast.
More solving work.
This following one actually represents a solution, whereby all 1's are beside 2's, all 3's are beside 4's and all 5's are beside 6's.

A solution.
I had at one point estimated that a Pentium III running at 600 MHz could probably exhaust the solution space in 45 minutes to an hour.

Sunday, July 8, 2012

Rock N' Roll Racing Codec (2003)

I am a huge fan of the game Rock 'N Roll Racing, by Silicon & Synapse (now better known as Blizzard Entertainment).  I must have spent twice the price of the cart on rentals.  One of my good friends landed me the actual copy of the game I used to rent all the time when the rental store closed down their SNES section.  Having beat the game innumerable times, I decided to take up a new challenge - to see if I couldn't reverse-engineer the password-encoding system.  The result was this:

Hand-written notes about password system.
Rock N' Roll Racing password codec application.
You can download the codec here (probably requires some antiquated .NET runtime, it was written just as .NET was coming to be):

Rock N' Roll Racing Codec

It was a pretty fun experiment, and I had initially written it up as a project hosted on the Waterloo Engineering student website server. Here is a slightly adapted copy of that post.

-----

The Basics

Passwords are encoded as three groups of four symbols each - twelve symbols total. On the password entry screen, the symbol table is laid out as such:

B C D F G H J K
L M N P Q R S T
V W X Y Z 0 1 2
3 4 5 6 7 8 9 !

If you count those, you’ll notice there’s thirty-two symbols.  (If you’ve ever played the game, you’ve also probably noticed that both 5 and S are symbols in that table and that yes, if you have chicken-scratch handwriting, you’re likely to write down or read your password back wrong, oh damnations of damnations.)  Each symbol represents one of 32 possibilities; 32 is 2^5, which that means each symbol encodes five bits of data.  Since each password is twelve symbols long, this means there are 60 bits of data in a password.

In my codec, I arbitrarily chose to use a simple numeric encoding as if the symbols were placed in rows:

00 01 02 03 04 05 06 07
08 09 10 11 12 13 14 15
16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31

Or, in hex:

00 01 02 03 04 05 06 07
08 09 0A 0B 0C 0D 0E 0F
10 11 12 13 14 15 16 17
18 19 1A 1B 1C 1D 1E 1F

As it turns out this maps in quite a straightforward fashion to the encoded information, and it seems somewhat likely the developers assigned a similar layout internally.  Now, what we need to figure out now is how all the game state information is encoded in 60 bits.

What’s encoded...

The game encodes the following state information:
Information # of Bits Notes
Money 3x4 Binary Coded Decimal (BCD)
Difficulty Level 2 0: Rookie
1: Veteran
2: Warrior
3: "Password"
Character 3 0: Snake Sanders
1: Cyberhawk
2: Ivanzypher
3: Katarina Lyons
4: Jake Badlands
5: Tarquinn
6: Olaf
7: ???
Planet 3 0: Chem VI
1: Drakonis
2: Bogmire
3: New Mojave
4: NHO
5: Inferno
6: ???
7: ??? (music)
Division 1 0: Division B
1: Division A
Vehicle 3 0: Marauder
1: Dirt Devil
2: Havac
3: Battle Trak
4: Havac “X”
5: Battle Trak “X”
6: ???
7: Air Blade
Color 3 0: Black
1: Blue
2: Red
3: Green
4: Yellow
5: Aqua/Purple
6: Orange/Green
7: Green/Green (duotone type deal)
Tires 2 0: Track Masters
1: Road Warriors
2: Super Mudwhumpers
3: Atlas Power Claws
Engine 2 0: Cobra Mark VII
1: War Hammer
2: Super Charger
3: Atlas Power Boss
Suspension 2 0: Grasshoppers
1: Hydrosprings
2: Hydro Twinpacks
3: Atlas Power Lifts
Armor 2 0: Defender
1: Rhino Skin
2: Saber Tooth
3: Atlas Powerplate
Front weaponry 3 VK Plasma Rifle, Rogue Missile, Sundog Beam (0 to 7)
Middle charges 3 Lightning Nitro, Locust Jump Jets (0 to 7)
Rear weaponry 3 BF's Slipsauce, Bear Claw Mine, K.OS Scatterpack (0 to 7)

...and in what format

So how does the game get all this information into 60 bits? If you add up the bits, it doesn’t even make it to 60 bits - only 44. The extra 16 bits are used for error detection, but not correction. This is what causes the game to know when you just input random characters as a password and hope for $500,000 in funds… ;-) instead you just get a beep and an “INVALID PASSWORD” error.

As it turns out, plain data is clearly segregated from the error detection bits. But first, let me explain how the bit layout works (or how it works with my codec, anyway). Here’s an example password:

XGL0 RS2V WS6M
  0-4            54-59

Each symbol represents 5 bits.  By convention (it seems the original programmers saw it this way too), let’s say bit 0 is on the left, so the X contains bits 0 to 4.  Likewise, the last symbol, the M, contains bits 55 to 59.  If we adopt this view of things, the 16 error detection bits occupy message bits 0 through 15, while data bits occupy message bits 16 through 59.

We are close to being able to assemble a complete password from this information, but there are a few more crannies to deal with. Certain bits are logically inverted - they use negative logic. This is noted in the following table, where the left column refers to this ficticious password:
ABCD EFGH IJKL


Bit 4 Bit 3 Bit 2 Bit 1 Bit 0
A !(!Char0 ^ !Diff1 ^ !Tire0) Engine1 ^ Diff0 ^ Div0 !(Engine0 ^ !$23 ^ !Planet2) !(!$22 ^ !Middle2 ^ !Planet1) !($21 ^ Middle1 ^ Planet0)
B !Color2 ^ $20 ^ Middle0 !Color1 ^ $13 ^ Rear2 !Color0 ^ !$12 ^ Rear1 $11 ^ Car2 ^ Rear0 Front2 ^ !$10 ^ Car1
C Front1 ^ !$03 ^ Car0 !Armor1 ^ Front0 ^ $02 Armor0 ^ $01 $00 ^ Susp1 Char2 ^ !Susp0
D !Char1 ^ !Tire1 Diff1 !Diff0 $23 !$22
E $21 !$20 !$13 $12 !$11
F $10 !$03 !$02 $01 $00
G !Char­2 !Char1 !Char0 Div0 !Planet2
H !Planet1 Planet0 Color2 !Color1 Color0
I !Car2 Car1 Car0 Armor1 !Armor0
J Susp1 !Susp0 !Tire1 !Tire0 Engine1
K !Engine0 !Middle2 Middle1 Middle0 !Rear2
L Rear1 Rear0 Front2 Front1 Front0
  • Money is encoded as three separate digits, representing thousands of dollars. For example, $293,000 is encoded as 293. In the above table these three digits are represented as $2, $1, and $0 (2, 9, and 3 respectively in this example). Since each digit can range from 0 to 9, four bits are required to represent each digit. These are denoted as $23 (MSB), $22, $21, and $20 (LSB) for the hundreds of thousands; $13, $12, etc. for the tens of thousands, and so on. 
  • Char is the character index.
  • Car is the vehicle index.
  • Color is the color scheme index.
  • Planet is the planet index.
  • Front is the front-facing weapon count.
  • Middle is the center charge count (nitro or jump jet).
  • Rear is the rear charge count.
  • Susp is the suspension level.
  • Engine is the engine level.
  • Tire is the tire level.
  • Armor is the armor level.

The Monster (2003)

An incomplete Lego construction that I'm documenting shortly here because it spent so much time gathering dust before I finally took it apart. The pictures aren't great, but such is life.

It was Lego monster truck/dune 2x4 buggy of sorts. It was relatively large, and as such, was quite underpowered by the Mindstorms motors. This was much to my chagrin, but the exercise in designing and building it was very entertaining.



It sported 4-wheel independent suspension built using Lego suspension arm parts, ending in sports car / F1 Silver Champion wheels. The drivetrain featured a twin-engine, twin-transmission system, so I guess it would be more appropriate to say there were two independent drivetrains. Each rear wheel was controlled by a separate motor. The trains were mirror images of each other, with each transmission supporting two reduction ratios (1:3 and 1:1 to the wheels). The gear ratio was locked manually before operation. I considered using a micromotor as an operator, but 1) I was missing ports on the RCX, and 2) after seeing how little torque I was getting at the wheels, the wind in my sails faltered.


Underside - you can see the steering motor at the very bottom, with the pair of transmissions just above. 
Rear of the vehicle, with both transmissions.
The transmissions and shifting levers (the grey axle terminators).  The propulsion motors are up top, and the steering motor is at the bottom right.
Another view of the same.  Transmission is in alternate gear.
Perhaps the coolest part of the monster was the steering system, and it's a shame I have no great pictures of it. The steering servo was at the very rear of the car, and driveshafts were routed through chassis all the way to the steering pinion. (You can see this on the underside pic above.) It was a standard sliding rack and pinion system that was assembled to work at the steep strut angle. I had to shorten the rack from the standard suspension setup in order to get the pivot points lined up properly and all the links operating in parallel instead of as just some weird four-bar linkage.

There was a light sensor encased in the chassis right behind and below the rack. It sensed the light level in a closed chamber that opened onto the underside of the steering rack. On the rack was a series of white and black 2x1 flat bricks that sealed the chamber; thus, as the rack moved back and forth, the proportion of black and white bricks that was exposed to the chamber varied, affecting the amount of light that bounced around inside the chamber. The inside of the chamber was fitted with aluminum sheeting to maximize the ability of the light sensor to detect the movement of the steering rack. The RCX monitored the varying light levels; after a calibration process, it was able to determine how the wheels are angled from the light level.

I also built a handgun-style controller for the vehicle, complete with analog bi-directional trigger (did you know the Lego touch sensors are actually pressure-sensitive?) and an analog steering wheel that uses the same principle as the steering: a light sensor on a coloured strip. There was an RCX on the remote that sent signals to the RCX on the vehicle; commands were multiplexed using a small protocol I threw together.

Low-res view of the unmolested remote.
You can sort of see the two facing pressure sensors, used to detect fore and aft tilt on the trigger.  The light-detection mechanism for steering was unfortunately busted at this point - I had dropped the controller during a move and not bothered to put it back together properly.
Another view of the same.