AI and PacMan (A story of ghosts’ intelligence)
Do you remember the good old days when we were playing PacMan and sometimes losing because of “intelligent” ghosts? What a wonderful era!
Apparently, the ghosts were not moving in a random path. And this article aims to provide AI solutions for the paths that can be used for ghosts as well as for the PacMan to reach the goal. This article will not discuss a way to implement the actual game (with all maze logic, pills, UI and etc.), this is an algorithmic discussion 🤓. This article uses Java for coding example purposes ☕️.
The article covers algorithms of Uniform Cost Search, BDFS, A* Search, and DFS. If you have never heard of these, I hope in the end of the article you’ll know how these work 😇.
Let’s start with the idea of PacMan. So, our childhood game was about to get to the pills and avoid interactions with ghosts. Ghosts were moving towards us. By the way, ghosts had names — Blinky, Pinky, Inky and Clyde. In this article let’s assume Blinky was moving with Uniform Cost Search, Pinky with DFS, Inky with A* Search, Clyde with BDFS. This just gives some gamey mood you know 😄.
Before we start, let’s speak of the actual game. The game board on the board 😎.
Here you see the game UI, CS students see a matrix 😁. A magic transformation to a code would look something like this.
int[][] maze = {
{2, 1, 1, 1, 1},
{1, 1, 1, 1, 20},
{1, 1, 1, 1, 1},
{1, 1, 1, 1, 1},
{-5, 1, 1, 1, 1}
};The code above creates a matrix named maze and is a possible representation of the UI shown above. Imagine 2 is a notation for Pacman, 20 for a ghost, -5 for pill and 1 for an empty spot. I know I have dramatically made the game easier just putting a pacman, a pill, a ghost in there. As I mentioned, this is an algorithmic article, so without any fancy and cool staff let’s move forward ✨.
For PacMan, the goal is to reach the power pills (in our case 2 needs to reach -5 (2 -> -5)), for ghosts — to eat PacMan (20 -> 2).
Now, to be able to proceed, we’d need a structure to describe a unit in a maze. Ladies and Gentlemen, welcome Node!
Node represents a unit in the maze (ghost, pacman, empty or pill). Node stores the cost of the path to reach it, it’s parent node, adjacent Nodes. What this means is that if in our maze PacMan moves to the right, the right’s position would have PacMan’s initial position as its parent node, a path cost of 1, and adjacent nodes would be right, left and bottom nodes. The node also stores a boolean value indicating if it’s PacMan, ghost, empty or pill, and a location of type Location. Location is a class which stores just the row and col. See an implementation below.
To think analytically for both PacMan and ghosts we have a start node (the node in which PacMan or ghost stands in), a destination node (the pill for PacMan, PacMan for ghosts).
Conversion of the maze units (which are basically integers)into a matrix of Nodes.
This might seem a lit bit tough, but nothing difficult happens in here.
On the second line, we create a variable named result to store all our nodes from maze units. Then we start iterating over our maze’s units, creating & populating a node for each unit. Starting from line 20, since we have already got our nodes, we iterate over them to find and populate its adjacency nodes.
One more implementation to get a pill, PacMan and a ghost node.
Nothing tough happening right? Let’s quickly jump into the cool part 😅
3, 2, 1 … Welcome AI 🎉
Blinky — UCS
The first search algorithm we would implement is the Uniform Cost Search. Since we have our maze and each maze cell has an index, we need to define costs based on active power pills, active pills locations.
Not to scare you with Java implementation yet, let’s see a pseudo code.
UCS works with priority queue as you see. In general UCS algorithm takes cost being maximal as a priority. Yet in our case we want to reach the destination in efficient way, and we use a slightly modified version of UCS to find the best move for a ghost (for a given goals set and costs). The cost of each action is 1 by default, and it can change based on three variables:
- 2 if the new node contains PacMan
- -5 if the new node contains a pill
- +20 if the new node contains a ghost
The algorithm stores an explored set for explored nodes not to add those in the frontier again.
So, in each iteration of the algorithm, it pops element from the frontier, if the element is a goal then our ghost has reached the destination` PacMan. Elsewhere, the node is added to explored set and it’s children are added to the frontier to be considered for a goal path. If the child is already contained in the frontier and has a lower path cost, then that child’s node in the frontier is replaced by the child having less cost.
Here is Java implementation.
In the code above, we define the costs and find an optimal path to the destination.
Executing the above code, for the maze
int[][] maze = {
{2, 1, 1, 1, 1},
{1, 1, 1, 1, 20},
{1, 1, 1, 1, 1},
{1, 1, 1, 1, 1},
{-5, 1, 1, 1, 1}
};We’ll get the path for 20 to reach 2 as the following
row 1 - col 4
row 1 - col 3
row 1 - col 2
row 1 - col 1
row 1 - col 0
row 0 - col 0To show the path on maze
int[][] maze = {
{2, 1, 1, 1, 1},
{1, 1, 1, 1, 20},
{1, 1, 1, 1, 1},
{1, 1, 1, 1, 1},
{-5, 1, 1, 1, 1}
};What this means is that Blinky would go to the left for its next move to be much closer to PacMan. Overall, 24 nodes were expanded. Speaking of complexity, if the branching factor is b, every time you expand out a node, you will encounter k more nodes. Therefore, there are
- 1 node at level 0,
- b nodes at level 1,
- b² nodes at level 2,
- b³ nodes at level 3,
- …
- b^k nodes at level k.
This strategy is not the most optimal one in terms of running time. Yet Blinky is happy. If Blinky is happy, we are happy 🥰.
Pinky — DFS
When it comes to algorithms, DFS is pretty popular for finding a path to destination.
DFS is a recursive algorithm that uses the idea of backtracking. It reaches to the depth of the tree, then backtracks to other branches of the tree. As a result all the nodes get visited. In our case DFS’s start node is the ghost position and destination node is the pacman’s node.
See the pseudo code below.
DFS(graph, start_node, end_node):
frontier = new Stack()
frontier.push(start_node)
explored = new Set()
while frontier is not empty:
current_node = frontier.pop()
if current_node in explored: continue
if current_node == end_node: return success
for neighbor in graph.get_neigbhors(current_node):
frontier.push(neighbor) explored.add(current_node)DFS algorithm uses stack and firstly pushes the first node in the stack. It has a set called explored to store the nodes that algorithm already explored. Then while stack is not empty, it pops the element (latest added node is popped since stacks are LIFO), adds in explored set if is not explored yet. If it is the destination node, then we’ve reached the destination, if it is not, we will add the neighbors into the stack.
See the Java implementation below.
DFS didn’t give us the best answer to the solution since it is not always guaranteed that it will give us solution, the time complexity is more and it is also recursive, which introduces an overheat, and also might cause the code to hit the stack size limit for large mazes. In our case we also terminate the algorithm when the destination node is reached which means that it can also be a non-optimal solution. DFS in our case just finds a path to the goal.
For the maze above, let’s see the result
row 1 - col 4
row 2 - col 4
row 3 - col 4
row 4 - col 4
row 4 - col 3
row 3 - col 3
row 2 - col 3
row 1 - col 3
row 0 - col 3
row 0 - col 2
row 1 - col 2
row 2 - col 2
row 3 - col 2
row 4 - col 2
row 4 - col 1
row 3 - col 1
row 2 - col 1
row 1 - col 1
row 0 - col 1
row 0 - col 0As we might notice, this is not the best solution to the problem. Overall, 21 nodes expanded. The complexity of the algorithm is O(V+E) where V is the number of vertexes and E is the number of edges.
Pinky was upset with the result, but you know what? Pinky continues to research for better one 😏.
Inky — A* Search
One of the most widely known form of best-first search is called A* search. A* is the most popular choice for pathfinding, because it’s fairly flexible and can be used in a wide range of contexts. It evaluates nodes by combining g(n), the cost to reach the node, and h(n), the cost to get from the node to the goal:
f(n) = g(n) + h(n)As a h(n) we use Manhattan distance:
h(n) = [abs(node.x — goal.x) + abs(node.y — goal.y)].
g(n) gives the path cost from the start node to node n.
The aim of this search is to catch PacMan as quickly as it possible — do not let him eat big pills. The method works quicker than other searches — the ghost finds PacMan. For this particular method, we’d need 2 more properties in the structure of Node to store f and g costs.
This works as follows. We store sets of explored and unexplored nodes. Iterate over unexplored ones and for each one if the node is a goal, then it’s found, if it’s not — then we explore the children of it. Since g cost is the path to the node, we’ll make a tempGCost to store the new path which is basically current nodes’ f cost + pathcost and tempFCost would be tempGCost + heuristic (manhathan distance) of the child node and goal.
If the child was already explored and the new f cost was bigger than the child’s actual f cost, we’d just continue the loop, since smaller f cost for that child was already found. Elsewhere, we are changing the child’s g and f costs, updating the parent, and adding it to the unexplored set.
Executing the above code for the maze, we’ll obtain
row 1 - col 4
row 1 - col 3
row 0 - col 3
row 0 - col 2
row 0 - col 1
row 0 - col 0Again, a cool result. And this is quick. Inky rocks!
BFS-Clyde
This algorithm works layer by layer — the neighbors get visited, then the children get visited.
For the BFS, a queue structure is used. The queue stores the nodes to iterate over those and an explored set stores the explored nodes. In each iteration, a new node is taken from the queue, added to the explored set if was missing in there, seen if a goal state or no, and its children are expanded to iterated over.
It turned out that Clyde that used this algorithm was just to get the pacman in one of the best ways. BDFS’s advantage was that it will always give a solution, will never get trapped to unwanted nodes, if many solutions, it will find the shortest one. However, it requires large memory, and time complexity is more. It also has long pathways when all paths to the destination are on approximately the same depth.
Clyde has the potential to develop this further. No worries, they will get to this ☺️.
Conclusion
All in all, we’ve gone through 4 AI algorithms that made ghosts much smarter for a goal of finding PacMan. For the ghosts, we have been using the destination as the PacMan. Actual game uses techniques that are not currently described in this article such as destination node as two possible steps ahead of PacMan’s initial position. Anyway, this article aimed to provide some AI cool staff in a gamy mood, and I hope you enjoyed it 😊.
Go Ahead and clap me as much as ocean’s waves 🌊😁!!!
