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[1] 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
References
- ↑ ANSI Escape Code, Wikipedia, Dec. 2012, http://en.wikipedia.org/wiki/ANSI_escape_code
