On java.net, there was a post by kfarnham about my articles on writing Pac-man game in JavaFX. He wondered whether there would be a fifth article. The answer is positive. Yesterday, my last article of a series, “Writing the Pac-Man Game in JavaFX Part 5“, had been published on insiderRIA.com. This final article detailed the chasing algorithms of the ghosts. I think it is probably one of the most interesting things in the code.
When writing the game, there are a few points we need to consider before designing an algorithm of the ghosts, such as effectiveness, randomness, simplicity. You can refer to the article about considerations on these aspects. An excerpt from the article is listed below in blue text. It discussed the choice of a proper algorithm. This algorithm not only serves as the chasing logic, it can also control the escaping behavior of the ghosts.
. . . . . .
After some thinking, I found that the distance between a ghost and the Pac-Man is a good ranking metric. The shorter the distance is, the higher the score is given to a particular choice. The advantages of using the distance as a metric are obvious. It is very simple and can be caculated easily. Besides, this algorithm makes a ghost move in the direction that has the shortest distance to thePac-Man. To illustrate this algorithm, let’s look at the below figure.
In the figure, the ghost Blinky is moving into an intersection from the right to the left. When it reaches the intersection, it has three possible choices of its next movement: to go up, to go down and to continue heading left. Going down is not a valid move because it hits the border of the maze. So we need to compare the other two options. The below table shows the computation of the distance of the two possible moves:
|Choice||X distance||Y distance||Total|
As shown in the table, the distance from the intersection to the Pac-Man character is 13 (The distance between two adjacent dots is 1). If Blinky goes up, the distance is reduced to 12. If it heads left, the distance becomes 14. Therefore, going up seems a better choice for Blinky. In this way, Blinky should be able to get closer and closer to the Pac-Man and eventually catches him.
Of course, this simple algorithm does not take into consideration for the walls in the maze. For this reason, sometimes the calculated score does not in fact represent the shortest path. However, this inaccuracy makes the ghosts appear “stupid” in the game, which is the randomness we want to achieve in the behavior. So we are going to implement it in our code. We rewrite the class MoveDecision. When the function evaluate() calculates a score, it takes in two arguments: the reference to Pac-Man instance and whether the ghost is in a hollow state. The variable distance is used to compute the score. If the ghost is going after the Pac-Man character, the score is 500-distance, which means a shorter distance yields a higher score. If the Pac-Man is hunting the ghosts(when they are hollow), the score is caculated as 500+distance. This makes the ghosts running away from the Pac-Man.
. . . . . .
Now that all the articles had been published and I hope you enjoyed reading them. The game was originally written in JavaFX 1.0, and was compatible with JavaFX 1.1. Because multi-inheritance has been removed in JavaFX 1.2, I made some minor changes to the code. The abstract class MovingObject had been changed to mixin class. The code for JavaFX 1.2 can be download from JavaFX Game Download Page.
You can now click on the below image to play the completed Pac-Man game, it is based on the newly released JavaFX 1.2 . With the improved performance, the game run very smoothly.
The Featured Articles on insideRIA.com:
May 14, 2009: Writing the Pac-Man Game in JavaFX – Part 1
May 21, 2009: Writing the Pac-Man Game in JavaFX – Part 2
May 28, 2009: Writing the Pac-Man Game in JavaFX – Part 3
June 4, 2009: Writing the Pac-Man Game in JavaFX – Part 4
June 11, 2009:Writing the Pac-Man Game in JavaFX – Part 5