The rules of Pac-Man are as follows: Pac-Man must eat dots to win, while avoiding monsters (also known as ghosts) in order to stay alive. This was a simplified version of Pac-Man: there was only one monster, one dot, and no player interaction. Everything was automated.
When I was teaching C programming in Fort Worth, I gave my class a fairly difficult assignment to teach them rudimentary object-oriented programming. The task was to write a simple automated "Pac-Man" style game. Later, I challenged the class to improve the program with some artificial intelligence. I fielded several questions about how to go about this task, and most people thought it was too hard.
Now, my class was not about graphics, so the assignment was really pretty simple and ugly. Text appeared on the screen to represent the players. Pac-Man was represented by the letter 'P' (remember the difference between single and double quotes, students?), the monster was the letter 'M', and the dot was the letter 'o'. (A small circle, that is.) The position of these three objects was represented by the place of the letters on the screen.
The artificial intelligence of the program was also pretty limited, and this was not helped by the fact that a letter on a screen can only reasonably move one space up, down, sideways, or diagonally. Moving farther than one square would make the program look jumpy, and moving less would be flatly impossible with ASCII graphics. As a result, Pac-Man would try to approach the dot on a diagonal, and would continue moving diagonally until he reached the same row or column where the dot was, then he would proceed horizontally or vertically until it ate the dot. At this point, the dot would be randomly regenerated elsewhere, and the program would go on.
At the same time, the monster was also trying to catch Pac-Man, using the same algorithm for moving towards him. And the monster would pretty easily succeed, for a number of reasons. First, Pac-Man and the monster have the same speed, so it's not hard for the monster to catch up. Second, Pac-Man doesn't "think" about the monster; he just goes for the dot. So Pac-Man had a bad habit of walking directly into the monster in his quest for food, and the game is over.
As extra credit, I suggested that the students should try to prolong Pac-Man's life by making him both faster and smarter. Only two students ever really took me up on this suggestion, with good but imperfect efforts. In some cases it looked like Pac-Man was "cheating" by jumping past or through the monster. In another situation, Pac-Man would blindly run away from the monster until he hit a wall, then clumsily dodge around and go in the other direction to get back to the dot.
Some students asked how I would do this, and I really didn't know; I hadn't thought about the problem, I just decided it would be a good exercise. But I did say I was learning Java, and I'd like to give the project a try some time.Well, here it is. In this project, I have both learned Java AND solved an interesting problem. Now you can read about my work and hopefully learn something from the experience yourself.
Here is my designer diary explaining what I went through to write this program.
And here is the code.