CSC231 Homework 12 2012

--D. Thiebaut 15:16, 5 December 2012 (EST)

---

Homework 12

This homework is optional. If you elect to do it, and if your grade is higher than the current lowest of your assignment grades, then this grade will replace the lowest. Wether you do this assignment or not, the lowest of all your homework grades will be dropped before computing the final grade. Note that if you elected to drop an assignment during the semester, you got an F for that assignment, which then becomes the grade that is dropped.

Page under construction!

Recursive traversal of a maze

The program below was written by a Aurelia Moore in 2007. It is given a maze represented by ASCII characters arranged in some 2-dimensional patter, and a place to start exploring it (2nd row, 1st column). When it finds a location where it can escape the maze, then it states that the maze has a solution. Otherwise it states that the maze does not have a solution.

;;;__     ___     _ _   __  __
;;;\ \   / (_)___(_) |_|  \/  | __ _ _______
;;; \ \ / /| / __| | __| |\/| |/ _` |_  / _ \
;;;  \ V / | \__ \ | |_| |  | | (_| |/ /  __/
;;;   \_/  |_|___/_|\__|_|  |_|\__,_/___\___|
;;;
;;;
;;; Aurelia Moore (c) 2007
;;;
;;; This program takes a maze defined in maze1.dat where the
;;; walls are denoted by # and the empty space defined by
;;; spaces. The maze should be in the variable maze in
;;; maze1.dat, and the number of columns and rows in the maze
;;; in the variables width and height, respectively. It will
;;; then try to find a path through the maze. It will leave
;;; "breadcrumbs" for the path it is trying, and when it discovers
;;; that there are no successful paths from a point, places a v
;;; there. The program will end 2 ways: it finds an exit, or returns
;;; to the entrance to put a v there. If it found an exit, it
;;; removes all v's from to show only the maze and the
;;; breadcrumbs for the succesful path, and notes it has found a
;;; path. If it does not, it prints the maze without v's or
;;; breadcrumbs, and notes that it has failed.
;;;
;;; Each visitMaze puts a net 4 doublewords (16 bytes) on the stack:
;;; the row, column, return address, and stored ebp. During the
;;; execution of visitMaze, up to 40 bytes are added, but they
;;; are removed before the next visitMaze is called. They are the
;;; return address when printMaze is called, the return address
;;; when printMaze calls killTime, and the 8 registers that are
;;; pushed during killTime.
;;;
;;; If there are the 10,485,760 bytes I calculated in hw7 for the
;;; stack, then the 40 bytes that only occur once (they don't
;;; "stack") can be taken off the maximum available for the
;;; recursions. If visitMaze is called and there isn't this amount
;;; available in the stack, it will not succeed in running. So
;;; there are 10,485,720 bytes available for recursions. If there
;;; are 16 bytes used in each recursion, there are 655,357 possible
;;; recursions. This is the number in "open" paths, so not including
;;; bits we've marked with v.
;;; In the worst case scenario, where it visits every space in the
;;; interior of a blank maze and then goes to an exit, it will have
;;; (# of rows - 2) * (# of columns - 2) + 2 recursions. The - 2 to
;;; the rows and columns are for the walls - if they are not there
;;; it will exit. The +2 is for the entrance and exit.
;;; In the best case scenario for no walls, where it goes straight to
;;; the exit, it will have the # of columns recursions (it will go to
;;; the opposit wall in the last column).
;;; In the best case scenario for any maze with interior walls, there
;;; is a wall immediatly east of the entrance, and visitMaze is called
;;; only once.
;;;
;;; To assemble and run:
;;;     nasm -f elf -F stabs hw8.asm
;;;     gcc -o hw8 driver.c asm_io.o hw8.o
;;;     ./hw8
;;; -----------------------------------------------------------------------


;;;  ____        _          ____            _   _
;;; |  _ \  __ _| |_ __ _  / ___|  ___  ___| |_(_) ___  _ __
;;; | | | |/ _` | __/ _` | \___ \ / _ \/ __| __| |/ _ \| '_ \
;;; | |_| | (_| | || (_| |  ___) |  __/ (__| |_| | (_) | | | |
;;; |____/ \__,_|\__\__,_| |____/ \___|\___|\__|_|\___/|_| |_|
;;; 

        section .data

maze   db      "##########################"
width  equ     $-maze	
       db      "   ### # ## # ##   ## #  #"
       db      "#  # # # #### ##   ## #  #"
       db      "#  ###         #      #   "
       db      "#       #### ###  ### #  #"
       db      "#       ##     #    # #  #"
       db      "#       ####   ###  # #  #"
       db      "#       ##          #    #"
       db      "##########################"
height equ     ($-maze) / width	

WRITE   equ     4
STDOUT  equ     1

;;; clrScreen variables
home    db      27,"[2J"                ; clear the screen
        db      27,"[1;1H"              ; ansi sequence to bring
                                        ; cursor at position 1,1
homeLen equ     $-home

;;; My variables
i       dd      0                       ;Keeps track of which row we are on
j       dd      0                       ;Keeps track of which column we are on
fmsg    db      "Fail! No path found. I think this maze has no exit."
fmsgLen	equ	$-fmsg	
smsg    db      "Found a path!"
smsgLen	equ	$-smsg	


;;;   ____          _        ____            _   _
;;;  / ___|___   __| | ___  / ___|  ___  ___| |_(_) ___  _ __
;;; | |   / _ \ / _` |/ _ \ \___ \ / _ \/ __| __| |/ _ \| '_ \
;;; | |__| (_) | (_| |  __/  ___) |  __/ (__| |_| | (_) | | | |
;;;  \____\___/ \__,_|\___| |____/ \___|\___|\__|_|\___/|_| |_|
;;;         

        section .text
        global 	_start
