Anyone who grew up in the 1980s will be familiar with Pac-Man, the arcade game in which players use a joystick to guide a tiny yellow character through a two-dimensional maze. As it moves, the character must chomp its way through golden coins while avoiding being killed by ghosts who also sweep through the maze.
Pac-Man’s popularity and gameplay make it one of the iconic games of the 1980s and among the most influential of all time.
So it’s no surprise that various groups have tried to reinvent the game for the modern world. Today, Thomas Chatzidimitris and pals at the University of the Aegean in Greece reveal how they have tackled the problem. These guys have created an Android version of the game that uses smartphone technology to translate Pac-Man into a real world chase game.
The game, called PacMap, uses a smartphone’s GPS sensors to determine a player’s location on OpenStreetMap. It then superimposes a Pac-Man grid onto the local street network within 200 meters of the player and distributes gold coins throughout. The player then has to run through these streets to collect the coins while avoiding computer-generated ghosts who also sweep the maze looking for the player.
That’s a simple idea that requires some subtlety in its implementation. The ghosts come in two types. The first move at random around the grid, hoping to catch the player by accident. Calculating their routes is straightforward using standard algorithms.
The second type of ghost, the red ghosts, actually follow the player. One way to do this would be to use commercial mapping services to determine the shortest route to the player and then follow it.
But when the player’s location changes, the ghost (and its mapping service) has to recalculate. And that’s a problem because these services limit the number of queries a single phone can make in a given time.
So the game calculates the shortest route itself by extracting the topology of the grid and then using a standard shortest route algorithm to do the calculations. The game recalculates the ghost’s routes each time the player changes direction.
Chatzidimitris and co say a modern smartphone can handle these kinds of calculations with ease. For a game space with 420 nodes, they say a Samsung Galaxy S4 smartphone can crunch the numbers in under 100 milliseconds.
PacMap is not a new game. Various websites suggest that it was launched in 2011 and is no longer available.
However, Chatzidimitris and co say the techniques they have developed to bypass the limitations of commercial mapping services could be used for any map-based chase game in future. “The use of those techniques enables programmers and designers to develop location/map-based games, with flexible scenarios that involve intelligent virtual characters dynamically adapting on players movement behavior during the game,” they say, in the Proceedings of the International Conference on Pervasive Games, which took place in Rome in October.
Incidentally, PacMap is not the first attempt to translate Pac-Man into the real world. In 2004, a team in Singapore developed a land-based version of the game in which players used augmented reality goggles with backpack power supplies to play the game in local streets. The players could chose to be the Pac-Man or the ghosts but in the pre-smartphone age, the game required specialist location equipment and numerous helpers to keep the game going.
The new work from Greece makes all this easier and could help a new generation of smartphone-based chase-games hit the market.
Ref: arxiv.org/abs/1501.02659 : PacMap: Transferring Pac-Man to the Physical Realm