Category Archives: Pac-Man

Pac-Man source code now on GitHub

For those who wish to follow along with my Pac-Man project without having to copy/paste source code from these articles, I have posted my current work-in-progress source (which includes many changes I have not discussed, yet).

https://github.com/allenhuffman/PacMan

I have broken the program up in to multiple files, but since this makes quite a mess in the IDE, I am probably going to combine all the bitmaps in to one file instead of separate ones.

If you want to play with it, you can modify the Joystick code to read whatever you have for input (buttons, analog joystick, whatever) and at least move the Pac-Man around the screen. There is no ghost collision detection, no scoring, and no dot handling yet… But it’s a fun demo.

Arduino Pac-Man part 9 – ghosts

See also: part 1part 2part 3part 4part 5part 6part 7 and part 8.

NOTE: As mentioned in the last post, many of these are written at a time then posted over the next week. This is another example of that. Initially, I had planned to write some test code and get the dot stuff working, but I decided that the ghost movement would be more fun to work on. And, as previously mentioned, I have had more time to think about things by the time you read this, so much of what you will read here (“thoughts in progress”) have evolved. I will be sharing new things with you in part 10, including a substantial change to how movement is tracked (which solved two problems I encountered with the approaches I have been taking). Spoilers: below is a short video of how it is turning out… Details soon. Until then, read part 9…

It is time for things to get a bit deep as we look in to making the ghosts act like ghosts. So far, we have have figured out how to have our sprites move across dots and either eat them or redraw them. Now it’s time to figure out how the ghosts will be moving.

Pac-Man ghosts have five basic modes they are in. They may be stuck in the ghost house waiting to exit, they may be disembodied eyes trying to return to the ghost house (after being eaten by Pac-Man), or they may be in SCATTER, CHASE or FRIGHTENED mode.

For excellent descriptions and photos of these modes, see the excellent Pac-Man Dossier site, or the excellent GameInternals site that focuses just on the ghosts. Both are quite excellent.

SCATTER is the simplest of the modes. The ghosts will be trying to reach a specific tile, and simply turn at any intersection in the direction that would get them closest to it. The target tiles are outside the maze, so the ghosts will never reach them. Each ghost has a target tile in a different corner, which is why ghosts appear to have favorite corners they will head to during the game. If left in SCATTER mode, the ghosts would circle endlessly trying to reach the impossible tile.

CHASE changes these targets so they track Pac-Man. The red ghost, Blinky, starts outside of the ghost house and its CHASE target tile is whatever tile Pac-Man is in. In chase mode, Blinky is the only ghost that is directly pursuing Pac-Man.

Pinky, the pink ghost, targets four tiles in front of Pac-Man. A bug in the original Pac-Man code causes the target tile to be wrong when Pac-Man is going UP, and it will be shifted four tiles to the left as well. I plan to replicate this bug. (Interesting note: If Pac-Man heads directly towards Pinky and gets within four tiles, this causes the target to be behind Pinky. If there is an opening in the side of the hallway between Pac-Man and Pinky, Pinky will turn down that opening trying to backtrack and reach the target that is now behind him.)

Inky, the blue ghost, has a much more complex target. It is based on two tiles in front of Pac-Man, and the location of the red ghost. The target tile is created by taking a vector that runs between the red ghost and two tiles in front of Pac-Man, then doubling that length. Yowza. Due to the same Pinky bug, when Pac-Man is facing up, the tile used is actually two up and two left from Pac-Man.

Clyde, the orange ghost, bases his target on how close to Pac-Man he is. If he is eight tiles or more away, he targets Pac-Man just like Blinky. If he is closer, he starts targeting his scatter mode tile and heads to his corner. This means Clyde should never catch Pac-Man unless you get in his way as he is trying to flee back towards his corner! If you park Pac-Man in a corner, Clyde will never reach him unless that corner is on the way to Clyde’s home corner. Cool.

And to think… some folks figured this out back in 1982 and became world champions on this game! (And they did that without MAME and disassemblies of the game code.)

And lastly, we have FRIGHTENED mode. When one of the energizers is eaten, the ghosts reverse direction (as they do when any mode change happens) and then they wander around randomly at a slower speed. During this, if Pac-Man collides with a ghost, the ghost is eaten, points are scored, and the disembodied eyes of the eaten ghost target a tile above the ghost house so they can return there and resurrect as a ghost again.

Just think of all the Pac-Man ripoffs written over the years for home computers and consoles that used randomness for the ghosts… The only bit of randomness in the original Pac-Man was when they were running away, frightened!

There is alot to cover here, so let’s start small with how the ghosts actually target a tile. Every time the ghost moves to a new tile, it looks ahead to the next tile and determines which way it will go when it reaches it. Ghosts never reverse except when switching modes, so there can be up to three choices. If the next tile has only one way to go, that is chosen. If there is more than one choice, the distance between each of the choice tiles and the target tile will be compared and the shortest one will be chosen. In the case that multiple tiles are the same distance to the target, a priority of UP, LEFT and DOWN is used to choose.

It sounds like we need a function to return the distance between two tiles. It might look like this:

// Return the distance between two coordinates. Math is hard.
uint8_t getTileDistance(int8_t x, int8_t y, int8_t targetx, int8_t targety)
{
  int8_t distx, disty;
  distx = targetx-x;
  disty = targety-y;
  return sqrt( (distx*distx)+(disty*disty));
}

Yes, that’s the Pythagorean Formula theaory thing (A squared plus B squared equals C squared.) we learned back in high school algebra to determine the size of the edges of a right triangle. I knew someday it would come in handy, but since this was the first time it ever has, I had to look it up since I couldn’t remember much from classes I took over 30 years ago!

NOTE: Since I wrote this, my buddy Mike has pointed out a much easier way to achieve the same end result. He suggested that since we can easily determine which direction the target is, just checking the distance between X and Target X versus the distance between Y and Target Y should be enough. I will be revising things in a future article to use this approach. A benefit of this is that we will also save some CPU time. The sqrt() function uses floating point math, which is slower than quick integer math if you don’t have dedicated floating point hardware to help out (the Arduino doesn’t, does it?). But I digress. As you were. Nothing to read here, yet.

One more thing to consider is that ghosts cannot reverse direction unless their mode changes. Because of this, as potential directions are scanned, reverse can never be one of them. It looks like we need a simple way to figure out which direction is reverse. We could brute force it like this:

uint8_t getOppositeDir(uint8_t dir)
{
  if (dir==LEFT) {
    return RIGHT;
  } else if (dir==RIGHT) {
    return LEFT;
  } else if (dir==UP) {
    return DOWN;
  } else if (dir==DOWN) {
    return UP;
  } else {
    return dir;
  }
}

But, as Mike pointed out, reversing from DOWN would always be slower since it has to check LEFT, RIGHT and UP before it gets there. Maybe we could do it using switch/case statements:

uint8_t getOppositeDir(uint8_t dir)
{
  switch(dir)
  {
    case LEFT:
      return RIGHT;
    case RIGHT:
      return LEFT;
    case UP:
      return DOWN;
    case DOWN:
      return UP;
    default:
      return dir;
  }
}

The end result is the same, but depending on how the compiler generates code, this could be more efficient since it may be using lookup table so jumping to DOWN would be as quick as jumping to LEFT. (Highly optimizing smart compilers may do things like this with IF/THEN logic anyway. I believe the compiler made at the place Mike and I used to work actually did that, allowing programmers to write less efficient brute force source code in some instances and still generate efficient machine code… Hmm. At my current job, I work with one of the compiler engineers from back then, so I may have to ask his opinion sometime. But I digress…)

Or we could do something more clever…though clever doesn’t always make faster or smaller code. Time for a quick test!

The directions are represented by 0=RIGHT, 1=LEFT, 2=UP and 3=DOWN. (NOTE: This is going to change in the next article, for reasons I will explain then.) This is lucky because if you look a the bit patterns for 0-3, you get 00, 01, 10, 11. If you reverse from RIGHT (00) to LEFT (01), you see the difference is toggling that right most bit. If you reverse from UP (10) to down (11), you see the difference is toggling that right most bit. Knowing this pattern, we could write a simple function to flip the right most bit:

uint8_t getOppositeDir(uint8_t dir)
{
  if (dir & 1) // If rightmost bit is set,
  {
    return dir & ~1; // Turn it off.
  } else {
    return dir | 1;  // Else, turn it on.
  }
}

This wouldn’t have been the case if the directions had been represented clockwise as 0=UP (00), 1=RIGHT (01), 2=DOWN (10), and 3=LEFT (11). If that were the case, switching from LEFT (11) to RIGHT (01) would have toggled the left most bit, and UP (00) to DOWN (10) would have toggled…the left most bit. Oh. Apparently it could have worked that way too, just by changing which bit was being tested.

Well, if the directions were in the order of ghost priority (used to determine which direction the ghost turns in case there is a tie between potential tile distances to the target) 0=UP (00), 1=LEFT (01), 2=DOWN (10) and 3=RIGHT (11), then UP (00) to DOWN (10) would toggle the left most bit, and LEFT (01) to RIGHT (11) would toggle…the left most bit. Okay, that works too.

But SURELY it wouldn’t have worked if the order was more random like 0=UP (00), 1=RIGHT (01), 2=LEFT (10) and 3=DOWN (11). UP (00) to DOWN (11) toggles both bits, and LEFT (10) to RIGHT (01) toggles both bits. That would be  easy to do in C to by using the “~” bitflip thing.

Screw it. It looks like with only four bits there would be a way to flip using bit math. This is useful, since having the directions in the order of priority will come in handy later. (This is the reason for changing directions in a future article.)

NOTE TO SELF: Do that. It makes things easier. (NOTE BACK FROM SELF: Already did, next article. Move on.)

Which one we end up using depends on things like code size, speed, and memory. I compiled a sketch with an empty setup() and empty() loop, and added just these functions, one at a time. Here are the results:

getOppositeDir() if/then version – 466 bytes
getOppositeDir() switch/case version – 466 bytes
getOppositeDir() bit flip version – 466 bytes

How can that be? Because the compiler is smart. When I created the empty test code:

#define RIGHT 0
#define LEFT  1
#define UP    2
#define DOWN  3

void setup()
{
}

void loop()
{
}

uint8_t getOppositeDir(uint8_t dir)
{
  switch(dir)
  {
    case LEFT:
      return RIGHT;
    case RIGHT:
      return LEFT;
    case UP:
      return DOWN;
    case DOWN:
      return UP;
    default:
      return dir;
  }
}

…the compiler realized nothing was actually using that function and discarded it. If anything were using it, the compiler would have to keep the code. Let’s try this:


#define RIGHT 0
#define LEFT  1
#define UP    2
#define DOWN  3

void setup()
{
  Serial.begin(9600);

  Serial.println(getOppositeDir(DOWN));
}

void loop()
{
}

uint8_t getOppositeDir(uint8_t dir)
{
  if (dir==LEFT) {
    return RIGHT;
  } else if (dir==RIGHT) {
    return LEFT;
  } else if (dir==UP) {
    return DOWN;
  } else if (dir==DOWN) {
    return UP;
  } else {
    return dir;
  }
}

By printing the result, the code has to run to get the result. Now we get:

getOppositeDir() if/then version – 2214 bytes
getOppositeDir() switch/case version – 2214 bytes
getOppositeDir() bit flip version – 2214 bytes

We can see that using the Serial.xxx() functions adds quite a bit of code bulk, but the sizes are still the same. If the compiler was getting rid of unused code before, but why are the sizes still the same? Could each function really generate the same amount of code? If it was, then it wouldn’t matter which one we used — at least, not just based on code size. More on this in a moment…

Without looking at the assembly code generated by the compiler, I cannot say which one is more efficient. For now, we will use the switch/case approach since it is really easy to understand and doesn’t make the code any larger. Also, that will work regardless of what values are chosen for UP, DOWN, LEFT and RIGHT so if I change them later (NOTE: which I am doing), I won’t have to rewrite the getReverseDir() function like I would with the bit flipping version.

But wait! There’s more! While standing outside during a file alarm the other day, I mentioned this to the previously mentioned compiler engineer I used to work with… He suggested another option: a lookup table. It might look like this:

// Directions are: 0-RIGHT, 1-LEFT, 2-UP and 3-DOWN
// Therefore, reverse directions in this table would be:
const uint8_t oppositeDir[] = { LEFT, RIGHT, DOWN, UP };

uint8_t getOppositeDir(uint8_t dir)
{
  return oppositeDir[dir];
}

See what that does? If your original order is 0, 1, 2 and 3, you could create an array that contains four numbers in whatever order you want, like 1, 2, 3, and 2. Then if you asked for the element of the array that matches your original direction, it returns whatever is there (which is the opposite direction number). You wouldn’t even have to use a function: reverse = oppositeDir[dir];

getOppositeDir() array version – 2214 bytes

Dambit. Either these really are taking the same amount of space, or there is some compiler stuff going on where the size of the binary is being rounded up, or things are being optimized out.

Okay, one last try. This time, we’ll do more with the function than just change one hard coded value. A really smart compiler could see “oh, this is only being done once, and it’s being done with a 3, so I can just pull in the code that handles the 3 case and discard the rest.” Is this compiler that smart? Here is my test code, with all four variations included:

#define IFTHEN
//#define SWITCHCASE
//#define BITFLIP
//#define LOOKUPTABLE

#define RIGHT 0
#define LEFT  1
#define UP    2
#define DOWN  3

void setup()
{
  uint8_t dir;

  Serial.begin(9600);

  for(dir=0; dir<3; dir++)
  {
    Serial.println(getOppositeDir(dir));
  }
}

void loop()
{
}

#if defined(IFTHEN)
uint8_t getOppositeDir(uint8_t dir)
{
  if (dir==LEFT) {
    return RIGHT;
  } else if (dir==RIGHT) {
    return LEFT;
  } else if (dir==UP) {
    return DOWN;
  } else if (dir==DOWN) {
    return UP;
  } else {
    return dir;
  }
}
#endif

#if defined(SWITCHCASE)
uint8_t getOppositeDir(uint8_t dir)
{
  switch(dir)
  {
    case LEFT:
      return RIGHT;
    case RIGHT:
      return LEFT;
    case UP:
      return DOWN;
    case DOWN:
      return UP;
    default:
      return dir;
  }
}
#endif