_start:	
        ;;Push starting coordinates and call fn
        push    1                       ;Row 1
        push    0                       ;Column 0
        call    visitMaze
        jnc     none    ;if false, skip
        call    printMazeSuc
        jmp     done
none:
        call    printMazeFail
done:

        ;; return to O.S.
	mov	eax, 1
	mov	ebx, 0
	int	0x80

        
;;; -----------------------------------------------------------------------
        ;; visitMaze:
        ;;      Takes row then col on stack
        ;;      Checks if it is at an exit. Then checks to E,S,N,W,
        ;;      calling itself and checking for space. If it is @ an exit
        ;;      or recieves true from its recursion, it returns true.
        ;;      If none of its paths are viable (from walls, visited spaces,
        ;;      or paths that do not lead to an exit) it places a v and
        ;;      returns false.
;;; -----------------------------------------------------------------------

visitMaze:
        push    ebp                     ;Store old ebp
        mov     ebp,esp
        ;; Get row and col # from stack
        mov     eax,dword[ebp+12]
        mov     ebx,dword[ebp+8]
        call    ijoffset                ;eax<-offset
        mov     byte[maze+eax],"."      ;Change character to .
        mov     edx,eax                 ;copy offset
        call    printMaze               ;print, overwrites eax-ecx
        ;; Get back row and col #
        mov     eax,dword[ebp+12]       ;row #
        mov     ebx,dword[ebp+8]        ;col #
        mov     ecx,height              ;number of rows
        dec     ecx                     ;last row
        ;; Check for exit conidtions (!start and on 1st or last row or col)
        ;; exit row?
        cmp     eax,ecx                 ;in last row?
        je      exit
        cmp     eax,0                   ;in 1st row?
        je      exit
        ;; exit coulun?
        mov     ecx,width               ;# of Columns
        dec     ecx                     ;last columns
        cmp     ebx,ecx                 ;in last col?
        je      exit
        cmp     ebx,0                   ;in 1st col?
        jne     notExit                 ;If not, not at an exit
        cmp     eax,1                   ;If are in 1st col, check if entrance
        jne     exit                    ;if in 1st col but not row=1, exit
        jmp     notExit
exit:
        jmp     true                    ;If at exit, return true
notExit:

        ;; try east
