The Pacman Project
Simulation
Simulating games can be useful for many aspects of developing a game. On the one hand it is easier to follow the ghosts and the pacman on a map representing Maastricht than it is to read the movement from the coordinates printed in the console. On the other hand, the simulation can be used to look for bugs in the programs. For debugging purposes, we would like to see if all the conditions defining the game rules are being followed correctly by all the players that are simulated. Such conditions could for example be: eating the pills, eating the pacman, ending the game when all pills are eaten and so on.
Like most simulations, this simulation aims on modelling the real life situation as closely as possible. This way the approximate fun factor and expected runtime can be calculated. To have a simulation as closely to the real life situation as possible, several conditions have to be taken into account such as the walking speed of humans, the fact that humans do not necessarily follow the advices provided by the AI and that we want to speed up the simulation without loosing the modelling properties.
The walking speed is modelled using a constant that defines how far a player can move in a time step of one second. These steps can then be performed as quickly as wanted without effecting the gameplay or realism properties. The modelling of humans not following the advice is done using probabilistic value that defines with which probability the player follows the advice that is provided by the Artificial Intelligence advisor.
8.1 Simulating a game
The overall process of simulating the game works as follows: the starting positions of ghosts and pacman are set at the beginning and movement is simulated from there on into the chosen direction.
In our case we chose a probability of 85% for the players to follow the advice. If a player does not follow the advice, he follows one of the remaining paths with equal probabilities. So if the player chooses to not follow the advice, the direction of the advice is ruled out and the other directions are chosen according to a random integer that is uniformly distributed.
After each refresh cycle, several checks are performed. Those checks determine whether the game ended, a pill has been eaten, the pacman is invulnerable and if the ghosts are in eating range of the pacman. If the pacman is invulnerable and one or more of the ghosts are in eating range, the pacman will eat the ghost and it will have to walk back to the starting position. If pacman is not invulnerable and in eating range of one of the ghosts, he will be eaten and the game is over. The only way to win the game for pacman to eat all the pills, while for games that last for longer than 180 minutes, it will be a draw. The advices are triggered if a player is within a certain range of the next decision node.
8.2 Realtime Simulation
The implementation of the real time simulation is written in such a way that the simulation can run parallel to any other application that is running on the server, meaning that the Simulation runs in it's own Thread. This enables the Server to run the simulation and update the player positions from it while the simulation does not have to stop. This simulation also uses the time limit of 180 minutes to set the game to be a draw.
A timer can be used to schedule the refresh cycles and it can be set to either 0, in which case no timer is used in between the simulation cycles or 1, where the timer calls the update every second or an integer bigger than one that then defines the factor with which the simulation is running referring to real time. So a timer factor of 4 would make the simulation run in 4 times real time speed.
8.3 Training simulation
The training simulation is necessary for the train of the evolutionary algorithm. Since every chromosome has to be evaluated to determine its fitness, a quick way to simulate a game using those settings needs to be available. The simulation implements the java.util.concurrent.Callable, causing the thread to make the application that calls it wait until the computation is finished and then take the result that is returned. It does not use a timer to simulate the outcome of the game as quickly as possible. So at each cycle one second is simulated. This way one game can be simulated in an average time of 500ms and and different run times depending on the heuristic parameters that are used for the evaluation. If the pacman runs away from all the ghosts games can take longer. Furthermore, there is no possibility for a game to end in a draw since the fitness needs to be explicit.