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.

So sieht ein Labyrinth dann aus.

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


Links

Copyright-Bestimmungen: siehe Über diese Seite