steamknight.com

In my previous post I mentioned that we’d talk about how we store the state in Ataxx, or as I’ll call it from now on, Pookie Pookie.

Not all squares on the 7×7 game board are free, some of them can have a wall or obstacle, making that particular square permanently occupied. The walls are mirrored on all four quadants like these examples:

If we label the squares in the top-left quadrant 0-15, we can encode the walls with 16 bits, where a 0 signifies an empty square and a 1 is a square with a wall. The previous 3 examples would be encoded as 0111100010001000, 000000110100010, and 1000000100100100 respectively or 0×7888, 0×01A2, and 0×8124.

Note that bits 3, 7, 11, 12, 13, 14, and 15 are shared between two or more quadrants. Because the players always start at the corners, bit 0 can never be 1 so there really are 2^15 possible board layouts. Of those 32k board types, many will result in the players being “locked in” unable to move causing the game to automatically end since there are no more moves. It takes a minimum of 8 “on” bits to make sure that the game is over before it starts. I find that 6 “on” bits is about the most you can do and still have interesting playable boards, so really, the number of functional game boards is much smaller.

Weird Math…
If I’ve done my math right, any 6 bits out 15, 5 out of 15, 4 out of 15, 3 out of 15, 2 out of 15, 1 out of 15 and all zeros are valid boards. “X choose Y” is calculated by so the equation should be which should equal to 9949 boards! If someone sees fault with this, please let me know

Now that we know how to encode the board type, how do we encode the board itself?

Assuming we do a two player game, each square can have one of four states: it’s free, it has a piece from player 1, it has a piece from player 2, or it has a wall. (4 player is similar, just requires a little extra work). Since we have 4 different states we can encode each cell with 2 bits, making each row 14 bits. If we squeeze this into the lower bits of a 16-bit integer, the whole board gets encoded in 14 bytes! How’s that for frugal?

We’ve accomplished a few goals by having created such a small data structure for the representation of the board. We have very little data that we have to transfer in a multiplayer game over the ‘net, and we’re minimizing the ammount of memory needed by the AI to figure out what move to make. As well see in the next post, we’ll be very glad that our board data is so small!

Also, I promise that the next one will have less math, certainly it won’t have any equations!

Marty, fire up the Flux Capacitor with 1.21 gigawatts bacause we’re taking the Delorian Back to… 1999!

It was the summer of 1999 and people were scambling to save us from Y2K, M. Night Shyamalan releases The Sixth Sense on the world permanently searing “I see dead people” into pop-culture, and of course, Sega releases the Dreamcast. I, on the other hand, was smack in the middle of my second internship at Microsoft, on the Access team. Ah, Building 17, the memories we shared…

It was in one of the halls of ‘17 is where I was first introduced to the game Ataxx, a weird arcade game whose winning condition was, much like Othello, to fill the board with pieces of your color whole “converting” your opponent’s pieces. The rules were very simple, but I’ll let the official instructions speak for themselves:

• Move Globs 1 or 2 squares to an unoccupied square but selecting a Glob, then selecting a square
• Moving to an adjacent square (1-square move) will also maintain the Glob at the original square [Ed: I call this a slide]
• Moving 2 squares causes the original square to be vacated [Ed: I call this a jump]
• After moving, all opponent’s Globs in adjacent squares will be ‘captured’ (changed to your color)
• WATCH YOUR CLOCK! Your clock runs ONLY when it is your turn, but you lose the game if the clock runs down to 0
• Buy more time on your clock at any time
• Player with most Globs at end of game wins

Simple, no? The rules about the clock were there solely to eat at your quarters, but since the machine was in Free-Play mode, it wasn’t really a factor. One of the cool things about the arcade cabinet is that it had two giant trackballs instead of joysticks.

Ever since that day, I was charged by God to create an Ataxx clone for the PC. I started like any other project and did some research, turns out that there are a few Ataxx adaptations for various platforms, but that didn’t deter me, I wanted to create my own version damn it. Since then, I started-stopped-restarted this project many times. I even had a bet with the friend who I played this game with religiously about which one of us would built a clone first. As of this writing, neither one of us has won the bet. Almost every time I restarted I ended up trying on a different platform, PC, Pocket PC, even the GameBoy Advance! I have to say that the version I was working on for the GBA actually was one of the closest I’ve gotten to completion. In any case, though the code was always different, one theme stayed the same: the game was going to be called Pookie Pookie, since the “globs” were going to be these cute slime creatures called Pookies.

Sometime in 2002 or 2003 I decided to start working on the game logic and AI separately of the platform specific code so that I could use it as a staging ground for learning new platforms since I’d have the game logic in place and all I’d have to do is write that platform specific code. Want to learn OpenGL? Make PookieGL! Want to learn GameBoy Advance? Make PocketPookie! You get the idea. Now that I think about it, the Nintendo DS would make an excellent platform… mmm…

Anyway, I managed to build all the game’s logic into a nice 32 byte package perfect for sending across the network (well, how am I going to play against my friend otherwise?) or for low memory devices like cell phones, GameBoys, and the like.

I’ve also come up with a working AI scheme for the game though I would not consider the AI complete by any stretch of the imagination.

In these next posts I’ll be cataloging my attempt to, yet again, restart the project. I should probably list a few expectations for what I would consider this to be a success:

• The game allowes you to play Ataxx against a human on the same computer or against an AI with varying degrees of difficulty
• It would be nice to have network support, and though this version won’t have it, I’ll build it with it in mind
• The game has a tutorial mode that teaches the player how to play the game
• The game feels polished.

I know the last one is vague, but it’s one of those things that you know it’s there when you play the game and makes the difference between a good game and a great one. Those demands above are good enough for the first release of the game, but I will be happy until I’ve added multiplayer to it, it’d be just too cool but also possibly a ton of extra work and I want to see Pookie vie for supremacy with vicious cuteness™ damn it!