其他
我花了一夜用数据结构给女朋友写个H5走迷宫游戏 ｜ CSDN 博文精选
以下文章来源于bigsai ，作者bigsai
什么东西简单容易呢？我百度一下，我靠，这个鸟游戏原来不好搞啊，得接触一堆不熟悉的东西，搞不来搞不来。有了(灵光一闪)，写个猜数字游戏，问他加减乘除等于几。 超越妹妹又不是小孩子，糊弄不过去。 经过一番折腾，终于在半夜12点确定写迷宫小游戏了。大概弄清楚其中的几个步骤。
<!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 = [];//存放是否联通var isling=[];//判断是否相连for(var i=0;i<aa;i++){ tree[i]=[];for(var j=0;j<aa;j++){ tree[i][j]=-1;//初始值为0 } } for(var i=0;i<aa*aa;i++){ isling[i]=[];for(var j=0;j<aa*aa;j++){ isling[i][j]=-1;//初始值为0 } }function drawChessBoard(){//绘画for(var i=0;i<aa+1;i++){ context.strokeStyle='gray';//可选区域 context.moveTo(15+i*30,15);//垂直方向画15根线，相距30px; context.lineTo(15+i*30,15+30*aa); context.stroke(); context.moveTo(15,15+i*30);//水平方向画15根线，相距30px;棋盘为14*14；context.lineTo(15+30*aa,15+i*30); context.stroke(); } } drawChessBoard();//绘制棋盘// var mymap=new Array(36);// for(var i=0;i<36;i++)// {mymap[i]=-1;}</script></html>因为我们想要迷宫，那么就需要这个迷宫出口和入口有连通路径，你可能压根不知道迷宫改怎么生成，用的什么算法。小声BB：用并查集(不相交集合)。
之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合)，它的主要功能是森林的合并，不联通的通过并查集能够快速将两个森林合并，并且能够快速查询两个节点是否在同一个森林中！
while(search(0)!=search(aa*aa-1))//主要思路 {var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数var neihbour=getnei(num);if(search(num)==search(neihbour)){continue;}else//不在一个上 { isling[num][neihbour]=1;isling[neihbour][num]=1; drawline(num,neihbour);//划线 union(num,neihbour); } }<!DOCTYPE html><html><head><title>MyHtml.html</title></head><body><canvas id="mycanvas" width="600px" height="600px"></canvas></body><script type="text/javascript">//自行添加上面代码// var mymap=new Array(36);// for(var i=0;i<36;i++)// {mymap[i]=-1;}function getnei(a)//获得邻居号 random{var x=parseInt(a/aa);//要精确成整数var y=a%aa;var mynei=new Array();//储存邻居if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点if(x+1<14){mynei.push((x+1)*aa+y);}//下节点if(y+1<14){mynei.push(x*aa+y+1);}//有节点if(y-1>=0){mynei.push(x*aa+y-1);}//下节点var ran=parseInt(Math.random() * mynei.length );return mynei[ran]; }function search(a)//找到根节点{if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点 {return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩 }elsereturn a; }function value(a)//找到树的大小{if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点 {return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩 }elsereturn -tree[parseInt(a/aa)][a%aa]; }function union(a,b)//合并{var a1=search(a);//a根var b1=search(b);//b根if(a1==b1){}else {if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数()，为了简单减少计算，不在调用value函数 { tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加 注意是负数相加 tree[parseInt(b1/aa)][b1%aa]=a1; //b树成为a树的子树，b的根b1直接指向a；}else { tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa]; tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树 } } }function drawline(a,b)//划线，要判断是上下还是左右{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)//左右方向的点 需要上下划线 {//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))//主要思路 {var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数var neihbour=getnei(num);if(search(num)==search(neihbour)){continue;}else//不在一个上 { isling[num][neihbour]=1;isling[neihbour][num]=1; drawline(num,neihbour);//划线 union(num,neihbour); } }</script></html>