查看: 2551|回复: 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=[];
# Z2 q6 q  S, P- y# r) ~* c       for(var j=0;j<aa;j++){
0 q& Q) {  j* x  @1 h3 X          tree[j]=-1;//初始值为0
0 t: P( A3 q  _6 S( P  V6 b; O       }
6 j0 h; a+ c+ H# x2 Q }  for(var i=0;i<aa*aa;i++){
' U; V+ Q- \1 V# f( r' d       isling=[];
0 l" h1 d1 G  M" T; N3 q       for(var j=0;j<aa*aa;j++){- \0 M* C8 ?- H* K, L
         isling[j]=-1;//初始值为0- ?2 z; p1 q& L2 h, l2 v6 j) D- B
      }
3 h* C6 ]+ n2 G: R }
+ b; F: i6 G; S
# s7 c  H/ \& F- W; I: M, c4 J  g function drawChessBoard(){//绘画' J& z2 f" ^; v; X8 Y
      for(var i=0;i<aa+1;i++){( C0 {# I. v/ Y  v
         context.strokeStyle='gray';//可选区域7 v# \' ^9 D: U
         context.moveTo(15+i*30,15);//垂直方向画15根线，相距30px;
. s1 q- i' S1 A2 h          context.lineTo(15+i*30,15+30*aa);
$ e2 m/ R  {7 g9 q/ P' W8 H9 x          context.stroke();
' [# m. ~6 k. }# W$ N0 K          context.moveTo(15,15+i*30);//水平方向画15根线，相距30px;棋盘为14*14；
. Q% C3 O0 [1 ~$ k          context.lineTo(15+30*aa,15+i*30);
& F# Y$ T* s/ s/ y          context.stroke();
* P" r* m  m. j6 I% \6 t& Y& p; _       }
: g3 H) u9 ?* t) `6 `! w% ] }
; N0 Q* ]! K3 |  d( G. @0 M drawChessBoard();//绘制棋盘$ }# H& Y/ w: H$ N' k1 M, O

" x6 W* d, y' J; }- F% T  p  w //    var mymap=new Array(36);
/ m0 d. Q! z( Y- }% o //    for(var i=0;i<36;i++)
4 j! {0 t3 Q  L& J( S% j //    {mymap=-1;}
2 @9 y% E4 b# f$ p: R
: S- T$ B" @; m% |+ S4 y5 E( r  E7 ?& t5 C/ Z/ T. M/ R" }
  </script>
* o& {* D0 C  F, @</html>
& k4 q* c* v, {5 F5 M: ]3 x
7 j2 g) J. S; N3 b" m( V
" P( I4 }" F, P0 g; N/ K% p$ b实现效果
& V( o( a+ C/ K% G

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

  B1 t. f& O+ P
  G" P/ B/ e0 r5 ?! d+ I
画迷宫
, @9 z0 j9 `" p; ?1 B# _/ r' t0 k1 w0 N0 `: f1 @. _6 y9 q1 M
随机迷宫怎么生成？怎么搞？一脸懵逼。
; ?- J3 j( i9 M' I+ G  `% ^; l+ k/ F
& _# b6 x+ f5 L4 Z! t因为我们想要迷宫，那么就需要这个迷宫出口和入口有连通路径，你可能压根不知道迷宫改怎么生成，用的什么算法。小声BB：用并查集(不相交集合)。% _" T" L8 e" F" ]) V: F9 B% q& P
迷宫和不相交集合有什么联系呢？(规则)- t) Z" T/ N, x# v

- [2 J2 |# O" Z之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合)，它的主要功能是森林的合并，不联通的通过并查集能够快速将两个森林合并，并且能够快速查询两个节点是否在同一个森林中！
0 p: n1 a% ~5 G. s0 d而我们的随机迷宫：在每个方格都不联通的情况下，是一个棋盘方格，这也是它的初始状态。而这个节点可以跟邻居可能相连，也可能不相连。我们可以通过并查集实现。
+ ^! a" j6 W! k; K. m
1 F/ O$ D% m0 F/ w. p" a具体思路为：(主要理解并查集)! |% B; Q4 @8 f- S* m
& y5 w* s2 W3 t4 n; T+ Y9 F
1：定义好不想交集合的基本类和方法（search,union等）
3 [2 F3 m, r- j) n% l" f6 D1 i2：数组初始化，每一个数组元素都是一个集合，值为-1
3 ~! @% ^3 e  s2 c3：随机查找一个格子（一维数据要转换成二维，有点麻烦），在随机找一面墙（也就是找这个格子的上下左右），还要判断找的格子出没出界。
8 ~1 o# D" t  F. {9 [/ R具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界
3 o3 m7 }2 z) i$ u9 z4：判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在，则重新找，如果不在，那么把墙挖去
( e; P+ X4 v( O% |5：把墙挖去有点繁琐，需要考虑奇偶判断它那种墙(上下还是左右，还要考虑位置)，然后擦掉。（根据数组转换成真实距离）。具体为找一个节点，根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。
! q- _2 @$ D& _) O4 p; d' X! ^  ?6：最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙，但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据，并查集操作。二维是位置。要搞懂转化！3 f: h+ a. W! T7 P) n
注意：避免混淆，搞清数组的地址和逻辑矩阵位置。数组从0开始的，逻辑上你自己判断。别搞混淆！
- `, R. h9 A1 z* l  W

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

$ S- _: ^& A' F6 R/ T& q
主要逻辑为：+ v, f$ w' e! C& X9 Z/ ]
while(search(0)!=search(aa*aa-1))//主要思路, j0 X8 H+ S) [& s- ~6 Q
{
8 U) @; A2 g" r) g       var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
% j+ n! p9 k9 }7 B: p5 ^       var neihbour=getnei(num);
8 ?& w  D: o# g6 F4 M' w       if(search(num)==search(neihbour)){continue;}$ y/ \  k" C( }+ P+ I# P8 W
      else//不在一个上
6 {3 i2 a$ K. D! J) ?6 B" @       {5 m! g; h  ^' C8 Q: k
         isling[num][neihbour]=1;isling[neihbour][num]=1;0 m! C; I/ D  H. q0 n) }
         drawline(num,neihbour);//划线
* B: `' N+ |+ N" z- E( U          union(num,neihbour);% W& H2 V! u$ F( k& Z* j4 t( ^/ l' B
3 h8 E2 c9 Y% J6 T
      }4 p& x) E3 ]3 n5 z2 h2 U4 H
}
' D. q* Y4 {2 D0 w+ u; t8 k" s- `) `' w7 J4 u1 F5 `$ r

0 T+ _5 ]  p+ }  }! E那么在前面的代码为. ^3 w- N) A! w1 R, M
<!DOCTYPE html>$ v8 ~1 K4 _) v9 ^6 ?" {
<html>' B4 S6 F$ d* f7 x8 h/ r: {
  <head>* ^4 @& V9 o- T3 \, R9 Q0 ]
<title>MyHtml.html</title>
4 ?  Q9 J! ^: X# w  </head> + q3 R) x8 F- ]0 V% P0 y
  <body>
) P' g0 }/ f, u% C  <canvas id="mycanvas" width="600px" height="600px"></canvas>
7 y$ j  x$ c" _; Q" p: E0 D: t% R0 f2 ^
  </body>3 ~: \$ x3 {( T- z4 T
  <script type="text/javascript">4 ]) Y& h: x$ Z# W) O
//自行添加上面代码! ?  [5 u( b9 v9 D
//    var mymap=new Array(36);
* \& }2 J' ^& n! x //    for(var i=0;i<36;i++). D% U! g9 O* B6 ^9 o+ E. E
//    {mymap=-1;}
3 F  U- s3 A  l) s7 ] function getnei(a)//获得邻居号  random
, R/ A/ S* b6 D' s7 k( W {: E! L, Q8 k: e1 w( a; K: D+ v3 J
      var x=parseInt(a/aa);//要精确成整数; g- l5 {0 G0 g9 X, }, O* a6 n* M; r
      var y=a%aa;
6 _1 P8 }9 e' H: z! a/ [- g       var mynei=new Array();//储存邻居% f7 X) g1 }8 u
      if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点
4 M! c9 Y% ?6 i' M+ e. U       if(x+1<14){mynei.push((x+1)*aa+y);}//下节点! y' |- J, k: m# [% s
      if(y+1<14){mynei.push(x*aa+y+1);}//有节点
) V% f- |+ O  Z  V       if(y-1>=0){mynei.push(x*aa+y-1);}//下节点8 y, S8 z+ H. u$ u
      var ran=parseInt(Math.random() * mynei.length );
' D1 J7 {; O4 w7 F7 T, U, V       return mynei[ran];2 b, d9 d2 i; i( p; v  |1 w

8 r0 P% V" |' k0 b  K' Z5 ? }* P( z1 Y3 |# p8 q: ^# o: d
function search(a)//找到根节点" B8 l9 B0 r% i
{
( y% ]; M# J% P& p- x4 Y7 o       if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
+ d' S, l5 O% I. m. P8 K       {
5 [" ~# b7 K& c3 Y8 C/ A7 _          return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩, L5 J; g% H8 Y8 m. T6 j
      }
0 c1 o3 w& M3 N       else, d' n% N' N  o: t: J; I
         return a;) D  ^, }2 d8 W( Z0 N8 P, g
}, d' ~# F- x( d4 l
function value(a)//找到树的大小& I( G' L  k4 ?5 K; i
{
" ]+ o* z2 _/ z* l: w. `4 @       if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
1 F: e2 X% V4 ^       {: v0 L% g+ g7 N1 S
         return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩( G" S  z7 u( D2 M9 o9 U; k! S3 V
      }
' x. u3 u: @' O7 P9 o% z; `       else* |: u, d% X2 s6 \2 e+ _$ C) b
         return -tree[parseInt(a/aa)][a%aa];( n3 h6 u6 }: o( P
}
0 d/ W& m2 M  A5 S function union(a,b)//合并. s) x: r/ L6 W
{
, }$ x$ o3 y+ P) o( v# ^4 v& [       var a1=search(a);//a根0 `+ k0 R& P& b' K3 D9 l
      var b1=search(b);//b根. C+ \# L. u& {5 G" [
      if(a1==b1){}
9 A( g: `( D# Y+ ]0 H- V5 p, ^       else  s2 k6 O4 t- X
      {& M7 Y" w% i) h$ V
         if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数()，为了简单减少计算，不在调用value函数7 d6 Q1 _. K  X* n3 o5 q1 L6 j
         {: s% u' r+ H% y* W) O" H5 d8 \
            tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加  注意是负数相加) a1 G+ C0 A; |* d! G
            tree[parseInt(b1/aa)][b1%aa]=a1;    //b树成为a树的子树，b的根b1直接指向a；4 k5 h% p! A7 O/ i
         }& a5 m6 P( z  c; q- G
         else
/ m6 b+ a! O. ]          {
) S( m0 {+ J. v1 ~6 S             tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];
9 E6 n# N7 ?- G1 h. ~) H             tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树
* u0 Q8 b! F! v; C/ z! \          }- [( E& b6 S' B3 c; q+ y
      }9 d6 G- a* t) Q* x* |1 t
}
0 c1 u/ t4 {# X0 i8 H, c7 Z3 _
. G6 m! l  [( M1 O' [ function drawline(a,b)//划线，要判断是上下还是左右8 P) ^/ ]4 v) _0 h0 ]" C1 B6 o: }# P
{0 C0 l* D, w  |7 _4 \- x' J
5 c  B7 ?" u8 ^- T
      var x1=parseInt(a/aa);
% @/ Q5 {  b; w; f( o       var y1=a%aa;( u/ P# {) L" p: L- j4 D0 l
      var x2=parseInt(b/aa);
' f2 p5 a0 H* _; L( Y' ]) Z       var y2=b%aa;
6 G6 b0 ~9 f: b: ?       var x3=(x1+x2)/2;: v. R' g, r8 ^1 P) {* n
      var y3=(y1+y2)/2;
5 ?* _, r0 u5 `4 i1 z9 {- Z       if(x1-x2==1||x1-x2==-1)//左右方向的点  需要上下划线8 g1 K+ _/ S' X" w& ~
      {
; e* g& F% o7 ^6 ]7 t) o          //alert(x1);2 A* h2 {5 t- L, f
         //  context.beginPath();# w2 p4 \2 f1 E2 J) ]% Z/ F
         context.strokeStyle = 'white';
' J/ x* }% A$ e$ Y' v3 E  g          // context.moveTo(30+x3*30,y3*30+15);//, E. k6 B) l/ E2 g& y( p6 p
         // context.lineTo(30+x3*30,y3*30+45);1 x: {% o. i& R3 |
         context.clearRect(29+x3*30, y3*30+16,2,28);0 |- n- L' e$ C/ N. l, R4 P9 d' _
         // context.stroke();# g5 w& F  u5 P1 b4 o
      }$ E9 m" u) H# w$ Q" c1 ^+ Y1 Z
      else
. V) q& U- `" _6 i: w2 f' m+ C       {
% u1 o4 y4 i% X( J3 L          // context.beginPath();' l* d# p2 k2 j3 `, D$ E3 C) F6 c
         context.strokeStyle = 'white';
