查看: 2628|回复: 1

我花了一夜用数据结构给女朋友写个H5走迷宫游戏

字体大小: 正常放大

杨利霞

5273 主题	82 听众	17万积分

TA的每日心情

	开心 2021-8-11 17:59

签到天数: 17 天

[LV.4]偶尔看看III

网络挑战赛参赛者

自我介绍: 本人女，毕业于内蒙古科技大学，担任文职专业，毕业专业英语。

群组: 2018美赛大象算法课程

群组: 2018美赛护航培训课程

群组: 2019年数学中国站长建

群组: 2019年数据分析师课程

群组: 2018年大象老师国赛优

电梯直达

1^#

发表于 2020-4-1 10:57 |只看该作者 |正序浏览

|招呼Ta 关注Ta

我花了一夜用数据结构给女朋友写个H5走迷宫游戏
文章目录

起因
分析
画线(棋盘)
画迷宫
方块移动
结语
先看效果图(在线电脑尝试地址http://biggsai.com/maze.html)：

起因

又到深夜了，我按照以往在公众号写着数据结构！这占用了我大量的时间！我的超越妹妹严重缺乏陪伴而怨气满满！

超越妹妹时常埋怨，认为数据结构这么抽象难懂的东西没啥作用，常会问道：天天写这玩意，有啥作用。而我答道：能干事情多了，比如写个小游戏啥的！

当我码完字准备睡觉时：写不好别睡觉！

分析

如果用数据结构与算法造出东西来呢？

什么东西简单容易呢？我百度一下，我靠，这个鸟游戏原来不好搞啊，得接触一堆不熟悉的东西，搞不来搞不来。
有了(灵光一闪)，写个猜数字游戏，问他加减乘除等于几。

超越妹妹又不是小孩子，糊弄不过去。
经过一番折腾，终于在半夜12点确定写迷宫小游戏了。大概弄清楚其中的几个步骤。

大概是：

画线—>画迷宫(擦线)—>方块移动、移动约束(不出界不穿墙)—>完成游戏。
画线(棋盘)

对于html+js(canvas)画的东西，之前学过javaswing应该有点映像。在html中有个canvas 的画布，可以在上面画一些东西和声明一些监听(键盘监听)。

对于迷宫来说，那些线条是没有属性的，只有位置x,y，你操作这个画布时候，可能和我们习惯的面相对象思维不一样。所以，在你设计的线或者点的时候，记得那个点、线在什么位置，在后续划线还是擦线还是移动的时候根据这个位置进行操作。
<!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=[];, ^. u) e' K9 W6 X( `7 b5 V
      for(var j=0;j<aa;j++){
" d6 d$ q( _! v9 W& ]4 \          tree[j]=-1;//初始值为06 q2 l' ^6 n! D5 F+ V0 _
      }
