doodles
drububu
Pacman is a classic arcade game from the 1980s and still is a popular game among both male and female users.
Pacman has to find his way through a maze, a collection of dots, while, at the same time, a number of ghosts, named Blinky, Pinky, Inky and Clyde, are trying to capture Pacman.
Once Pacman has been captured by a ghost, a life is lost. Pacman can collect dots and can also earn a bonus dot, which gives him, for a limited amount of time time, the power to capture ghosts. Extra points are earned when, during this limited amount of time, a ghost is captured.
I decided to make a Pacman clone in HTML5.
I slightly altered the rules of the game and added some additional artificial intelligence.
The text below explains how the chosen techniques work.
The playfield is a grid containing nine horizontal and eleven vertical positions. A number is assigned to each position within the playfield. The number indicates which directions are not available. This prevents Pacman and the ghosts from moving across borders.
The numbers are composed as follows:
1 up
2 down
4 left
8 right
Number nine, for example, will prevent Pacman and the ghosts from moving to the right or upwards. Number ten prevents him from moving to the left and to the right, etc.
Unlike Pacman, which is moved by the user, the ghosts need to find their way across the playfield by using a code.
The ghosts move around the playfield and think about which direction to take whenever there is an opportunity to change direction.
In some cases, there is no need to evaluate a possible direction
change; this is the case when the available directions are horizontal or
vertical. The numbers five and ten in the example are practically not
used to consider a direction change.
If the available directions are orientated both horizontally and vertically, the current direction is assessed.
A simple solution can be used to have Pacman found by the ghost. Pacman's position in relation to the ghost's current position is assessed; if Pacman is situated to the right of the ghost's current position, the ghost should move to the right. If Pacman is situated above the ghost's current position, the ghost should move upwards, etc.
In many cases, there are two preferred directions; one of these direction is chosen at random.
The same solution is used to hide from Pacman when Pacman is trying to capture the ghosts. Instead of moving towards Pacman, the ghost will move away from Pacman.
The next approach is a more advanced solution aimed at finding Pacman.
The program keeps track of Pacman's position. Each time Pacman is moved, it check the position of the neighbours of the current position. This could be to the left, to the right, at the top or bottom. If the direction has not already been visited or blocked, it will not be used. The neighbour with the highest number is used and increased by one. This number is stored at the current position. After a while, the path of Pacman may look like the image on the right.
The numbers are used by the ghosts. When the ghost tries to capture Pacman and picks up one of these numbers, it will be easy to find Pacman; if you follow the increasing numbers, then Pacman will be found sooner or later.
Depending on the level in the game, the last approach is used more frequently, at lower levels the approach is used once in a while, to keep the player engaged. Continuous use of the last approach will lead to Pacman's sudden death; the player is not able to keep up with the deadly accuracy of the ghosts.
Each time it visits the position, the ghost increases the number of visits accordingly. If a position results in a direction change, the ghost will check how many times it has been visiting the neighbouring available positions.
The neighbouring position with the lowest number is the least visited position. This position is used as a new direction. In this way, the ghosts is able to scan the playfield efficiently without staying too long at a specific region.
Depending on the game mode - do the ghosts try to capture Pacman or do they hide from Pacman? - the new direction can be another direction than the least visited position.
If you click in the playfield, a path leading to the clicked position will appear. The path is calculated by using a technique called recursion or feedback.
The clicked position is used as a starting point. The selected position is assigned the value zero. Next, all the neighbours are checked. If the neighbour is available, the value of this position is assigned the value one; the value of the current position is increased by one. Next, the newly found positions are used for the same process. The neighbours that are available, are assigned the value of the current position increased by one.
This process is repeated until a number has been assigned to all the positions.
To lead Pacman towards the clicked position, the computer only needs to check the available directions for Pacman's current position and choose the one with the lowest number. When the number equals zero, Pacman has reached the clicked position.
The path finding technique is also used for the ghosts. Once they are capatured by Pacman, they will return to their initial position.
