How to detect deadlocks

From Sokoban Wiki

---

Revision as of 07:00, 8 December 2008

The implementation of an algorithm for detecting deadlocks depends on which types of deadlocks are to be detected. The deadlocks article describes some of the most common deadlock types. This article describes how to detect these deadlocks by a program. Please read the deadlocks article first because this article assumes the basic knowledge about the deadlock types is already known.

Detecting simple deadlocks

Simple deadlocks are a special type of bipartite deadlocks. Hence, they are detected by the bipartite deadlocks recognition algorithm. Nevertheless there should be some special treatment for this type of deadlock in a program. Simple deadlocks squares of a level never change during the gameplay. Therefore they can be precalculated at the time the level is loaded for playing. When a box is pushed during the gameplay the program just has to check if the destination square of the push is a simple deadlock square which results in a huge performance improvement (the bipartite deadlock detection is very time consuming).
We need to code an algorithm which identifies the squares from which a box never can be pushed to a goal - no matter where the other boxes are located in the level.
To do this, one can do the following for every goal square in the level:

1. Delete all boxes from the board
2. Place a box at the goal square
3. PULL the box from the goal square to every possible square and mark all reached squares as visited

After this has been done for every goal we know that from all squares that have been visited a box can be pushed to a goal. From this follows that every square not being marked as visited is a simple deadlock square.
This information is saved. When a box now is pushed to a specific square during the gameplay the program just has to check:

is this square a simple deadlock square ? If yes, then the whole situation is a deadlock and the level has become unsolvable.

Detecting freeze deadlocks

Freeze deadlocks are named "freeze" deadlocks, because one or more boxes are "frozen" on a square, that means they can NEVER be pushed away from that square - no matter how the other boxes in the level are pushed.
Therefore, to detect "frozen" boxes we have to check whether a box can ever be pushed or not.
When a box is pushed during the game we have to check whether it and maybe also some other boxes are frozen now. To do this, we do the following for both axes (vertical and horizontal push). Here the example for the horizontal axis:
The box is blocked along the horizontal axis when one of the following checks are true:

1. If there is a wall on the left or on the right side of the box then the box is blocked along this axis
2. If there is a simple deadlock square on both sides (left and right) of the box the box is blocked along this axis
3. If there is a box one the left or right side then this box is blocked if the other box is blocked.

If the box is blocked along both axes the box is "frozen". Now the program has to check whether any frozen box is not located on a goal. If this is true the level has become unsolvable.

The third check has to be implemented in a recursive algorithm. Here is an example for that:

Pushing the box to the left results in a freeze deadlock. First the algorithm checks the vertical axis -> the box is blocked for pushing vertically by a wall.
Now the program has to check if the box can be pushed horizontally.
The first two checks doesn't classify the situation as blocked (no walls and no simple deadlock squares as neighbor squares). However, the box may be blocked by the box on the left! Therefore the same checks have to be done for the box on the left of the just pushed box. This is repeated for the other two boxes. The last box (the box on the lower left) is blocked by a wall. Therefore the box right to that box is also blocked - hence, the box above that box is also blocked - and finally this also means that the box we have pushed is blocked. This means that all boxes are frozen! And, because there is one box that isn't located on a goal, the whole situation is a freeze deadlock.

Avoiding circular checks
The algorithm needs one refinement. If the algorithm just followed the 3 rules above it would result in an endless loop because (assume that we have pushed the box left to the player on square to the left):
First the box to the left of the pushed box is checked for being blocked. While doing this check the algorithm detects that the box has a neighbor box to the right. Therefore it will check that box - which is the just pushed box again! This results in a circular check which never ends.
Fortunately we can avoid this easily: Every box we already have checked for being blocked can be treated as a wall! As a result we just have to check the opposite axis for the next box we want to check for being blocked.
In the shown example level this means (again assume we just have pushed the box one square to the left):
The pushed box is checked for being blocked vertically -> yes, it is blocked
the pushed box is checked for being blocked horizontally -> the result depends on the blocking status of the box to the left -> the box to the left is checked for being blocked. Now we just have to check if this box is blocked vertically! The box may be blocked - the result depends on the blocking status of the box under the currently investigated box. And again we just have to switch the axis: we just have to check if the box is blocked horizontally!

For better understanding here are all checks that have to be done in the shown example situation:
Checks for the 1. box:

• check if the box can be pushed vertically
  • is there a wall above or under the box -> yes => the box can't be pushed vertically
• check if the box can be pushed horizontally
  • is there a wall left or right to the box -> no
  • are there simple deadlock squares on the left and right side of the box -> no
  • is there a box on the left or right side that may block the current box -> yes => check that box for being blocked

Checks for the 2. box:

• check if the box can be pushed vertically
  • is there a wall above or under the box -> no
  • are there simple deadlock squares above and under the box -> no
  • is there a box above or under the box that may block the current box -> yes => check that box for being blocked

Checks for the 3. box:

• check if the box can be pushed horizontally
  • is there a wall left or right to the box -> no
  • are there simple deadlock squares on the left and right side of the box -> no
  • is there a box on the left or right side that may block the current box -> yes => check that box for being blocked

Checks for the 4. box:

• check if the box can be pushed vertically
  • is there a wall above or under the box -> yes => the box is blocked

Because the 4. box is blocked all other boxes are blocked, too - they are frozen on their squares and can never be pushed again.
Now the program has to check whether at least one of the boxes isn't located on a goal. This is true. Hence, the whole situation is a deadlock.