% L) o! k- P2 U. A3 y }  for(var i=0;i<aa*aa;i++){& O3 r! @: J/ Q  C: A
      isling=[];
/ L2 B, _" l/ W" [, _% `& }& W: [8 h       for(var j=0;j<aa*aa;j++){/ D3 K6 K' z" T& e% A
         isling[j]=-1;//初始值为05 N! [! o& |- z4 m& |* m4 U
      }8 C# c% w7 U3 X2 J9 @4 h* v
}
5 e7 w& P) w1 M% g% n$ F/ @9 g5 |. \% {! A% ^9 v
function drawChessBoard(){//绘画' [+ E# q# f% G9 d2 ^
      for(var i=0;i<aa+1;i++){
' V: k/ r& F1 a' N: ]6 D5 i3 H          context.strokeStyle='gray';//可选区域
6 l$ Y% b" [: V4 h& w          context.moveTo(15+i*30,15);//垂直方向画15根线，相距30px;8 p. ?. |+ m5 p
         context.lineTo(15+i*30,15+30*aa);8 j7 I" r; X% K
         context.stroke();
1 R0 q8 W$ ~5 ~# k0 _4 |" N/ `; J          context.moveTo(15,15+i*30);//水平方向画15根线，相距30px;棋盘为14*14；2 i) i* y* t/ O, u* D7 m& g* y& Z1 T
         context.lineTo(15+30*aa,15+i*30);
- H+ e9 [/ b. s          context.stroke();
& r3 _; `9 x* O8 r       }
5 c. y1 ?+ B6 r# o$ u, u/ B }
. K5 U5 O( m0 L# e( ?( l( i5 C2 s drawChessBoard();//绘制棋盘
& N* i# m* r+ Q: v8 ?
) S8 N3 t5 @/ Y0 M0 T //    var mymap=new Array(36);5 F' q. E) l; k, f& ]; K
//    for(var i=0;i<36;i++)
+ p6 B6 ^# y) E, L //    {mymap=-1;}
* j. d9 P5 i' X2 e9 E9 T
: o" K  ~& h8 C- a; J
6 P5 p' ]& @2 j+ u- }$ r3 _4 H  </script>6 W. t; P. v) g
</html>0 S/ y4 N: G3 h- t; a# H6 R/ n% _

$ X3 t+ j: Y$ k' q+ m, c* v7 d1 a2 G* j
实现效果
6 ?/ s, S! x1 }

2020-4-1 10:52 上传
下载附件 (184.4 KB)

) I" G! g: G: d9 F. E

. S7 o* t/ A( X+ {画迷宫3 c  Z; C0 b! ^* I0 Q; J  I  n& v
% C. S7 }: j, `  U6 U  R
随机迷宫怎么生成？怎么搞？一脸懵逼。; Y/ R' l) c, P5 k1 p' j- Q7 X6 m" |

, _, v$ M* e8 d) B3 b; p因为我们想要迷宫，那么就需要这个迷宫出口和入口有连通路径，你可能压根不知道迷宫改怎么生成，用的什么算法。小声BB：用并查集(不相交集合)。
( S, e4 h- m, r. W& |迷宫和不相交集合有什么联系呢？(规则)! a: |5 n# v* J. S$ `* K! [/ B

- Y7 a% N6 S" i3 O$ w' H之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合)，它的主要功能是森林的合并，不联通的通过并查集能够快速将两个森林合并，并且能够快速查询两个节点是否在同一个森林中！/ z" r. @+ S: ^" Y9 g
而我们的随机迷宫：在每个方格都不联通的情况下，是一个棋盘方格，这也是它的初始状态。而这个节点可以跟邻居可能相连，也可能不相连。我们可以通过并查集实现。, K6 T  T  t- l( Y) ]
3 {  w7 _0 }+ S
具体思路为：(主要理解并查集)
, H/ ~( B! ^* d. N3 C; q( c- o1 y7 x& X0 ^, S
1：定义好不想交集合的基本类和方法（search,union等）+ i# G$ i" K. R
2：数组初始化，每一个数组元素都是一个集合，值为-19 r: N1 K- J7 e. D# Y
3：随机查找一个格子（一维数据要转换成二维，有点麻烦），在随机找一面墙（也就是找这个格子的上下左右），还要判断找的格子出没出界。
& T" }$ A: ]* e9 h6 e( z具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界3 ~' h" s8 g/ c& n3 p& t9 N
4：判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在，则重新找，如果不在，那么把墙挖去/ Y  G+ M2 U& w& {- C: B
5：把墙挖去有点繁琐，需要考虑奇偶判断它那种墙(上下还是左右，还要考虑位置)，然后擦掉。（根据数组转换成真实距离）。具体为找一个节点，根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。
+ _5 w: c$ x- l% V- P: I6：最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙，但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据，并查集操作。二维是位置。要搞懂转化！6 h$ Q4 S- H9 i
注意：避免混淆，搞清数组的地址和逻辑矩阵位置。数组从0开始的，逻辑上你自己判断。别搞混淆！
' j/ v6 u& e' Y4 M6 q8 h, f

2020-4-1 10:53 上传
下载附件 (184.21 KB)

+ J1 M3 f  y/ n8 W) M主要逻辑为：) R2 Y; w( @) r) N0 D% i# j$ a
while(search(0)!=search(aa*aa-1))//主要思路
2 c/ e3 y! B( d" {; x! _ {  q, j2 n6 \: m# ]- k8 Q. @
      var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
/ K. ?: o0 D/ `& G6 n  O       var neihbour=getnei(num);
9 _) {/ Q  ^3 }- _9 e$ Y; ?       if(search(num)==search(neihbour)){continue;}
6 R4 |" a" ]: r       else//不在一个上
; b- }+ ~( ?2 X5 w3 i' @5 _       {
5 b( C6 o8 S4 n          isling[num][neihbour]=1;isling[neihbour][num]=1;0 M! R( B" }- s+ \: D
         drawline(num,neihbour);//划线
- ^5 j2 E7 T% U' `; g9 d- N2 B          union(num,neihbour);/ X) x4 M7 {/ i

8 V/ N1 d. K; O       }
- N" y3 Z! D+ f) B! _: P+ i3 V }! {8 ^0 n* c, i
2 J. [/ D' R) ^) _. G
# k% K; b5 |5 X6 `# r& L6 e) i
那么在前面的代码为
) P9 e) b$ _- N; L# p& s<!DOCTYPE html>
/ X7 J# m" ?6 u2 E$ l& A% c. p<html>
5 f( `% ?7 H) d" i* J  <head>% q0 Q2 h  o; s6 L+ k
<title>MyHtml.html</title> 5 S; m4 _7 i& F/ `1 l, }
  </head>
  <body>
; N4 p0 G; J" c" \7 b8 c8 X  <canvas id="mycanvas" width="600px" height="600px"></canvas>0 u6 S: d, u! z" n
7 X6 J/ f$ L7 Z6 M" T% ~: s0 C
  </body>
( A$ C% ~8 f! D9 u7 J' G* ?7 m' ?  <script type="text/javascript">' M* h/ ^% M! k; Q$ k
//自行添加上面代码0 G1 M  |4 h8 l$ E5 W( u1 v7 ~
//    var mymap=new Array(36);5 }8 ?' w9 v, E7 E+ t- {& w4 ]
//    for(var i=0;i<36;i++)
% v% T& h; S: w //    {mymap=-1;}
1 B# N3 u, N2 n8 W3 M function getnei(a)//获得邻居号  random! |# S9 V" C7 A, p$ C* o
{
, N. f) Y) p5 F  A: g* B       var x=parseInt(a/aa);//要精确成整数
0 s, f4 b4 n) s" d3 q/ h" ^7 ?# ^  D       var y=a%aa;
  L, g! t+ Y: Z3 Y! g       var mynei=new Array();//储存邻居
  c( c& t9 s) m* d& i, a0 ^, f) v       if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点$ N. j! Y0 K: v9 ~& r' Y
      if(x+1<14){mynei.push((x+1)*aa+y);}//下节点  L8 s5 Z& g5 Q8 d7 K8 w
      if(y+1<14){mynei.push(x*aa+y+1);}//有节点
