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.

Leave a Reply