查看: 2616|回复: 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=[];
" L9 D4 b3 S! H4 r6 a       for(var j=0;j<aa;j++){% m9 f: o2 ]! ^$ N$ E/ F! o% j1 b
         tree[j]=-1;//初始值为09 }0 r' t$ [: m+ V' v4 n' c
      }
  j3 Z; ~; d* t8 M  j# M" e  S* u }  for(var i=0;i<aa*aa;i++){
; M8 {; m% o! A% C) |% [' V       isling=[];
# M; ~* t: q* P       for(var j=0;j<aa*aa;j++){
1 O4 [: d- X5 @& _$ [" t% z/ L, [          isling[j]=-1;//初始值为07 `. ?, ~5 i+ X3 D  O
      }: S8 t& a! T5 A5 a- U
}, d6 f4 K; O- d' ^- u2 ^6 z

% l+ S/ O8 b3 o& e1 d function drawChessBoard(){//绘画
7 e6 d# S, P; c: b% o       for(var i=0;i<aa+1;i++){
+ F  @7 D- X9 z6 R          context.strokeStyle='gray';//可选区域5 e2 O4 _& K4 Q6 V( D
         context.moveTo(15+i*30,15);//垂直方向画15根线，相距30px;
4 B) [: b. T* Y8 V; ~8 x; @, W& `0 G          context.lineTo(15+i*30,15+30*aa);" T2 u0 ^0 |+ O' e
         context.stroke();' {& H* q8 a' |0 s% r& K
         context.moveTo(15,15+i*30);//水平方向画15根线，相距30px;棋盘为14*14；& J# K' y: }6 M. g" n9 t) g
         context.lineTo(15+30*aa,15+i*30);
- U' H3 [# s3 Y" n0 ], o  S; I2 k          context.stroke();
. b/ P( Q- @4 ]- J       }
- Z5 g+ {% f; W' L# O }/ r" k  O4 p# l3 }
drawChessBoard();//绘制棋盘* ?0 P) v' |/ m6 p4 V

5 c' ~' J$ H, u4 x# M //    var mymap=new Array(36);2 A4 [/ |0 f. s
//    for(var i=0;i<36;i++)( e  A9 l( I# F% \0 B
//    {mymap=-1;}2 X) W1 }9 R. [2 ?8 Z

+ r: A9 X: F9 _( i7 R; u
! ?: E$ r7 F9 f' M' A; j: [1 Q/ q  </script>9 z7 g2 \. c! F9 e: B
</html>
( z% C+ A% o( Z5 s0 C2 q$ p
7 H* p' S8 {" X; e' R7 v; |0 z0 t  Y7 @9 `6 Z- q# t
实现效果
; y/ ]& L9 }' ~/ t

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

