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Ă:
- 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.
- 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.
- 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.