Implementation of A* Algorithm for Solving Sokoban Logic Games

Abstract

Sokoban is one of the puzzle category games that requires players to push boxes towards the top, bottom, left and right until the specified destination. Sometimes it takes a long time to complete a very difficult level so that a solution is needed. So that these difficulties can be overcome, we need an algorithm that can help find the right path.

A * algorithm is an algorithm that minimizes the total cost of the track under the right conditions that will provide the best solution in optimal time. A * algorithm will find the distance of the fastest route to be taken by a starting point to the destination object by removing unnecessary steps.

From the test results, this A * algorithm can help players in finding a solution to the road in the form of completion steps in the Sokoban game by determining the smallest F value.

 

Keywords - Artificial Intelligence, Games, Sokoban, A * algorithm