. j; Z6 e9 {0 c
. w* |: J1 o' }; X/ g& f; Z' E7 H
画迷宫; ~7 q% I2 p* X' U' G, s0 h  @: C

$ R% }+ @: R0 }( L1 I随机迷宫怎么生成？怎么搞？一脸懵逼。! Z$ }. `$ y* U: R& c
; o: X/ i2 i7 y  Y) H- v# g
因为我们想要迷宫，那么就需要这个迷宫出口和入口有连通路径，你可能压根不知道迷宫改怎么生成，用的什么算法。小声BB：用并查集(不相交集合)。; U3 D- ?- |" f& r
迷宫和不相交集合有什么联系呢？(规则)
& P5 X+ W; n$ ]3 s4 ^4 @; p0 f6 ]/ C7 `3 K3 `$ T* l* t- s
之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合)，它的主要功能是森林的合并，不联通的通过并查集能够快速将两个森林合并，并且能够快速查询两个节点是否在同一个森林中！- n8 e, q* o: g" {
而我们的随机迷宫：在每个方格都不联通的情况下，是一个棋盘方格，这也是它的初始状态。而这个节点可以跟邻居可能相连，也可能不相连。我们可以通过并查集实现。1 Z$ ~5 U: V3 G# l. Q+ D

* V! a0 _4 H' M$ T/ ?! p" {具体思路为：(主要理解并查集)0 M+ b& D9 Y, O

! e0 ~5 V& X! [& ?- `6 E, w1：定义好不想交集合的基本类和方法（search,union等）) r9 f; I, a- o( Q: z  `
2：数组初始化，每一个数组元素都是一个集合，值为-1
9 {- c$ F, j/ e# \1 e: p- n- t4 ?3：随机查找一个格子（一维数据要转换成二维，有点麻烦），在随机找一面墙（也就是找这个格子的上下左右），还要判断找的格子出没出界。
# p0 `  G4 Y5 f1 L8 v具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界" L* J. U- u  V/ ~, E
4：判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在，则重新找，如果不在，那么把墙挖去  Q) w! ^" p9 G5 @. b
5：把墙挖去有点繁琐，需要考虑奇偶判断它那种墙(上下还是左右，还要考虑位置)，然后擦掉。（根据数组转换成真实距离）。具体为找一个节点，根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。# P& ^/ S1 q0 \
6：最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙，但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据，并查集操作。二维是位置。要搞懂转化！3 J+ f6 r% j) a7 ?9 t( C$ l
注意：避免混淆，搞清数组的地址和逻辑矩阵位置。数组从0开始的，逻辑上你自己判断。别搞混淆！
/ ?# h$ W4 f2 w* C

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

: g0 {) o) w; d4 O/ E主要逻辑为：
" l) r, o& G% y2 ^! xwhile(search(0)!=search(aa*aa-1))//主要思路2 c. C8 S0 O1 y% Q8 |, M* A
{
" ]5 S- N2 \0 |& ^% H       var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
( M: f1 O4 z0 S  T5 B       var neihbour=getnei(num);/ f: ^  f, a3 f$ i3 y1 {; D
      if(search(num)==search(neihbour)){continue;}
3 i; _5 m% M" P5 h* [       else//不在一个上7 V" h* i6 D; t9 c: ]
      {+ \0 y5 U" h0 x: ^8 W1 _6 ]
         isling[num][neihbour]=1;isling[neihbour][num]=1;
. r! j# C/ f6 p8 v& u* O* D9 e6 ?          drawline(num,neihbour);//划线
- g4 E& T; b/ G% E% b* v4 `+ v          union(num,neihbour);9 q. N; U: ?: u% y# }
) l2 j" ]; f  m2 P5 q% W7 X
      }  \5 J- M- o1 C
}( s/ M" G: b6 r1 J* `

- z7 K6 p6 m# j6 Y3 L! j, z% V3 s/ w4 G# k# O$ i
那么在前面的代码为
, y+ ~. R" s8 R; F# M5 }% n<!DOCTYPE html>
$ c4 S: c: |; k/ N4 y0 a<html>$ R: }! D7 A5 @6 I- r! L
  <head>. _! q8 B) f# T3 u" S) D
<title>MyHtml.html</title> - Q9 I# i& _* V0 H  l/ j' r2 H
  </head>
* Y$ i- Z, t6 ]) E9 u5 Y0 L; ?) `7 H7 m  <body>
( y: {$ |7 ]6 s% Q, y  <canvas id="mycanvas" width="600px" height="600px"></canvas>
/ u  O, M6 h) m2 e  T
7 W' _0 a% C* k$ z/ O. r  </body>
$ V7 C# V# b1 E: ]' h. T3 b  <script type="text/javascript">
( L8 W& Y* k! e4 i; x//自行添加上面代码
9 r( y( Y3 e, ?! o //    var mymap=new Array(36);# u& f# q9 M. A7 I* O
//    for(var i=0;i<36;i++)! e6 ^9 o1 U5 `. S
//    {mymap=-1;}) m( N' j. R; A) C& l+ O
function getnei(a)//获得邻居号  random' k9 m6 `$ O* g) i, H! d
{
2 R: F1 G/ ?" h1 R; y       var x=parseInt(a/aa);//要精确成整数  T) O' L" t" Q  k
      var y=a%aa;: v& C% f& z0 i0 [& a
      var mynei=new Array();//储存邻居
! Y6 {' m) L/ G" c# S6 N# C2 ]       if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点' m2 ^0 ]! ]/ K& K
      if(x+1<14){mynei.push((x+1)*aa+y);}//下节点% D% C! s- p/ I( x2 k
      if(y+1<14){mynei.push(x*aa+y+1);}//有节点0 b, x* w0 K  J* R# W: _, j" L
      if(y-1>=0){mynei.push(x*aa+y-1);}//下节点6 W/ a6 t' ?6 Y. ]5 B% d
      var ran=parseInt(Math.random() * mynei.length );
1 w2 u! K8 M6 A       return mynei[ran];
. l  E/ L2 z% y* S4 Q
* N& A& {9 ^& Y/ | }
8 R8 S+ B% }% o# Z2 k function search(a)//找到根节点
0 z, }8 j! }6 D7 K {6 J: p8 N  A' M1 `$ r& k. f
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
; G5 E8 }% v% L$ Y" r       {& M) `# u; f( H" Z3 i6 _
         return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩
