Photos  Personal  Links  Restaurants  Recipes  2020 Cruise 

pacBuzzAI

pacBuzzAI is a chase-and-evade arcade Java applet patterned after the now-famous Pacman arcade game. In this game, our hero pacBuzz tries to gobble up as many of the round power pellets as he can without getting eaten by one of the four bulldog ghosts who inhabit his maze homeland.

In pacBuzzAI, the game is played from the point of view of the actors rather than from the point of view of a human player. What this means is pacBuzz is only aware of the surroundings he can see. He doesn't know if there is a ghost lurking around the corner until he gets to that junction. Therefore, he needs to be constantly on guard, checking for ghosts at every step. In a standard Pacman game, the human player is fully aware of the maze and where the ghosts are. This makes it much easier to avoid deadends and the ghosts.

The pacBuzzAI Pellet-Gathering Algorithm

Several algorithms were explored before it was decided that pacBuzzAI would use a modified greedy algorithm for pellet gathering. At every step, pacBuzz looks down the available corridors and assigns a point value to the number of pellets. Each pellet has a base worth of 30, but that value is reduced based upon pacBuzz's distance from the pellet. This prevents him from walking clear across the maze simply to find a single pellet. After the pellets' values have been summed, a deduction is made if pacBuzz detects one of the bulldog ghosts in the corridor. The corridor which scores highest is the one pacBuzz chooses to traverse.

So what happens if pacBuzz can't find any pellets in the corridor? Well, several algorithms were tried here, including breadth-first searching and a standard maze-walk (keeping the maze wall to the right at all times), but it was found that using a simple random selection was just as good as any of those algorithms, considering the cost in time of doing an exhaustive search for pellets. To prevent the pacBuzz from getting hung up, once he makes the first random selection, he continues moving in that direction until he either comes across a corridor with pellets, or he is blocked. If he gets blocked, he will not go back the way he came, unless that is the only possible option ( i.e. he's in a dead-end ). With the standard Java pseudorandom generator, it is highly unlikely pacBuzz will ever get stuck in a particular area as he might with a standard greedy algorithm.

Ghost Avoidance

pacBuzz has a strong survival instinct. When he encounters a ghost in a hallway, he is aware the ghost is going to begin chasing him. So, he immediately enters a ghost avoidance algorithm designed to put as much distance as possible between himself and the ghost. He figures out whether he is closest to the ghost in the x or y direction and makes his move away from the ghost based on that. (If he is closest to the ghost in the x-direction, then he tries to move away in the x-direction, and if that is impossible, he moves in the y-direction.) pacBuzz only moves towards the ghost as a last resort.

Meet The Ghosts

The original Pacman game had four ghosts named Inky, Blinky, Pinky and Clyde. Our four bulldog ghosts keep the same names and some of the same behaviors as the original ghosts. Blinky is the fastest of the four ghosts and makes a single move every round. Pinky is slightly slower and makes one move every other round. Inky makes a single move every three rounds and Clyde (Pokey) only makes a move every four rounds.

The ghosts move out of their house as quickly as possible and then make random movements until they spot pacBuzz. As pacBuzz does, once the ghosts make a random movement, they continue to go that same direction until they are forced to make another choice (or they spot pacBuzz). Also like pacBuzz, they do not retrace their steps on a random movement.

Once a ghost notices pacBuzz in a corridor, he begins giving chase. Because at level 1, each of the ghosts is only as fast as the pacBuzz, they cannot catch him unless they can corner him or gang up on him.

Performance

I was slightly disappointed by the performance of the modified greedy algorithm. Without ghosts in the picture, pacBuzz successfully cleared the maze with no problems. However, with the ghosts in the picture, he tends to eventually get trapped by the ghosts. The main reason for this is because pacBuzz can only really handle the presence of one ghost at a time. What needs to be done is for pacBuzz to recognize that he is being trapped and try to evade all of the ghosts converging on him.

Future Work

1. pacBuzzAI was designed to allow pacBuzz to learn, but there was not enough time to implement all of the learning features.What I had envisioned was to allow pacBuzz to adjust the weights on pellet value and ghost cost until he was able to successfully complete the maze. The factor by which he discounts a pellet based upon its distance from him also is a factor he should be able to adjust. The way I envisioned this was that after every game in which pacBuzz was killed by a ghost, he would increase that ghost's cost by 5 percent, which would mean he would put a greater value on avoiding that ghost next time.
2. As mentioned above, pacBuzz does not handle being chased by multiple ghosts very well, particularly when they are coming at him from multiple directions. There are two main reasons for this problem, both of which are relatively easy to fix. First of all, pacBuzz makes his avoidance choice based upon the first ghost he sees. It would be better for him to look at the positions of all ghosts he can see before making an avoidance decision. Second, pacBuzz only cares about ghosts he can see. So, if he avoids the ghosts by turning a corner, he stops caring, which is fine for immediate avoidance. pacBuzz should, however, remember there was a ghost nearby so he can keep avoiding him.
3. I had intended to install a timer to monitor game movement, but when there was not enough time to fully implement learning, I did not bother. With a timer, pacBuzz would be able to monitor how quickly he navigated the board and adjust the pellet weights accordingly to allow him to clear the board faster. Each time he cleared the board, he would record the time it took and increase the value of the pellets closer to him to make sure he got all the pellets he could in one zone. If the next game took longer, then he'd adjust the numbers back down.
4. Also built into the game is an ability for pacBuzz to remember his last 20 moves, since a real person in a maze would likely be able to remember a certain number of steps. In a learning pacBuzz game, pacBuzz would be able to check back against those moves to make sure he is not retracing his steps. Ideally, pacBuzz would never go back down the same path twice, unless he was trying to avoid a ghost.
5. The ability exists for pacBuzzAI to play like a regular Pacman game and allow you to continue playing after getting killed. I did not implement this because I was more interested in seeing how pacBuzz performed at the start of each game as opposed to as a game continued. With a learning pacBuzzAI, it would be important to be able to pick up where you left off and continue the game. The ability also exists to add levels of difficulty with different mazes. The ghosts' speed is tied to a level number, so as the level increases, they would move faster.
6. pacBuzzAI has built-in support for power pellets and ghost chasing, but this is not implemented, either. ( Well, actually, the power pellets are implemented, but pacBuzz does not chase the ghosts. )

Bugs

There is a flaw in the game which appears very rarely. When three of the ghosts align themselves side-by-side in a corridor, it is impossible for them to find a valid move and the game hangs. This is a simple matter of detecting this error, throwing an exception and the catching the error condition. Unfortunately, the error did not first appear until late Wednesday night.