Sokoban Deadlock Detection (CavePacker)
While implementing CavePacker - a Sokoban player - I stumbled upon some quite interesting problems. The deadlock detection is the most puzzling one in my opinion. It's quite hard to do a sane detection of these kind of board states in real time. Some kind of deadlocks are quite easy to detect, some others are really hard.
First of all, let me explain what a deadlock is: The sokoban board is in a state where the player(s) can't solve it anymore. That means, at least one of the packages can't be pushed onto a free goal.
Next there are different kind of deadlocks. To get an overview of some of them, just check out this Sokoban wiki.
Right now I've implemented two detection types: "Dead square deadlocks" (I called them simple deadlocks) and "Freeze deadlocks". The 2nd is already one of the none-static detectors. I had to limit the runtime of the algorithms for this one, because there are some Sokoban maps that could lead to a lot of computation. To verify the deadlock code I've added a lot of test cases in the CavePacker codebase. The most interesting ones are not yet implemented. But I'm not even sure whether it's worth the effort, because I highly doubt that these will be able to run in realtime on each package push.
The algorithm for the simple deadlocks is also quite simple:
They are detected by trying to "pull" packages from each target destination in all four directions until this doesn't work anymore. Afterwards the fields that were not touched during these pulls are deadlock fields.
The algorithm for the frozen fields is also quite straighforward:
We just try to move a package - if it is at least movable into one direction, it's not frozen. But we have to keep in mind that the package that is blocking our move might still be movable itself. This is the place where the problems arise (runtime-wise) - this algorithm is recursive and some maps require a lot of packages to be checked recursively.
First of all, let me explain what a deadlock is: The sokoban board is in a state where the player(s) can't solve it anymore. That means, at least one of the packages can't be pushed onto a free goal.
Next there are different kind of deadlocks. To get an overview of some of them, just check out this Sokoban wiki.
Right now I've implemented two detection types: "Dead square deadlocks" (I called them simple deadlocks) and "Freeze deadlocks". The 2nd is already one of the none-static detectors. I had to limit the runtime of the algorithms for this one, because there are some Sokoban maps that could lead to a lot of computation. To verify the deadlock code I've added a lot of test cases in the CavePacker codebase. The most interesting ones are not yet implemented. But I'm not even sure whether it's worth the effort, because I highly doubt that these will be able to run in realtime on each package push.
The algorithm for the simple deadlocks is also quite simple:
They are detected by trying to "pull" packages from each target destination in all four directions until this doesn't work anymore. Afterwards the fields that were not touched during these pulls are deadlock fields.
The algorithm for the frozen fields is also quite straighforward:
We just try to move a package - if it is at least movable into one direction, it's not frozen. But we have to keep in mind that the package that is blocking our move might still be movable itself. This is the place where the problems arise (runtime-wise) - this algorithm is recursive and some maps require a lot of packages to be checked recursively.
Kommentare
Kommentar veröffentlichen