Tuesday, January 22, 2008

The Bits of the Dots Game Core

As I promised last week, I am going to explain how I implemented the Dots game core. As with any programming project, there are numerous routes that I could have taken. You have a grid of dots. Lines between dots are made. When a 1x1 box has been completed, the player who made the box gets a point and gets to make another move. This means that you need to track both the lines and the boxes. Each box is made up of four lines, but each line is shared between two boxes. My solution to this problem is to give ownership of the top and left line to the box. Each box then has six bits of information that need to be tracked. These bits are literally bits as all of the bits that make up a box can only have two states. This is why I grouped all the bits into a single byte and use an array of bytes to hold the game board.

Obviously you have the top and the left bits. If the bit is on, then the side has been drawn and if not, then it can still be drawn. Next, and this information is not needed but only takes a couple of bits so why not track it, is which player drew the line. I am using off to represent the first player and on to represent the second player. Determining if the box has been completed could be calculated on the fly, but it is more efficient to calculate this when a move is being made and store the results in a bit. Finally, you have a bit to tell you which player completed the box. That is all the information you need.

Setting a bit is done by ORing the bit's value with the byte. Clearing the bit, which is something that I never actually have to do as the only time bits are cleared is when the game is started at which point I just need to zero out the entire byte, is done by ANDing the inverse value of the bit with the byte. I know this is all old-school and that most people would probably create a separate class to hold the above information. Heck, you could store all four walls in each box and simply have the line setting function call a set wall function for both boxes that are affected. After all, it's not like this game is time or memory sensitive. I just remember way back when 64K was a lot of memory (and those poor Atari 2600 programmers only has 2K).

No comments: