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.
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.
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.
This module was a double module with Advanced rendering (HLSL shader), which made it more demanding due to time requirements.