Der Labyrinthen-Bauer (Pascal)

Wer sich je der Denksportaufgabe gewidmet hat, ein Labyrinth zu konstruieren oder für ein Computerspiel zu programmieren, weiß um die Probleme, die dabei auf-treten können. Georg Viehöver erstellte ein Programm, das auf dem Bildschirm ein beliebig großes Labyrinth baut. Darin gibt es zwischen je zwei Punkten stets genau einen Weg.

Das Programm verwendet dabei die Verfahren Backtracking und Rekursion, die zum Beispiel auch in der künstlichen Intelligenz verwendet werden.

Rekursion bedeutet lediglich, daß sich ein Programm(teil) immer wieder selbst aufruft. Ein bekanntes Beispiel dafür ist die Definition der Fakultät fak(n) (bzw. n!):

fak(n) = 1 * 2 * 3 * ... * n.

Das ist die einfache Definition, durch die man fak(n) mit einer einfachen for-Schleife berechnen kann. Die rekursive Definition lautet:

fak(O) = 1
fak(n) = n * fak(n-1) für n > 0

Die Definition ist rekursiv, da fak(n) durch fak(n-1) definiert wird, also durch sich selbst. Beispiel:

fak(2) = 2 * fak(2-1) (wegen 2>0)
fak(1) = 1-frfak(1-1) (wegen 1>0)
fak(O) = 1	(wegen	0 = 0)

also ist fak(1)= 1 * 1 = 1, also fak(2) = 2 * 1 = 2. Wer Lust hat, kann einmal das zugehörige PASCAL-Programm schreiben.

Diese Art zu rechnen ist wesentlich arbeitsaufwendiger als das einfache Durchlaufen einer Schleife. Deshalb bemüht man sich meist, ein iteratives Programm (also mit for- und while-Schleifen) zu schreiben. Ein Ergebnis der theoretischen Informatik besagt sogar, daß das immer geht. (Das läuft im Prinzip darauf hinaus, den Stack durch ein vom Programm verwaltetes Feld zu ersetzen und dort z. B. die lokalen Variablen abzuspeichern.) Manchmal ist es jedoch wesentlich einfacher, ein Problem mit rekursiven Programmen zu lösen. Während eine iterative Problemlösung oft nur sehr unübersichtlich zu programmieren ist, wird bei der rekursiven die Lösungsidee sofort klar.

Backtracking (Rückzug) ist eines der Verfahren, mit dem der Computer eine Lösung durch systematisches Probieren finden kann. Während Menschen (z. B. beim Schach) oft gefühlsmäßig sagen können: ”Das ist ein guter Zug”, muß der Computer stur und systematisch alle Möglichkeiten durchprobieren und sehen, was passiert. Er findet eine Lösung durch Versuch und Irrtum (trial und error).

Eigentlich ist ein Computer auch nicht klüger als ein Maulwurf, der ein unterirdisches Labyrinth baut: Wenn der an seinem Startplatz ist, überlegt er sich zuerst, in welche Richtung er losgraben und wie weit er geradeaus graben will. Dann versucht (!) er, ob er in diese Richtung graben kann. Wenn es möglich ist, tut er es soweit wie möglich. Anschließend trifft er die gleichen Entscheidungen wie am Startpunkt: Rekursion.

Was passiert, wenn er nicht in die gewünschte Richtung losgehen kann (z. B., weil da eine Hauswand ist, oder weil er dann wieder auf einen alten Gang treffen würde)? Dann probiert er eben die anderen Grabe-Richtungen durch. Nachdem er alles versucht hat und feststellt: "Hier geht’s nicht mehr weiter” (das ist der Irrtumsfall), geht er eben zurück zum letzten Eckpunkt (der ’Backtrack’!) und probiert, von dort aus weiterzugraben.

So geht das immer weiter - bis er schließlich wieder an seinem Startplatz ankommt und auch dort nicht weiter kann. Das Labyrinth ist fertig!