' y  x# C8 A6 G* D       if(y-1>=0){mynei.push(x*aa+y-1);}//下节点* A. V7 l5 X# C& [1 R0 b
      var ran=parseInt(Math.random() * mynei.length );
1 Z8 k4 ]1 X% a+ H& x       return mynei[ran];
% Z: a5 v+ x0 L* W9 I! R- Q
2 F2 S/ ?& T% y& o }
' E0 J* Z1 A4 }" F% k& O) H function search(a)//找到根节点+ U1 `' e* @7 N1 H7 D# p' u( i, P: s
{* x, B; K+ [9 n
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
3 M% y' v6 |& q# m       {3 Y" `2 F( {' t3 {+ g- u, g5 |8 m
         return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩1 S8 }9 D- x- _. r
      }
! o3 _& h$ p& S! z: Q1 q! q4 |       else
9 M( _9 W" f7 {3 Y+ p2 ^* x          return a;8 ^4 C% V3 ^: U7 Y
}
4 p% F8 u* Y* @; y, x2 O3 Q function value(a)//找到树的大小+ S6 f' k/ R3 r6 x2 W
{7 }; m5 n9 U% j% Y9 m" ]
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
% D* A6 P3 ]- Q2 r7 K3 Y8 z       {
$ Y* j* u, W6 q          return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩
! ^3 S9 j. x. ?- K" ~' x: x0 r       }
6 w7 B  ~. U# {0 R       else
1 s5 `3 L: l( e          return -tree[parseInt(a/aa)][a%aa];
$ X7 v+ e% M6 S, B- L }
/ I; a3 _+ I& k; q9 l1 u+ w% h" d; n9 m function union(a,b)//合并
2 i* n  g: S+ m" f {6 @5 K0 L" k3 g7 n2 V+ ~
      var a1=search(a);//a根" ^9 D8 s9 f  ]; K# |
      var b1=search(b);//b根: u5 h9 L5 ^. g0 @1 y
      if(a1==b1){}. z7 Y. p4 ?$ l
      else8 s4 E: `  |( Z( s; I
      {
& e7 r. m( _; W+ z) z$ h5 ^          if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数()，为了简单减少计算，不在调用value函数
4 x! S. f+ k1 W0 U          {
8 n1 {6 O# f/ ^2 x: z8 k) @             tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加  注意是负数相加
& N0 |- w4 z- l; U             tree[parseInt(b1/aa)][b1%aa]=a1;    //b树成为a树的子树，b的根b1直接指向a；
5 X+ T% J' K# h7 O& h( g0 Q          }; F0 D7 y9 x* a* e! k! u
         else
3 D. Q$ h0 O4 f% v+ }          {6 Z- j% k: `) }' E( i! d5 ?4 d
            tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];
; @1 X  p! \* w& o( a             tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树
% r  j8 m+ Y# r- w  H          }! Q- r- `! Y9 R9 D; W
      }9 X/ g* ]8 e) B+ q
}" ~' [: ?; j/ z" V

. t* @/ H% M  ?2 F& K( p/ r function drawline(a,b)//划线，要判断是上下还是左右. T5 e5 [7 ~  b" L, P% g
{

  |7 h5 e- S  @. y       var x1=parseInt(a/aa);" \/ t5 c. P! O
      var y1=a%aa;5 H! W  Q, `2 ?) ]1 ^
      var x2=parseInt(b/aa);
5 A9 A! C0 c) P+ P       var y2=b%aa;
! o8 ]& x' I4 @  J       var x3=(x1+x2)/2;
8 K, ~! _! b% ^* b; W' C       var y3=(y1+y2)/2;3 q' ~9 x5 q8 I1 K1 }! \, P, S6 ^
      if(x1-x2==1||x1-x2==-1)//左右方向的点  需要上下划线
/ f0 y. Y& z& j3 ?       {4 u6 H: [5 w1 l8 B
         //alert(x1);
' f( @: r. ^4 M3 r: o# f/ j% Z          //  context.beginPath();* [; [; [! ]7 ?& T5 Z% }
         context.strokeStyle = 'white';
6 M; `3 {8 A; F! r* d# ^          // context.moveTo(30+x3*30,y3*30+15);//- v8 K) o8 l! Z$ ~& g( s
         // context.lineTo(30+x3*30,y3*30+45);
, @. Q, Q! u3 p4 t          context.clearRect(29+x3*30, y3*30+16,2,28);
  h1 ]0 ~& J0 i( d) j4 }          // context.stroke();
3 i' U& x: ~$ J, Z" j: G       }9 y* C; R) C! L; {( q+ R
      else% [( W* F$ O: a' _. }6 V
      {; L; p8 r1 h- e4 N7 I
         // context.beginPath();* ^( |; Y0 V! X, w  Q: I" L
         context.strokeStyle = 'white';& G4 S) B. |8 L* d( y7 `1 R; Q
         //  context.moveTo(x3*30+15,30+y3*30);//
8 F/ m) ^, M/ h. @9 M" e3 K6 S9 p  u          // context.lineTo(45+x3*30,30+y3*30);: m6 Q7 L2 Z& t( d' f( v! S
         context.clearRect(x3*30+16, 29+y3*30,28,2);+ Y0 Z% ?2 q( X: ^6 d
         //    context.stroke();
9 z: J1 o* }8 m1 I; o       }
% }9 B1 o: l, @7 p' `- G% V, R  { }
1 N% a( w- e: j# g
5 Z6 u, L) f# }, ^; l while(search(0)!=search(aa*aa-1))//主要思路
6 v! j" G1 |, D {# [; ^' |) Z. I7 C  {# u1 ~9 T3 L
      var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
6 _: ]) G3 Y- c5 T/ b       var neihbour=getnei(num);# ~: [- b$ f& s+ n0 G$ c' d) n6 ]
      if(search(num)==search(neihbour)){continue;}
0 {2 C- l% g* s; g# |7 T- M       else//不在一个上
9 C0 a# A9 E/ V8 ~! i- x       {
  u0 d8 Z' b' h2 s, B          isling[num][neihbour]=1;isling[neihbour][num]=1;( B9 ~* N+ g" d& [* g
         drawline(num,neihbour);//划线, n+ _) [$ G' O
         union(num,neihbour);/ D  i% Z, t* d% d) z7 V( O  Q* s
/ @/ m! o5 m" t5 {+ M
      }
5 n# }& h# P4 F2 _* m; A! Q }, Y! z" r2 L: e) [8 x
  </script>
8 b( ^( a$ @- R- k2 v+ ?4 M1 T/ ]</html>
7 }- [6 y: e- N9 Z6 _4 L7 f0 u3 e4 o
# A/ ^& ^6 j6 p6 G! X
实现效果：
& h! W# b- M2 X
# O  N. S* t$ v

2020-4-1 10:55 上传
下载附件 (114.08 KB)

& Z8 _) \/ h4 v  d+ A2 _0 P/ Y
+ B7 _) A9 f/ y% ~  Y) N9 t8 Z

2020-4-1 10:56 上传
下载附件 (115.53 KB)

& |3 b1 j: h' n5 p. l. ]方块移动; R7 B( D: y& O9 F9 Y& U4 C

, H- t+ `$ I2 [- f* [7 y2 L这部分我采用的方法不是动态真的移动，而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉，在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除，可以根据像素大小精准擦除。
2 |; f) n$ P* c: K6 o3 z1 i! \$ b
( E$ @+ N: b3 @. m7 k$ G另外，再移动中要注意不能穿墙、越界。那么怎么判断呢？很好办，我们再前面会判断两个格子是否联通，如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组)
1 t: I' H& J' I  d3 `8 U$ N( Y$ D1 R/ |$ Z1 B
另外，事件的监听上下左右查一查就可以得到，添加按钮对一些事件监听，这些不是最主要的。9 l5 X/ @- q# s1 x

( [4 x# f" v, x* u' ]; S' m2 H为了丰富游戏可玩性，将方法封装，可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外，如果写成动态存库那就更好了。

2020-4-1 10:56 上传
下载附件 (12.12 KB)

, Z* b4 Z4 f! a5 _4 e8 Q, F( S( k- i. K
8 g; e) D6 S1 ?. V
————————————————
; _+ T; W) L( o% }4 j: F. c版权声明：本文为CSDN博主「Big sai」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
# v) Q0 v& l* B3 q原文链接：https://blog.csdn.net/qq_40693171/article/details/100716766) J6 Y# U6 y1 c- A4 ^, k3 t

6 e& Y4 z9 q! F
0 P! i. \! W/ K9 h- a* n' T