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

Edited 3 Years Ago by mike_2000_17: Fixed formatting

? How did you get it working? What did you add/change to make it work? Please tell, so others have the same problem, they have a solution :)

This article has been dead for over six months. Start a new discussion instead.