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.

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.

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:

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:

n

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.

n

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):

n

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:

n

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:

n

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:

n

#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):

n

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:

n

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:

n

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…

n

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...