Der Garten des Minos
Das Programm soll zeigen, wie man auch in einer Sprache wie Assembler eine Rekursion programmieren kann. Dazu habe ich als anschauliches Beispiel ein Labyrinth gewählt. Wollen wir zuerst klären, was Rekursion bedeutet.
Als Rekursion wird der Aufruf eines Unterprogramms /einerProcedure aus sich selbst heraus bezeichnet, ohne daß dabei bestimmte Variablen überschrieben werden. Diese Variablen heißen lokale Variablen. In der Praxis sieht eine Rekursion folgendermaßen aus:
Procedure Beispiel;
Local a,b;
...
(Gosub) Beispiel;
...
End; (Return)
Damit lokale Variablen nicht überschrieben werden, werden sie entweder gleich bei der Deklaration auf dem Stack untergebracht, oder vor einem rekursiven Aufruf werden die Variablen auf den Stack gerettet und bei der Rückkehr wieder von dort geladen. Diese Methode wird in diesem Programm praktiziert.
Nun zu dem Programm selber. Das Prinzip des Programms ist relativ einfach, aber zugegebenermaßen nicht sehr einfach zu verstehen, wie es übrigens bei den meisten rekursiven Programmen der Fall ist.
Das Prinzip
Das Programm arbeitet ähnlich einem Maulwurf. Er gräbt in eine zufällig gewählte Richtung. Wenn er bemerkt, dort geht es nicht weiter, versucht er die anderen Richtungen. Wenn es auch dort nicht weitergeht (auf gut deutsch, wenn er eingeklemmt ist), läuft er zurück. Dieses anschauliche Beispiel kann ohne weiteres auf den Computer übertragen werden. Man geht von einem Startpunkt A aus und sucht einen Zielpunkt B. der so gelegen ist, daß nichts zwischen diesen beiden Punkten A und B ist. Ist B ein gesuchter Punkt, wird die aktuelle Position A gespeichert (lokale Variable auf Stack gelegt). B wird nun der neue Startpunkt A, und die Procedure beginnt von vorne. Angenommen, es gibt von A aus keinen weiteren Punkt B. Dann muß zurückgesprungen werden. Der alte Punkt A wird vom Stack geholt und wieder aktueller Startpunkt. Wenn das Labyrinth fertig gezeichnet, also alles versperrt ist, hat der Startpunkt A wieder die Ausgangskoordinaten.
Das Suchen eines Punktes B erfolgt über die 4 Richtungen. Der Abstand zwischen A und B hat jeweils in die Horizontale und Vertikale einen konstanten Wert. Zwischen A und B wird die Farbe aller Punkte ermittelt. Wenn die Farbe ungleich Null ist, ist der Weg versperrt. Ein Zähler für die getesteten Richtungen wird dekrementiert und eine neue Richtung gesucht. Hat der Zähler den Wert Null, geht es von dieser Position aus nicht weiter, und es erfolgt ein Rücksprung.
Natürlich soll eine Richtung nicht mehrmals getestet werden. Zu diesem Zweck richtet man ein Array ein, in dem man vermerkt, wo schon getestet wurde. Dieses muß selbstverständlich wieder gelöscht werden, wenn ein Punkt B gefunden wurde und die Routine wieder aufgerufen wird.
Nun zum Testen selber. Um alle Punkte zwischen A und B zu testen, werden zwei ineinander verschachtelte Schleifen verwendet. Eine Schleife behandelt die x-, die andere die y-Koordinaten. Da immer vom Startpunkt A aus gerechnet wird, müssen die Step-Werte für die beiden Schleifen ermittelt werden. Es gibt die Step-Werte + 1, 0, -1. Eine Schleife hat immer den Step-Wert 0. Mit den verschachtelten Schleifen läßt sich eine Fallunterscheidung für die getrennte Bearbeitung in x- und y-Richtung vermeiden.
Michael Krusemark
;************************************************
;* LABYRINTH - CREATOR *
;* =================== *
;* *
;* by Michael Krusemark *
;* *
;* (C) 1991 MAXON Computer *
;* *
;************************************************
XSTART EQU 320
YSTART EQU 200
XCLIP EQU 10
YCLIP EQU 10
WCLIP EQU 620
HCLIP EQU 380
XSTEP EQU 10
YSTEP EQU 10
DC.W $A000 ;LineA - Init
move.l A0,ABASE ;LineA - Variablen
moveq #-1,D0
move.l D0,24(A0) ;Farbe auf Schwarz
move.l D0,28(A0)
move.w D0,34(A0) ;durchgezogene Linie
DC.W $A00A ;die Maus muß aus
pea CLS(PC) ;Bildschirm löschen
move.w #9,-(SP) ;Print Line
trap #1
addq.l #6,SP
lea BOX(PC),A5 ;auf Koordinaten der Box
movem.w (A5)+,D4-D7 ;Koordinaten
bsr LINE ;übergeben
movem.w (A5)+,D4-D7 ;und Linien
bsr LINE ;ziehen
movem.w (A5)+,D4-D7
bsr LINE
movem.w (A5),D4-D7
bsr LINE
move.w #XSTART,D6
move.w #YSTART,D7
bsr.s LABY
move.w #1,-(SP) ;Cconin
trap #1
addq.l #2,SP
clr.w -(SP) ;Pterm
trap #1
LABY: move.w #4,D3 ;4 Richtungen testen
GET_DIR: lea TESTED(PC),A4
tst.w D3 ;Sackgasse?
beq AUS ;ja, —> zurück
bsr RANDOM ;neue Richtung holen
tst.b 0(A4,D0.w) ;Richtung probiert?
bne.s GET_DIR ;ja, —> noch einmal
st 0(A4,D0.w) ;Richtung getestet
subi.w #1,D3 ;eine Richtung mehr
move.w D6,D4 ;Xposition
move.w D7,D5 ;Yposition
lsl.w #2,D0 ;Richtung zu Offset
lea STEPS(PC),A4 ;Tabelle
add.w 0(A4,D0.w),D4 ;Xstep addieren
add.w 2(A4,D0.w),D5 ;Ystep addieren
movem.w D6-D7,-(SP) ;Register retten
clr.l XADD ;Steps = 0
pea YTEST(PC) ;bedingter Sprung
cmp.w D6,D4 ;Step für Schleife1
bit XSMALLER ;ermitteln und
bgt XBIGGER ;setzen
addq.l #4,SP ;Returnadr. löschen
YTEST: pea SCHLEIFE1(PC) ;dasselbe
cmp.w D7,D5 ;wie oben
bit YSMALLER ;aber für Schleife2
bgt YBIGGER
addq.l #4,SP
SCHLEIFE1: add.w XADD(PC),D6 ;Step addieren
move.w 2(SP),D7 ;Startwert
SCHLEIFE2: add.w YADD(PC),D7 ;Step addieren
movea.l ABASE(PC),A0 ;Test, ob der
movea.l 12(A0),A0 ;Weg versperrt ist
movem.w D6-D7,(A0) ;Koordinaten
DC.W $A002 ;Point
tst.w D0 ;Hintergrundfarbe?
beq.s NEXT ;nein, -->
movem.w (SP)+,D6-D7 ;restaurieren
bra.s GET_DIR ;neue Richtung
NEXT: cmp.w D5,D7 ;Schleife beendet
bne.s SCHLEIFE2 ;nein, --> zurück
cmp.w D4,D6 ;das selbe für die
bne.s SCHLEIFE1 ;äussere Schleife
movem.w (SP)+,D6-D7 ;restaurieren
bsr.s LINE ;Linie ziehen
GO_ON: clr.l TESTED ;Flags löschen
movem.w D6-D7,-(SP) ;Xpos,Ypos retten
move.w D4,D6 ;neues Xpos
move.w D5,D7 ;neues Ypos
bsr LABY ;Rekursion
movem.w (SP)+,D6-D7 ;restaurieren
bra LABY ;nächste Richtung
AUS: clr.l TESTED ;Flags löschen
rts ;zurück, Backtracking
LINE: movea.l ABASE(PC),A0 ;Basisadresse
movem.w D4-D7,38(A0) ;Koordianten
DC.W $A003 ;Arbitary Line
rts
RANDOM: move.w #$11,-(SP) ;Zufallszahl
trap #14 ;ermitteln
addq.l #2,SP
andi.w #3,D0 ;4 Bits für
rts ;4 Richtungen
XBIGGER: move.w #1,XADD ;Steps für
rts ;Schleifen
XSMALLER: move.w #-1,XADD ;setzen
rts ;dabei muß zwischen
YBIGGER: move.w #1,YADD ;aufwärts und
rts ;abwärts
YSMALLER: move.w #-1,YADD ;unterschieden
rts ;werden
DATA
STEPS: DC.W XSTEP,0,-XSTEP,0,0,YSTEP,0,-YSTEP
; Tabelle für die Steps in jede Richtung
BOX: DC.W XCLIP,YCLIP,WCLIP+XCLIP,YCLIP
DC.W WCLIP+XCLIP,YCLIP,WCLIP+XCLIP
DC.W HCLIP+YCLIP
DC.W XCLIP,HCLIP+YCLIP,WCLIP+XCLIP
DC.W HCLIP+YCLIP
DC.W XCLIP,HCLIP+YCLIP,XCLIP,YCLIP
;Koordinaten der Box
CLS: DC.B 27,'E',0 ;Escape für CLS
BSS
ABASE: DS.L 1 ;LineA-Basisadresse
XADD: DS.W 1 ;Step für Schleife1
YADD: DS.W 1 ;und Schleife2
TESTED: DS.B 4 ;Flags
END