查看: 2604|回复: 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( z" c$ q; c# @
      for(var j=0;j<aa;j++){' t( E. V7 b8 J/ T. a( T9 t# n5 u
         tree[j]=-1;//初始值为07 ^1 w! |) u' ]6 u( \
      }3 Q0 m+ |2 ?% t6 A( s
}  for(var i=0;i<aa*aa;i++){
3 g& ^! |6 w( l1 b9 [% Q" A       isling=[];- M7 w+ L3 e, k% }& r
      for(var j=0;j<aa*aa;j++){
( x/ `, c" {8 \: q- i          isling[j]=-1;//初始值为0
0 K0 |* C5 H  R       }
7 D4 O1 j- I, q( |8 q }7 g' Y5 ]$ X- X2 s8 D
" P7 d7 J9 X+ k4 ?/ R& L6 y* m& }
function drawChessBoard(){//绘画6 }$ D7 B) P% W5 a2 e
      for(var i=0;i<aa+1;i++){
2 r: ?1 e$ l! a: S# W% R6 l6 `4 a' s          context.strokeStyle='gray';//可选区域" x! V1 J. [2 E
         context.moveTo(15+i*30,15);//垂直方向画15根线，相距30px;: G* W) O) {+ u# H6 S, S8 [7 G5 x  h
         context.lineTo(15+i*30,15+30*aa);
% I7 ^" E; H! E1 t          context.stroke();
. [* j& y% d2 h) l: f          context.moveTo(15,15+i*30);//水平方向画15根线，相距30px;棋盘为14*14；
( S3 k3 N$ g% T! g: o          context.lineTo(15+30*aa,15+i*30);
2 q, b, R) Z* k3 o$ L5 N+ d, w          context.stroke();: J+ X% `5 P& b) W* V; S
      }# D" ~3 M, j4 X! @# E; o+ `: f. W/ ]
}9 m% n% K8 L$ D- q8 O3 _! X5 G3 E
drawChessBoard();//绘制棋盘
& F, X  F9 N+ c- h  l% a" B3 x7 O9 }- r
//    var mymap=new Array(36);
8 C5 v5 m9 l2 l //    for(var i=0;i<36;i++)
; a7 s' R6 l; ?* U; J/ n0 Y //    {mymap=-1;}6 M1 B! G" v3 t
" n& F. w+ e4 t3 X" ^) P' H' y

: f7 @& E# S  D  </script>6 ?: H) P0 Z  i( t# Z0 _
</html>
1 ^$ O2 |+ T0 _! W) k
; [" b1 U  j* G7 P
& R1 k6 `3 u) Q+ \" y实现效果. A; t6 O; `! ~* y

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

# W1 f9 m" Q7 ~
0 G% x# d! Z9 y: e1 Y
画迷宫
. g  d& b1 o* z; w, I
, I5 N- c% \/ [0 p" R随机迷宫怎么生成？怎么搞？一脸懵逼。
# `- D% w3 ?9 n  t5 s; ]7 y- E, C
( c4 ^$ w& z6 |; E  K& ^& R因为我们想要迷宫，那么就需要这个迷宫出口和入口有连通路径，你可能压根不知道迷宫改怎么生成，用的什么算法。小声BB：用并查集(不相交集合)。1 D5 n0 i) q' v1 a( g. ^/ }, B& g
迷宫和不相交集合有什么联系呢？(规则)9 Q# S7 V8 ~9 }8 T
1 F# g& @, B. e
之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合)，它的主要功能是森林的合并，不联通的通过并查集能够快速将两个森林合并，并且能够快速查询两个节点是否在同一个森林中！) K, p; t# J( R; S4 z( s/ j& N% Z! w% V
而我们的随机迷宫：在每个方格都不联通的情况下，是一个棋盘方格，这也是它的初始状态。而这个节点可以跟邻居可能相连，也可能不相连。我们可以通过并查集实现。
% G5 G# b9 Q$ h2 T! m
0 ^6 p% Y% c6 P6 P* p具体思路为：(主要理解并查集)# F* O: t0 c, y+ J' B  c$ q  H
& V: ]$ Y0 {9 A6 M& w7 v; |+ t+ Q2 `/ s
1：定义好不想交集合的基本类和方法（search,union等）8 k; }3 g- k! f/ }. a1 `3 `
2：数组初始化，每一个数组元素都是一个集合，值为-1
5 c% q! @. [3 \/ }2 ?! f# Y3：随机查找一个格子（一维数据要转换成二维，有点麻烦），在随机找一面墙（也就是找这个格子的上下左右），还要判断找的格子出没出界。
3 ^# |! p+ l/ s; ?6 M' z: Q" _) z具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界
5 `  s  v& w9 N. S4：判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在，则重新找，如果不在，那么把墙挖去
" _3 X4 A1 H  Z* G5：把墙挖去有点繁琐，需要考虑奇偶判断它那种墙(上下还是左右，还要考虑位置)，然后擦掉。（根据数组转换成真实距离）。具体为找一个节点，根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。; C7 Z9 [$ g3 L: b* L
6：最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙，但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据，并查集操作。二维是位置。要搞懂转化！6 L6 l% ~- x3 r- p
注意：避免混淆，搞清数组的地址和逻辑矩阵位置。数组从0开始的，逻辑上你自己判断。别搞混淆！
; e( `3 [7 L" I' ]% |

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

" {% J, S! u3 R  U5 l! f6 ~主要逻辑为：. s6 Z' T8 n' ^8 s
while(search(0)!=search(aa*aa-1))//主要思路( j2 S' `9 ?; |; a$ i: _
{$ \3 e- i. g" }# a
      var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数9 }* ~, c8 D1 k0 S+ m
      var neihbour=getnei(num);- X( ~; G3 w( r. f  ~
      if(search(num)==search(neihbour)){continue;}
" b- x; E) V8 D3 d% |$ m       else//不在一个上
# X7 }) V6 Y6 V       {
6 l# J4 q' y% ^7 D4 v! \0 B          isling[num][neihbour]=1;isling[neihbour][num]=1;
! U! q4 G) q* [* V& Z# j7 X          drawline(num,neihbour);//划线
$ y+ K# J( c3 c  E5 E, {8 I" C          union(num,neihbour);7 F; B  F3 j3 o# N0 P1 [
% |1 m2 Q6 s& m
      }, e: ^: {3 b# T6 B- H& W7 H
}
. `- x1 c2 j. ?& y& p( a" X0 k* o: I% ]5 m% ?
; W3 J3 n* C% v% `7 F; q
那么在前面的代码为
  V: A1 m+ w4 G8 Z/ |<!DOCTYPE html>" b* o8 W) g; n- @% R
<html>9 K6 v+ q5 h. C6 t. m8 {$ R
  <head>
9 ?7 H' X+ T9 z4 L5 S: R" H" { <title>MyHtml.html</title>
- y* _1 h" `  Z  </head>
. B4 Y, H- b" J& q0 W  <body>0 J. C. N* x4 }: E+ z; \. r2 }8 X
  <canvas id="mycanvas" width="600px" height="600px"></canvas>4 _6 U5 l0 d- l# p
2 F8 i1 X: D& k8 o+ r
  </body>
0 ^+ C2 A2 N# I4 _' z  <script type="text/javascript">  h4 N" K" B; i) _4 N: I; m
//自行添加上面代码( I8 ~" G0 e# K! \
//    var mymap=new Array(36);4 u% S% o, R1 C8 V& o
//    for(var i=0;i<36;i++)" k5 V; _, D( G: W1 O; M
//    {mymap=-1;}! E/ ?2 p( K1 o) ?' [
function getnei(a)//获得邻居号  random
& ^8 A- Z  ^3 y& z: { {" }( x4 ^  L  m8 E# z
      var x=parseInt(a/aa);//要精确成整数
0 y) U+ t: w+ v4 J8 D4 N3 u       var y=a%aa;
4 w) B; C4 F% u: ^* J$ @       var mynei=new Array();//储存邻居9 E6 e% u* z; U* m1 W7 n. P3 v* \0 P
      if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点. a9 N; B6 x% c% K: h
      if(x+1<14){mynei.push((x+1)*aa+y);}//下节点
. c0 }2 j3 q& c( Q       if(y+1<14){mynei.push(x*aa+y+1);}//有节点
; ]" c6 a* p; A7 N+ A4 V0 i       if(y-1>=0){mynei.push(x*aa+y-1);}//下节点  E; @: e2 d/ o0 P, T
      var ran=parseInt(Math.random() * mynei.length );1 c- ~* `- t' B+ F+ ^2 c/ g3 ^
      return mynei[ran];
' `" s! q3 H) S0 J9 w/ l8 P" z4 ]+ U* I! R
}
7 ^* t# D7 b# V1 h9 l) u9 q function search(a)//找到根节点
% t- `0 z: U7 S' J7 Q {9 S, l  Q/ a( V& S. D: B! y
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
$ @3 J- m$ A/ ], q5 s       {
( ^8 Q, G: k9 }          return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩( Z, n) I$ h- a
      }
$ Q) h9 A% m+ J( C  B       else- N3 }. S: \8 K, z7 d+ }* H
         return a;# M3 T4 w% W+ g) s8 g; v2 T
}' P& k: U5 f/ l2 _5 B
function value(a)//找到树的大小7 e3 b, {8 r8 `( g8 W
{
$ W: V- h& a/ Z& H4 r( l; C; m' Y       if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点9 j4 o, j1 S+ |( O: d. `! Z) i
      {6 y( g9 }2 h3 b
         return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩. X; W6 z: M2 Y9 K9 E( q/ A5 R; A4 z
      }
& F' f; c( Y" ~- ^* M       else2 `3 B0 J2 |# E% P+ h- o
         return -tree[parseInt(a/aa)][a%aa];
( Q; d( M9 k% r) _, x+ P }
. b* E/ h" u# q  L" G function union(a,b)//合并0 P# L2 z2 I8 I* g% Z1 @4 X4 Y
{
2 Y# B% o( b8 }$ Q: m9 I; k6 }       var a1=search(a);//a根
: R' R- K. ]+ h# f9 s       var b1=search(b);//b根
7 W5 M/ w7 a' Y       if(a1==b1){}* I% x- I1 V* V9 [  n7 C
      else: Q( Y5 S. y, o/ K- F1 \+ W8 Q2 l
      {
  d# K- a% ?+ Z$ p3 D$ E* F          if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数()，为了简单减少计算，不在调用value函数, b! o4 u" ^' W" }. h
         {
1 f# ^# W0 B: B8 F) G, f  P             tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加  注意是负数相加) i$ u  {' G" z1 f" \6 b
            tree[parseInt(b1/aa)][b1%aa]=a1;    //b树成为a树的子树，b的根b1直接指向a；
  d9 X4 ]9 r" W' t- u4 Z          }
- d1 j* h1 T  I( v, ^- M. K          else2 Q: @2 P/ H; a0 i8 H
         {$ F  H1 e5 {1 a" H0 h8 \
            tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];
' ]7 u( C+ T/ ]$ h             tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树
0 M& D# I  T" I  G' t* W- k7 G          }
1 W. s/ n' a# B$ G& l# S+ f, d       }  Q8 j6 z# x0 H
}& b5 N. a9 X" |5 N2 b  n9 \% [" _! L

- L! a* ]7 g' G# ]5 w1 o) G5 Y2 U function drawline(a,b)//划线，要判断是上下还是左右1 F3 a- d) @" A) F8 Q* L
{) [" S$ J# ~% n7 |/ w/ k+ h

6 Q! [6 Z% V# a* ^2 s       var x1=parseInt(a/aa);
2 j8 h) g& @: E       var y1=a%aa;
6 [* e# o5 G2 l+ N) K       var x2=parseInt(b/aa);/ f7 R  k# O. Q: p4 f, @
      var y2=b%aa;
8 }7 k7 N8 d& a+ h, M0 |       var x3=(x1+x2)/2;
; i2 H5 u7 G$ u4 H0 {+ m  r       var y3=(y1+y2)/2;
# \2 [. ~9 |6 i, b" l       if(x1-x2==1||x1-x2==-1)//左右方向的点  需要上下划线! e8 N! t* y8 M* u8 d! f- Q
      {
- Q2 O0 N, r( T8 G' w3 e3 E          //alert(x1);4 @( p+ t3 \' f0 S
         //  context.beginPath();" z: i8 O4 M' D' ~' s/ D4 v
         context.strokeStyle = 'white';( e4 t  O$ {" E6 `  Y8 y7 c' P  B
         // context.moveTo(30+x3*30,y3*30+15);//
( U# ]2 W; U3 ~1 N$ {          // context.lineTo(30+x3*30,y3*30+45);
9 b* x+ U  M% ]! H. y( I# s          context.clearRect(29+x3*30, y3*30+16,2,28);7 C, x% B8 F( V4 S
         // context.stroke();6 N% o) ]0 ?, s& b. m9 q2 Y
      }$ b$ {8 Z, ?+ X, ]+ u+ y0 {0 v2 n) P
      else- d! h) l# K3 W1 x+ k; F7 \/ u
      {
2 ]4 S8 \5 Y8 \" `" s# d          // context.beginPath();
; w! s4 y+ b  }9 Z! A1 s          context.strokeStyle = 'white';5 P' t; f4 ^2 f/ N1 r. p
         //  context.moveTo(x3*30+15,30+y3*30);//4 @" q7 `5 h$ ?; B+ q8 }
         // context.lineTo(45+x3*30,30+y3*30);; @& l+ [( C9 L% \* N4 l) i
         context.clearRect(x3*30+16, 29+y3*30,28,2);1 A: B  |( J* Q# X3 a/ r( V
         //    context.stroke();: n1 ], l0 z4 [% p3 f1 G
      }4 G0 t9 z: s) K4 f
}( S. H4 h- z3 `2 c' q3 U9 G

3 a9 B) g6 h. x; V3 f; X( q  M while(search(0)!=search(aa*aa-1))//主要思路: \, m8 E4 }. J! a* J- N
{+ Q! g. P: G. T  W
      var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数1 ~0 C: D" V1 k5 Q$ N
      var neihbour=getnei(num);0 `" A# N6 l- O. ?. ~0 p5 p
      if(search(num)==search(neihbour)){continue;}
7 g6 O4 R& }) {5 K$ p       else//不在一个上3 e/ A/ R+ y0 v0 X3 v6 v% Z6 T* D# x
      {
4 Q3 W+ D( v. ]. E& j9 K8 g5 ^          isling[num][neihbour]=1;isling[neihbour][num]=1;
. [( J; `0 ~6 h: b8 M- F1 Z& ^          drawline(num,neihbour);//划线
: P: r6 ]3 @! X) x5 k          union(num,neihbour);+ S( ]: }7 U8 j. L0 U/ h

5 A% H2 a, T1 N9 |       }; ?4 q5 |9 l; r, ]- T
}
' _  l  j3 j) I" J7 j  </script>
" v+ ]% i4 b# u9 F</html>
8 N' W8 \1 t3 C2 j( P1 _3 B! M2 Y3 t/ |. _8 S& L5 ?' F% U

  Q. x! ?) T4 z; C% P5 S  w实现效果：
( r2 W" |% @2 Q0 Q( y, p1 L
3 N; q4 j) f+ A' ^0 i, N

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

$ [: D0 e* c# m8 v+ x9 `$ y

+ F  y1 p' ~7 ^, n1 j% [

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

  E& f/ h% K3 E% ^" ~  _/ F
方块移动* d3 Y6 N" |9 |% ?9 M! R
: a8 m% B! ]" [- v2 S% d
这部分我采用的方法不是动态真的移动，而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉，在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除，可以根据像素大小精准擦除。( h  Q1 n0 \7 R7 c. B

5 Q: t2 V' `: J6 g另外，再移动中要注意不能穿墙、越界。那么怎么判断呢？很好办，我们再前面会判断两个格子是否联通，如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组)  n, z; Z/ J# m

7 Q" H4 m/ }# r1 ]- X$ |另外，事件的监听上下左右查一查就可以得到，添加按钮对一些事件监听，这些不是最主要的。6 H4 `' h' T- f9 z9 p

  J- _+ _1 _' X8 B* J为了丰富游戏可玩性，将方法封装，可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外，如果写成动态存库那就更好了。
( |2 u' Q) e# P) J

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

2 _; ]; S$ h* f  |! G6 j& K

" M$ l( Y' k3 y0 |, n: E* u! C! d" d4 G/ F
————————————————
; y, |) X* ^2 n版权声明：本文为CSDN博主「Big sai」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。# }4 S  H* ~2 L0 A9 q9 T" Y
原文链接：https://blog.csdn.net/qq_40693171/article/details/1007167668 d$ v: z8 |' r) X8 `3 G- K/ ?1 p
3 ]/ j' |& _4 `) A
+ ?/ d4 Q8 B# i, f( w4 z2 @; e