Saturday, March 7, 2009

Clojure, Frozen Bubble, and how I learned to start worrying about my math education

So, I've been playing around with Clojure, reading the rough cut of Programming Clojure, (good book, so far), and was looking for a project to sink my teeth into in order to really get a feel for the language. Frozen Bubble, aka Bust A Move, has long been a favorite game of my wife, and while I tend to lose to my coworkers, should be interesting to implement.

Using a sample implementation of snake from the book as a template, I start hacking on the code, striping out all the snakey stuff, and just getting a minimal program that just displays a window. So, Frozen Bubble has only two real game objects: your target pointer, which ranges from -90 to +90 degrees, (a little less actually, no sense firing horizontally), and bubbles, which are in one of three states: not moving while in the initial position at the center of the bottom of the screen, stuck to the top of the game area (directly or via a chain of bubbles), and moving from the bottom of the screen to the top.

Well, the first state is easy, the third state is probably the same, but the second state has some unexpected complexity. First I think I'll give the bubble a location and direction, and handle the speed via the game tics. Seems reasonable, right? Then I run smack into something that makes me wish I had paid more attention in math class. The bubble has a direction, expressed in degrees, which I need to use to manipulate the location, which is expressed as [x,y].

Being a proper little reductionist, and stubborn enough to try to figure it out for myself instead of spending five minutes with google, I decide to think about the second simplest case, a 2x2 grid of pixels. (The simplest would be a single pixel, and I don't see how that would help at all. Perhaps I'm just not being clever enough, though.)

Anyway, this setup gives us the following:

Starting point: [0,0], 0 degrees (straight up or North) -> [0,1], 90 degrees (right or East) -> [1,0], and 45 degrees (NE) -> [1,1]

This says to me that if I want to work in single pixels, I have to do it in 45 degree increments. Not satisfactory. I can approximate closer and closer angles by using a larger grid, (why do I feel like this leads to calculus?) But that means that I'm not working with single pixels anymore.

I went and read some things at Better Explained, which while fascinating in their own right, (I love that site), didn't seem to help matters. I think the gap is that the actual position in real space would be floating point (well, kinda), but the game space in measured in integers (pixels).

Grabbing my trusty graph paper, I start diagramming. A 3x3 grid only buys me two new angles: 22.5 and 67.5. 4x4 gives me 0, 15, 30, 45, 60, 75, & 90.

I now have:
2x2 = 4 squares = 3 angles
3x3 = 9 squares = 5 angles
4x4 = 16 squares = 7 angles
5x5 = 25 squares = 9 angles, etc.
which generalizes to: AxA = A**2 squares, and 2A-1 angles
So to represent all 90 degrees, (which is actually kind of arbitrary anyway), I solve for 90 = 2A-1 = 45.5 squares to a side. My screen resolution on my laptop is 1024/768, so using the height as a guide, if I want to update to bubble position by individual degrees, I can only do it ~16 times from the bottom to the top of the screen. Clearly less than ideal, some sort of approximation is called for.

There are two ways that I can think of to do this off the top of my head for a 2x2 grid update: splitting the difference evenly, (i.e. a 20 degree angle will be bumped up to 45, or it can be rounded to the closer number, in this case 0. The rounding case seems more rational.) Obviously I want to stagger the updates to get the closes approximation to the actual angle I can, but a constraint I'm operating under is to have no other state saved between updates than location and direction. Ummmm.....

The only option I can see is to manipulate the direction each time so that after ~45 pixels, it arrives in the correct place. However, my laptop battery is about to die, and it's late, so I think I'll sleep on it and continue this later.