Genau das macht auch das PASCAL-Programm, und auch Expertensysteme machen oft nicht viel mehr: Um eine Vermutung zu beweisen, bauen sie eine Kette von Schlußfolgerungen (Versuch) auf, bis sie merken: ”Stop, so komme ich nicht ans Ziel” (Irrtum), gehen einen Folgerungsschritt zurück und versuchen es von da aus noch einmal etc., bis sie entweder am Ziel sind oder es nicht mehr weiter geht (Vermutung kann nicht bewiesen werden).

Die zentrale Prozedur im PASCAL-Programm ist MAKESTEP. Sie wählt zufällig die ’Grabe-Richtung’ und die Strecke aus (RANDOM), geht sie nach Möglichkeit (GOLINE) und ruft sich selbst auf, um am erreichten Eckpunkt wieder das gleiche zu tun. Danach probiert sie die übrigen Richtungen durch (while-Schleife) und geht schließlich einen Schritt zurück, indem sie zur aufrufenden Prozedur zurückkehrt.

Die Rolle des Tastsinns beim Maulwurf übernimmt die Funktion TESTSTEP. Sie überprüft, ob man beim nächsten Schritt auf einen anderen Gang stoßen wird oder ob der Weg frei ist.

Damit der Programm-Maulwurf nicht ewig weitergräbt, wird im Hauptprogramm zuerst eine ’Mauer’ um das Feld gemalt. Wenn das Programm fertig ist, blinkt der Cursor. Mit < alternate> + <Help> kann man das Labyrinth drucken lassen, mit < Space > wird das Programm beendet.

Drei Bemerkungen zum Schluß:

1. Das Programm braucht bei der Rekursion viel Speicherplatz. Bei einem Feld von 640 * 400 kann es Rekursionstiefen bis ca. 12 000 erreichen. Deshalb: Alle wichtigen Sachen vor dem Programmlauf auf Disk abspeichern. Denn wenn der Speicher überläuft, haucht der ST in der Regel sein Leben aus.
2. Ein vergleichbares Programm in Basic auf dem C64 lief etwa 60 mal (!) langsamer. Es war ohne Rekursion programmiert, da Basic nicht richtig rekursiv (mit lokalen Variablen etc.) arbeiten kann.
3. Ein Programm, das einen Weg zwischen zwei Punkten im Labyrinth findet, kann man ebenfalls mit Backtracking programmieren.

Viel Spaß!

(Das Programm wurde entwickelt mit ST-Pascal plus von CCD, Atari 520 ST+, S/W-Monitor, RAM-TOS vom 6.2.86)

program labyrinth;
{entwickelt mit ST-Pascal plus von CCD zeichnet Labyrinth beliebiger Größe!}

const modulus = 1063;	{Konstanten	für	Zufallsgenerator}
	factor = 5; 
	increment = 7227; 
	clr = 0; {Zeichenfarbe}

type tdir = 0..3; {Richtungstyp, 0=hoch , 1=rechts}

var seed, {Zufallszahl}
	xmax,ymax,x,y:integer; {Größe des Feldes, aktueller Bildpunkt}

procedure randomize;	{setzt startzahl auf 'zufälligen' Wert}
begin
	seed:= int(clock() mod modulus)
	{clock liefert Sekunden seit Start } 
end;

function random (a,b:integer):integer;
{erzeugt Zufallszahl zwischen a und b} 
begin
	seed := (factor * seed + increment) mod modulus; 
	random := trunc ((seed/modulus)*(b-a+1)+a) 
end;

procedure clear_home;	{löscht Bildschirm}
begin write(chr(27),'E') end;

procedure cur_on;	{ Cursor an }
begin write(chr(27),'e') end;

procedure cur_off;	{ Cursor aus }
begin write(chr(27),'f') end;

procedure aline(x1,y1,x2,y2:integer);
{zeichnet linie von (x1,y1) nach (x2,y2)} 
begin
	line (x1,y1,x2,y2,clr,0,0,0,$ffff,1) 
