Pacman AI An artificial intelligent controller for Pacman

Given a Pacman game with the ghost AI already implemented, the task was to implement the AI for Pacman. However, all the ghost code was hidden inside a DLL and we were limited in what we could call from the DLL. Essentially, we had access to a function that you pass board coordinates to, it returned a value representing the contents of that location.

With AI being such a broad subject, and the implementation up to the student, there were many solutions all yielding similar results. Most popular was A* path finding, but I believed that having a destination wasn't natural to playing Pacman. When you play Pacman do you always have a destination that you're heading for? Or do you generally evade the ghosts and go for the dots? In a nutshell my Pacman AI controller uses recursive functions to check the contents of each corridor to "look" if there is anything there. The contents of that direction is then summed up based on weighing of the content it finds, the direction that has the highest score is chosen.

Core Algorithm

Step 1: The orange lines represent the first method calls to LookLeft and LookRight (For simplicity only the right path will be explained).

Step 2: The LookRight method evaluates a grid coordinate, then checks if the next grid coordinate is possible to move into, if so it calls itself again, this repeatedly happens until it finds another opening / junction.

Step 3: Depending on the junction the other recursive functions are called. Where the orange line branches into the two green lines, it would call LookUpwards first then once that method has finished it would call LookDownwards.

Step 4: LookUpwards acts exactly the same as LookRight execpt, it searches upwards. It repeatedly evaluates each grid coordinate, once it finds a junction it calls look in that direction. This is where the upper green line branches to the right as a white line.

Step 5: The white LookRight method call branches in three directions and calls LookUpward, LookRight, and LookDown (in that order, not that the order makes a difference). These are the two red lines on the right, one going up, one going down.

Step 6: The white line continues until it finds a junction.

Step 7: Finally, the depth limit has been reached; the red lines do not call any other functions. Next the green line that branched upwards from the orange line going to the right, continues until it finds another junction, then the whole process is repeated.

The above steps are repeated in all directions possible. The results of each step's evaluation are summed up. This value represents the total potential of that direction. In this case the controller can see the turquoise ghost and the orange ghost. Therefore he would turn left.
Note: looking through the worm hole costs one depth so the white line doesn't continue. In this case, the left orange line would mirror the view paths on the right.

Evaluation function weights

Each one of these headings below indicates how attractive each direction is:

Dots: Food has a standard weighting. It isn't based on the dots value. This is because the controller isn't designed to rack up big scores; its purpose is to successfully complete the level. In addition, when the ghosts are "hunted" after a power pill was eaten, the value of dots is zero. This is to avoid Pacman taking a longer route with more dots when he could just eat a ghost.

Junctions: Where two or more corridors meet a junction is created. If a junction has more corridors connected to it, the more appealing it is, since there are more potential escape routes.

Direction Bonus: There is a bonus given for moving in the same direction as Pacman did in the previous step. This is to discourage him going back on his previous path.

Ghosts: The ghosts are weighted on standard value plus their Manhattan distance multiplied by a modifier. The modifier varies between the ghosts; red and orange have a lower modifier meaning they are more dangerous than the green and turquoise ghosts.

Blue Ghosts: Blue ghosts get a very big chunk of points. A blue ghost is weighted very favourably. If he is too far to be captured then his weighting is nothing. This is calculated by using Manhattan distance and getting their slow down factor. As a failsafe a timer is used to stop Pacman trying to eat them at the last minute.

Previous Path: A Pacman's previous position was stored. This trail he leaves behind him is less appealing since he has already been there. Logically, the fewer times he goes back on his own route the better. Thus he's more likely to be collecting dots.

Danger zones

There are known danger zones which are very dangerous for Pacman to enter since there is only one entrance and exit. Therefore he can be easily trapped.

These grid coordinates were stored. The current grid coordinate being evaluated is compared to this container.

If the position is in one of the danger zones then that cell becomes slightly less desirable, which means Pacman will only choose that route if there are no ghosts around and they are nearly the last dots.

Dynamic Power Pill weighting: the power pill's weight changes depending on the total distance (grid distance) of the ghosts. If it is below 30 then the pill becomes very desirable. This is based on an estimation that he will be able to catch at least one. Two is his average. He has frequently eaten all four ghosts. Otherwise it's reasonably undesirable. Although, it is still more desirable than nothing, so Pacman will take a power pill if there are no other dots around.

Further details

This module was a double module with Advanced rendering (HLSL shader), which made it more demanding due to time requirements.