Deadlock Detection in Puzzle Game Environment
Yong Suk Choi, Moon-Kyoung Park · 2012
The presence of deadlock that prevents the game player from reaching the goal state is one of well-known problems in most puzzle games. Existing deadlock detection techniques take too much time to perform algorithms detecting the deadlock, or can not guarantee that the algorithms detect all the deadlock. In this paper, we introduce Cycle Detection, a new detection technique using Graph, Local search and Pruning techniques for solving these problems. Cycle Detection presents current state of puzzle games in a graph, detects deadlock by minimizing the number of detected nodes. We performed this algorithm in real puzzle game environment in order to evaluate performance of our algorithm. As a result, we identified significant performance improvement compared to existing deadlock detection techniques.