end;

procedure wait;
{ wartet blinkend auf Taste } 
begin
	cur_on; repeat until keypress; cur_off 
end;

procedure step (var x,y :integer; direction: tdir);
{verändert x,y für einen Schritt nach Richtung} 
begin
	case direction of 
		0: y:=y-1;
		1: x:=x+1;
		2: y:=y+1;
		3: x:=x-1; 
	end {case} 
end;

function teststep(x,y:integer; direction:tdir): boolean;
{überprüfe, ob Schritt in Richtung möglich, wenn ja dann true. true, wenn nächstes Feld und die umliegenden frei.}

	function testnext (x,y:integer; direction:tdir):boolean;
	{ testet, ob Punkt und linker/rechter Nachbar gesehen in direction frei sind } 
	begin {testnext}
		if get_pixel(x,y)<>clr then (Punkt selbst ist frei} 
			case direction of { teste Nachbar }
				0,2: testnext:=((get_pixel(x+1,y)<>clr) and (get_pixel(x-1,y)<>clr));
				1,3: testnext:=((get_pixel(x,y-1)<>clr) and (get_pixel(x,y+1)<>clr)) 
			end {case} 
		else testnext := false 
	end; {testnext}

begin {teststep}
	step (x,y,direction); {nächster Punkt} 
	if testnext(x,y,direction) then begin {ist frei} 
		step(x,y,direction); { übernächster Punkt } 
		teststep := testnext(x,y,direction) 
	end {then}
	else teststep := false end; { teststep }

Procedure goline(var x,y:integer; direction: tdir; long:integer);
	{ geht maximal long Schritte in direction. stoppt, wenn Hindernis in Sicht. }

begin
	while(long >0) and teststep(x,y,direction) do begin 
		step(x,y,direction); { mache Schritt } 
		put_pixel(x,y,clr); { setze Punkt } 
		long := long-1 
	end {while} 
end;

procedure makestep(x,y:integer);
{ die erste Richtung wird zufällig ausgewechselt. Danach werden alle Richtungen systematisch geprüft. 
Wenn möglich wird 2..5 Schritte weitergegangen. }
var direction: tdir; { Gehrichtung: 0=up, 1=right..3} 
	xneu, yneu, { neue Koordinaten } 
	count, { zählt getestete Richtung } 
	long : integer; { Anzahl Schritte maximal }

begin
	direction := random(0,3); { erste Gehrichtung bestimmen } 
	count := 0; { zählt versuchte Richtung }
	while count <4 do begin { Schleife durchläuft alle 4 Richtungen } 
		if teststep(x,y,direction) then begin { wenigstens ein Schritt möglich } 
			xneu:=x; yneu:=y; { Startpunkt } 
			long:=random(2,5); { maximaler Weg } 
			goline(xneu,yneu,direction,long);  { gehe dahin } 
			makestep(xneu.yneu); { Versuche von da weiterzugehen } 
		end; { if Step möglich } 
		if direction=3 { nächste richtung wählen } 
			then direction := 0 
			else direction := direction + 1; 
		count:=count+1 
	end { while } 
end;


begin {hb}
	write(chr(27),'b0',chr(27),'c1'); { Weis aus Schwarz drucken } 
	clear_home;
	writeln('labyrinthmaker');
	write('xmax ymax (<640, <400): '); readln(xmax,ymax); 
	x:= xmax div 2; y:= ymax div 2;	{ Start in Mitte }
	randomize; cur_off;clear_home;
	aline(0,0,0,ymax);aline(0,0,xmax,0); { male Box um Feld } 
	aline(0,ymax,xmax,ymax);aline(xmax,0,xmax,ymax); 
	put_pixel(x,y,clr);	{ Startpunkt setzen }
	makestep(x,y); wait;
	write(chr(27),'b1',chr(27),'c0'); { schwarz auf weiß} 
end.

Georg Viehöver

---

---