Hi,
I'm trying to write a maze program in MIPS and have almost all of it working except the recursion part. For some reason, it does not correctly move through the maze.
In my code, the maze is fixed at 5x5. A 1 in the "maze" data indicates it's blocked. The visited matrix keeps track if it was visited. The code is below. Any help would be greatly appreciated:
.data
maze: .byte 0,0,0,0,0
.byte 1,0,1,1,1
.byte 1,0,0,0,1
.byte 0,0,1,0,1
.byte 1,0,0,0,0
visit: .byte 0,0,0,0,0
.byte 0,0,0,0,0
.byte 0,0,0,0,0
.byte 0,0,0,0,0
.byte 0,0,0,0,0
msize: .word 5
msg_y: .asciiz "Path through maze EXISTS!!\n"
msg_n: .asciiz "Path through maze DOES NOT EXIST!!\n"
msg_p: .asciiz "Path from exit to entrance\n"
op_par: .asciiz "("
comma: .asciiz ","
cl_par: .asciiz ")"
# print this string for a newline character
nline: .asciiz "\n"
.text
####
# main : Initializes pointers to maze and visited array, sets up initial r,c values
# and calls search
#
# NOTE: You should not have to change MAIN...It is complete!
#
####
main:
la $s6, maze # Base pointer to maze array
la $s7, visit # Base pointer to vis(ited) array
li $a0, 0 # r variable
li $a1, 0 # c variable
jal search
bne $v0,$zero,mL1
la $a0, msg_n
li $v0, 4
syscall
# exit
mL1: li $v0,10
syscall
####
# search : Recursive Maze search routine
# $a0 = r
# $a1 = c
# returns $v0 => 1 = found a path from entrance to exit, 0 => No path found yet
####
search: addi $sp, $sp, -4
sw $ra,0($sp) #saves stack pointer
sub $fp, $sp, 8 #push callers frame pointer
sw $a0, 0($fp)
sw $a1, 4($fp)
jal ploc
# Check if invalid location
jal iloc
beq $v0,1,epilogue
# Check if visited this location before
jal vis
beq $v0,1, epilogue
# Check if at exit and path was found
jal atexit
beq $v0,1,last_spot
# Check to the east
addi $a1, $a1, 1
jal search
lw $a0,0($fp)
lw $a1,4($fp)
# Check to the south
addi $a0, $a0, 1
jal search
lw $a0,0($fp)
lw $a1,4($fp)
# Check to the west
addi $a1, $a1, -1
jal search
lw $a0,0($fp)
lw $a1,4($fp)
# Check to the north
addi $a0, $a0, -1
jal search
lw $a0,0($fp)
lw $a1,4($fp)
# If no path was found, return false
last_spot: jal ploc
epilogue:
lw $a0,0($fp)
lw $a1,4($fp)
addi $fp,$fp,8
lw $ra,0($sp)
addi $sp,$sp,4
jr $ra
####
# iloc = Invalid Location (either a wall or out of bounds)
# $a0 = r
# $a1 = c
# returns $v0 => 1 = invalid, 0 = valid
####
iloc:
and $v0, $0, $0
slt $v0, $a0, $0 #if r <0 , set $v0 equal to 1.
slt $v0, $a1, $0
lw $t1, msize
addi $t1, $t1,-1
sgt $v0,$a0, $t1
sgt $v0,$a1,$t1
ori $t1,$0, 5 #initiailze $t1 to 5. Notice that an offset of five will move you from row i of the matrix to row (i+1) since matrix has 5 cols.
mult $t1,$a0 #number of row jumps saved to mflo register
mflo $t1 #get mflo value
add $t1, $t1, $a1 #get the entire offset of 5*matrix + column
add $t1, $t1, $s6 #offset the base matrix location value by the correct amount
lb $v0, 0($t1)
jr $ra
####
# ATEXIT = At Exit?
# $a0 = r
# $a1 = c
# returns $v0 => 1 = at exit, 0 = not at exit
# and prints success message
####
atexit: lw $t1, msize
addi $t1,$t1,-1
bne $t1,$a0,NotFinal
bne $t1,$a1,NotFinal
li $v0, 4 #4 is the system call for print string
la $a0, msg_y
syscall
ori $v0,$0,1
jr $ra
NotFinal: addi $v0,$0,0
jr $ra
####
# vis = Visited?
# $a0 = r
# $a1 = c
# returns $v0 => 1 = locations has already been visited, 0 = not visited
# and marks location as visited
####
vis:
#this function returns. It looks at the base matrix saved in location $a2. Thus $a2 must be updated to the correct matrix (maze or visit) before this is called.
#It also decides whether to write or read. If $a3 is set to 0, then it reads, if a3 is set to 1 then it writes.
#The result is saved in $v1 if we are reading. The matrix in data is updated if we are writing.
ori $t1,$0, 5 #initiailze $t1 to 5. Notice that an offset of five will move you from row i of the matrix to row (i+1) since matrix has 5 cols.
mult $t1,$a0 #number of row jumps saved to mflo register
mflo $t1 #get mflo value
add $t1, $t1, $a1 #get the entire offset of 5*matrix + column
add $t1, $t1, $s7 #offset the base matrix location value by the correct amount
lb $v0, 0($t1)
ori $t2,$0, 1 #sets $t2 to be equal to 1 (meaning we visited)
sb $t2, 0($t1)
jr $ra
####
# ploc = Print Location
# $a0 = r
# $a1 = c
####
ploc:
or $t1, $0, $a0
li $v0, 4 #4 is the system call for print string
la $a0, op_par
syscall
li $v0, 1 #1 is the system call for print_int
la $a0, ($t1)
syscall
li $v0, 4
la $a0, comma
syscall
li $v0,1
la $a0, ($a1)
syscall
li $v0,4
la $a0, cl_par
syscall
or $a0, $0, $t1
jr $ra