( ~0 Z3 S% I' H( {8 p4 k$ L          //  context.moveTo(x3*30+15,30+y3*30);//
. a" i, f2 S* [1 [2 F' n9 r          // context.lineTo(45+x3*30,30+y3*30);
0 G9 A0 \$ y; K( n- R          context.clearRect(x3*30+16, 29+y3*30,28,2);
% ]& U0 I& I7 d          //    context.stroke();
/ ]. T, Z% q$ o       }
5 l+ A8 g$ q/ L. o  t }7 G8 V3 C7 Y9 r# I' R. @
4 a! \9 t( d9 S1 S* y! q8 P
while(search(0)!=search(aa*aa-1))//主要思路
: \6 w" \( b: L' \ {/ T9 \! f/ I  P  K. Y
      var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数/ P2 t; O' R3 I1 n$ a
      var neihbour=getnei(num);. w3 [4 [& v* M5 c* m4 J4 h% o. Z
      if(search(num)==search(neihbour)){continue;}
* F3 v5 O! v7 A; o$ g$ |; t       else//不在一个上
. [$ D9 b/ P  U       {
2 d; ~, R! `* ]$ Z' g3 m          isling[num][neihbour]=1;isling[neihbour][num]=1;
( }% Q1 a+ M2 a$ H& U          drawline(num,neihbour);//划线% ]4 |$ b; f/ ^" R
         union(num,neihbour);
1 f) a4 R% L/ W1 _5 P% b# R4 d8 U: K" p4 z! m3 _
      }
" j0 D) [$ ^1 O: n% x/ t& @ }9 n: Y, m/ o+ `1 A3 @4 W9 X
  </script>3 [" x3 W7 }6 c( I( E. w
</html>
; n! s; R$ u3 {  V& l% N8 O" c5 |. Z5 v. j- b: Z! g

6 f- _4 C7 z9 e# b+ g- O, J+ m2 \实现效果：! X8 \2 V# ?6 P1 O* W# w
9 F2 g! Q4 S# O# L

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

- L$ s  U+ \7 _) a0 G
2 }% G0 @- E% t# Y0 X6 M0 A7 V6 k5 u

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

) w- M- L% ?$ B方块移动
% Z! _( ~1 t. {, |5 H$ A: O4 y1 n9 N/ X# G  v4 ~
这部分我采用的方法不是动态真的移动，而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉，在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除，可以根据像素大小精准擦除。
+ Y7 p1 @, G% g5 o
* H2 y3 j4 {) Z- l$ y另外，再移动中要注意不能穿墙、越界。那么怎么判断呢？很好办，我们再前面会判断两个格子是否联通，如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组)
& Q1 X; G8 z/ M# q# c: N9 l& b: ^5 n
另外，事件的监听上下左右查一查就可以得到，添加按钮对一些事件监听，这些不是最主要的。
3 r0 y7 f- f/ a) n/ \1 r. ?0 b! f1 \: u
为了丰富游戏可玩性，将方法封装，可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外，如果写成动态存库那就更好了。4 m5 i% P# I# g/ {! {% T, o0 N- p

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

& X# N9 H+ |: d# j! `+ C8 r- c8 `
4 w7 x+ R# V! \$ s' E
5 _: I' }6 X" }" i$ G- t' c
————————————————+ g: J% ^/ h, `0 t9 o- `+ {" Y& Y
版权声明：本文为CSDN博主「Big sai」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。0 w: C% }% c* d7 B
原文链接：https://blog.csdn.net/qq_40693171/article/details/100716766. a+ n4 J5 z; d6 K# H
9 `" [: K$ E; M2 l' P# h
# R8 ?+ A2 T$ z; |  t