" l( n  L7 c9 |/ J8 c: h; ~       }" l" m  P+ A2 k4 C$ a
      else3 i9 |9 W% e' Z! }+ K: `! H  H
         return a;
2 m; b7 F0 Q% b- N1 X8 z }
9 O; w* J# r; v function value(a)//找到树的大小( @6 r( U7 X( J, ]. S2 p8 F; g6 H& Z
{
! e. J0 y& i8 X* e, E5 }. O* @# n       if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点3 ?1 y- g7 W+ G4 D# y: C+ {
      {
% N0 _) }; F- @6 z          return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩. t# E# y6 Q! `# J3 _3 W) X) R
      }
( X% [% n3 U2 ?* I4 }       else
+ W, |/ h* K# |9 B/ Z+ B/ P& z3 e          return -tree[parseInt(a/aa)][a%aa];
0 m/ x- v. D9 w1 `2 P# e- r }/ j8 u7 \* @: k' T8 v8 ]
function union(a,b)//合并
5 a. T: z& I7 ~  i- O  w {) j" x! X" e: w0 Q, r' ~6 ^. k
      var a1=search(a);//a根# V. X+ s& G# I' A6 {$ ~2 e6 E  q9 i
      var b1=search(b);//b根1 V3 [( m+ a8 K; W  \0 T9 @
      if(a1==b1){}5 |+ m/ a& T8 u- O  e
      else' x0 ?0 W9 ^3 }$ R; k
      {
$ y$ |+ w- z+ t) n/ u2 i* t8 W, ]6 g          if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数()，为了简单减少计算，不在调用value函数4 w/ d$ K9 N! s& R# y9 M: O5 }0 \
         {1 t* I  X" L% `* K" l6 I+ H! z: X
            tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加  注意是负数相加9 Q3 E+ S/ @, z
            tree[parseInt(b1/aa)][b1%aa]=a1;    //b树成为a树的子树，b的根b1直接指向a；8 J+ E7 p% ^( }( a, M
         }
5 F. f8 d8 g; L8 F$ G! D2 E          else, x) u1 v) D) X$ r
         {
% ?% S1 O) g; a9 d% Q6 X# E3 V             tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];
, y" O  \/ j; k4 y             tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树: J$ L3 G% S& t- F: }
         }% x; z% ~( x, O( C
      }. Z6 y6 I( R5 G2 N! Z
}$ Z+ K) F1 L7 _/ u# x! q

! ~: e& S' i& I function drawline(a,b)//划线，要判断是上下还是左右
  S# P# R, Q) g: J) I8 e" S {" h& X2 d2 p! ^7 D' i

