Question

In RobotBASIC what is the best way to solve this random maze generator?

cellSize = 80 'pixel size of maze cells

mazeWidth = 9 'number of cells horizontally
mazeHeight = 6 'number of cells vertically
DIM maze[mazeWidth,mazeHeight]

'draw a random maze on the screen
Call CreateMaze(mazeWidth,mazeHeight,cellSize)
'place robot in a random location
rLocate Random(mazeWidth)*cellSize+cellSize/2, Random(mazeHeight)*cellSize+cellSize/2, 0, 20
Delay 1000 'pause

' YOUR PROGRAM SOLUTION GOES HERE...

xyString 0,500,"Done."
End 'this must be here!

Sub CreateMaze(w,h,s)
mConstant maze,0 'zero out entire matrix
' draw a grid
LineWidth 5
For y=0 to h \ Line 0,s*y,s*w,s*y \ Next
For x=0 to w \ Line s*x,0,s*x,s*h \ Next
'draw ending "finish box"
Rectangle s*w,s*(h-1),s*w+65,s*h,GREEN,GREEN
Call Cell(0,0,w,h,s)
Return

Sub Cell(x, y, w, h, s)
maze[x,y] = maze[x,y] bOr 4 'mark cell as visited
r = Random(4) 'choose a random direction
For i = r to r+3 'visit each neighbor
If Mod(i,4)=0 then p=x \ q=y-1 'N
If Mod(i,4)=1 then p=x \ q=y+1 'S
If Mod(i,4)=2 then p=x+1 \ q=y 'E
If Mod(i,4)=3 then p=x-1 \ q=y 'W
If (p>=0) and (p<w) and (q>=0) and (q<h)
If maze[p,q] < 4 'skip already visited cells
If p>x then maze[p,q]=maze[p,q]|1 \ Rectangle s*p,s*y+3,s*p,s*(y+1)-2,WHITE
If q>y then maze[p,q]=maze[p,q]|2 \ Rectangle s*x+3,s*q,s*(x+1)-2,s*q,WHITE
If x>p then maze[x,y]=maze[x,y]|1 \ Rectangle s*x,s*y+3,s*x,s*(y+1)-2,WHITE
If y>q then maze[x,y]=maze[x,y]|2 \ Rectangle s*x+3,s*y,s*(x+1)-2,s*y,WHITE
Call Cell(p,q,w,h,s) 'recurse
EndIf
EndIf
Next
Return

Answer 1

Solution: void remove(int) void findSol(int, int); void displaySol) class Mazet public: Maze(int); int find root(int); void union-cell(int, int). precondition: n must be a positive integer postcondition attributes of each cell are assigned values Maze:Maze(int n)\ determine each cell's location and initialize the data members precondition: n must be >= 0 and postcondition: return the root of n the number of all cells int Maze:find root(int n) return the root of n precondition: rootl and root2 both must be0 and < the number of all cells postcondition rootl and root2 belong to the same set void Mazeunion cell(int rootl, int root2) make rootl and root2 belong to the same set

int main int argc, char argv) exit if something is missing in the command line exit if the user provides unacceptable information initialize the random number generator store critical data in variables push all elements into a vector except the last one because it has no walls to knock down use a while loop to construct the maze inside the while loo randomly choose a cell deal with the case when the cell has 2 neighbors deal with the case when the cell has only 1 neighbor generate code for Matlab to display the maze find and put solution code in the solution file precondition: victim should, but not must, be an element in the vector that holds all cells postcondition: victim is erased from the vector void remove(int victim)\ remove victim the vector because victim is already processed

precondition: victim should, but not must, be an element in the vector that holds all cells postcondition: victim is erased from the vector void remove(int victim) remove victim the vector because victim is already processed precondition: from and to must be >-0 and < numOfCells postcondition: find the solution void findSol(int from. int to){ push from to the solution vector mark from visited if from equals to, that means we've found the solution, so we call displaySol0 to write code to output files now go through each surrounding wall inside an if block if the right wall is down and the cell on the other side is not visited yet, use that cell to call findSol recursively if control returns here, that means this cell has led to a deadlock, so pop the element in the back of the solution vector inside an if block if the lower wall is down and the cell on the other side is not visited yet, use that cell to call findSol recursively if control returns here, that means this cell has led to a deadlock, so pop the element in the back of the solution vector inside an if block if the upper wall is down and the cell on the other side is not visited yet, use that cell to call findSol recursively if control returns here, that means this cell has led to a deadlock, so pop the element in the back of the solution vector inside an if block if the left wall is down and the cell on the other side is not visited yet, use that cell to call findSol recursively if control returns here, that means this cell has led to a deadlock, so pop the element in the back of the solution vector