查看: 2554|回复: 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=[];
; \1 E5 q/ E+ m* V7 U       for(var j=0;j<aa;j++){/ B4 f" _) P- T8 K& g% w) E3 B
         tree[j]=-1;//初始值为0
      }+ E: f/ U6 @3 j' w- t& ~9 o
}  for(var i=0;i<aa*aa;i++){
- V+ V" t$ q  P% }- P       isling=[];
9 O: f5 o% j+ z  d8 b; w       for(var j=0;j<aa*aa;j++){8 Z) n2 K3 [- l# G' p7 y
         isling[j]=-1;//初始值为05 C7 w, s, \! Z: _
      }& N$ o; a5 d. s" m8 D. k
}: _. a/ i, t9 s2 D& D: L
3 B; {$ \: G3 w7 o+ e$ M2 \7 n
function drawChessBoard(){//绘画
& ]4 \' {  y3 S& G       for(var i=0;i<aa+1;i++){# j- K/ C  Z- v) N* M
         context.strokeStyle='gray';//可选区域
- q3 A: d; `# C" q! B/ G          context.moveTo(15+i*30,15);//垂直方向画15根线，相距30px;
3 K8 t  S  `+ Z, n' m6 J          context.lineTo(15+i*30,15+30*aa);
6 c3 c/ F! f. e4 O9 Q* Z6 b          context.stroke();
' B  ?0 c6 k* R6 a          context.moveTo(15,15+i*30);//水平方向画15根线，相距30px;棋盘为14*14；/ `& O3 J+ d& V+ L& _
         context.lineTo(15+30*aa,15+i*30);( W5 t4 H  B5 P& y
         context.stroke();0 h" {* I$ t, q, P# S
      }
) \$ h) N% }4 h }
; L+ j. ?7 N4 Z% B' f" k drawChessBoard();//绘制棋盘
6 U# o) ~$ x: @/ Y2 ]) a/ `* z, z% f3 }. X3 S2 k+ k
//    var mymap=new Array(36);7 G6 L3 X$ x5 ?" L5 Y
//    for(var i=0;i<36;i++)3 _; t, L: Y3 |& u( J
//    {mymap=-1;}& p  o7 N1 d1 L8 H! c0 [7 S8 p4 i
" |& S) @* M1 N  a" n$ n

% |; w& @9 ^; Q: y& @  </script>) s; d3 ], C2 E
</html>/ W! q# ~7 @& Q
9 g( A: L) _& P6 p% {; M
8 w4 \! S# U$ H4 T8 z
实现效果
- O9 `8 Q7 j& d, |) Z% V% F

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

+ d8 }; O* V$ S8 [9 U% x" R# M" h

% i9 a0 W0 j7 D& Q5 t7 w! f# A5 ?画迷宫
/ P9 W5 ~/ i/ I+ p7 |: ]8 h; ]: h4 G7 ~4 [4 T* q; _  g! T  C
随机迷宫怎么生成？怎么搞？一脸懵逼。
+ Z) S: s% J) u8 T) ~9 X
( n( {8 A9 C% g# m2 l& h因为我们想要迷宫，那么就需要这个迷宫出口和入口有连通路径，你可能压根不知道迷宫改怎么生成，用的什么算法。小声BB：用并查集(不相交集合)。
2 O$ F0 `  y7 A  @迷宫和不相交集合有什么联系呢？(规则)
  V) s! L8 c/ M; `! ?% Z4 O3 b( U! S
之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合)，它的主要功能是森林的合并，不联通的通过并查集能够快速将两个森林合并，并且能够快速查询两个节点是否在同一个森林中！( \5 `7 O* G3 g& I
而我们的随机迷宫：在每个方格都不联通的情况下，是一个棋盘方格，这也是它的初始状态。而这个节点可以跟邻居可能相连，也可能不相连。我们可以通过并查集实现。5 }+ J8 s! V0 |8 c' [$ P

