Gameplay

Pacman! plays similarly to the original arcade version, except for one major difference... you're in 3D! You guide Pacman through the maze by using the arrow keys. Eating all the dots will advance you to the next level, but watch out! Blinky, Pinky, Inky, and Clyde will do whatever it takes to keep you from succeeding!

But fear not, Pacman has a way to put those evil ghosts right back where they belong. Just chomp down one of the power pellets to throw the maze into Party Mode and stun those ghosts! When stunned, Pacman can gobble up those ghosts... and earn some serious bonus points for doing it!

Tips from the Pacmasters...

• Pacman moves slower when he's chomping down on those tasty dots. If a ghost is in hot pursit, abandon those dots to make a quicker getaway!
• The ghosts are so stunned by the the dance lights that they move slower in Party Mode. Chase them down and get those extra points!
• The ghosts are human (well, they were before they died!) so they don't make smart choices all the time. If you zig zag around enough when they're chasing you down they just might slip up and you can make your escape!

Technical Goals

I had several technical goals I wanted to accomplish with this project. These included designing a useful third-person chase camera, rendering a 3D mini-map overlay, using a weighted graph for maze navigtion, and writing effective AI to control the ghosts' movements.

Third-Person Chase Camera

Pacman makes sharp, 90-degree turns, but the last thing you want to do is make your chase camera do that as well. The game would be incredibly confusing to play if the camera teleported behind Pacman whenever he turned a corner. Thus, I needed a good way to create a fluid 3D chase camera.

The ideal position for the camera to be in would be situated directly behind the player. However I can't move it straight there from its previous position. The solution attach your actual camera position to the ideal camera position with "springs" in the x and z direction (Pacman moves in the xz plane).

I say "springs" in quotes because it's not, strictly speaking, a Newtonian spring. However it's a good approximation that's quick to calculate and gives the desired effect. Essentially the acceleration of the camera along a particular axis is proportional to the distance the camera is away from the ideal camera on that axis. This causes the camera to quickly accelerate when it's far away and slighty overshoot the target as it approaches it. If Pacman remains stationary, eventually the springs will settle to their steady state, which is in the ideal camera position.

Rendering a 3D Mini-Map

Pacman is a simple game to play from a top down view because you can always see whats happening in the rest of the maze at all times. However, once you switch to a third-person chase camera, you lose your knowledge of what is happening behind you. The mini-map allows the player to always know the ghost locations and quickly locate dots they may have missed.

The 3D mini-map is accomplished by rendering all of the world geometry twice. Before the first rendering pass the color buffer is cleared as normal. The camera is projected according to the third-person chase camera and the world geometry is rendered for the first time. The projection stack is then wiped and the camera is reprojected, but this time looking straight down from above the map.

Some trickery must be done at this point. If that was all that happened, the mini-map would be rendered, but it would be behind the first pass geometry. The reason for that is that the camera must be so far away from the maze to fit it all on the screen that it virtually guarantees that it will have the furthest value in the depth buffer. Remember that everything is being rendered by the same camera into the same buffer. That means they're all competing for the smallest depth value to be shown on top. Consequently, if we leave it like this, it will be rendered behind everything else.

The solution is to scale down the entire world before rendering it in the second pass. It's scaled down to the point that the camera can be bumped right up to it and the it's just past the near plane of the camera, but still fits the entire maze on the screen. This virtually guarantees that none of the first pass geometry will have a lower depth value and that the mini-map will be rendered on top of it.

Maze Navigation with a Weighted Graph

There is a fair amount of wall geometry in Pacman, and writing collision detection code for it all wouldn't exactly be very fun. It sure wouldn't be fun to test. For this reason, I opted to use a graph for maze navigation, lay out the graph nodes physically in strategic locations, then build the maze geometry around them.

Each node in the graph has four potential neighbors: north, south, east, and west, corresponding to an axis-aligned compass in the xz plane. Nodes are bidirectionally linked so that if you can leave node A eastward and arrive at node B, you can leave node B heading westward and arrive at node A.

Pacman navigates this maze by taking user input from the keyboard, but only applying it when he reaches a node intersection. This ensures that he doesn't take a crazy left turn in the middle of a straightaway and go barreling through a wall. The only key that takes effect immediately is the down arrow, which flips Pacman 180 degrees and sends him heading back towards the node he came from.

Movement directions can also be queued up. If you press the left arrow and Pacman cannot move left immediately, he'll try to do so at the next intersection he reaches. If he can't go left at that intersection, he'll try to keep going straight ahead instead, and give it another shot at the next intersection. This process ends when he finally reaches a node that he can make a left turn at, he reaches a node that he can't turn left or continue straight ahead (he stops), or the user queues up a different direction.

Ghost AI

Pacman wouldn't be a very fun game if the ghosts weren't a challenging opponent. Thus, some kind of AI was needed to ensure the player didn't get bored and that the ghosts didn't just wander the maze aimlessly. However, if the AI was too good, the ghosts would gang up and absolutely overrun the player in a matter of seconds. The ghosts needed a way to make intelligent decisions and a way to make dumb ones.

They need to make two decisions every time they reach an intersection:

1. Am I going to make an intelligent or dumb decision?
2. Which direction am I going to go next? (decided in an intelligent or dumb way, based on the answer to the previous question)

For intelligent decision making, I used the A* path finding algorithm. Traditionally it's used in an array of partitioned space to find the shortest path to a target with objects in the way. In my implementation, it simply finds the shortest path between two nodes on the weighted graph. The graph weights are used for the "actual distance traveled" cost and the as-the-crow-flies distance between the player and the next potential node is used as the heuristic cost. The shortest path is found between the node the ghost is currently sitting at (thinking about where to go next) and the node the player is heading towards. This allows the ghosts to potentially intercept the player, rather than constantly playing catch-up chasing after nodes the player has already visited.

For dumb decision making, the ghosts use the highly-sophisticated "pull it out of thin air" algorithm. The ghost surveys what directions it can go from a particular node (including back the way it came) and picks one at random.

To further spice up the AI, each ghost is given a particular intelligence rate. This is ensures that a particular ghost answers question 1 above with a specific ratio. For example, Blinky makes intelligent decisions 80% of the time, Pinky makes them 60% of the time, Inky makes them 40% of the time, and poor Clyde is frequently bullied at school because he only makes intelligent decisions 20% of the time.

This spread of intelligence ensures that the player doesn't end up with the ghosts constantly clustering around him or constantly spread all over the maze. Most of the time Blinky and Pinky will be in hot pursuit of Pacman, putting pressure on the player to flee. However, Inky and Clyde will frequently be spread out in the areas the player needs to flee to, so the game never gets stale.

References

K. Peters. ActionScript 3.0 Animation. 2007 Apress.

P. Lester. A* Pathfinding for Beginners. http://policyalmanac.org/games/aStarTutorial.htm

S. Lantinga, S. Peter, R. Gordon. SDL_mixer Documentation. http://jcatki.no-ip.org:8080/SDL_mixer/

"Ashwin". Using GLUT Bitmap Fonts. http://stackoverflow.com/questions/14318/using-glut-bitmap-fonts