east:
        mov     eax,dword[ebp+12]       ;get row
        mov     ebx,dword[ebp+8]        ;get col
        inc     ebx                     ;column+1
        call    ijoffset                ;eax<-offset
        mov     al,byte[maze+eax]       ;get char to East
        cmp     al," "                  ;is it blank
        jne     south                   ;if no go to next direction
        ;; Prepare to call/recurse
        mov     eax,dword[ebp+12]       ;row
        push    eax                     ;row
        push    ebx                     ;col
        call    visitMaze
        jnc     south                   ;if visitMaze returns false
        jmp     true                    ;if returns true,return true
        ;; try south
south:
        mov     eax,dword[ebp+12]       ;get row
        inc     eax                     ;row+1
        mov     ebx,dword[ebp+8]        ;get col
        call    ijoffset                ;eax<-offset
        mov     al,byte[maze+eax]       ;get char to South
        cmp     al," "                  ;Is it blank
        jne     north
        ;; Prepare to call/recurse
        mov     eax,dword[ebp+12]       ;row
        inc     eax                     ;row+1
        push    eax
        push    ebx                     ;column
        call    visitMaze
        jc      true                    ;if visitMaze returned true

north:
        mov     eax,dword[ebp+12]       ;get row
        dec     eax                     ;row-1
        mov     ebx,dword[ebp+8]        ;get col
        call    ijoffset                ;eax<-offset
        mov     al,byte[maze+eax]       ;get char to North
        cmp     al," "                  ;Is it blank
        jne     west
        ;;  Prepare to call/recurse
        mov     eax,dword[ebp+12]       ;row
        dec     eax                     ;row-1
        push    eax
        push    ebx                     ;column
        call    visitMaze
        jc      true                    ;if visitMaze returned true
west:
        mov     eax,dword[ebp+12]       ;get row
        mov     ebx,dword[ebp+8]        ;get col
        dec     ebx                     ;col-1
        call    ijoffset                ;eax<-offset
        mov     al,byte[maze+eax]       ;get char to east
        cmp     al," "                  ;Is it blank
        jne     false
        ;;  Prepare to call/recurse
        mov     eax,dword[ebp+12]       ;row
        push    eax
        push    ebx                     ;column
        call    visitMaze
        jc      true                    ;if visitMaze returned true
false:
        ;;change to v and print
        mov     eax,dword[ebp+12]
        mov     ebx,dword[ebp+8]
        call    ijoffset                ;eax<-offset
        lea     eax, [maze+eax]
        mov     byte[eax],'v'
        call    printMaze
        ;;return 0
        clc                             ;set carry bit = 0 (return false)
        pop     ebp
        ret     8

true:
        stc                             ;set carry = 1 (return true)
        pop     ebp
        ret     8

        
;;; -----------------------------------------------------------------------
        ;; printMaze: prints the maze in the maze variable
        ;; Nothing needs to be passed
;;; -----------------------------------------------------------------------
printMaze:
        call    killTime
        call    clrScreen
initfori1:
        mov     dword[i],0              ;Start at 1st row
        mov     ecx,height              ;Loop once for each row
fori1:  push    ecx                     ;Store loop counter
intiforj1:
        mov     dword[j],0              ;1st column
        mov     ecx,width               ;Loop once for each column
forj1:
        push    ecx
        ;; Get ready to call offset fn
        mov     eax, [i]
        mov     ebx, [j]
        call    ijoffset
        mov     al, byte[maze+eax]      ;Get correct character in maze
        call    print_char
        inc     dword[j]                ;go to next column
        pop     ecx                     ;Retrieve loop counter
        loop    forj1

        call    print_nl
        pop     ecx
        inc     dword[i]                ;next row
        loop    fori1
        ret

;;; -----------------------------------------------------------------------
;;; -----------------------------------------------------------------------
	section	.data
char	db	'.'	
	section	.text
print_char:
	pushad
	mov	byte[char], al
	mov	eax, 4
	mov	ebx, 1
	mov	ecx, char
	mov	edx, 1
	int	0x80
	popad
	ret

