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…