#if defined(BITFLIP)
uint8_t getOppositeDir(uint8_t dir)
{
  if (dir & 1) // If rightmost bit is set,
  {
    return dir & ~1; // Turn it off.
  } else {
    return dir | 1;  // Else, turn it on.
  }
}
#endif

#if defined(LOOKUPTABLE)
// Directions are: 0-RIGHT, 1-LEFT, 2-UP and 3-DOWN
// Therefore, reverse directions in this table would be:
const uint8_t oppositeDir[] = { LEFT, RIGHT, DOWN, UP };

uint8_t getOppositeDir(uint8_t dir)
{
  return oppositeDir[dir];
}
#endif

To test, I comment out all of the defines at the top except for the one I want to test, then I check each one.

getOppositeDir() if/then version – 2264 bytes
getOppositeDir() switch/case version – 2264 bytes
getOppositeDir() bit flip version – 2244 bytes
getOppositeDir() array version – 2246 bytes

Finally! Indeed, it does appear the compiler was smart enough to figure out that the functions as only being called once with a specific value — so why keep the rest of the code around? (If this is true, that’s pretty cool.) It seems the bit flip version is the smallest, coming in 20 whole bytes smaller than the brute force if/then. But, remember that it would have to be recoded if the direction order ever changes (which it will be for me, so that would have created a bug if I didn’t remember to change it). The array version is 18 bytes smaller, and it, too, would have to change if the directions ever changed. And none of this tells us which one executes faster necessarily, which might be very important to speed up a video game.

But I digress… Optimizations could be the topic for a whole series, and will no doubt come up again in this series.

Wasn’t that fun? Where was I? Oh, right. Looking ahead…

Now all we need to do is look ahead and see what tile options there might be. Here is how it should work:

The next tile in the direction the ghost is running should be determined. Then, from that tile, all the tiles around it (not including reverse, which isn’t an option since a ghost can’t go backwards) should be checked to see how far they are from the target tile. They will be checked in the priority order of UP, LEFT, DOWN and RIGHT. If a shorter distance is found, remember that direction, else continue. This will take care of distance ties and the priority. If UP is checked and it is 5 away, then LEFT is checked and it is 6, it will be skipped. Next, if DOWN is checked and it is also 5, it won’t be recorded since we already have a 5 (UP, a higher priority).

To do this, we need to check the directions in the order of 2 (UP), 1 (LEFT), 3 (DOWN) and 0 (RIGHT). If only these priorities lined up with our directions this would be simple. Since they don’t, we may have to use an array like this: (NOTE: Now see why changing the directions will help out? None of the things involving priorityDirs[] will need to be used, but I am keeping it all in this article to show how the concept evolved.)

PROGMEN const uint8_t priorityDirs[DIRS] = { UP, LEFT, DOWN, RIGHT };