;;; -----------------------------------------------------------------------
;;; -----------------------------------------------------------------------
print_string:
	pushad
	mov	ecx, eax
	mov	eax, 4
	mov	ebx, 1
	int	0x80
	popad
	ret
	
;;; -----------------------------------------------------------------------
;;; -----------------------------------------------------------------------
print_nl:
	push	ax
	mov	al, 0x0a
	call	print_char
	pop	ax
	ret
	
;;; -----------------------------------------------------------------------
        ;;      printMazeSuc: same as printMaze, but replaces v's with
        ;;      spaces and says a path was found
;;; -----------------------------------------------------------------------
printMazeSuc:
        call    killTime
        call    clrScreen
	call	printMaze
	
        call    print_nl

        mov     eax,smsg
	push	edx
	mov	edx,smsgLen
        call    print_string
	pop	edx
        call    print_nl
        ret

        
;;; -----------------------------------------------------------------------
        ;;      printMazeFail: same as printMaze, but replaces anything
        ;;      that is not a # with a space,and says no path was found
;;; -----------------------------------------------------------------------
        
printMazeFail:
        call    killTime
        call    clrScreen
	call	printMaze
	
	call	print_nl
	
        mov     eax,fmsg
	push	edx
	mov	edx, fmsgLen
        call    print_string
	pop	edx
        call    print_nl
        ret

        
;;; -----------------------------------------------------------------------
        ;;  ijoffset: gets a coordinate in the maze, taking the row # from eax
        ;;               and the column # from ebx, and calculates the
        ;;               appropriate offset and stores it in eax.
        ;;       uses eax, ebx, ecx
;;; -----------------------------------------------------------------------

ijoffset:
        mov     ecx, width              ;Number of columns
        mul     ecx                     ;eax<-row # * number of columns
        add     eax,ebx                 ;eax<-row# * # of columns + column #
        ret

;;; -----------------------------------------------------------------------
        ;; ------------------------------------------------------
        ;; clrScreen:  clears the screen and brings the cursor
        ;; to "home" position.  This is done by using ANSI sequences
        ;; that, when sent to the screen, do not actually print
        ;; anything, but instead modify different things, such as
        ;; the position of the cursor, the contents of the screen,
        ;; or other screen-related properties.  All ansi sequences
        ;; start with Ascii 27, which is the ESCape character.
;;; -----------------------------------------------------------------------
        
clrScreen:
        pushad                          ; save all registers

        mov             eax,WRITE       ; already defined
        mov             ebx,STDOUT      ; already defined
        lea             ecx,[home]
        mov             edx,homeLen
        int             0x80

        popad                           ; restore all registers
        ret

;;; -----------------------------------------------------------------------
        ;; killTime: performs many additions and subtractions between
        ;; each visit to make it easier to see each step of the
        ;; visiting process.
;;; -----------------------------------------------------------------------

killTime:
        pushad                          ;push all 32-bit registers
        mov     ecx, 50000000
for:    mov     edx, 1
        add     edx, 1
        sub     edx, 1
        loop    for
        popad                           ;pop all 32-bit registers
        ret

When the program stops with the current maze defined in the data section, we get this pattern:

##########################
...### # ## #v##   ## #  #
#v.# # # ####v##   ## #  #
#v.### ......vv# .....# ..
#v......####.### .###.# .#
#vvvvvvv##  ...# ...#.# .#
#vvvvvvv####  .###v.#.# .#
#vvvvvvv##    ......#....#
##########################

Found a path!

The program prints the maze, along with the places that it has visited, marked with dots '.', and with 'v' signs.

This is nice, but it would be much nicer if the program at the very end had printed the path it found from the entrance to the exit, as follows:

##########################
...### # ## # ##   ## #  #
# .# # # #### ##   ## #  #
# .### ......  # .....# ..
# ......####.### .###.# .#
#       ##  ...# ...#.# .#
#       ####  .### .#.# .#
#       ##    ......#....#
##########################

Found a path!

Your assignment is to modify the program so that it ends by printing the path it found, and not all the places it has visited, as shown above.

Submission

Store your program in a file called hw12.asm and submit it as follows:

     rsubmit hw12 hw12.asm