I decided to go with a graph data structure(adjacency list) to build a rectangular maze. The maze would be designed in a fashion that the vertices would be the nodes of the path and the edges between the vertices would be positions where walls can be inserted.
I maintain a list of vertices with each vertex data structure having an array list of edges. An edge data structure would consist of two vertices.
Once I fill in my data structure, I start building the maze. Oh, I also need a stack for backtracking if required and also an array to check if a vertex is visited. From the start vertex, I pick a random neighbour which is unvisited and move to it after labelling the initial vertex as visited. I keep moving until I hit a position where are there are 1) no unvisited neighbours available or 2) I reach the destination. If 1, then I use my stack and back track.
The challenge now remains with drawing the randomly built maze.
I maintain a list of vertices with each vertex data structure having an array list of edges. An edge data structure would consist of two vertices.
Once I fill in my data structure, I start building the maze. Oh, I also need a stack for backtracking if required and also an array to check if a vertex is visited. From the start vertex, I pick a random neighbour which is unvisited and move to it after labelling the initial vertex as visited. I keep moving until I hit a position where are there are 1) no unvisited neighbours available or 2) I reach the destination. If 1, then I use my stack and back track.
The challenge now remains with drawing the randomly built maze.
No comments:
Post a Comment