I'm writing a MIPS program that solves a randomly generated maze using a left-hand rule algorithm. I'm trying to find a way to track the best path through the maze as it completes the LHR algorithm.
In the program, $t9 is a 32-bit number that stores the current location and direction of the car that is traversing the maze. Bits 31-24 store the row location in an 8-bit 2C number and 23-16 store the column location. I've already figured out how to isolate the row and column numbers, and I know how to store them into arrays of word in the .data space, but I'm not sure how I'd go about finding which spaces have already been visited, aka duplicate values in the array.
So far, as it completes the maze the array would look something like this:
0001020110 [starts in 0,0, goes to 0,1, goes to 0,2, goes to 0,1, then 1,0], and I need to find a way to copy this into a new array, or basically weed out 0,1 since it visited that space twice and make it 000210.
Alternatively, I could split the rows and columns into two separate arrays. Any help is greatly appreciated.
Here is the code for the algorithm so far. I only included my main function, since the other functions described only link to functions that move the car, and don't change the location of the car.
.data
rows: .space 100
cols: .space 100
location: .space 100
.text
la $a0, location
jal _leftHandRule
j endProgram
_leftHandRule:
#a0: address of location space
.text
goForward:
addi $t8, $zero, 1
andi $t4, $t9, 0x80000 #if the value in 0x80000 (bit 19, row 8) is not 0, then the car is in row 8, and has finished the maze
#row
srl $t5, $t9, 24
andi $t6, $t5, 0xff
sw $t6, location($t7)
addi $t7, $t7, 1 #increments t7 in as the array location counter
#column
srl $t5, $t9, 16
andi $t6, $t5, 0xff
sw $t6, location($t7)
addi $t7, $t7, 1 #increments t7 for the next loop
bne $t4, $zero, endLeftHandRule
andi $t0, $t9, 0x08
bne $t0, $zero, hitWall #if the value in 0x08 is not zero, there is a wall in front of the car
andi $t2, $t9, 0x04
beq $t2, $zero, noLeftWall #if the value in 0x04 is zero, there is no left wall beside the car
j goForward
I wouldn't look for duplicate coordinate pairs in the stream of locations, as that's O(N) (where N is length of path).
I would instead initialize MxN bit visited array to zero at the start of algorithm (M, N = maximum maze sizes for columns/rows) (so size of array is M*N/8 bytes, or when whole byte is used instead of bit, then M*N bytes).
Then when you visit particular [x,y] location, you set corresponding bit/byte in visited to one, like visited[y*N + x] = 1.
To test if you already were to some location, you look up into visited[y*N + x] value. That's O(1) test.
And finally, if your maze definition is already M*N, and there is some free unused bit in each cell, which you can modify, you can use that one instead of separate array (it's not obvious from question, how is the maze defined, but there's some bit magic in the code like separate front/left walls, so maybe it would be possible to cram this visited-bit into it).
If you can destroy the maze definition during LHR, you can also add fake-walls to it to mark ways you already tried (so once you go forward, you would create "forward" wall behind you on original location, preventing the LHR to go "forward" next time, when it visits the original location, it will now see the route blocked).
Actually I'm not sure how this info will help with creating optimal path by LHR algorithm, I took a 5s thought, and I would need something else for it, incorporating recursion probably, so I would know about visited cells by returning to particular recursion depth. Then again that would be huge strain on stack, to write it like that, so I would go for array, and probably change from LHR into some wide-first search, as LHR is sort of depth-first, which is less optimal... so I'm already off your path. Take my answer only as description how to mark particular cell as visited, how you will use it is up to you.
Thinking about it for 5s more. You actually probably really want to find that particular first visit of cell in your "location" output, to overwrite the blind branch which returned back to it.
You can do that by reading the "location" data from start up to $t7 and when you find two bytes with current row/column, reset t7 after it, otherwise when t7 is reached, it's "not found" (so for every single step you do O(N) search in "location" data).
But I would still go with another "maze" array, this time storing not only "visited" flag, but "direction to next". Simply overwriting it during LHR without any test (O(1) "test" per LHR step).
After reaching end of maze, I would go back to start and just follow the "direction to next", producing the "location" data with coordinates. It will follow the LHR path from start to end without the dead-end branches (as only the last "direction of next" of particular cell will remain, which leads to exit.