// Do this for each ghost.
for (i=0; i<GHOSTS; i++)
{
  // Get the file in front of us.
  getNextTile(gx[i], gy[i], ghostDir[i], &nextX, &nextY);

  // Now, from that tile, see what options might exist.

  // We cannot reverse, so we should ignore that direction.
  // Storing this in a variable for speed.
  uint8_t reverseDir = reverseDir(ghostDir[i]);

  for (j=0; j<DIRS; j++)
  {
    uint8_t potentialX, potentialY;
    uint8_t tempDist;
    uint8_t shortestDist = 255; // Max distance.

    // Skip reverse dir since it's not a choice.
    if (j==reverseDir) continue;

    // What tile is in that direction?
    getNextTile(nextX, nextY, priorityDir[j], &potentialX, &potentialY);

    // Get distance from potential tile to target tile
    tempDist = getDistance(potentialX, potentialY, targetX, targetY);
    // If closer than previous closest,
    if (tempDist < shortestDist) {
    {
      shortestDist = tempDist;
      tempDir = priDir[j];
    }
  }
  // The next direction the ghost should go is...
  ghostDir[i] = tempDir;
}

Could this actually work??? To find out, we can combine this mechanism with the dot merchanism, and see if the ghosts will now SCATTER to their corners and behave like Pac-Man ghosts should behave…

To be continued…

Ardunio Pac-Man part 8 – dot dilemma 2

See also: part 1part 2part 3part 4part 5part 6 and part 7.

NOTE: I tend to sit down and write up a bunch of things at one time, then publish them over the next week. This article was originally written on 2/17, and often by the time they are published I have had time to think about things and reconsider. Much of what you will read in the next two articles is being replaced by a better approach, but I still want to share the thought process. Maybe we will end up in the same place! Here we go… (Also, I created a Facebook page for Sub-Etha as well. It will update every time I post a new article.)

I believe I have solved the dot dilemma, and it looks like it might be easier than I expected. First, a recap on what this dilemma is.

The Pac-Man game considers a collision to be when the center of a sprite crosses over the center of another object. This is how collisions with the ghosts, dots, energizer pellets and fruits are handled. Since the center is used for this, it is possible for two sprites to touch and even overlap slightly without anything happening. This is why it’s possible to brush up against ghosts in the arcade game without losing a life. It is also why if Pac-Man approaches a dot halfway, then turns around without getting to the center point, the dot is not eaten.

As previously discussed, a simple way to keep track of the dots would be to use variables to track the on/off status of each dot. 240 dots could be represented by the bits of some bytes (8 bits per byte) and would take up 30 bytes of RAM. Since I only have around 200 bytes of RAM available, using 15% of available RAM for this may not be practical. Plus, it would also require some sort of table that links each bit to which grid tile on the screen the dot is in. While this may be doable, I have decided to try to come up with a different approach.

Instead of tracking each dot, I will be detecting them as each sprite moves around. If a ghost is moving right and is about to cover up a dot, it will remember that and, as the ghost passes over where the dot is, it will redraw the dot behind it. Some considerable has to be taken for when a sprite changes directions while covering a dot, and I think I have this all worked out.

For Pac-Man, the story is the same, except instead of redrawing the dot, it will score points when the Pac-Man sprite is over the center of where the dot was.

Since objects are constantly being drawn, erased, and redrawn in new locations as they move around the screen, some care must be taken with the order that these things happen to ensure a dot is properly detected. I have a few ideas on how this might be handled, from one that will “most certainly” work but take more CPU time and code, to one that will “quite possibly” work and leave more CPU time free for other game tasks.

Brute force programming is not something I generally do beyond initial tests to see if something will work.

Once again, let’s revisit our screen. The screen is made up of a grid of tiles. Each tile is 3×3 in size. The character sprites are 5×5. A dot is in the center of a tile, so every three pixels there can be a dot. This means a 5×5 sprite can actually be covering two dots.

Screen Shot 2014-02-17 at 7.19.42 PM

If a 5×5 sprite begins in the center of a 3×3 tile, it will extend one pixel past each edge of the 3×3 tile. There are four cross paths in the maze where there could be dot touching each of the four sides of a sprite, but we really only need to track the ones in front of the character and remember to draw it back once the character is past it, or count it for the score once the sprite is dead center over it.

Screen Shot 2014-02-17 at 7.32.47 PMBecause of how the math works out, any time the sprite is at a tile offset of 0 (in the center), we should be able to check the tile in the direction we are going to see if there is a dot there. If there is, we can increment a counter variable that will indicate how many dots are under us. For this game, this counter will never be higher than 2, but if we were animating a long snake through a maze, we could use the same system to count being on top of many more dots.

Also at the 0 offsets, we check to see if we need to redraw a dot behind us that we just passed over. We do this by checking the counter to see if it is greater than 0. If it is, we draw a dot behind us and decrement the counter.

If we are moving over a dot and have just incremented the counter, the next frame will be to draw the sprite on the current tile with an offset of 1 in that direction (moving one pixel to the right, for example, and now covering the dot). As the character continues moving right, it moves to the next tile, with an offset of -1. When it moves right one more pixel, the offset is 0 and once again we check to see if there is another dot in front, and if a dot needs to be redrawn behind.

This seems like it will work quite easily, but we also have to take in to consideration what might happen if the sprite changes direction. If it backs up, the counter is still set (>0 = we are covering a dot) and I expect the same code may work, since we reverse back and expose where a dot used to be, and just draw one. Some test code is needed to see if it can really be this simple…

Since all turns are done at offsets of 0 in the middle of a tile, there is never a situation where the two dots being covered would be around a corner, but even if there was, it seems like this system would still work.

Some test code will need to be written.

Arduino Pac-Man part 7 – what’s next?

See also: part 1, part 2, part 3, part 4, part 5 and part 6.

What started out as a simple evening experiment with Arduino video output has escalated in to a full-on attempt to recreate a classic 1980s arcade game as accurately as possible given the limitations of the platform. Ignorance is bliss, as they say, and if I hadn’t discovered such detailed Pac-Man dissection sites, I would have been done by now with something that looked like a dot eating game, but didn’t actually play like the dot eating game it was trying to look like.

At this stage in development, I have recreated the maze layout very accurately, and even recreated the tile grid system that is the key to collision detection with walls and, eventually, with the ghosts. The current Arduino sketch displays the maze and four non-moving animated ghosts and allows Pac-Man to move around the maze, complete with animation in all four directions. (Not quire true; I did some work after that and now have one ghost roaming around randomly, erase dots as it goes.)

There are now two challenges to be solved, and this posting will describe my proposed solutions. The two challenges are dot tracking and ghost targeting.

Dot tracking involves detecting if Pac-Man has passed over a dot and eaten it, or if a ghost has passed over a dot without doing anything to it. My proposed solution is to have each character check to see if it is about to erase a dot and then either eat it (Pac-Man), or redraw it once the character has passed over it.

Ghost targeting is the key to how the ghosts move through the maze, tracking Pac-Man or running away from him. In order for this to work, each ghost must be able to determine what tile is in front of it, then make a decision on which way to turn (if there is a turn) once it reaches that tile.

I believe both of these challenges can be solved by using the grid system the maze is based on. This article will discuss the framework that will be used to determine which tile a character is about to enter. I will be working with the dots for the rest of this article.

A dot is in the center of a 3×3 grid. The sprites are 5×5. A sprite that is perfectly centered on a grid tile will cover all 3×3 pixels of the tile, plus extend one pixel in to each adjoining tile. This will make the sprite be touching any dots that are on any side of it.

Screen Shot 2014-02-17 at 7.19.42 PM

I propose to do dot detection based on any time a sprite is about to be drawn with a tile x and y offset of 0 (meaning it is centered on a tile). If there is a dot pixel set in the direction the sprite is moving, a flag will be set to either eat or redraw it. Once the offset reaches -1 or 1, the 5×5 sprite should now be over the dot. Once the offset reaches 0 of the tile in the direction the sprite is moving, the dot will be considered eaten (scored), or ignored (ghost). Once the character is two tiles away from the original with an offset of 0, the dot will be redrawn on the side opposite of the direction.

Screen Shot 2014-02-17 at 7.32.47 PM

To the right is a diagram demonstrating this.

  1. Pac-Man is at the center of the first tile, offset 0. Here it would detect there is a pixel about to be covered. Dot counter goes from 0 to 1.
  2. The next row is Pac-Man moving one pixel to the right, offset +1. It would be covering the dot.
  3. Pac-Man’s center has entered the second tile, offset -1.
  4. Pac-Man is at the center of the second tile, offset 0, and detects another dot is about to be covered. Dot counter goes from 1 to 2.
  5. Pac-Man moves one pixel to the right, offset +1.
  6. Pac-Man’s center has entered the third tile, offset -1.
  7. Pac-Man is in the center of the third tile, offset 0. A dot is eaten (Pac-Man) or drawn behind him (ghost). Dot counter goes from 2 to 1.

There will probably need to be a secondary counter that counts how many tiles have been passed, since the sprite has to move two tiles to the right before the dot is visible/eaten. We’ll figure that out shortly…

A few bits of code need to be created to achieve this. The first will be a method to determine what the next tile is the sprite is heading towards. Since a character can be moving up, down, left or right, and it’s location is based on an X/Y coordinate in a grid, it makes things a bit tricky. Here is an example:

Screen Shot 2014-02-17 at 7.44.51 PM

Above, the character is currently in position (X,Y) and is moving to the right. The next tile it reaches will be (X+1, Y). Or, if it were moving to the left, it would be (X-1, Y). If it were moving up, it would be (X, Y-1) and down would be (X, Y+1). A nice if/then or switch/case block could handle this:

int8_t px, py;
int8_t nextTileX, nextTileY;

px = 5;
px = 5;
pacDir = RIGHT;

if (pacDir==RIGHT) {
  nextTileX = px + 1;
  nextTileY = py + 0;
} else if (pacDir==LEFT) {
  nextTileX = px -1;
  nextTileY = py + 0;
} else if (pacDir==UP) {
  nextTileX = px + 0;
  nextTileY = py - 1;
} else if (pacDir==DOWN) {
  nextTileX = px + 0;
  nextTileY = py + 1;
}

This would let us calculate the X and Y coordinate of the next tile in whatever direction the character was facing. This works, but isn’t very elegant. A more elegant approach might be to us an array to hold the “next tile” X and Y coordinates.

First, I created a special structure that represents an X and Y coordinate. A C structure lets you create custom data types that can have many elements, and then access those elements by name.

typedef struct {
  int8_t x, y;
} Coordinate;

I can now create a new variable of type “Coordinate” just like I might create a variable of type int or char, and set the elements of it (X, Y):

Coordinate foo;

foo.x = 10;
foo.y = 5;

Now foo represents the coordinates (10, 5). Since the elements (x and y) are signed. they can be negative or positive numbers. In this example, instead of representing a physical X and Y coordinate, they will be used as X and Y offsets to be added to the current location coordinate. Here are the offsets represented by Coordinates:

Coordinate tileRight, tileLeft, tileUp, tileDown;

tileRight.x = 1;
tileRight.y = 0;

tileLeft.x = -1;
tileleft.y = 0;

tileUp.x = 0;
tileUp.y = -1;

tileDown.x = 0;
tileDown.y = 1;

In this case, each Coordinate is the offset (X and Y) to the tile in that direction. If I knew Pac-Man was at location 5,5, I could simply add the appropriate offsets and get the coordinate of the tile in that direction. Here is the previous example done using these new Coordinate structures:

int8_t px, py;
int8_t, nextTileX, nextTileY;

px = 5;
px = 5;
pacDir = RIGHT;

if (pacDir==RIGHT) {
  nextTileX = px + tileRight.x;
  nextTileY = py + tileRight.y;
} else if (pacDir==LEFT) {
  nextTileX = px + tileLeft.x;
  nextTileY = py + tileLeft.y;
} else if (pacDir==UP) {
  nextTileX = px + tileUp.x;
  nextTileY = py + tileUp.y;
} else if (pacDir==DOWN) {
  nextTileX = px + tileDown.x;
  nextTileY = py + tileDown.y;
}

It doesn’t look like we gained anything, because we haven’t. However, since we are already tracking directions in multiple places (like which Pac-Man sprite bitmap to display, and which direction the joystick is being pressed), we can continue to use this by creating an array of “next tile” coordinates in the same order as the directions (0=right, 1=left, 2=up, 3=down).

A note on arrays: If you create an array of integers, like “int foo[10];”, you can initialize them one at a time like “foo[0]=1;” and “foo[9]=42;”, or you can initialize them all at the same time like “int foo[10] = {1,2,3,4,5,6,7,8,9,10};” You can also do this with structures, but instead of just putting a single number there, you are putting in initializer values for each element of the structure. Using extra braces around each one makes this example more clear:

#define RIGHT 0
#define LEFT  1
#define UP    2
#define DOWN  3
#define DIRS  4

Coodinate nextTileOffset[DIRS] = {
 {  1, 0 }, // 0=right
 { -1, 0 }, // 1=left
 {  0,-1 }, // 2=up
 {  0, 1 }  // 3=down
};

C would have allowed you to just do “Coordinate nextTileOffset[DIRS] = {1, 0, -1, 0, 0, -1, 0, 1};” but please don’t do that. It’s icky.

So above, nextTileOffset[0].x is 1, and nextTileOffset[0].y is 0, and nextTileOffset[1].x is -1 and nextTileOffset[1].y is 0. Great. So what?

Once this is done, the next tile can be figured out by applying whatever set of coordinates is in the array element that corresponds to the direction (0-3):

int8_t px, py;
int8_t, nextTileX, nextTileY;

px = 5;
px = 5;
pacDir = RIGHT;

nextTileX = px + nextTileOffset[pacDir].x;
nextTileY = py + nextTileOffset[pacDir].y

A function could even be written to do this, by letting you pass in X, Y and DIRECTION, and then two variables by reference that will be modified and returned from the function:

bool getNextTile(int8_t x, int8_t y, uint8_t dir, int8_t *nextX, uint8_t *nextY)
{
  // We might want to error check.
  if (dir>DIRS) return false;

  *nextX = x + nextTileOffset[dir].x;
  *nextY = y + nextTileOffset[dir].y;

  return true;
}

Now we could do it like this:

int8_t px, py;
int8_t, nextTileX, nextTileY;

px = 5;
px = 5;
pacDir = RIGHT;

getNextTile(px, py, pacDir, &nextTileX, &NextTileY);

And if you enjoy checking for potential errors…


if (getNextTile(px, py, pacDir, &nextTileX, &nextTileY)==true)
{
  // We were able to determine the next tile.
} else {
  // Bad things happened.
}

The error condition currently just makes sure DIR is valid to avoid accessing a non-existent array member and potentially crashing the system, but it could be modified to return some status about what is in the next tile - wall? dot? Ghost? Bacon?

The reason I decided to make a function for this is because it will be used for other purposes, like the ghost logic where they look ahead one tile to determine which direction to go.

Now that we have a simple way to determine what tile is in front of our sprite, we can proceed to see if that tile contains a dot...

To be continued...

Arduino Pac-Man part 6 – moving

See also: part 1, part 2, part 3, part 4 and part 5.

It’s funny how easy something can be done when you aren’t trying to do it, and how difficult it can be once you actually start to focus on the task at hand. For the past few days, I have spent very little time coding, and quite a bit of time thinking. And coding small examples to see if my thinking was correct.

As I learn more about Pac-Man from sites such as Jamey Pittman’s Pac-Man Dossier, I realize there is much more to this simple dot eating game than I ever imagined. Fortunately, the design work has already been done and all I should have to do is create a clean room version of the game. (In this case, clean room refers to never seeing the actual original code, but having a rather extensive list of functionality so a workalike could be created. It was this technique that allowed for the explosion of IBM-PC compatible computers in the early 1980s when other companies created clean room versions of the BIOS chip that made a PC a PC. But I digress.)

The bane of my existence the past few days has been this simple image from the Pac-Man Dossier site:

CorneringI have heard that Pac-Man players could evade ghosts by turning corners, but I never knew why. It turns out, in the original Pac-Man game, Pac-Man can basically cut corners (now those rounded edges have a purpose!) while the ghosts always turn at 90 degree angles. If you recall my earlier posting about wall detection, recreating these rounded corners was causing me a bit of a problem since it was not easy to just detect set pixels – my Pac-Man could get stuck on those corners. My plan was to use the tile grid system and just make my Pac-Man not need to detect wall pixels… But once I saw that the original game actually used this for something, I figured I would try to cut corners with my version.

Over the course of this week, I thought about different approaches to this, and even coded a few samples, including some that would let my Pac-Man round those corners nicely. I was still able to create a situation where Pac-Man could get stuck. Basically, if Pac-Man was moving LEFT down a hallway, and the joystick was pressed DOWN, my new code would start hugging the wall and moving down/left around a corner. But, if at the very moment Pac-Man was on the curved edge, the player decided to move UP, the code would start moving Pac-Man up and he would be one pixel out of alignment with the maze grid and get stuck.

I had concluded that I would simply have to know when Pac-Man was moving in a diagonal so I could force the character to keep moving until it ended up back in the center of a tile before letting the player switch directions. My solution was to detect when Pac-Man was off the grid center, and adjust accordingly. (I wonder what the arcade game does if you try this?)

As it turns out, It was going to be quite a bit of work, and even implementing this would not truly replicate this feature in Pac-Man. For my low resolution display, I really would have only one step that could be saved between moving left and moving down. One pixel. But in the original arcade game, there were multiple variations. Observe this image also from the Pac-Man Dossier site:

cornering_example2Above, the yellow square in the center of the green and red squares is where Pac-Man could turn at a 90 degree angle. In the top left image, you can see he would have to move four pixels to the right, then four pixels down (8 pixels total) doing a 90 degree turn, or he could go down as soon as possible and start moving diagonally down/right (like the left side of a right triangle) and get from start to destination in only four pixels. I suppose in my implementation, moving from taking two pixels to one pixel would be the same type of advantage (half as much time). But, all those other lines show how there were actually other places the turn could be made, each saving a different amount. I simply do not have the resolution to replicate this fully.

So, for now, I am going to skip this feature and let my Pac-Man only turn corners at the center of a tile (90 degree turn), just like the ghosts. This brought me back to the wall detection system, and my thoughts of using the tile grid. Here is what the screen looks like with each grid spot marked. It is like the arcade tile layout (28×36), except there are five rows of tiles above and below the maze (score, players left, level, etc.) that I am not displaying.

Tiles for the Pac-Man game.The tiles that contain maze parts look like this:

Pac-Man maze tiles.But since a tile was smaller than a Pac-Man or ghost sprite (just like in the arcade), I could not just use a tile X/Y location for the game. My tiles were 3×3, and the characters were 5×5. In order to move a character smoothly, I still needed to track the screen X/Y coordinate. For instance, once my maze was drawn, my Pac-Man character would be displayed at position 41,70. This would correspond to tile 14,23. As the character moved right, it would move three pixels before entering the next tile. So, the tile position would remain 14,23 for three moves, while the screen position moved from 41,70 to 44,70. (I really need drawings for this. This isn’t making much sense to me as I type it out.)

Basically, I would need to track both screen position and tile position. After testing several methods, I think I finally decided on one.

First, let’s revisit the tiles. I created an array of bytes that represent the walls and the hallways. It looks like this:

#define TILEW    28
#define TILEH    31

#define TILEBYTESPERROW ((TILEW-1)/8+1) // bytes per row in mazeTiles

PROGMEM const unsigned char mazeTiles[TILEH][TILEBYTESPERROW] = {
  0b11111111, 0b11111111, 0b11111111, 0b11110000,
  0b10000000, 0b00000110, 0b00000000, 0b00010000,
  0b10111101, 0b11110110, 0b11111011, 0b11010000,
  0b10111101, 0b11110110, 0b11111011, 0b11010000,
  0b10111101, 0b11110110, 0b11111011, 0b11010000,
  0b10000000, 0b00000000, 0b00000000, 0b00010000,
  0b10111101, 0b10111111, 0b11011011, 0b11010000,
  0b10111101, 0b10111111, 0b11011011, 0b11010000,
  0b10000001, 0b10000110, 0b00011000, 0b00010000,
  0b11111101, 0b11110110, 0b11111011, 0b11110000,
  0b00000101, 0b11110110, 0b11111010, 0b00000000,
  0b00000101, 0b10000000, 0b00011010, 0b00000000,
  0b00000101, 0b10111001, 0b11011010, 0b00000000,
  0b11111101, 0b10100000, 0b01011011, 0b11110000,
  0b00000000, 0b00100000, 0b01000000, 0b00000000,
  0b11111101, 0b10100000, 0b01011011, 0b11110000,
  0b00000101, 0b10111111, 0b11011010, 0b00000000,
  0b00000101, 0b10000000, 0b00011010, 0b00000000,
  0b00000101, 0b10111111, 0b11011010, 0b00000000,
  0b11111101, 0b10111111, 0b11011011, 0b11110000,
  0b10000000, 0b00000110, 0b00000000, 0b00010000,
  0b10111101, 0b11110110, 0b11111011, 0b11010000,
  0b10111101, 0b11110110, 0b11111011, 0b11010000,
  0b10001100, 0b00000000, 0b00000011, 0b00010000,
  0b11101101, 0b10111111, 0b11011011, 0b01110000,
  0b11101101, 0b10111111, 0b11011011, 0b01110000,
  0b10000001, 0b10000110, 0b00011000, 0b00010000,
  0b10111111, 0b11110110, 0b11111111, 0b11010000,
  0b10111111, 0b11110110, 0b11111111, 0b11010000,
  0b10000000, 0b00000000, 0b00000000, 0b00010000,
  0b11111111, 0b11111111, 0b11111111, 0b11110000
};

It is a multidimensional array of 32 rows of 3 bytes each. I would need a routine that could take a tile X,Y coordinate and tell me if it was empty (0) or a wall (1). I ended up with something that looks like this:

// Given tile x/y, return whether that tile is path (0) or wall (1)
uint8_t getTileStatus(uint8_t tilex, uint8_t tiley)
{
  uint8_t byte = pgm_read_byte_near(&mazeTiles[tiley][tilex/8]);
  uint8_t bit = tilex-((tilex/8)*8);
  return bitRead(byte, 7-bit);
}

To test this out, I created a few routines that would try to draw the maze tiles (like the earlier screen shots). Here is one that draws the wall tiles:

// Draw tiles for the walls.
void drawWallTiles()
{
  // Draw grid center dots.
  for (uint8_t tilex=0; tilex<TILEW; tilex++)
  {
    for (uint8_t tiley=0; tiley<TILEH; tiley++)
    {
      if (getTileStatus(tilex, tiley)!=0)
      {
        TV.draw_rect(tilex*3, tiley*3, 2, 2, WHITE, WHITE);
      }
    }
  }
}

And if I wanted to draw just the path (non wall) sections, it might look like this:

// Draw tile center dots.
void drawTileCenters()
{
  for (uint8_t tilex=0; tilex<TILEW; tilex++)
  {
    for (uint8_t tiley=0; tiley<TILEH; tiley++)
    {
      if (getTileStatus(tilex, tiley)==0)
      {
        TV.set_pixel((tilex*3)+1, (tiley*3)+1, WHITE);
      }
    }
  }
}

Clever readers may notice that this is the same function, except it looks for empty tiles (0) and then just puts a dot in the center instead of drawing a box.

Ah, a quick word about coordinates. Originally I was using X and Y to represent the top left of an item. Since Pac-Man uses the center of the character, I have adjusted accordingly. If I were to draw a 5×5 ghost on the screen at position 0,0, the center would be 2,2. I will be using the center coordinate, meaning that any time I draw a ghost or Pac-Man, I would draw it at X-2,Y-2. This adds a bit of overhead every single time due to the extra subtraction, but for now it will make things easier. If I ever decide to write a series on optimizations, I can share many of the methods I use to increase code speed or reduce code size by improving this example.

So now I would be using X,Y as the center of an object, and using the tile X,Y to look for walls (and, later, the ghost behaviors which are entirely based on targeting tiles).

This next part is going to get even more confusing…

If I decide Pac-Man should start out on tile 14,23, that could be converted to a screen position like this:

  uint8_t pactilex, pactiley;
  uint8_t px, py;

  pactilex = 14;
  pactiley = 23;

  px = pactilex*TILESIZE+1;
  py = pactiley*TILESIZE+1;

(TILESIZE is 3.) The +1 is to get to the center of a 3×3 tile. px and py would now be the center for where Pac-Man is. But, since Pac-Man is not going to jump three pixels at a time, I decided I would need an offset value as well. The offset would be -1, 0 or 1 depending on where the character was in relation to the center of a tile.

  uint8_t pactilex, pactiley;
  int8_t  pacoffx, pacoffy;

  uint8_t px, py;

  pactilex = 14;
  pacoffx = -1;

  pactiley = 23;
  pacoffy = 0;

  px = pactilex*TILESIZE+1+pacoffx;
  py = pactiley*TILESIZE+1+pacoffy;

The offset could change to move the character one position left or right of the center of a tile. Then, when moving a character, I will use the tile X,Y position, and the offset. As a character moves to the right, it first enters a tile at the far left, with an offset of -1. Then the offset goes to 0 and the character is in the center. Then it goes to the right and the offset is 1. Then it moves to the next tile with an offset of -1, and so on. Trust me, it works.

And, by doing this, I now know when a character is at the center of a tile (offset is 0) and that’s when I can check for walls, etc. Also, collision with ghosts is based on the center, so if a ghost is at 12,16 with an offset of 0, and Pac-Man is at 12,16 with an offset of 1, they have not yet collided. Ditto for eating the dots. Everything is based on the center of the tile or the center of the character. It looks like the pieces are starting to fall together… Again.

I would handle moving the same way I did in the demo, using mx and my to represent the movement along the X or Y axis. mx=1 means the character is moving to the right. mx=-1 means it is moving to the left. mx=0 means it is not moving.

After checking the input and setting mx and my accordingly, I could do something like this:

    if (mx!=0 && pacoffx==0) // Moving LEFT or RIGHT.
    {
      if (getTileStatus(pactilex+mx, pactiley)!=0) mx = 0;
    }

    if (my!=0 && pacoffy==0) // Moving UP or DOWN.
    {
      if (getTileStatus(pactilex, pactiley+my)!=0) my = 0;
    }

This means, if we are moving along X (mx!=0), and we are in the center of a tile (x offset 0), now would be a good time to check for a wall. We either check the left or right tile (based on mx being -1 or 1) on our current tile row, and if we find a wall, we stop moving.

Instant wall detection based on the tile map!

To actually do the moving, things get a bit messier and I expect I can rewrite this and make it clever. Right now, it’s this…

    // Move...
    if (mx!=0 && pacoffy==0)
    {
      px = px + mx;
      pacoffx = pacoffx + mx;
      if (pacoffx<-1) {
        pacoffx=1;
        pactilex--;
      }
      if (pacoffx>1) {
        pacoffx=-1;
        pactilex++;
      }
    }

    if (my!=0 && pacoffx==0)
    {
      py = py + my;
      pacoffy = pacoffy + my;
      if (pacoffy<-1) {
        pacoffy=1;
        pactiley--;
      }
      if (pacoffy>1) {
        pacoffy=-1;
        pactiley++;
      }
    }

In the first part, if we are moving LEFT or RIGHT (mx!=0) and we are vertically in the center of a tile (pacoffy==0) then we know we could allow turning UP or DOWN (if there is no wall). The pacoffy==0 prevents us from turning around the corner and getting stuck (problem solved!). If it looks like we can move this direction, we apply the movement (px = px + mx) and then we do the same for the tile offset (adding -1 or 1 or 0 to it). We then check for rollovers… If the offset is less than -1, we have moved left in to the next tile so we decrement the tile X and then set the offset to 1 (we are at the right side of the tile to the left of where we started). If we are moving to the right, we do the same but opposite… If greater than 1, we move tile X to the right and reset the offset to the left of that tile, -1.

And now we have easy movement that, so far, does not let me get stuck in a corner.

Here is a rough sample of how this works — using dots in the center of each tile that would be a wall, and a square for the player character. I have included a few other draw routines you can play with if you want to see the grid blocks or the maze wall blocks.

#include <TVout.h>

TVout TV;

#define JOYSTICKXPIN 1
#define JOYSTICKYPIN 0

#define DIRRIGHT     0
#define DIRLEFT      1
#define DIRUP        2
#define DIRDOWN      3

#define TILESIZE 3
#define TILEW    28
#define TILEH    31

#define TILEBYTESPERROW ((TILEW-1)/8+1) // bytes per row in mazeTiles

PROGMEM const unsigned char mazeTiles[TILEH][TILEBYTESPERROW] = {
  0b11111111, 0b11111111, 0b11111111, 0b11110000,
  0b10000000, 0b00000110, 0b00000000, 0b00010000,
  0b10111101, 0b11110110, 0b11111011, 0b11010000,
  0b10111101, 0b11110110, 0b11111011, 0b11010000,
  0b10111101, 0b11110110, 0b11111011, 0b11010000,
  0b10000000, 0b00000000, 0b00000000, 0b00010000,
  0b10111101, 0b10111111, 0b11011011, 0b11010000,
  0b10111101, 0b10111111, 0b11011011, 0b11010000,
  0b10000001, 0b10000110, 0b00011000, 0b00010000,
  0b11111101, 0b11110110, 0b11111011, 0b11110000,
  0b00000101, 0b11110110, 0b11111010, 0b00000000,
  0b00000101, 0b10000000, 0b00011010, 0b00000000,
  0b00000101, 0b10111001, 0b11011010, 0b00000000,
  0b11111101, 0b10100000, 0b01011011, 0b11110000,
  0b00000000, 0b00100000, 0b01000000, 0b00000000,
  0b11111101, 0b10100000, 0b01011011, 0b11110000,
  0b00000101, 0b10111111, 0b11011010, 0b00000000,
  0b00000101, 0b10000000, 0b00011010, 0b00000000,
  0b00000101, 0b10111111, 0b11011010, 0b00000000,
  0b11111101, 0b10111111, 0b11011011, 0b11110000,
  0b10000000, 0b00000110, 0b00000000, 0b00010000,
  0b10111101, 0b11110110, 0b11111011, 0b11010000,
  0b10111101, 0b11110110, 0b11111011, 0b11010000,
  0b10001100, 0b00000000, 0b00000011, 0b00010000,
  0b11101101, 0b10111111, 0b11011011, 0b01110000,
  0b11101101, 0b10111111, 0b11011011, 0b01110000,
  0b10000001, 0b10000110, 0b00011000, 0b00010000,
  0b10111111, 0b11110110, 0b11111111, 0b11010000,
  0b10111111, 0b11110110, 0b11111111, 0b11010000,
  0b10000000, 0b00000000, 0b00000000, 0b00010000,
  0b11111111, 0b11111111, 0b11111111, 0b11110000
};

void setup()
{
  TV.begin(NTSC, 120, 96);

  TV.clear_screen();

  //drawTileGrid();
  //drawWallTiles();
  drawTileCenters();
}

void loop()
{
  uint8_t px, py;
  int8_t  mx, my; // Movement direction (-1 to 0 to +1)

  uint8_t pactilex, pactiley;
  int8_t  pacoffx, pacoffy;

  pactilex = 14;
  pacoffx = -1;
  pactiley = 23;
  pacoffy = 0;

  px = pactilex*TILESIZE+1+pacoffx;
  py = pactiley*TILESIZE+1+pacoffy;

  mx = my = 0;

  while(1)
  {
    uint8_t dir;

    dir = readJoystick();

    switch(dir)
    {
    case DIRLEFT:
      mx = -1;
      break;
    case DIRRIGHT:
      mx = 1;
      break;
    case DIRUP:
      my = -1;
      break;
    case DIRDOWN:
      my = 1;
      break;

    default:
      break;
    }

    // Wall detection.
    if (mx!=0 && pacoffx==0) // Moving LEFT or RIGHT.
    {
      if (getTileStatus(pactilex+mx, pactiley)!=0) mx = 0;
    }

    if (my!=0 && pacoffy==0) // Moving UP or DOWN.
    {
      if (getTileStatus(pactilex, pactiley+my)!=0) my = 0;
    }

    TV.delay_frame(1);

    // Erase player.
    TV.draw_rect(px-2, py-2, 4, 4, BLACK);

    // Move...
    if (mx!=0 && pacoffy==0)
    {
      px = px + mx;
      pacoffx = pacoffx + mx;
      if (pacoffx<-1) {
        pacoffx=1;
        pactilex--;
      }
      if (pacoffx>1) {
        pacoffx=-1;
        pactilex++;
      }
    }

    if (my!=0 && pacoffx==0)
    {
      py = py + my;
      pacoffy = pacoffy + my;
      if (pacoffy<-1) {
        pacoffy=1;
        pactiley--;
      }
      if (pacoffy>1) {
        pacoffy=-1;
        pactiley++;
      }
    }

    // Draw player.
    TV.draw_rect(px-2, py-2, 4, 4, WHITE);
  }
}

// Given tile x/y, return whether that tile is path (0) or wall (1)
uint8_t getTileStatus(uint8_t tilex, uint8_t tiley)
{
  uint8_t byte = pgm_read_byte_near(&mazeTiles[tiley][tilex/8]);
  uint8_t bit = tilex-((tilex/8)*8);
  return bitRead(byte, 7-bit);
}

// Draw tiles for the walls.
void drawWallTiles()
{
  // Draw grid center dots.
  for (uint8_t tilex=0; tilex<TILEW; tilex++)
  {
    for (uint8_t tiley=0; tiley<TILEH; tiley++)
    {
      if (getTileStatus(tilex, tiley)!=0)
      {
        TV.draw_rect((tilex*3), (tiley*3), 2, 2, WHITE, WHITE);
      }
    }
  }
}

// Draw tile center dots.
void drawTileCenters()
{
  for (uint8_t tilex=0; tilex<TILEW; tilex++)
  {
    for (uint8_t tiley=0; tiley<TILEH; tiley++)
    {
      if (getTileStatus(tilex, tiley)!=0)
      {
        TV.set_pixel((tilex*3)+1, (tiley*3)+1, WHITE);
      }
    }
  }
}

// Draw tile grid.
void drawTileGrid()
{
  for (uint8_t x=0; x<TILEW; x++)
  {
    for (uint8_t y=(x & 1); y<TILEH; y=y+2)
    {
      TV.draw_rect(x*TILESIZE, y*TILESIZE, 2, 2, WHITE, WHITE);
    }
  }
}

// Read joystick.
uint8_t readJoystick()
{
  uint16_t joy;

  joy = analogRead(JOYSTICKXPIN);
  if (joy<24)
  {
    return DIRLEFT;
  }
  else if (joy>1000)
  {
    return DIRRIGHT;
  }

  joy = analogRead(JOYSTICKYPIN);
  if (joy<24)
  {
    return DIRDOWN; // reversed on iTead Joystick Shield
  }
  else if (joy>1000)
  {
    return DIRUP;
  }
}

Next time, I will move this movement system in to the maze bitmap display, and see if I can’t get the animated Pac-Man running around the maze without getting stuck. Of course, after all this work, it won’t look like much more than the first demo I put together… But it looks much different on the inside…

To be continued…

Arduino Pac-Man part 5 – dot dilemma

(This bit was written on 2/10/2014. I am setting these posts to go up on a schedule so I don’t just dump five new articles in one day. It’s like time travel. By the time you read this, and notice problems in what I have written, I may have already figured that out, in the past. Time travel is cool.)

See also: part 1, part 2, part 3 and part 4.

In today’s part of this series I will be stepping away from coding for a bit to discuss some problems that popped up once I actually took some time to think about the task at hand: writing a Pac-Man game for an Arduino.

In the previous four parts, you have seen how I went from hooking up two resistors to get video out of an Arduino, to experimenting with the TVout library to display things on a TV screen and, ultimately, creating the shell of a Pac-Man style dot eating game. Initially, things went very fast and easy. In the video demo I originally posted…


…you see what appears to be a somewhat working game engine, complete with an animated character that can be moved around a maze (without going through the walls) and passing over dots which disappear. What can I say? I got lucky, and remember doing things like this in BASIC on my first computer, a Commodore VIC-20 and then on a Radio Shack TRS-80 Color Computer.

But there was a problem with the demo. The way Pac-Man is kept from running through walls is by checking pixels in the direction he is moving. If there is a conflict, I stop the motion. As you see in the video, this simple trick works quite well…unless you have rounded corners. To demonstrate, let’s revisit the layout graphic I created:

Screen Shot 2014-02-10 at 9.43.56 PMHere, the red Pac-Man is heading to the right, and it can easily check for the white wall in front of it by checking above or below where the dot would be (so it does not detect a dot and stop on it). BUT, I kept finding the Pac-Man getting stuck and then even running through and over the screen, crashing in to unknown memory. After a bit of experimenting, I understood why.

Screen Shot 2014-02-10 at 9.47.57 PMIn this second photo, if Pac-Man was moving down, and then at this moment he tried to move right, the program would allow it since there was no pixel to the top right or bottom right. It was because of this that my Pac-Man would get stuck and, sometimes, get out of alignment with the maze and end up going through walls.

I experimented with various types of hot spots, and thought this one might work:

Screen Shot 2014-02-10 at 9.50.26 PMMy thought was that I would first check the green dots in the direction Pac-Man was moving. If they were clear, then I would check the light blue dots. As you can see, it works for this corner situation. Unfortunately, it also stopped the Pac-Man when it was a full pixel from any solid wall since the green dots would pass, but the light blue were on the wall. Fail! If I had just made the walls square, I could cheat and do it like this quite easily, but I am trying to replicate the arcade game as close as I can given the limitations of these graphics.

If you have already seen a solution, I’d love to hear it. But as it turns out, I won’t be doing it this way as all because while I was trying to figure this out, I ran in to a much larger problem: the dots.

I already knew I couldn’t just check for pixel collision. I had to ignore the dots. I had planned to just check above and below where the dot would be. In Invaders09 (my Space Invaders-style game I did in 6809 assembly for the Color Computer), I checked for screen pixels for my collision and it worked great. But, I had a multicolor screen and I could check for pixels of a certain color and determine what to do based on that. (I could have put white stars in the background and ignored them, but stopped on anything not white to test for a hit.)

But that’s not the problem… I was already looking ahead to the ghosts and, indeed, my current version of the software has four ghosts (three in the “Ghost House” and one on top in starting position) sitting there, animating away (but not moving around yet). As those ghosts wander the maze (needing the same type of wall detection as our hero would need), I realized they would pass over the dots and erase them, just like Pac-Man does. (Yeah, in my demo it looked like he was eating the dots, but it was really just erasing them.)

Normally, I might just track all of the dots on the screen as game objects. But, with only 2K of memory on an Arduino UNO (and most of that being used for the video output — I had about 230 bytes free), there was not even enough RAM to give each dot a status byte. I needed something more clever.

First, I could just leave them on the screen and do pixel detection. I would have to have the ghosts detect walls AND see if they hit a dot. If there was a dot, I would redraw it as the ghost passed. If Pac-Man hit a dot, I could score it and not redraw it. Not a bad idea.

Second, I could have the dot positions stored in Flash in an array (so it did not use RAM) and use  an RAM array of bytes where each bit represented the status of a dot. There are 240 dots, so dividing that by 8 (eight bits per byte, so each byte could represent eight dots) would take up only 30 bytes. As things moved around the screen, I could see if there were on a “dot spot” and check the status of the dot by looking it up in a table and checking those RAM bytes. Also not a bad idea.

Third, I worried that even 30 bytes might be too much, and considered just setting pixels along the right side of the screen and using video memory for scratch memory. As the game played, there would be an annoying set of dots/lines somewhere on the right side that would slowly vanish as Pac-Man ate up the dots. This would probably look awful. This was a bad idea.

While I was worrying about the dots and wall detection, I then realized I have no idea how Pac-Man really works. If I were being lazy (like oh so many 80s home versions of dot eating games), I would just let the ghosts wander around the maze randomly or in the general direction of the player. It would be a fine dot gobbling game, but it wouldn’t be Pac-Man to anyone who really knew how to play it. I have long heard that Pac-Man had patterns that could be used to solve each level, and that each ghost had its own personality with how it moved. Most home versions did not play the same.

pacman-cocoThinking back, I remembered an Australian fried of mine, Nick Marentes, had come out with a Pac-Man Tribute game for the Tandy Color Computer 3 years ago. He lovingly recreated the look of the game and the sounds of the game, but since I was not much of a player of the arcade version, I had no idea if it played remotely like the original.

So I asked him.

No. I didn’t have any of those luxuries when I did Pacman. I came up with my own algorithm.

But it came out very similar in concept although I didn’t have the multiple Ghost personalities. – Nick M.

Nick is a real game programmer going back to the early 1980s on a TRS-80 Model I. He even had hist games sold by Radio Shack. His website is a great read. Here is his Pac-Man Tribute website:

http://www.members.optusnet.com.au/nickma/ProjectArchive/pacman.html

And his current game project, Popstar Pilot (which is what inspired me to document my humble efforts at a game):

http://www.members.optusnet.com.au/nickma/PopstarPilot/

If Nick couldn’t figure it out, what chance did I have? But, he wrote his tribute back in 1997. The public internet was barely getting started (remember AOL?). Today, you can find just about anything! And indeed, this is the case. Nick referred me to a webpage called “Game Internals”:

http://gameinternals.com/post/2072558330/understanding-pac-man-ghost-behavior

This site broke down how the ghosts behaved, and in doing so, also solved my wall detection problem. (See also: Jamey Pittman’s “Pac-Man Dossier”). Everything seems to have been reverse engineered about this game, allowing someone to create a very accurate playalike, if they desire.

The modern programmer has no excuse nowadays. – Nick M.

If you visit either of those sites, you will see that the Pac-Man screen is broken up in to 8×8 tiles, and the entire 224×288 resolution display holds 28×36 tiles. The ghosts use these tiles for targeting where they will move. A ghost will decide which route to take, for instance, by determining which open tile (left, right, up, down) from the ghost is closer to the target square. In some cases, this causes the ghosts to do stupid things, like taking a much longer route than necessary. Math is hard.

The tiles are also used for collision detection. Since the Pac-Man game sprites are larger than a tile, a sprite is considered to be in whatever tile the CENTER of the sprite touches. And if a ghost and Pac-Man are in the same tile, there is a collision.

I decided I would create a binary map of the tiles to represent walls or spaces. 28×36 tiles is 1008, and if I used bits, I could represent that with an array of 126 bytes in flash memory (1008/8). I created the tile map in a text editor:

XXXXXXXXXXXXXXXXXXXXXXXXXXXX
X            XX            X
X XXXX XXXXX XX XXXXX XXXX X
X XXXX XXXXX XX XXXXX XXXX X
X XXXX XXXXX XX XXXXX XXXX X
X                          X
X XXXX XX XXXXXXXX XX XXXX X
X XXXX XX XXXXXXXX XX XXXX X
X      XX    XX    XX      X
XXXXXX XXXXX XX XXXXX XXXXXX
     X XXXXX XX XXXXX X
     X XX          XX X
     X XX XXX--XXX XX X
XXXXXX XX X      X XX XXXXXX
          X      X          
XXXXXX XX X      X XX XXXXXX
     X XX XXXXXXXX XX X
     X XX          XX X
     X XX XXXXXXXX XX X
XXXXXX XX XXXXXXXX XX XXXXXX
X            XX            X
X XXXX XXXXX XX XXXXX XXXX X
X XXXX XXXXX XX XXXXX XXXX X
X   XX                XX   X
XXX XX XX XXXXXXXX XX XX XXX
XXX XX XX XXXXXXXX XX XX XXX
X      XX    XX    XX      X
X XXXXXXXXXX XX XXXXXXXXXX X
X XXXXXXXXXX XX XXXXXXXXXX X
X                          X
XXXXXXXXXXXXXXXXXXXXXXXXXXXX

The Pac-Man tiles include the whole screen, including the top and bottom of the screen that my version would not display, but that was okay since there was no need for walls up there anyway – no way to get there. BUT, I found that there were four target tiles the ghosts would use that were were outside of the maze. I worked out that I could still the tile map represent everything (for ghost targeting) but only care about the “visible” section that would map to the screen.

My Pac-Man maze was 84×95. If I made my tiles 3×3, that would be 84 pixels across (28*3=84). Since my screen did not include the top and bottom section (score, players left, fruits, etc.), I was really only showing about 31 vertical tiles of the 36 the arcade had (31*3=93). With this in mind, I went back to my layout graphic to see what I would have to change, if anything.

Screen Shot 2014-02-10 at 10.32.56 PMIf you count the grid blocks across the top of the image, you will see there are 30 versus the arcade’s 28. I had made each grid a size that divided evenly with the maze with (all based on math, which is hard). My grids were 3×3, and just like in the Pac-Man arcade tiles, a dot was in the center of a grid. But why was I off by 2 tiles? Because my low resolution graphics didn’t let me draw the thin walls around the outside of the maze as thin as they really needed to be. If I took out the 1-pixel gap around the outside wall, you would see that my maze actually would be 28 tiles across. Perfect!

Even though that would be more accurate, it wouldn’t look as nice, so at this point I decided to keep my maze like it was, and adjust so the tiles started one pixel in to my drawing. Basically, I would ignore my extra left and right grid columns, and pretendI just had 28 since those were all the game cared about.

I got lucky! Here is what my display looks like with the tiles drawn where the walls are:

Screen Shot 2014-02-10 at 11.17.28 PM

Now, I would be able to use this tile map to know if Pac-Man could move somewhere, and I would also be able to use it for the ghost targeting. All I would need to do is translate between the larger screen resolution and the tile map. i.e., if Pac-Man were at (41,69) based on his top left corner — and that is his starting position in the maze — the center of Pac-Man (a 5×5 sprite) is at (43,71). That represents tile (14,whateveritis). I just had to do some math (math is hard) and adjust the physical X/Y coordinates from the extra space I had to the left or right, and then do some converting stuff.

Math is hard.

The end result, I hope, will be some functions that let me pass in a screen X/Y coordinate and get back the appropriate tile the object is in. I will also need a way to query a tile and see if it is available for Pac-Man to move in. Recall my earlier code:

  // Initialize player.
  px = 41;
  py = 69;
  mx = 0;
  my = 0;

Pac-Man’s on screen top-left coordinate is (px,py). If the joystick is pressed to the right, mx=1 is set. Then, every time we move the object, we do “px = px + mx;” so px=41 becomes px=42 (moving one pixel to the right). All I would have to do is query that new (x,y) to see if Pac-Man could move there, and disallow it if he could not. (Update: As I review this before posting, I have found a flaw in this logic. I will discuss that in an upcoming post.)

For ghosts, each time Pac-Man moved, it would loop through each of the four ghosts to see what tile they were currently in. To save processing time, I’d probably stash that away somewhere so I wouldn’t have to do all the math (math is hard) every single time through for multiple ghosts.

AND… maybe I could do something else kinda neat. Here is a photo from the webpage of Simon Owen:

pacman-sprites

He captured the sprite data from the arcade Pac-Man. These are the objects used to draw the arcade game (raw objects, color is applied when they are placed on screen based on palette settings I think). Notice the row of blue/red shapes in the center? Those are all the sprites that make up the maze. Rather than me having to have an entire bitmap of the maze I want to draw, I think I could just scan that tile table (the thing I drew with X’s earlier) and blast the appropriate maze tile on the screen! My maze bitmap data takes up 1045 bytes of flash storage, and if I could draw the maze based on the size of those tiles plus my tile map, I would be saving quite a bit of flash.

It’s not quite as easy as this. I could draw all the line portion of the maze based on the map and not use tiles at all, but the ghost house in the center is a special case so I’d have to either draw it manually, draw it using tiles, or just bitmap that object there. Any of those would save flash over how I currently do it.

Consider this added to the “to try” list for this project.

But before I go, look at those sprites again… Notice there aren’t enough of them for Pac-Man? The arcade hardware has Pac-Man facing right and down, but not up and left. Apparently it takes the existing sprite data and just flips it to make the other versions of Pac-Man. What a neat way to save some memory back in 1982! Unfortunately, for Arduino we have more flash than RAM, so these types of tricks won’t help us. Still, it’s neat.

In the next installment, maybe I will have had time to work on what I have discussed here and can tell you if it worked. Or not. Math is hard.

Arduino Pac-Man part 4 – maze

In the first entry of this series, I explained how I got started playing with Arduino video output. In the second update, I discussed getting the first TV output displayed. In part 3, I learned how to display bitmaps and animate a simple character. Today, I begin discussing how I built the maze for a Pac-Man style game.

Puck-Man was an arcade game released in Japan in 1980. When it was brought over to America, the name was changed to Pac-Man to avoid having a name that rhymed with a dirty word. To read more on the history of Pac-Man, check out the Wikipedia article:

http://en.wikipedia.org/wiki/Pac-Man

To create an Arduino Pac-Man, I would need to recreate the maze. I was originally going to try to draw out the maze in binary (see part 3). I looked for a screen shot of the actual Pac-Man arcade game so I could recreate the maze as closely as possible. I did a Google image search and found a screen shot like this one from the wikipedia entry:

Pac-manThe tiny image was 224×288 because that was the actual resolution of the arcade game. Many arcade games used standard monitors turned sideways so they were in portrait mode (taller). I would be using a standard landscape TV display and TVout video with a resolution of 120×96. If I was willing to turn a TV set sideways, I could almost make the maze work just by trimming everything in half. Instead, I decided I would get rid of the score at the top, and the lives left/level display at the bottom, and move them to the right side of the screen. This is a common approach taken by home versions of arcade games designed to play on sideways monitors.

I loaded up the image in a graphics program and cropped off the top and bottom, leaving me with something like this:

Pac-man-croppedSince I was having problems trying to draw this out pixel by pixel in binary, I decided to scale the image down to the desired height (96) and then zoom in to it so I could get a closer look at where the pixels should go. This would produce an 87×96 pixel image, leaving 33 pixels to the size of the image to move the score and other items. (The size would have to be adjusted to 86×95 for some reasons I have already forgotten.)

My scaled image looked like this:

Pac-man-cropped-scaledThat was a bit too tiny to work on, so I zoomed in to 800% and started inspecting the layout.

Screenshot 2014-02-09 15.46.41Now I was able to try to count dots and start recreating the level. I was too lazy to try to recreate this by hand in binary code, so I made a new layer to draw pixels on, and began drawing out the maze. It looked like this (you will notice I was actually using a different screen shot than the Wikipeida page example I showed above):

Screenshot 2014-02-09 15.52.15

Since the maze is a mirror image, I was only doing one side of the screen. When I got it done, I would just copy that half, flip it and paste it to the other side. The process to do this was a bit time consuming as I was figuring spacing out. Originally, I thought the sides and thing parts of the maze would be solid (two pixels side by side) but as I did the math, I realize I could make the thin sections of the maze have one pixel space, and the thicker portions have two pixel space, and it will all work out. I did quite a bit of trail and error as I adjusting things to make sure the spacing of every hallway was consistent.

I created a Pac-Man graphic object so I could move it around the maze to test clearance. In my TVout experiment, I was making an 8×7 Pac-Man. To fit in this maze, the character would have to be 5×5, as would the ghosts. Eventually, I had a maze created, including where the dots would go (even the correct number of them). My finished product looked like this:

Screenshot 2014-02-09 16.00.46The grid lines were set to the spacing of an individual pixel, to help with drawing. You will see the test Pac-Man bitmaps as well as a ghost, which I would then move around the screen in the graphics editor to make sure all the tunnels and hallways were the same size. Eventually, I produced this final graphic:

pacman-arduino-mazedotsYou may notice that there is some extra space on the right side. I kept the final output to be a multiple of 8-pixels (one per byte) because I thought it might make things easier for what comes next.

At this point, I could have used this graphic and recreated it in binary source code, but I decided to use a program that would convert a graphics file to C data structures. The TVout site suggests a program, but I would have had to compile it and run it from a command line. Instead, a quick Google led me to this site:

http://www.cemetech.net/sc/

This web page allows you to upload a graphics file and have it translated in to a variety of formats. It seems to be for graphic calculators, but one of the options was “Prizm/Nspire C (1/2/4/8-Bit Palettized Color)” which did the trick. I uploaded my bitmap graphics file, selected that conversion option, and then it produced the following source code:

1-Bit Palettized Color: Each pixel takes 1 bits.

	const color_t sprite_palette[2] = {0x0000, 0xffff};

	const unsigned char sprite[1045] = {
		0x3f,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xf0,
		0x40,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x08,
		0x9f,0xff,0xff,0xff,0xff,0x87,0xff,0xff,0xff,0xff,0xe4,
		0xa0,0x00,0x00,0x00,0x00,0x48,0x00,0x00,0x00,0x00,0x14,
		0xa0,0x00,0x00,0x00,0x00,0x48,0x00,0x00,0x00,0x00,0x14,
		0xa4,0x92,0x49,0x24,0x92,0x49,0x24,0x92,0x49,0x24,0x94,
		0xa0,0x00,0x00,0x00,0x00,0x48,0x00,0x00,0x00,0x00,0x14,
		0xa0,0x00,0x00,0x00,0x00,0x48,0x00,0x00,0x00,0x00,0x14,
		0xa4,0x7f,0x88,0xff,0xe2,0x49,0x1f,0xfc,0x47,0xf8,0x94,
		0xa0,0x80,0x41,0x00,0x10,0x48,0x20,0x02,0x08,0x04,0x14,
		0xa4,0x80,0x41,0x00,0x10,0x48,0x20,0x02,0x08,0x04,0x94,
		0xae,0x80,0x49,0x00,0x12,0x49,0x20,0x02,0x48,0x05,0xd4,
		0xa4,0x80,0x41,0x00,0x10,0x48,0x20,0x02,0x08,0x04,0x94,
		0xa0,0x80,0x41,0x00,0x10,0x48,0x20,0x02,0x08,0x04,0x14,
		0xa4,0x7f,0x88,0xff,0xe2,0x31,0x1f,0xfc,0x47,0xf8,0x94,
		0xa0,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x14,
		0xa0,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x14,
		0xa4,0x92,0x49,0x24,0x92,0x49,0x24,0x92,0x49,0x24,0x94,
		0xa0,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x14,
		0xa0,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x14,
		0xa4,0x7f,0x88,0xc4,0x7f,0xff,0xf8,0x8c,0x47,0xf8,0x94,
		0xa0,0x80,0x41,0x20,0x80,0x00,0x04,0x12,0x08,0x04,0x14,
		0xa0,0x80,0x41,0x20,0x80,0x00,0x04,0x12,0x08,0x04,0x14,
		0xa4,0x7f,0x89,0x24,0x7f,0xcf,0xf8,0x92,0x47,0xf8,0x94,
		0xa0,0x00,0x01,0x20,0x00,0x48,0x00,0x12,0x00,0x00,0x14,
		0xa0,0x00,0x01,0x20,0x00,0x48,0x00,0x12,0x00,0x00,0x14,
		0xa4,0x92,0x49,0x24,0x92,0x49,0x24,0x92,0x49,0x24,0x94,
		0xa0,0x00,0x01,0x20,0x00,0x48,0x00,0x12,0x00,0x00,0x14,
		0xa0,0x00,0x01,0x20,0x00,0x48,0x00,0x12,0x00,0x00,0x14,
		0xbf,0xff,0x89,0x1f,0xe0,0x48,0x1f,0xe2,0x47,0xff,0xf4,
		0x80,0x00,0x41,0x00,0x10,0x48,0x20,0x02,0x08,0x00,0x04,
		0x7f,0xfe,0x41,0x00,0x10,0x48,0x20,0x02,0x09,0xff,0xf8,
		0x00,0x01,0x49,0x1f,0xe0,0x30,0x1f,0xe2,0x4a,0x00,0x00,
		0x00,0x01,0x41,0x20,0x00,0x00,0x00,0x12,0x0a,0x00,0x00,
		0x00,0x01,0x41,0x20,0x00,0x00,0x00,0x12,0x0a,0x00,0x00,
		0x00,0x01,0x49,0x20,0x00,0x00,0x00,0x12,0x4a,0x00,0x00,
		0x00,0x01,0x41,0x20,0x00,0x00,0x00,0x12,0x0a,0x00,0x00,
		0x00,0x01,0x41,0x20,0x00,0x00,0x00,0x12,0x0a,0x00,0x00,
		0x00,0x01,0x49,0x20,0xff,0xff,0xfc,0x12,0x4a,0x00,0x00,
		0xff,0xfe,0x41,0x20,0xff,0x03,0xfc,0x12,0x09,0xff,0xfc,
		0x00,0x00,0x41,0x20,0xc0,0x00,0x0c,0x12,0x08,0x00,0x00,
		0xff,0xff,0x88,0xc0,0xc0,0x00,0x0c,0x0c,0x47,0xff,0xfc,
		0x00,0x00,0x00,0x00,0xc0,0x00,0x0c,0x00,0x00,0x00,0x00,
		0x00,0x00,0x00,0x00,0xc0,0x00,0x0c,0x00,0x00,0x00,0x00,
		0x00,0x00,0x08,0x00,0xc0,0x00,0x0c,0x00,0x40,0x00,0x00,
		0x00,0x00,0x00,0x00,0xc0,0x00,0x0c,0x00,0x00,0x00,0x00,
		0x00,0x00,0x00,0x00,0xc0,0x00,0x0c,0x00,0x00,0x00,0x00,
		0xff,0xff,0x88,0xc0,0xc0,0x00,0x0c,0x0c,0x47,0xff,0xfc,
		0x00,0x00,0x41,0x20,0xc0,0x00,0x0c,0x12,0x08,0x00,0x00,
		0xff,0xfe,0x41,0x20,0xff,0xff,0xfc,0x12,0x09,0xff,0xfc,
		0x00,0x01,0x49,0x20,0xff,0xff,0xfc,0x12,0x4a,0x00,0x00,
		0x00,0x01,0x41,0x20,0x00,0x00,0x00,0x12,0x0a,0x00,0x00,
		0x00,0x01,0x41,0x20,0x00,0x00,0x00,0x12,0x0a,0x00,0x00,
		0x00,0x01,0x49,0x20,0x00,0x00,0x00,0x12,0x4a,0x00,0x00,
		0x00,0x01,0x41,0x20,0x00,0x00,0x00,0x12,0x0a,0x00,0x00,
		0x00,0x01,0x41,0x20,0x00,0x00,0x00,0x12,0x0a,0x00,0x00,
		0x00,0x01,0x49,0x20,0x7f,0xff,0xf8,0x12,0x4a,0x00,0x00,
		0x7f,0xfe,0x41,0x20,0x80,0x00,0x04,0x12,0x09,0xff,0xf8,
		0x80,0x00,0x41,0x20,0x80,0x00,0x04,0x12,0x08,0x00,0x04,
		0xbf,0xff,0x88,0xc0,0x7f,0xcf,0xf8,0x0c,0x47,0xff,0xf4,
		0xa0,0x00,0x00,0x00,0x00,0x48,0x00,0x00,0x00,0x00,0x14,
		0xa0,0x00,0x00,0x00,0x00,0x48,0x00,0x00,0x00,0x00,0x14,
		0xa4,0x92,0x49,0x24,0x92,0x49,0x24,0x92,0x49,0x24,0x94,
		0xa0,0x00,0x00,0x00,0x00,0x48,0x00,0x00,0x00,0x00,0x14,
		0xa0,0x00,0x00,0x00,0x00,0x48,0x00,0x00,0x00,0x00,0x14,
		0xa4,0x7f,0x88,0xff,0xe2,0x49,0x1f,0xfc,0x47,0xf8,0x94,
		0xa0,0x80,0x41,0x00,0x10,0x48,0x20,0x02,0x08,0x04,0x14,
		0xa0,0x80,0x41,0x00,0x10,0x48,0x20,0x02,0x08,0x04,0x14,
		0xa4,0x7c,0x48,0xff,0xe2,0x31,0x1f,0xfc,0x48,0xf8,0x94,
		0xa0,0x02,0x40,0x00,0x00,0x00,0x00,0x00,0x09,0x00,0x14,
		0xa4,0x02,0x40,0x00,0x00,0x00,0x00,0x00,0x09,0x00,0x94,
		0xae,0x92,0x49,0x24,0x92,0x01,0x24,0x92,0x49,0x25,0xd4,
		0xa4,0x02,0x40,0x00,0x00,0x00,0x00,0x00,0x09,0x00,0x94,
		0xa0,0x02,0x40,0x00,0x00,0x00,0x00,0x00,0x09,0x00,0x14,
		0xbe,0x12,0x48,0xc4,0x7f,0xff,0xf8,0x8c,0x49,0x21,0xf4,
		0x81,0x02,0x41,0x20,0x80,0x00,0x04,0x12,0x09,0x02,0x04,
		0x81,0x02,0x41,0x20,0x80,0x00,0x04,0x12,0x09,0x02,0x04,
		0xbe,0x11,0x89,0x24,0x7f,0x8f,0xf8,0x92,0x46,0x21,0xf4,
		0xa0,0x00,0x01,0x20,0x00,0x48,0x00,0x12,0x00,0x00,0x14,
		0xa0,0x00,0x01,0x20,0x00,0x48,0x00,0x12,0x00,0x00,0x14,
		0xa4,0x92,0x49,0x24,0x92,0x49,0x24,0x92,0x49,0x24,0x94,
		0xa0,0x00,0x01,0x20,0x00,0x48,0x00,0x12,0x00,0x00,0x14,
		0xa0,0x00,0x01,0x20,0x00,0x48,0x00,0x12,0x00,0x00,0x14,
		0xa4,0x7f,0xff,0x3f,0xe2,0x49,0x1f,0xf3,0xff,0xf8,0x94,
		0xa0,0x80,0x00,0x00,0x10,0x48,0x20,0x00,0x00,0x04,0x14,
		0xa0,0x80,0x00,0x00,0x10,0x48,0x20,0x00,0x00,0x04,0x14,
		0xa4,0x7f,0xff,0xff,0xe2,0x31,0x1f,0xff,0xff,0xf8,0x94,
		0xa0,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x14,
		0xa0,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x14,
		0xa4,0x92,0x49,0x24,0x92,0x49,0x24,0x92,0x49,0x24,0x94,
		0xa0,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x14,
		0xa0,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x14,
		0x9f,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xe4,
		0x40,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x08,
		0x3f,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xf0
	};

Look familiar? We do not need the “const color_t sprite_palette” structure, and only need to make a minor change to the other one (adding PROGMEM so it is stored in Arduino flash rather than RAM, and adding the width and height values as the start):

PROGMEM const unsigned char playfield[] = {
  88,95,
  0x3f,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xf0,
  0x40,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x08,
  ...

This gave me a bitmap I could display on startup with “TV.bitmap(0, 0, play field)”. I created the new Pac-Man 5×5 bitmaps by hand, as well as the ghosts. For Pac-man, he can face four directions, so I decided to add another dimension to the array: direction. Then, each direction had four frames. And each frame had the array of actual bitmap data. Fun! It looked like this:

#define PLAYERW    5
#define PLAYERH    5
#define PDIRS      2
#define PFRAMES    4

PROGMEM const unsigned char player[PDIRS][PFRAMES][PLAYERH+2] = {
  { // Right
    {
      PLAYERW,PLAYERH,  // width, height
      //12345---
      0b01110000,
      0b11111000,
      0b11111000,
      0b11111000,
      0b01110000
    }
    ,
    {
      PLAYERW,PLAYERH,  // width, height
      //12345---
      0b01110000,
      0b11111000,
      0b11000000,
      0b11111000,
      0b01110000
    }
    ,
    {
      PLAYERW,PLAYERH,  // width, height
      //12345---
      0b01110000,
      0b11100000,
      0b11000000,
      0b11100000,
      0b01110000
    }
    ,
    {
      PLAYERW,PLAYERH,  // width, height
      //12345---
      0b01110000,
      0b11111000,
      0b11000000,
      0b11111000,
      0b01110000
    }
  }
  ,
  { // Left
    {
      PLAYERW,PLAYERH,  // width, height
      //12345---
      0b01110000,
      0b11111000,
      0b11111000,
      0b11111000,
      0b01110000
    }
    ,
    {
      PLAYERW,PLAYERH,  // width, height
      0b01110000,
      0b11111000,
      0b00111000,
      0b11111000,
      0b01110000
    }
    ,
    {
      PLAYERW,PLAYERH,  // width, height
      //12345---
      0b01110000,
      0b00111000,
      0b00011000,
      0b00111000,
      0b01110000
    }
    ,
    {
      PLAYERW,PLAYERH,  // width, height
      //12345---
      0b01110000,
      0b11111000,
      0b00111000,
      0b11111000,
      0b01110000
    }
  }
  ,
};

Since I was just making things up as I went (I started working on this around 10pm or so, and spent a few hours on it), I probably will clean things up in the code I present in these articles. In the above example, the bitmaps are 0=right, 1=left, 2=up and 3=down. I think I may reorder them to follow the “NEWS” format (0=north/up, 1=wast/right, 2=west/left, and 3=south/down) just so there is a pattern. Not that it really matters, since a good program would be using #defines for the directions anyway, so the magic numbers won’t be seen.

For the ghosts, since there are no colors, and the resolution is so small you can’t really even do tricks with checkerboard patterns, I decided all the ghosts needed were two frames (to animate the bottoms), and four bitmaps to represent the ghost looking up, down, left or right. I am still not sure I like the bottom of the ghosts, but here is the data for them:

#define GHOSTS     1
#define GHOSTW     5
#define GHOSTH     5
#define GDIRS      4
#define GFRAMES    2

PROGMEM const unsigned char ghost[GDIRS][GFRAMES][GHOSTH+2] = {
  { // Right
    {
      GHOSTW,GHOSTH,  // width, height
      //12345---
      0b01110000,
      0b11111000,
      0b11010000,
      0b11111000,
      0b10101000
    }
    ,
    {
      GHOSTW,GHOSTH,  // width, height
      //12345---
      0b01110000,
      0b11111000,
      0b11010000,
      0b11111000,
      0b01010000
    }
  }
  ,
  { // Left
    {
      GHOSTW,GHOSTH,  // width, height
      //12345---
      0b01110000,
      0b11111000,
      0b01011000,
      0b11111000,
      0b10101000
    }
    ,
    {
      GHOSTW,GHOSTH,  // width, height
      //12345---
      0b01110000,
      0b11111000,
      0b01011000,
      0b11111000,
      0b01010000
    }
  }
  ,
  { // Up
    {
      GHOSTW,GHOSTH,  // width, height
      //12345---
      0b01110000,
      0b10101000,
      0b11111000,
      0b11111000,
      0b10101000
    }
    ,
    {
      GHOSTW,GHOSTH,  // width, height
      //12345---
      0b01110000,
      0b10101000,
      0b11111000,
      0b11111000,
      0b01010000
    }
  }
  ,
  { // Down
    {
      GHOSTW,GHOSTH,  // width, height
      //12345---
      0b01110000,
      0b11111000,
      0b10101000,
      0b11111000,
      0b10101000
    }
    ,
    {
      GHOSTW,GHOSTH,  // width, height
      //12345---
      0b01110000,
      0b11111000,
      0b10101000,
      0b11111000,
      0b01010000
    }
  }
};

I can now animate the ghosts the same way I did the Pac-Man in the earlier example. My next task would be to put Pac-Man on the screen and let him move around.

To be continued… (After the next part, I will have covered all the work I did that night, and I will begin turning this test in to an actual game. Assuming I have time to work on it.)

Arduino Pac-Man part 3 – animating bitmaps

In the first entry of this series, I discussed what led me to experimenting with video output on an Arduino UNO. In the second entry, I describe getting my first simple sketch showing on the TV, including bouncing some balls around the screen and moving a player. Today I continue sharing my progress as I started playing with bitmap graphics.

Another feature of the TVout library is the support of bitmapped graphics. Since the display is black and white, the graphics are 1-bit images, where each bit of a byte represents 8 pixels on the screen. “00000000” would be all pixels off, and “11111111” is all pixels on. The TVout library has a simple structure for these bitmaps, which is just an array of bytes. The first two bytes are the width (in pixels) and height (in bytes) of the bitmap. A simple 8×8 square might look like this:

PROGMEM const unsigned char square[] = {
  8, 8,
  0xFF,
  0xFF,
  0xFF,
  0xFF,
  0xFF,
  0xFF,
  0xFF
}

Digression: Hexidecimal, binary and other weird numbers.

If you are already familiar with hexadecimal, binary and such, skip this section.

0xFF in hexidecimal is 255, which is 11111111 in binary (all bits on). If you have never used hex before, here’s a quick explanation. Our “normal” numbers are base ten. We count 0 to 9 (ten) and then increment the digit to the left. We can count 0 to 9, and then we add a 1 to the beginning and start over going 10 to 19, then we add 1 to the first digit and go 20 to 29. When the first digit reaches 9 (at 99), we continue with 100 and so on.

Hexideximal is base 16. We do exactly the same thing, but counting to 16. Since our digits only cover 0-9 (ten), hex continues after the 9 with the letters A through F. So, with hex, you count 0-9, followed by A-F, then you increment the first digit and it becomes 10 through 1F, and then 20 through 2F and so on.

I wish someone would have explained it to me like this back in 1982. I found it far more confusing then.

Anyway, in a hex number (represented in C by 0x at the start), each digit represents four pixels. 0xF0 would be “11110000” and 0x0F would be “00001111”. In binary (base 2), the numbering counts to 2 and then adds the one, so you get 0, 1, 10, 11, 100, 101, 110, 111, and so on. At this point, it gets more confusing.

My point is, drawing a square in hex may be easy (all pixels on is F), but trying to create anything else quickly gets confusing. You may know binary enough to know that you can figure out the bit values (0001=1, 0010=2, 0100=4, 1000=8), but trying to draw something using 3C EF AE 31 is not the way I want to spend my time.  Instead, we cheat.

End of digression.

Creating the bitmap in hex is cumbersome, but there is a non-standard way to represent binary in the compiler that the Arduino IDE uses. This is non-standard and generally you should not write code using things that are non-standard because that code may not work in other places. But, since we are cheating, and will only be running the code on an Arduino, here is how it works:

In C, the prefix “0x” makes a number hexadecimal. In non-standard Arduino C, you can use “0b” to make the number binary. It looks like this:

x = 255;        // 255 (11111111) in decimal
x = 0xFF;       // 255 (11111111) in hexidecimal
x = 0b11111111; // 255 (11111111) in binary

This would make creating 1-bit graphics much easier in source code:

PROGMEM const unsigned char square[] = {
  8, 8,
  0b11111111,
  0b11111111,
  0b11111111,
  0b11111111,
  0b11111111,
  0b11111111,
  0b11111111,
  0b11111111
}

Don’t those 1s look more like a solid square now? How about a non-solid square with an “X” across it?

PROGMEM const unsigned char square[] = {
  8, 8,
  0b11111111,
  0b11000011,
  0b10100101,
  0b10011001,
  0b10011001,
  0b10100101,
  0b11000011,
  0b11111111
}

If you squint just right, you can see it. And this is how I decided to change my filled circle to a Pac-Man shape. Here are three variations of Pac-Man facing the right (mouth closed, mouth partially open, and mouth fully open). To get things to work out evenly, the character size was 8×7.

PROGMEM const unsigned char pacmanClosed[] = {
  PLAYERW,PLAYERH,  // width, height
  0b00111100,
  0b01111110,
  0b11111111,
  0b11111111,
  0b11111111,
  0b01111110,
  0b00111100
};

PROGMEM const unsigned char pacmanOpenSmall[] = {
  PLAYERW,PLAYERH,  // width, height
  0b00111100,
  0b01111110,
  0b11111100,
  0b11110000,
  0b11111100,
  0b01111110,
  0b00111100
};

PROGMEM const unsigned char pacmanOpenBig[] = {
  PLAYERW,PLAYERH,  // width, height
  0b00111100,
  0b01111100,
  0b11111000,
  0b11110000,
  0b11111000,
  0b01111100,
  0b00111100
};

Any one of these bitmaps could be displayed by doing “TV.bitmap(x, y, pacmanClosed);” Initially I just drew an open-mouthed Pac-Man and moved him around instead of the filled circle. Here is the complete code, with some extra stuff added, like a border around the screen (and adjusting the X/Y edge detection to know about that).

#include <TVout.h>

TVout TV;

#define BALLS      10 // Number of balls to bounce.
#define BALLSIZE   4  // Size of balls.
#define PLAYERSIZE 6  // Size of player.

#define ANALOGXPIN 0  // Pin 0 is X on iTead joystick
#define ANALOGYPIN 1  // Pin 1 is Y on iTead joystick

#define PLAYERW    8
#define PLAYERH    7

#define BORDERSIZE 2  // 1 pixel border around the screen

PROGMEM const unsigned char pacmanOpenBig[] = {
  PLAYERW, PLAYERH,  // width, height
  0b00111100,
  0b01111100,
  0b11111000,
  0b11110000,
  0b11111000,
  0b01111100,
  0b00111100
};

void setup()
{
  uint8_t i;

  TV.begin(NTSC, 120, 96);
  Serial.begin(9600);

  TV.clear_screen();

  for (i=0; i<BORDERSIZE; i++)
  {
    TV.draw_rect(i, i, TV.hres()-i*2-1, TV.vres()-i*2-1, WHITE);
  }
}

void loop()
{
  uint8_t  x[BALLS], y[BALLS];    // X and Y position of ball
  int8_t   xm[BALLS], ym[BALLS];  // X and Y movement of ball
  uint8_t  i;       // counter

  uint8_t  px, py;                // X and Y position of player

  // Initialize balls.
  for (i=0; i<BALLS; i++)
  {
    // Random position
    x[i] = random(BALLSIZE+BORDERSIZE, TV.hres()-BALLSIZE-BORDERSIZE-1);
    y[i] = random(BALLSIZE+BORDERSIZE, TV.vres()-BALLSIZE-BORDERSIZE-1);

    // Random direction
    xm[i] = random(2)*2 - 1;
    ym[i] = random(2)*2 - 1;
  }

  // Initialize player.
  px = TV.hres()/2;
  py = TV.vres()/2;

  // We will do our own control loop here.
  while(1)
  {
    // Wait for end of screen to be drawn.
    TV.delay_frame(1);

    for (i=0; i<BALLS; i++)
    {
      // Erase balls.
      TV.draw_circle(x[i], y[i], BALLSIZE, BLACK);

      x[i] = x[i] + xm[i];
      if (x[i]<=BALLSIZE+BORDERSIZE || x[i]>=TV.hres()-BALLSIZE-BORDERSIZE-1)
      {
        xm[i] = -xm[i];
        x[i] = x[i] + xm[i];
      }
      y[i] = y[i] + ym[i];
      if (y[i]<=BALLSIZE+BORDERSIZE || y[i]>=TV.vres()-BALLSIZE-BORDERSIZE-1)
      {
        ym[i] = -ym[i];
        y[i] = y[i] + ym[i];
      }

      TV.draw_circle(x[i], y[i], BALLSIZE, WHITE);
    }

    // Erase player
    TV.draw_rect(px, py, PLAYERW, PLAYERH, BLACK, BLACK);

    // Read joystick (0-1023) and convert to screen resolution.
    px = analogRead(ANALOGXPIN)/(1024/TV.hres());
    if (px<BORDERSIZE)
    {
      px = BORDERSIZE;
    } else if (px>=TV.hres()-PLAYERW-BORDERSIZE-1)
    {
      px = TV.hres()-PLAYERW-BORDERSIZE-1;
    }

    py = analogRead(ANALOGYPIN)/(1024/TV.vres());
    if (py<BORDERSIZE)
    {
      py = BORDERSIZE;
    } else if (py>=TV.vres()-PLAYERH-BORDERSIZE-1)
    {
      py = TV.vres()-PLAYERH-BORDERSIZE-1;
    }

    // Draw player.
    TV.bitmap(px, py, pacmanOpenBig);
  }
}

In the above code, the right and bottom edge detection is still off by one pixel, but I was just rushing from experiment to experiment and wasn’t taking the time to fix things.

So now we have a Pac-Man that can be moved around the screen… But Pac-Man animates. I had already created the different frames of Pac-Man, but rather than use code to choose which one to display, I decided I would put them all in an array, and let the program cycle through them. Instead of just having one array of bitmap bytes, I would use a multidimensional array so I could hold each array of bitmap frames in it. I duplicated one of the animation frames so I could just cycle through them (1 closed, 2 slightly open, 3 fully open, 4 slightly open, 1 closed, 2 slightly open, 3 fully , 4 closed) instead of having to control the sequence myself.

I created the array like this:

PROGMEM const unsigned char pacman[PFRAMES][PLAYERH+2] = {
  { // Closed
    PLAYERW,PLAYERH,  // width, height
    0b00111100,
    0b01111110,
    0b11111111,
    0b11111111,
    0b11111111,
    0b01111110,
    0b00111100
  }
  ,
  { // Open Small
    PLAYERW,PLAYERH,  // width, height
    0b00111100,
    0b01111110,
    0b11111100,
    0b11110000,
    0b11111100,
    0b01111110,
    0b00111100
  }
  ,
  { // Open Big
    PLAYERW,PLAYERH,  // width, height
    0b00111100,
    0b01111100,
    0b11111000,
    0b11110000,
    0b11111000,
    0b01111100,
    0b00111100
  }
  ,
  { // Open Small
    PLAYERW,PLAYERH,  // width, height
    0b00111100,
    0b01111110,
    0b11111100,
    0b11110000,
    0b11111100,
    0b01111110,
    0b00111100
  }
};

I needed a new #define for the number of frames (four frames, an array of four), and then had to specify the size of each array. If the bitmap is 7 bytes tall, the array is 7 plus the extra two bytes at the start that tell the width and height.

Now to display a frame, I would use “TV.bitmap(px, py, pacman[frame]);” where frame is 0-3 (four frames). I added a new frame counter that would cycle from 0 to 3 over and over, but it was way too fast. I added a frame delay value so it would only increment the frame every type that count was reached. The code that does that looks like this:

#include <TVout.h>

TVout TV;

#define BALLS      10 // Number of balls to bounce.
#define BALLSIZE   4  // Size of balls.
#define PLAYERSIZE 6  // Size of player.

#define ANALOGXPIN 0  // Pin 0 is X on iTead joystick
#define ANALOGYPIN 1  // Pin 1 is Y on iTead joystick

#define PLAYERW    8  // Width of player.
#define PLAYERH    7  // Height of player.
#define PFRAMES    4  // Frames for the player.
#define PFRATE     5  // Count to 5, display next frame.

#define BORDERSIZE 2  // 1 pixel border around the screen

PROGMEM const unsigned char pacman[PFRAMES][PLAYERH+2] = {
  { // Closed
    PLAYERW,PLAYERH,  // width, height
    0b00111100,
    0b01111110,
    0b11111111,
    0b11111111,
    0b11111111,
    0b01111110,
    0b00111100
  }
  ,
  { // Open Small
    PLAYERW,PLAYERH,  // width, height
    0b00111100,
    0b01111110,
    0b11111100,
    0b11110000,
    0b11111100,
    0b01111110,
    0b00111100
  }
  ,
  { // Open Big
    PLAYERW,PLAYERH,  // width, height
    0b00111100,
    0b01111100,
    0b11111000,
    0b11110000,
    0b11111000,
    0b01111100,
    0b00111100
  }
  ,
  { // Open Small
    PLAYERW,PLAYERH,  // width, height
    0b00111100,
    0b01111110,
    0b11111100,
    0b11110000,
    0b11111100,
    0b01111110,
    0b00111100
  }
};

void setup()
{
  uint8_t i;

  TV.begin(NTSC, 120, 96);
  Serial.begin(9600);

  TV.clear_screen();

  for (i=0; i<BORDERSIZE; i++)
  {
    TV.draw_rect(i, i, TV.hres()-i*2-1, TV.vres()-i*2-1, WHITE);
  }
}

void loop()
{
  uint8_t  x[BALLS], y[BALLS];    // X and Y position of ball
  int8_t   xm[BALLS], ym[BALLS];  // X and Y movement of ball
  uint8_t  i;       // counter

  uint8_t  px, py;                // X and Y position of player
  uint8_t  playerFrame;           // Player frame to display
  uint8_t  playerRate;            // Frame speed counter

  // Initialize balls.
  for (i=0; i<BALLS; i++)
  {
    // Random position
    x[i] = random(BALLSIZE+BORDERSIZE, TV.hres()-BALLSIZE-BORDERSIZE-1);
    y[i] = random(BALLSIZE+BORDERSIZE, TV.vres()-BALLSIZE-BORDERSIZE-1);

    // Random direction
    xm[i] = random(2)*2 - 1;
    ym[i] = random(2)*2 - 1;
  }

  // Initialize player.
  px = TV.hres()/2;
  py = TV.vres()/2;

  playerFrame = 0;
  playerRate = 0;

  // We will do our own control loop here.
  while(1)
  {
    // Wait for end of screen to be drawn.
    TV.delay_frame(1);

    for (i=0; i<BALLS; i++)
    {
      // Erase balls.
      TV.draw_circle(x[i], y[i], BALLSIZE, BLACK);

      x[i] = x[i] + xm[i];
      if (x[i]<=BALLSIZE+BORDERSIZE || x[i]>=TV.hres()-BALLSIZE-BORDERSIZE-1)
      {
        xm[i] = -xm[i];
        x[i] = x[i] + xm[i];
      }
      y[i] = y[i] + ym[i];
      if (y[i]<=BALLSIZE+BORDERSIZE || y[i]>=TV.vres()-BALLSIZE-BORDERSIZE-1)
      {
        ym[i] = -ym[i];
        y[i] = y[i] + ym[i];
      }

      TV.draw_circle(x[i], y[i], BALLSIZE, WHITE);
    }

    // Erase player
    TV.draw_rect(px, py, PLAYERW, PLAYERH, BLACK, BLACK);

    // Read joystick (0-1023) and convert to screen resolution.
    px = analogRead(ANALOGXPIN)/(1024/TV.hres());
    if (px<BORDERSIZE)
    {
      px = BORDERSIZE;
    }
    else if (px>=TV.hres()-PLAYERW-BORDERSIZE-1)
    {
      px = TV.hres()-PLAYERW-BORDERSIZE-1;
    }

    py = analogRead(ANALOGYPIN)/(1024/TV.vres());
    if (py<BORDERSIZE)
    {
      py = BORDERSIZE;
    }
    else if (py>=TV.vres()-PLAYERH-BORDERSIZE-1)
    {
      py = TV.vres()-PLAYERH-BORDERSIZE-1;
    }

    // Draw player.
    TV.bitmap(px, py, pacman[playerFrame]);

    playerRate++;
    if (playerRate>=PFRAMES)
    {
      playerRate = 0;
      playerFrame++;
      if (playerFrame>=PFRAMES)
      {
        playerFrame = 0;
      }
    }
  }
}

And now I had an animated Pac-Man I could move around the screen… At this point, I think I had decided I would try to draw a Pac-Man maze and see if I could move the Pac-Man around in it.

In the next update, we will look at how I recreated the Pac-Man maze.

Arduino Pac-Man part 2 – It lives!

In the first entry of this series, I discussed what led me to experimenting with video output on an Arduino UNO. Today I will begin retracing my steps of what I did on the night of February 9th, 2014, which led to be creating the basic structure of an unplanned Pac-Man style video game.

To hook video up to an Arduino, all you need is two resistors and an RCA connector. I used an old audio/video cable for a digital camera, and had to visit my local Radio Shack to pick up one of the resistors I did not already have. On the TVout project page, you will see you need 1K ohm resistor, and a 470 ohm resistor. Each resistor connects to specific pins of the Ardunio, then they are wired together on the other side and connected to the center (video) wire of the RCA cable/jack. The shield wire of the RCA cable/jack goes to the Arduino ground. That’s all there is too it. Here is a cluttered photo of how I wired things up, using an iTead Studios screw shield to make things a bit easier, and a random terminal block screw thing just to hold some wires together:

20140210-122859.jpg

To install the TVout library, visit the Google-hostred project page and download the zip file. I extracted the zip file, and then from the Arduino IDE I selected “Sketch -> Import Library -> Add Library…”

Screenshot 2014-02-09 13.09.27After this, I was able to create a new project based on one of the included TVout examples:

Screenshot 2014-02-09 13.10.51I built and uploaded this example project, and watched it run on the only thing I had handy with composite video input: some old video goggles I bought from a liquidator clearance years ago for dirt cheap. These low resolution displays were useless for most things, but would have more resolution than what the TVout could provide: 120×96 default.

The demo looks like this (video from YouTube user Cottees):

It lives! I must have connected the two wires and two resistors properly!

Now, with video output, the first thing I wanted to do was create my own sketch that drew something. I gutted the demo leaving just the bare lines of code:

#include <TVout.h>

TVout TV;

void setup()
{
  TV.begin(NTSC, 120, 96);

  TV.clear_screen();

  TV.draw_circle(TV.hres()/2,TV.vres()/2,TV.vres()/3,WHITE);
}

void loop()
{
}

This simple sketch draw a circle in the middle of the display. Once I had this working, my next thought was to test animation by making the circle bounce around the screen. I added variables to track X and Y position, and movement for X and Y (either +1 or -1, or 0 if not moving). I also added edge detection so the ball wouldn’t fly off the screen. (The TVout library appears to be coded for speed and does little if any error checking – drawing things outside of displayed screen crashed my UNO).

The circle blazed across the screen leaving a trail of pixels.

#include <TVout.h>

TVout TV;

void setup()
{
  TV.begin(NTSC, 120, 96);

  TV.clear_screen();
}

void loop()
{
  uint8_t  x, y;    // X and Y position of ball
  int8_t   xm, ym;  // X and Y movement of ball
  
  // Center of screen
  x = TV.hres()/2;
  y = TV.vres()/2;
  
  // Start moving to the right, and down.
  xm = 1;
  ym = 1;
  
  // We will do our own control loop here.
  while(1)
  {
    TV.draw_circle(x, y, 4, WHITE);
    
    x = x + xm;
    if (x<4 || x>TV.hres()-4) xm = -xm;
    y = y + ym;
    if (y<4 || y>TV.vres()-4) ym = -ym;
  }
}

To resolve this, I added some code to erase the circle before drawing it at a new position. This created much flickering, so I used the “wait for frame” function so I could slow things down and do the drawing/erasing at the end of a screen being updated.

#include <TVout.h>

TVout TV;

void setup()
{
  TV.begin(NTSC, 120, 96);

  TV.clear_screen();
}

void loop()
{
  uint8_t  x, y;    // X and Y position of ball
  int8_t   xm, ym;  // X and Y movement of ball
  
  // Center of screen
  x = TV.hres()/2;
  y = TV.vres()/2;
  
  // Start moving to the right, and down.
  xm = 1;
  ym = 1;
  
  // We will do our own control loop here.
  while(1)
  {
    // Wait for end of screen to be drawn.
    TV.delay_frame(1);
    
    // Erase circle
    TV.draw_circle(x, y, 4, BLACK);

    x = x + xm;
    if (x<4 || x>=TV.hres()-4) xm = -xm;
    y = y + ym;
    if (y<4 || y>=TV.vres()-4) ym = -ym;
    
    TV.draw_circle(x, y, 4, WHITE);
  }
}

Next, I wondered how many more balls I could bounce before it started to slow down. I changed my X and Y variables to arrays, and used a #define to set the number of balls. I also made a #define for the ball size, and could use this for checking the edge of the screen. If a circle size is 4, the center will be at the specified X and Y coordinate, and the circle will be drawn 4 pixels away from that. So, if you tried to “draw_circle(0, 0, 4)”, the left and top of the circle would be drawn off the screen. To adjust, X and Y should never go lower than the circle size, and should never go larger than screen width/height minus circle size. (Note the use of “BALLSIZE-1” in the example below. TVout will report the horizontal size as 120, and vertical size as 96. The pixels are actually 0-119 and 0-95, so you subtract one to get the end pixel.)

#include <TVout.h>

TVout TV;

#define BALLS    10 // Number of balls to bounce.
#define BALLSIZE 4  // Size of balls.

void setup()
{
  TV.begin(NTSC, 120, 96);

  TV.clear_screen();
}

void loop()
{
  uint8_t  x[BALLS], y[BALLS];    // X and Y position of ball
  int8_t   xm[BALLS], ym[BALLS];  // X and Y movement of ball
  uint8_t  i;       // counter
  
  // Initialize balls.
  for (i=0; i<BALLS; i++)
  {
    // Random position
    x[i] = random(BALLSIZE, TV.hres()-BALLSIZE-1);
    y[i] = random(BALLSIZE, TV.vres()-BALLSIZE-1);
  
    // Start moving to the right, and down.
    xm[i] = 1;
    ym[i] = 1;
  }
  
  // We will do our own control loop here.
  while(1)
  {
    // Wait for end of screen to be drawn.
    TV.delay_frame(1);
    
    for (i=0; i<BALLS; i++)
    {
      // Erase balls.
      TV.draw_circle(x[i], y[i], BALLSIZE, BLACK);
    
      x[i] = x[i] + xm[i];
      if (x[i]<=BALLSIZE || x[i]>TV.hres()-BALLSIZE-1) xm[i] = -xm[i];
      
      y[i] = y[i] + ym[i];
      if (y[i]<=BALLSIZE || y[i]>=TV.vres()-BALLSIZE-1) ym[i] = -ym[i];
      
      TV.draw_circle(x[i], y[i], BALLSIZE, WHITE);
    }
  }
}

Ten circles was still fast. Twenty showed some slowdown. But it still looked cool. To make it cooler, you could randomize the ball directions:

    // Random direction
    xm[i] = random(2)*2 - 1;
    ym[i] = random(2)*2 - 1;

The random(2) function will return 0 or 1, so multiplying that by 2 produces 0 or 2, and subtracting 1 from that produces -1 or 1. (It took me a bit to figure this out. Math is hard.)

My next thought was to put a player character on the screen and allow it to be moved by the joystick. (This could also be done by the serial console and keyboard presses.) I initially drew a square to make it look different from the circles, but then I had to do different math for screen edge detection since X and Y of a square is the top left corner. I decided to use a filled circle. I would move it around using the analog joystick.

#include <TVout.h>

TVout TV;

#define BALLS      10 // Number of balls to bounce.
#define BALLSIZE   4  // Size of balls.
#define PLAYERSIZE 6  // Size of player. 

#define ANALOGXPIN 0  // Pin 0 is X on iTead joystick
#define ANALOGYPIN 1  // Pin 1 is Y on iTead joystick

void setup()
{  
  TV.begin(NTSC, 120, 96);
  Serial.begin(9600);

  TV.clear_screen();
}

void loop()
{
  uint8_t  x[BALLS], y[BALLS];    // X and Y position of ball
  int8_t   xm[BALLS], ym[BALLS];  // X and Y movement of ball
  uint8_t  i;       // counter

  uint8_t  px, py;                // X and Y position of player
  
  // Initialize balls.
  for (i=0; i<BALLS; i++)
  {
    // Random position
    x[i] = random(BALLSIZE, TV.hres()-BALLSIZE-1);
    y[i] = random(BALLSIZE, TV.vres()-BALLSIZE-1);
  
    // Random direction
    xm[i] = random(2)*2 - 1;
    ym[i] = random(2)*2 - 1;
  }
  
  // Initialize player.
  px = TV.hres()/2;
  py = TV.vres()/2;
  
  // We will do our own control loop here.
  while(1)
  {
    // Wait for end of screen to be drawn.
    TV.delay_frame(1);
    
    for (i=0; i<BALLS; i++)
    {
      // Erase balls.
      TV.draw_circle(x[i], y[i], BALLSIZE, BLACK);
    
      x[i] = x[i] + xm[i];
      if (x[i]<BALLSIZE || x[i]>TV.hres()-BALLSIZE-1) xm[i] = -xm[i];
      
      y[i] = y[i] + ym[i];
      if (y[i]<=BALLSIZE || y[i]>=TV.vres()-BALLSIZE-1) ym[i] = -ym[i];
      
      TV.draw_circle(x[i], y[i], BALLSIZE, WHITE);
    }
    
    // Erase player
    TV.draw_circle(px, py, PLAYERSIZE, BLACK, BLACK);
    
    // Read joystick (0-1023) and convert to screen resolution.
    px = analogRead(ANALOGXPIN)/(1024/TV.hres());
    if (px<PLAYERSIZE) 
    {
      px = PLAYERSIZE;
    } else if (px>TV.hres()-PLAYERSIZE-1)
    {
      px = TV.hres()-PLAYERSIZE-1;
    }
    
    py = analogRead(ANALOGYPIN)/(1024/TV.vres());
    if (py<PLAYERSIZE) 
    {
      py = PLAYERSIZE;
    } else if (py>TV.vres()-PLAYERSIZE-1)
    {
      py = TV.vres()-PLAYERSIZE-1;
    }
    
    // Draw player.
    TV.draw_circle(px, py, PLAYERSIZE, WHITE, WHITE);
  }
}

At this point, I was starting to think a simple game might be “dodge the circles” and the player would see how long they could survive moving their larger filled circle around while trying to avoid all the bouncing, smaller circles.

But I wasn’t done experimenting with TVout yet. There was still more it could do, with bitmaps, to draw things that weren’t just lines or circles.

Next time, I will discuss how I turned my filled circle in to a simple Pac-Man type character, which made the rest of the night turn in to an attempt to recreate that game.

Arduino Pac-Man project

Here is a quick demo of something I wrote last night for an Arduino UNO. I have an iTead Studios Screw Shield attached to it ($3.50, to simplify hooking up wires), and an iTead Joystick Shield ($4.50, for input). Then, using only two resistors and an RCA cable, plus a clever library, I was able to start programming a Pac-Man style game on the Arduino. This is the first of a multi-part series of articles explaining the steps in this project.

When I first began playing with an Arduinio Duemilanove at work in 2012,  I learned how to program it by reading through the reference material at the main Arduino website. I had heard of Arduino, but had never learned anything about it, so I was quite impressed with all the various libraries that were available to handle everything from serial communication to I2C protocol. One of the more surprising discoveries was that you could do  video output by wiring up two resistors to an RCA phono jack. Clever programming allowed the Arduino to create the scan line signals that would produce a low resolution black and white composite video screen. Here is the information page on it, showing a simple diagram of how you wire things up:

http://playground.arduino.cc/Main/TVout

At the time, I thought we might be able to use low-cost Arduinos to output some information displays at a local haunted house event (wait times, “now serving” queue management systems, etc.) but I never pursued it.

Later, I found out about two projects that were based on this TVout concept to produce retro Arduino video games: Hackvision, and the Video Game Shield.

The Hackvision was a custom Arduino device (based around the UNO) with directional and fire buttons right on the circuit board, as well as RCA jacks for audio and video output. It is currently available in a kit for $33.95, or fully assembled for $43.95.

The Video Game Shield is an add-on shield for an Arduino UNO that provided RCA jacks for audio and video output, as well as connectors for two Nintendo Wii nunchuck controllers. It is available in a kit for $22.50.

A third, similar project, called the Gamby, is a shield that includes a low resolution LCD display as well as bottoms, and turns an Arduinio in to a portable Gameboy-style gaming device. It is available in a kit for $25.

If you visit the project websites, you will find some example videos of games written for these add-ons. Due to the different ways that input is handled, games written for one platform do not play on the others (and I think the Gamby has a different video system). It does appear that games written for the generic TVout library are easily ported between systems.

Some of the games that have been written include clones of Space Invaders, Pong, Tetris, and Asteroids. The Gamby site has quite a few other titles (like a Joust clone) that I do not think have been ported to the other platforms.

I have recently become re-interested in retro video games. Two  retro video arcades have recently opened here in Des Moines, Iowa. (UP-DOWN opened in October 2013, followed by  Barcadium opened in January 2014.) Being able to step back in time and play games like Space Invaders (1978) and Pac-Man (1980) makes me feel both young again, and very old, as I realize most of the visitors to these arcades were not even born when I was first inserting quarters in these machines when they were brand new.

This led me to dusting off the old MAME emulator and once again exploring various classic arcade games. I was particularly intrigued by some of the late 1970s games that came out before the arcade scene got popular. These games used low resolution, black and white graphics and simple sound effects. I couldn’t help but think “I could have written this.” But back then, “no one” had a computer – especially not some seven year old kid growing up in Houston, Texas (like I was). So no, I could not have written any of those games, back then, two decades later, I did create and sell my own Space Invaders clone for the Radio Shack Color Computer running under OS-9. If I could have done that in 1978, maybe I would be a millionaire right now ;-)

Up next: It lives!