CSIT 441

Maze generator

The method that I used to generate the maze comes from a Java game design book. And this week, I am still working on how to make a random maze. I build a new method generate. I use a Boolean to mark the sell or square and use random generator to generate a direction. Then I will not visit the squares I marked. Then I still use random generator to generate a number which decide the direction. But here are a lot of situations, I already finished the cases when the  square is at top left, top right, bottom left and bottom right, which have only two direction. In addition, here are two other cases. One for the square at the first lines but the corner, which have four situations at four sides. For this case, I need to generator three different directions. And the last case is the square in the middle, which are all the squares except the outermost layer, so I have (height-2)*(width-2) squares. For this case, I have to generate 4 different directions obviously. Actually, what I did is use the position of squares to do the classification and use the random number generator use generator the number accordingly and then use a Boolean method to judge the existence of the wall, then take the walls. Then I made another method called traverse to find the path from origin to termination. I used the valid method to judge if the aim square is valid which means I didn't get out of the area and I didn't go back to the square I've been to.

Comments

Post a Comment

Popular posts from this blog

Conclusion

Image
Actually, I tried a lot of different cases before. I didn't know how many paths between entrance and exit. So I used to want to add missions in my maze, such as the wumpus, I want to add enemy in my maze to limit the solution, however, It's hard to achieve. Because I can't make sure how many solutions first and I also can't limit the choices. So only one solution between entrance and exit is the best choice. So I decided to make that tree model for my project. Which means I set the entrance as the start node and the exit as one of the little branches, so I can make sure only one path.  And I also tried that simple solution that find the way both from entrance and exit. Here is what I got for that: Finally, I used the DFS to figure it out： I learned a lot from my project.
Read more

My model

After I choose to use Deep First Search, I make a model for my project. I want to make sure I have only one way between the entrance and the exit. So I thought what would be a tree, I randomly select a grid as a root node, starting from its depth at random search, offer a way to, until no way to go, take a step back and find another way, go to the corner and back to step back and change another one...Such a cycle, until completely no choice...Actually still back also.In the procedure is the following process (see the code in createMaze () function) :Randomly select a grid as a root node, pressing it into the stack.Then when the stack is not empty execute the following cycle:INTREE symbol of take out a grid, it is set to 1, and then will be out of the tree all of its neighbors in the grid pressure into the stack (random order), and the father of the neighbor grid points to the grid.Solve the two problems, the rest of the maze, display path, ball movement is relatively simple.
Read more

Random Maze Generator

         I was planning to do a KENKEN problem solver but recently I changed my idea for the final project. I am doing the Random Maze Generator now. I am trying to get the Maze randomly and find the solution right away with DFS.          Firstly, I set the size of the maze, and set the first maze as matrix which are the height and the width. Then I got number of the squares are h*w. And I can generate the vertical and horizontal wall randomly according to signs. I need to make the unit square with a Boolean statement: this.notMarked = new boolean[this.height][this.width]; Actually my general idea of the maze generator is trying to take the walls away randomly. So I do need to judge the existence of the both vertical and horizontal walls. Constantly randomly choose one side wall, if it can be separated by the walls of the room which is not connected to each other, then pull down the wall. Then repeat the process until the entre and the exit, resulting in the maze.  And the key prob
Read more