$ z# ^' V6 u8 X. r' z! |       var x1=parseInt(a/aa);
( |4 [5 D, u7 M- J( }, s       var y1=a%aa;
- z% x6 l' V' c9 [+ ?       var x2=parseInt(b/aa);4 x. _- d) I/ W! v
      var y2=b%aa;       4 s# _# q' W( z  I6 {
      var x3=(x1+x2)/2;. {# F3 ^2 S/ X; l% P6 p
      var y3=(y1+y2)/2;# c! Y% S( M, f/ b# Z
      if(x1-x2==1||x1-x2==-1)//左右方向的点  需要上下划线
2 k8 w% b% ^8 N! W( o- P       {
( _" N7 ~" q) l# X7 X9 T  s* P          //alert(x1);
6 t6 q- x0 w1 D1 q- ?) j          //  context.beginPath();+ R1 x* S* ^+ T( X4 K
         context.strokeStyle = 'white';3 s! o4 V7 z2 Q
         // context.moveTo(30+x3*30,y3*30+15);//! A4 N7 H8 b5 `: {( r3 A/ [! O
         // context.lineTo(30+x3*30,y3*30+45);
7 Y0 W& v. m$ |. [          context.clearRect(29+x3*30, y3*30+16,2,28);
' o& j% Y6 V$ f! c4 O) i3 {& T" W          // context.stroke();
& g% z. H/ T4 C$ X8 X       }
0 p  W/ S; w! r5 y, X" I       else! [% q7 a* T1 C/ R; F* S, Q) i
      {
9 e/ @, z- ?# l( |8 [, g0 {2 }) G          // context.beginPath();8 N" g. z) i4 p2 D
         context.strokeStyle = 'white';
' Q' ]6 q  X- V) z0 `- b          //  context.moveTo(x3*30+15,30+y3*30);//
: B* F4 C5 K8 c% q% U9 @          // context.lineTo(45+x3*30,30+y3*30);
2 k  D: S% _, C  n1 @0 C% K* a; ?          context.clearRect(x3*30+16, 29+y3*30,28,2);1 R5 |  _  `0 ]6 j, [6 \' P
         //    context.stroke();
. z4 K; e8 w* a) U7 {6 a       }3 j: }+ V* A, Y! H, K- y
}. D( @4 D; ?. R
3 N* M( B. S' V0 ]3 M2 z2 [) h3 V
while(search(0)!=search(aa*aa-1))//主要思路
3 z, c8 Z. ?2 |/ ? {
3 D5 |! U, [) U2 }% A: _& W       var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数; `& N9 ]! Y; l# N: g
      var neihbour=getnei(num);
, H" v# S) u' @* r# a% ]       if(search(num)==search(neihbour)){continue;}( }1 T  {" x# @3 k5 K7 I, {* p& {. k
      else//不在一个上
% V6 ~; z/ E4 {# N5 a# v' H2 x, |, ^# c       {/ }4 g+ O8 ~8 U2 V4 E
         isling[num][neihbour]=1;isling[neihbour][num]=1;
, m9 G) m7 X9 ?: |( P8 m9 G* G          drawline(num,neihbour);//划线
3 S8 b1 d7 P$ Q) s" q1 ~) j- X          union(num,neihbour);" s* C* o) y7 B* R3 k8 }. B

3 k3 ]: z- Y5 `! I       }
9 [/ I3 e- U' `+ Q5 @7 f }
7 F  B4 @$ P9 a" Q8 f6 m  </script>
' t, q4 p8 e. l6 b! E8 C9 d</html>. q; ?$ \" G+ \) p6 n/ h
9 ~7 l2 a+ y% \

# D( @6 P. ^6 c. B3 J3 [) j; K实现效果：$ n/ w- ]7 P" V5 z0 \6 y  ^8 `
7 P8 z; p4 v$ m) t) M

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

) i+ i1 S" ]0 s! i
7 D, f  J. U' _4 \/ M% O

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

, U5 G' E& r8 L# s
方块移动" T$ h" `+ `' `; O: Z9 S

* W, H5 A. |# W1 H这部分我采用的方法不是动态真的移动，而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉，在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除，可以根据像素大小精准擦除。
- ]& a  O5 {. `+ P- r: _0 ~. v
/ p5 V" X: Z3 e6 q5 h) B- g( X另外，再移动中要注意不能穿墙、越界。那么怎么判断呢？很好办，我们再前面会判断两个格子是否联通，如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组)( x! p: H& a% ^

* t* @5 F1 |. z% k; w* L0 O& d另外，事件的监听上下左右查一查就可以得到，添加按钮对一些事件监听，这些不是最主要的。
0 l. ?1 T/ t) J8 M3 M, x) }6 e' H* ~5 V1 c3 G1 s1 z& g
为了丰富游戏可玩性，将方法封装，可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外，如果写成动态存库那就更好了。
) j- v0 {5 ?. [$ |4 |& N

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

1 {' ~  f% i4 Z4 D/ }2 M0 ~- O" X, m- j- m. h

3 u8 f5 ?1 r5 s5 W————————————————
$ ^4 y# B) J2 W' b) u/ c版权声明：本文为CSDN博主「Big sai」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
3 V+ e% j: T$ x6 e原文链接：https://blog.csdn.net/qq_40693171/article/details/100716766
  S" c% M  t: m3 a* p% D
  e9 ?5 Z) Q  ^% z6 _, L3 @
  M/ ?* X, J8 S' v, ?