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
