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:
I 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:
Above, 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.
The tiles that contain maze parts look like this:
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:
n
#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:
n
// 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:
n
// 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:
n
// 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:
n
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.
n
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:
n
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…
n
// 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.
n
#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…
