Article directory
First look at the rendering (online computer try address) http://biggsai.com/maze.html): 
cause
It's late at night again. I've written data structures in public numbers as usual! It takes up a lot of my time! My surpassing sister is full of resentment for her serious lack of company.
Beyond my sister, I often complain that it is useless to write something so abstract and difficult to understand. I often ask: What is the use of writing this thing every day? And I answered: can do a lot of things, such as writing a little game or something!
When I'm ready to go to bed after coding: Don't sleep if you can't write well!
Analysis
What if we use data structures and algorithms to make things?
- What is simple and easy? I Baidu, I depend on, this bird game was not easy to do ah, have to contact a bunch of unfamiliar things, can not do it.
With a flash of inspiration, write a guessing game and ask him how much is the sum, subtract, multiply and divide.
- Beyond her sister, she is not a child. She can't fool around.
After a lot of ups and downs, I finally decided to write a maze game at 12:00 in the middle of the night. Figure out some of these steps.
Probably:
- Draw lines - > Draw mazes (wiping lines) > Move blocks, move constraints (no walls outside the boundaries) > Complete the game.
Draw lines (chessboard)
For html+js(canvas) drawings, learning javaswing before should be a bit of an image. In html, there is a canvas canvas canvas canvas on which you can draw something and declare some listening (keyboard listening).
For maze, those lines have no attributes, only position x,y. When you operate this canvas, you may not be the same as our habitual thinking of face-to-face. So, when you design a line or point, remember where the point or line is, and operate according to that position when you draw or scratch or move it later.
<!DOCTYPE html> <html> <head> <title>MyHtml.html</title> </head> <body> <canvas id="mycanvas" width="600px" height="600px"></canvas> </body> <script type="text/javascript"> var aa=14; var chess = document.getElementById("mycanvas"); var context = chess.getContext('2d'); // var context2 = chess.getContext('2d'); // context.strokeStyle = 'yellow'; var tree = [];//Is storage connected or not? var isling=[];//Judge whether or not they are connected for(var i=0;i<aa;i++){ tree[i]=[]; for(var j=0;j<aa;j++){ tree[i][j]=-1;//Initial value is 0 } } for(var i=0;i<aa*aa;i++){ isling[i]=[]; for(var j=0;j<aa*aa;j++){ isling[i][j]=-1;//Initial value is 0 } } function drawChessBoard(){//painting for(var i=0;i<aa+1;i++){ context.strokeStyle='gray';//Optional area context.moveTo(15+i*30,15);//Draw 15 lines vertically, 30 PX apart. context.lineTo(15+i*30,15+30*aa); context.stroke(); context.moveTo(15,15+i*30);//Fifteen lines were drawn horizontally, 30 PX apart, and the chessboard was 14*14. context.lineTo(15+30*aa,15+i*30); context.stroke(); } } drawChessBoard();//Draw chessboard // var mymap=new Array(36); // for(var i=0;i<36;i++) // {mymap[i]=-1;} </script> </html>
Realization effect
Painting maze
How do random mazes occur? What's going on? His face was blurred.
- Because we want a labyrinth, we need to have a connecting path between the entrance and exit of the labyrinth. You probably don't know how to generate the labyrinth and what algorithm to use. Whisper BB: Use And look up (disjoint sets).
What is the relationship between mazes and disjointed sets? (rules)
- In the previous series of data structures and algorithms, I have introduced and collected them.( Disjoint sets Its main function is the merger of forests. Through and collection of unconnected forests, two forests can be merged quickly, and two nodes can be queried quickly whether they are in the same forest.
And our random maze: in the case that each square is not connected, it is a checkerboard square, which is also its initial state. This node may or may not be connected to its neighbors. We can do this by collecting and searching.
Specific ideas are as follows: (mainly understand and collect)
-
1: Define the basic classes and methods that do not want to intersect (search,union, etc.)
2: Array initialization. Each element of an array is a collection with a value of -1.
3: Random search for a grid (one-dimensional data to be converted into two-dimensional, a little troublesome), random search for a wall (that is, to find the grid up and down around), but also to determine whether the grid found out.
In the lattice, find a random number m - > random number m in the two-dimensional position [m/length, m% length] - > the two-dimensional position p[m/length + 1,m% length] or [m/length-1,m% length] or [m/length, m% length + 1] or [m/length, m% length + 1] - > to determine whether the boundary is crossed or not.
4: Determine whether two lattices (one-dimensional array number) are in a set (and look it up). If so, look again. If not, dig out the wall.
5: It's a bit cumbersome to dig out the wall. We need to consider the parity to judge the wall (up or down, or left or right), and then erase it. (Converts to real distance from an array). Specifically, to find a node, according to the location relationship to find the number of one-dimensional arrays and find the set to determine whether or not in a set.
6: Eventually a complete maze is achieved. Until the first (1,1) and (n,n) unions stop. Although random numbers are used to find walls, the effect is not particularly bad. The relationship between one-dimensional and two-dimensional arrays should be clarified. One dimension is real data, and search operation. Two dimensions are positions. Understand transformation!
Note: Avoid confusion and figure out the address of the array and the location of the logical matrix. Arrays start at 0, and logically you decide for yourself. Don't confuse!
The main logic is:
while(search(0)!=search(aa*aa-1))//Main idea { var num = parseInt(Math.random() * aa*aa );//Generate a random number less than 196 var neihbour=getnei(num); if(search(num)==search(neihbour)){continue;} else//Not on one { isling[num][neihbour]=1;isling[neihbour][num]=1; drawline(num,neihbour);//Scribing union(num,neihbour); } }
So the previous code is
<!DOCTYPE html> <html> <head> <title>MyHtml.html</title> </head> <body> <canvas id="mycanvas" width="600px" height="600px"></canvas> </body> <script type="text/javascript"> //Add the above code by yourself // var mymap=new Array(36); // for(var i=0;i<36;i++) // {mymap[i]=-1;} function getnei(a)//Get the neighbor number random { var x=parseInt(a/aa);//To be exact as an integer var y=a%aa; var mynei=new Array();//Store neighbors if(x-1>=0){mynei.push((x-1)*aa+y);}//Upper node if(x+1<14){mynei.push((x+1)*aa+y);}//Lower node if(y+1<14){mynei.push(x*aa+y+1);}//Some nodes if(y-1>=0){mynei.push(x*aa+y-1);}//Lower node var ran=parseInt(Math.random() * mynei.length ); return mynei[ran]; } function search(a)//Find the root node { if(tree[parseInt(a/aa)][a%aa]>0)//Description is a child node { return search(tree[parseInt(a/aa)][a%aa]);//Incompressible path compression } else return a; } function value(a)//Find the size of the tree { if(tree[parseInt(a/aa)][a%aa]>0)//Description is a child node { return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//Unable to compress paths } else return -tree[parseInt(a/aa)][a%aa]; } function union(a,b)//merge { var a1=search(a);//a root var b1=search(b);//b root if(a1==b1){} else { if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//This is a negative number (), so in order to simplify the calculation, the value function is not called. { tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//Number additive attention is negative number additive tree[parseInt(b1/aa)][b1%aa]=a1; //b-tree becomes a subtree of a-tree, and the root b1 of b points directly to a. } else { tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa]; tree[parseInt(a1/aa)][a1%aa]=b1;//The tree where a resides becomes the subtree of the tree where b resides. } } } function drawline(a,b)//To draw a line, we should judge whether it is up or down or left or right. { var x1=parseInt(a/aa); var y1=a%aa; var x2=parseInt(b/aa); var y2=b%aa; var x3=(x1+x2)/2; var y3=(y1+y2)/2; if(x1-x2==1||x1-x2==-1)//Points in left and right directions need to be underlined { //alert(x1); // context.beginPath(); context.strokeStyle = 'white'; // context.moveTo(30+x3*30,y3*30+15);// // context.lineTo(30+x3*30,y3*30+45); context.clearRect(29+x3*30, y3*30+16,2,28); // context.stroke(); } else { // context.beginPath(); context.strokeStyle = 'white'; // context.moveTo(x3*30+15,30+y3*30);// // context.lineTo(45+x3*30,30+y3*30); context.clearRect(x3*30+16, 29+y3*30,28,2); // context.stroke(); } } while(search(0)!=search(aa*aa-1))//Main idea { var num = parseInt(Math.random() * aa*aa );//Generate a random number less than 196 var neihbour=getnei(num); if(search(num)==search(neihbour)){continue;} else//Not on one { isling[num][neihbour]=1;isling[neihbour][num]=1; drawline(num,neihbour);//Scribing union(num,neihbour); } } </script> </html>
Achieving results:
Block movement
This part of the method I used is not dynamic real movement, but a grid-by-grid jump. That is to say, when you go to the next grid, erase the square of the current grid and draw another square in the moving grid. The box is chosen because it is easier to erase and can be precisely erased according to the size of the pixel.
In addition, attention should be paid to not crossing walls and boundaries when moving again. So how to judge? It's easy to do. We'll see if the two lattices are connected. If not, we'll take the wall apart. Record these two points when removing the wall (array)
In addition, the event monitoring can be found by checking up and down, adding buttons to monitor some events, which is not the most important.
In order to enrich the game's playability, the method can be encapsulated and the level can be set (just change the size of the maze). In this way, customs clearance can be achieved. In addition, it would be better if it was written as a dynamic repository.
epilogue
Online Attempt Address Code can directly view the source code of the web page!
The author's front-end ability and algorithmic ability are limited, writing may not be particularly good, please forgive me! Of course, the author welcomes people who love learning to make progress and learn together. Welcome to pay attention to the author's public number: bigsai, if it feels good, welcome to pay attention and praise! Crab crab!
