30
/
6/2013

Der Lagerhausverwalter

Was haben ein Lagerhausverwalter und ein Informatikstudent gemeinsam? Ihr Ziel ist es Kisten auf dafür vorgesehene Zielfelder zu buchsieren. Womit sich der Lagerhausverwalter bis zur Rente abwrackert, das hat der Student in einer Woche zu lösen.

  ####  
###  ####
#     $ # 
# #  #$ #
# . .#@ #
#########
@ = Spielfigur, $ = Kiste, . = Ziel

Damit ist Spielprinzip des in den 80ern entwickelten Computerspiels Sokoban (japanisch Lagerhausverwalter) bereits erklärt. Das zugrunde liegende Spielfeld wird im ASCII-Format übergeben. Wir sollen nun einen parallelen Löser implementieren, der die Laufroute der Spielfigur ausgibt.

Paralleler Lösealgorithmus
Die Grundidee des Lösers ähnelt einem Brute-Force-Algorithmus. Von unserem Standpunkt bewegen wir die Spielfigur in alle vier Himmelsrichtungen (sofern keine Wand oder zwei hintereinander liegende Kisten den Weg versperren). Von jedem im letzten Schritt gefundenen freien Feld laufen wir wieder in alle vier Richtungen usw. Irgendwann wird die Spielfigur zwangsläufig auf eine Kiste treten und diese dabei verschieben. Und irgendwann liegen dann alle Kisten auf Zielen.

Ein Problem wird schon ersichtlich. Gehen wir von Feld A auf ein angrenzendes Feld B, dann läuft die Spielfigur beim Untersuchen von Feld B mitunter auch zurück zu Feld A. Und daraufhin wieder von A nach B... Um Zyklen zu vermeiden, müssen wir uns bereits besuchte Spielsituationen merken. Für's erste sollte dazu die Position des Läufers und die Lage der Kisten genügen. Um die bereits besuchten Spielsituationen effizient durchsuchen zu können, empfiehlt sich als Ablagestruktur beispielsweise eine ConcurrentHashMap.

Im Prinzip könnte der Löser bei (sehr) einfachen Spielfeldern mit etwas Rechenzeit schon zu einem Ergebnis kommen. Hier ein Codebeispiel für die Run-Methode der einzelnen Threads (eigentlich Runnables), die simultan nach dem richtigen Weg für die Spielfigur suchen.

@Override
public void run() {
	while (!foundSolution) {
		Zustand currentState = null;
		try {
			currentState = states.take();
		} catch (InterruptedException e) {
			return;
		}

		// Anderes Runnable hat eine Loesung gefunden
		if (currentState.equals(poisonpill))
			return;

		// alle von dieser Position moeglichen Folgespielfelder
		// berechnen und der Warteschlange anhaengen
		String solution = findNextStates(states, visitedStates, board, currentState);
		if (null != solution) {
			foundSolution = true;
			solutionTrail = solution;
			// an take() nuckelnde Runnables mit Giftpillen stilllegen
			for (int runsToKill = 0; runsToKill < threads - 1; runsToKill++)
				states.add(poisonpill);
		}
	}
}

Zur Vorgehensweise:
Die Threads arbeiten eine gemeinsame Warteschlange states ab, die mögliche Spielsituationen enthält. Als Warteschlange empfiehlt sich beispielsweise eine threadsichere BlockingQueue<T>. Danach ruft der Thread eine Methode auf, die alle aus dieser Position möglichen Folgespielfelder an die Warteschlange der zu untersuchenden Spielsituationen anfügt. Die Spielfigur wird quasi in alle vier Richtungen bewegt. Wird in einem dieser vier Schritte bereits eine Spielfeld entdeckt, bei dem alle Kisten auf Zielen liegen, wird der gesamte Weg des Läufer als String zurückgegeben. Hieraufhin kann der Löser beendet werden. Wird in diesem Schritt keine Lösung gefunden, muss der Thread eben eine neue Spielsituation aus der Schlange entnehmen und diese untersuchen.

Findet ein Thread eine Lösung, signalisiert er den anderen Threads mithilfe des Flags foundSolution, dass sie die Suche einstellen können. foundSolution muss als volatile deklariert sein, damit wirklich alle Threads eine Änderung mitbekommen. Nachdem sie ihre derzeitige Spielsituation abgearbeitet haben, werden sie den Rumpf der while-Schleife also nicht mehr betreten.

Jedoch kann es passieren, dass ein oder mehrere Threads an states.take() festhängen, da die take()-Methode der BlockingQueue<T> so lange blockiert, bis sie ein T-Element liefern kann. Damit die blockierten Threads trotz der leeren Warteschlange terminieren können, fügt der erfolgreiche Thread so viele "Giftpillen" in die Warteschlange ein wie maximal Prozesse daran festhängen können. Die Giftpille bringt die noch nicht beendeten Threads schließlich zum Erliegen.

Effizienz durch Deadlock Erkennung
Schiebt man eine Kiste beispielsweise in eine Ecke, ist sie schlichtweg nicht mehr von dieser Position wegzubewegen. Ist die Ecke nicht zufällig auch als Ziel markiert, dann kann die Spielfigur so schön über das Spielfeld tanzen wie sie möchte, das Level ist nicht mehr lösbar. Das Gleiche gilt für eine Kiste auf einer Randzeile/-spalte, die kein Ziel enthält.
Der Löser kommt wesentlich schneller zu einem Ergebnis, wenn er sowieso nicht lösbare Zustände so früh wie möglich erkennt und nicht weiter betrachtet. Von daher ist eine gute Deadlock-Erkennung wesentlicher Bestandteil des Programmes. Nicht die Leistungsfähigkeit des Rechners ist entscheidend, sondern die Effizienz des Algorithmus ;-)

Zur Vermeidung von Deadlocks gibt es weit tiefergehendere Konzepte, die im Sokoban Wiki vorgestellt werden. Wer Interesse an der Thematik eines Sokoban-Lösealgorithmus gefunden haben sollte, auch dem mag das Sokoban Wiki mit Implementierungsvorschlägen wesentlich weiterhelfen.

+

Einen Kommentar hinzufügen

Name: 
eMail*: 
Wie viel ist 1 + 1? 
 

*) Die eMail-Adresse wird nicht veröffentlicht.