CSC231 Homework 12 2012

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

---

Homework 12

This homework is optional. If you elect to do it, you have to work individually; no group work allowed. If your grade on this homework is higher than the current lowest of your previous assignment grades, then this grade will replace the lowest. Wether you do this assignment or not, the lowest of all your homework grades for Homework 1 to 11 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.

Recursive traversal of a maze

For this problem I am giving you a program that is already written. It is a recursive complex program that solves the traversal of a maze by finding a path between the input and the output of the maze. The only documentation you have on the program is its internal documentation. Fortunately, Aurelia Moore, the student author of the program was good at documenting her programs. Your assignment is to take this program, study it, study it hard, figure out how it works, and then modify it, in an efficient way, without rewriting or adding too much code, so that you answer the question that is asked of you. This is similar to arriving at a company for a job or an internship and having to work on some code that has been already written by somebody else, and try to figure out how to make it work better.

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 pattern, along with a place to start exploring it (2nd row, 1st column). The program keeps on exploring the maze, recursively, until it finds a location where it can escape the maze (being on the edge of the maze in a place where there is no '#' character. When it finds such a place the program stops, displays the maze along with all the places it visited, and it states that the maze has a solution. Otherwise it states that the maze does not have a solution.

Copy the program into a program called hw12.asm and run it a few times to see how it operates. Note that this program uses ANSI sequences to position the cursor back at the top left position of the screen before re-drawing the maze.

;;;__     ___     _ _   __  __
;;;\ \   / (_)___(_) |_|  \/  | __ _ _______
;;; \ \ / /| / __| | __| |\/| |/ _` |_  / _ \
;;;  \ 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 
;;; 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 ends by displaying all the breadcrumbs
;;; it left in the maze, including the path and places visited.
;;;
;;;
;;; To assemble and run:
;;;     nasm -f elf -F stabs hw12.asm
;;;     ld -melf_i386 -o hw12 hw12.o
;;;     ./hw12
;;; -----------------------------------------------------------------------


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

        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:  says a path was found
;;; -----------------------------------------------------------------------
printMazeSuc:
        call    print_nl

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

        
;;; -----------------------------------------------------------------------
        ;;      printMazeFail:  says no path was found
;;; -----------------------------------------------------------------------
        
printMazeFail:
	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!

Assignment

Part 1 (3 points)

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. However, when the program is running, the 'v' characters should appear as they do now. It's only the last image printed that should show only the '.' and '#', but not the 'v' characters.

Part 2 (1 point)

Indicate in the header of your program the largest possible amount of stack space used up by the program as a function of the width and height of the maze.

Submission

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

     rsubmit hw12 hw12.asm