A brief explanation of a maze game made in Java for a cousin of an elementary school student
at first
The other day, cousins in the 4th and 1st grades of elementary school came to visit us. Playing with the body is difficult, so I thought that if I made it in the game, it would be quiet, so I created a maze game that works with CUI. As a result, their mother was more addicted than their cousins, and in the end they couldn't stop the Dottanbattan fuss.
environment
Linux Mint 18 'Sarah' MATE 64-bit Java 1.8.0_131 Google Chrome 61.0.3163.79 (Official Build) (64-bit)
Maze generation algorithm
There seem to be various algorithms for creating a maze, but this time we will use an algorithm called ** digging method (road extension method) **. Various algorithms are written in an easy-to-understand manner on this site, so it is recommended to refer to them.
Premise
Suppose the maze is on a two-dimensional plane and is a collection of "mass" like graph paper. At this time, the square shall play the role of either "wall" or "road". Also assume that the outside of the maze is completely filled with roads. And there is only one road from the start to the goal.
Drilling method (road extension method)
This algorithm is similar to how humans create a maze by hand. Therefore, the degree of randomness of the road is high. Also, the number of straight lines tends to decrease, so if you create a large maze, it will look messy. The contents of the algorithm are shown below.
- Make the entire maze a wall.
- Use one randomly selected square as the road, except for the squares that touch the outside of the maze.
- Randomly extend the road from there (unless the one square above, below, left, or right in the direction you are going is the road).
- Repeat step 3 as much as possible.
- Randomly select one square from the squares that are already on the road, except outside the maze.
- Repeat steps 3-5 as much as possible.
I will explain only step 3 a little.
■: Wall □: Road ○: The square that is about to move forward -: It doesn't matter whether it's a wall or a road
Suppose you're trying to go left from a road. At this time, if the squares on the left side of the road are as follows, you can extend the road to the left.
-■- ■ ○ □ ← Trying to extend the road from here -■-
However, if even one square that was a wall in the previous figure (for example, the square above ○) becomes a road, you will not be able to extend the road to the left. The reason is that the "road that is being extended" and the "road that is adjacent to ○" are connected. Allowing the two roads to connect creates a looping road, and there is no single road from the start to the goal.
-□- ■ ○ □ ← Trying to extend the road from here -■-
After completing step 6, all you have to do is select the squares that will be the start and goal from the squares that touch the outside of the maze.
Implementation
All are implemented using Java. Here's the part of the maze generation algorithm I just described (for those who want to see the full code here). In addition, the part corresponding to each step shown in the previous explanation is shown in the comment.
Maze.java
//Method to create a new maze
static void createMaze() {
// [step 1]Initialization
for (int i = 0; i < mazeSize; i++) {
for (int j = 0; j < mazeSize; j++) {
wall[i][j] = true;
}
}
// [Step 2]Randomly select the start position (1 ~ mazeSize- 2）
Random rnd = new Random();
row = rnd.nextInt(mazeSize - 2) + 1;
col = rnd.nextInt(mazeSize - 2) + 1;
wall[row][col] = false;
rowStack.push(row);
colStack.push(col);
boolean continueFlag = true;
// [Step 6]Below, wall[][]Repeat until the whole is filled
while (continueFlag) {
// [Step 3,4]Extend the road to the limit either up, down, left or right
extendPath();
// [Step 5]Select the next starting position from the existing road (0 to mazeSize)- 1）
continueFlag = false;
while (!rowStack.empty() && !colStack.empty()) {
row = rowStack.pop();
col = colStack.pop();
if (canExtendPath()) {
continueFlag = true;
break;
}
}
}
}
The explanation of the main variables is as follows.
--int mazeSize: The length of one side of the generated maze (square). --Boolean [] [] wall: The state of the entire maze. True represents the wall and false represents the road. --int row: The row of "the square you are trying to make the way". --int col: A column of "masses trying to make way". --Stack rowStack: A stack with rows of "squares already on the road". --Stack colStack: A stack with columns of "masses already on the road".
The explanation of the main methods is as follows.
--extendPath (): Perform steps 3 and 4 in the previous description. --canExtendPath (): Determines if the "mass you are trying to make a way" can really make a way.
By stacking "Mass that have already been made into a road", you can check all the roads to which Step 3 can be applied.
Execution result
The execution result looks like this (mazeSize = 30).
The "**" in the lower left represents the player, and the "GO" in the upper right represents the goal. You can move the player up / down / left / right with the wsad key. When you reach the goal, the clear time will be displayed along with the praise. When you actually try it, it is quite difficult because it branches in a complicated way.
Implementation in JavaScript and HTML
I also implemented it in JavaScript and HTML so that it can be played in the browser. It's basically the same as the Java implementation. For how to draw the maze, I used this site as a reference.
Execution result of browser version
The execution result looks like this (mazeSize = 50).
The blue block in the lower left represents the player, and the red block in the upper right represents the goal. You can move the player up / down / left / right with the arrow keys. When you reach the goal, the clear time will be displayed in the dialog along with the praise. You can freely change the size of the maze from the input field at the top. I'm not thinking about how it works on smartphones. ~~ By the way, you can play from here. ~~
Future tasks
―― ~~ I want to make it a GUI so that I can easily play it on Windows and put it in an exe file. ~~ The era seems to be the Web, so I made it possible to play with a browser. ―― ~~ The appearance is messy, so I want to increase the number of straight roads. ~~ I think it's more interesting as a maze if it's messed up, so leave it as it is. -~~ Currently, you need to press the enter key after pressing the wsad key, so I want to move it with just the wsad key. ~~ The browser version can be played with the arrow keys. ――I want to display high scores.
Reference URL, etc.
Automatically generated maze http://www5d.biglobe.ne.jp/stssk/maze/make.html GitHub https://github.com/hey-cube/maze [JavaScript] Create a mysterious dungeon maze with HTML + JavaScript http://www.yoheim.net/blog.php?q=20151202 ~~ HeyCube Maze http://www.coins.tsukuba.ac.jp/~s1411396/index.html~~
Finally
When I broke up with my cousins, I was asked, "Can I play that game anymore?" So I promised to make it available for download and play on the web. So, eventually this maze will be available for download and play.
I'm glad if there are people who are interested in what I made.
(Added on 2017/09/08) I didn't use the method of downloading and playing, but I created a browser version so that my cousins can play at home.
(Added on 2018/03/24) At that time, I didn't understand JavaScript, but looking back, it's terrible ... Regardless of the algorithm, please do not refer to the JavaScript code.
Recommended Posts