+ n  U: z9 c, r3 U& x具体思路为：(主要理解并查集)
9 K3 x% r- K3 T# R% ]. {8 f
; e* y8 d2 e. m, h: Z% J+ i1：定义好不想交集合的基本类和方法（search,union等）
' \# N0 g5 A+ B2：数组初始化，每一个数组元素都是一个集合，值为-1; m0 z# W& Z. ?/ H. ^. q/ D& Z/ P
3：随机查找一个格子（一维数据要转换成二维，有点麻烦），在随机找一面墙（也就是找这个格子的上下左右），还要判断找的格子出没出界。5 r5 c8 e3 r9 L
具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界
6 b1 W& m+ q8 B8 I& u7 e4：判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在，则重新找，如果不在，那么把墙挖去
* t( z' f- G3 H; d5：把墙挖去有点繁琐，需要考虑奇偶判断它那种墙(上下还是左右，还要考虑位置)，然后擦掉。（根据数组转换成真实距离）。具体为找一个节点，根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。
, `! j1 [. W$ n8 S) |. f7 D6：最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙，但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据，并查集操作。二维是位置。要搞懂转化！
2 D  M; n' }  i- Q) Y6 R0 Z注意：避免混淆，搞清数组的地址和逻辑矩阵位置。数组从0开始的，逻辑上你自己判断。别搞混淆！2 j& H1 s2 X+ h- i$ O/ S. ]

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

" u7 u4 b9 l2 n, N/ V+ D2 O主要逻辑为：
- Z! I$ |: |" f; g) Hwhile(search(0)!=search(aa*aa-1))//主要思路& N' }9 t' M5 t3 Q$ F
{/ c8 A# E* n* G2 l3 U1 `" A
      var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
% s: h- H2 c; A       var neihbour=getnei(num);+ l$ c0 J+ I' _7 y- K3 ~: @
      if(search(num)==search(neihbour)){continue;}. b" h' U8 r+ `1 U
      else//不在一个上
/ s) j: R: n5 e1 V6 F, D9 F       {: `- @+ g6 m1 F$ p2 X( M* }+ C
         isling[num][neihbour]=1;isling[neihbour][num]=1;
9 {9 B" F0 H4 @& p( e7 v          drawline(num,neihbour);//划线: ?% R; L( ?8 P3 J
         union(num,neihbour);. {0 C$ g2 B8 j/ f& M
& V6 o- l( `7 r: ?* Z7 \5 K( Q
      }7 x, ^; C3 _1 ?0 N7 N
}
! u! G, E6 p; ^' K, L, w, k& t  a  k6 @5 u

% G9 D* v5 Y" ^那么在前面的代码为8 T8 K( Q( u; R. C
<!DOCTYPE html>
1 s+ o: C* }/ a4 y# s9 o<html>5 i6 d9 ]0 M% {# e
  <head>! t$ i. P, y+ v
<title>MyHtml.html</title> ; f+ a" h' P! l% u
  </head> 7 _! z5 s+ Q0 ^- j7 a- E
  <body>
