Padua, Christine Joy E. and Songcuan, Glievenze P.
An enhancement of DIJKSTRA Algorithm with jump point search algorithm applied in pacman game
- Undergraduate Thesis: (BSCS major in Computer Science) -Pamantasan ng Lungsod ng Maynila 2017.
Abstract Pacman is a popular arcade game that was released in Japan in May 1980 and the game use an algorithm, the Dijkstra algorithm, which is known to find the shortest path towards its target. In our study, we are going to optimize the Dijkstra algorithm using the jump point search algorithm. The subject of this study is the ghosts that chase Pac-Man during the game and we would investigate the path, the nodes and the time of the ghost as it travels toward its target and applied the jump point search algorithm. The results should be able to help the future researches to understand on how the Dijkstra and Jump Point Search algorithm works. In the methodology, we used, we found that applying the jump point search algorithm in the ghost behavior could minimize the node, reduce the time it travels, and avoid being stuck in the loop. This optimize algorithm could be applied to other games that have the same problem and incorporate it in some applications like that used graphs or maps.