3 ]7 _7 |1 S4 T5 a* z; J  |  <canvas id="mycanvas" width="600px" height="600px"></canvas>
4 W2 e' `9 x2 I% g& n
; h* l7 q' W9 C: i4 S2 ?# t( [- M  </body>
: b* O# _( N' d5 d7 x  <script type="text/javascript">6 O5 y; N$ V# L! m
//自行添加上面代码4 l9 A7 N' p9 v. f
//    var mymap=new Array(36);
" `! [# m8 y! B8 C+ A //    for(var i=0;i<36;i++)
, E7 Y% ?2 l  ?% o //    {mymap=-1;}
, h( O* z# Y# N7 q4 W. ^ function getnei(a)//获得邻居号  random: S, V, R% R' k0 _
{" P; r0 ~: V, _3 N7 \
      var x=parseInt(a/aa);//要精确成整数+ F3 d1 ^3 k: }
      var y=a%aa;( |1 N) b8 S" ?' `3 E# t
      var mynei=new Array();//储存邻居
# K/ e. L* j6 S3 D& n0 C6 A0 D$ b       if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点
8 c# B7 Z3 ~- p6 s, t# D       if(x+1<14){mynei.push((x+1)*aa+y);}//下节点) q3 X: |( r  I$ D
      if(y+1<14){mynei.push(x*aa+y+1);}//有节点- V: v$ I4 Z$ y: u
      if(y-1>=0){mynei.push(x*aa+y-1);}//下节点+ P  ~' I2 m! b0 H
      var ran=parseInt(Math.random() * mynei.length );1 n5 F% `4 \$ _) D2 c7 e$ e
      return mynei[ran];( k8 c2 b) A/ ^( q% r9 B6 a
. K2 `) W* {+ t  Q$ j1 S2 z
}
( M) w4 {0 g5 Z function search(a)//找到根节点
9 x( @! U: v0 L, v8 y  I$ { {7 H4 U+ Q# n. R7 }. k$ Z$ p
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
: b/ q  H3 V3 }3 g% k$ c7 b3 O       {8 l* n* ^% H9 h6 u3 I; H8 r
         return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩
% l, `% Z4 g( @5 |       }5 N* K4 L! V  M8 S# P
      else: ^2 v4 j! \5 l( p; I8 Z8 }
         return a;( w* G) v$ c( r1 ~
}! t) O; n$ C; r
function value(a)//找到树的大小' {+ M: Q- O" d3 l* c
{/ ?/ F+ j7 Q5 b3 R
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
' S/ S3 r2 |8 V       {
+ {- R. H# L* F  N) b+ R, y9 q$ z          return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩+ W# ?* D% [+ T- E  i: v( g
      }9 t2 x; d( O# U% L8 Y, F
      else
2 H7 E& s3 v. {  `1 Z          return -tree[parseInt(a/aa)][a%aa];
, U2 M/ a# p, F. G( G" n8 W$ c }
* R+ H5 i  ~4 t+ \% ?2 M" d function union(a,b)//合并1 a3 T+ K" C5 z# B. v4 i# T) t
{
5 \: L: [- ?! k4 L, l' m# q       var a1=search(a);//a根2 E" }, P' E% y& ?  @: }2 R
      var b1=search(b);//b根
( M8 ]1 J7 M" @$ |$ t5 o3 y       if(a1==b1){}4 ?' E/ ^6 W  k- W
      else' p) q% w7 r+ A: \; m/ t, R
      {$ M* [8 J( A, N. I
         if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数()，为了简单减少计算，不在调用value函数
! T& `* R* f5 p7 @" ~          {4 \9 i( Q7 z4 k3 A: L. k- K% e2 V+ M
            tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加  注意是负数相加
' i7 |" M" S: f4 {7 h# Q2 p4 J             tree[parseInt(b1/aa)][b1%aa]=a1;    //b树成为a树的子树，b的根b1直接指向a；
) H+ H% W2 O' g- g% p          }* k; k: d0 u9 D* i: ^4 \
         else
# T2 H1 x* V$ F  u$ |; x' M          {
# c7 {/ o8 ?6 a( `" Y3 X, n9 E5 p: u" P             tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];
. L$ m7 q6 j- E0 e* d             tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树
) X2 N6 T( S% b% m- M1 I* d; n          }/ Q" ~' I, C* F5 a$ A' |
      }
7 `9 k' i+ p$ @" p1 V/ D }
: I5 u. ?0 I7 f3 q8 V
! V( k6 g* m: Z function drawline(a,b)//划线，要判断是上下还是左右* Q0 _# i# G* r% k
{
0 ]% W3 j& s9 C5 y" Z$ x/ E, z% l8 |
      var x1=parseInt(a/aa);9 C0 i4 j! r1 E
      var y1=a%aa;
/ c8 ~# \2 \- _' [2 h6 V  h       var x2=parseInt(b/aa);/ ^8 ]- J, I- j
      var y2=b%aa;
/ i4 h9 a7 L. n3 n       var x3=(x1+x2)/2;% E. P9 U& N. ^) f/ [7 m
      var y3=(y1+y2)/2;+ m6 g( r$ \- v8 R- c( W/ d
      if(x1-x2==1||x1-x2==-1)//左右方向的点  需要上下划线& z1 A  B: A9 H! _& ]+ W; o
      {
/ a. H/ m  l3 c4 ]0 I' g          //alert(x1);0 r. s2 J* ^( b1 k
         //  context.beginPath();  _* Z! h. |, i! t
         context.strokeStyle = 'white';3 d9 _, W4 l8 p0 u
         // context.moveTo(30+x3*30,y3*30+15);//$ k% \6 _: l6 e, k8 e  V" j
         // context.lineTo(30+x3*30,y3*30+45);" [6 B. Q+ v0 e" {7 j% i/ O5 y" F
         context.clearRect(29+x3*30, y3*30+16,2,28);0 p- v3 S3 W9 o5 c7 U
         // context.stroke();
1 A# h5 C5 @& Y       }2 w5 ^' t0 Q' h% p& z1 k
      else* v+ M- m9 {& ]6 k: g
      {
5 ]3 }& i3 R# \1 i- J4 r          // context.beginPath();
% x, ^. F0 p$ D; [. f          context.strokeStyle = 'white';3 \& e5 a: h  O6 {) b
         //  context.moveTo(x3*30+15,30+y3*30);//
         // context.lineTo(45+x3*30,30+y3*30);
6 R8 E, r1 E) l( K2 B/ f          context.clearRect(x3*30+16, 29+y3*30,28,2);
& E/ u6 r9 ]2 m3 M7 U          //    context.stroke();
0 P* |# b$ I' J- t       }
+ t' N3 F( u. u) ^ }
8 e3 [2 {3 N8 r9 a: b0 B3 e! A( J, |* g+ G) w' H& n
while(search(0)!=search(aa*aa-1))//主要思路
; w/ r9 I6 y* O! X2 @3 K {
6 r) R9 X, p+ \' C. ~- N       var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
+ k  L; t7 t( l; e: s# |       var neihbour=getnei(num);6 _: F3 Y5 G* Q- O7 C* [
      if(search(num)==search(neihbour)){continue;}
0 D! Z# s' k) d$ J# [       else//不在一个上
" Q5 d" j, c& J, p1 i4 \$ B       {
5 X0 v* _! X2 r  t          isling[num][neihbour]=1;isling[neihbour][num]=1;
+ O/ u; G$ m: g1 F. V- ]          drawline(num,neihbour);//划线
1 N" F- |4 g1 @$ @          union(num,neihbour);0 A, T0 t/ z; L1 a. g
6 _: f. t6 M$ ]! K; w
      }6 J. \$ g3 j* ~8 e* @) v
}3 b9 p7 a( D1 `2 F' w& Y/ P! R
  </script>
* A# F* v0 U6 I% m) e</html>% D" t/ v/ n; A9 [) V* ~1 I
; P& s  f" z2 r& |1 x$ ?1 Q

3 c/ [" t- O+ H; S- l, q5 _2 ?# F5 ~- E实现效果：0 F3 U7 Y6 R* N' k0 A( B

% ~) L5 C+ Z/ p2 `

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

5 `* ?0 \# O3 M. B
4 D  J7 N! f! M) I

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

( d% k* a$ Q7 M方块移动* Y. P! \- Q: N" o9 _* B
4 }3 C& j8 _+ s2 \1 C& `7 p: e
这部分我采用的方法不是动态真的移动，而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉，在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除，可以根据像素大小精准擦除。
9 C& {9 J8 L$ V3 P' z  o
) L5 K) W/ c/ L3 l2 z2 p另外，再移动中要注意不能穿墙、越界。那么怎么判断呢？很好办，我们再前面会判断两个格子是否联通，如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组)
, b1 r# _/ j! }8 d6 G- i- j, ~9 N# P3 b
另外，事件的监听上下左右查一查就可以得到，添加按钮对一些事件监听，这些不是最主要的。, b+ T: u: ^9 `9 A" Z! r# n

% j- E2 \7 g" k# W# ?# d为了丰富游戏可玩性，将方法封装，可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外，如果写成动态存库那就更好了。5 q* w+ X$ u. l& Q" `. {) _! k

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

: V4 q4 f' A+ h- h' Y
4 h# v( T+ r) r+ I

. ?4 c! L1 B* p. V7 t2 i' G6 {————————————————
- x7 ^  k- ~" @3 }4 H版权声明：本文为CSDN博主「Big sai」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。5 f; h0 ?3 `- l0 J- T9 k
原文链接：https://blog.csdn.net/qq_40693171/article/details/100716766
$ {/ d+ y- v! R/ n% E' V' V  ?8 G' T; Y" B# n$ h! K  @
3 D; S; n8 b) E5 N