查看: 2626|回复: 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=[];, L0 B+ _  h0 u! L) D
      for(var j=0;j<aa;j++){/ t4 G; b. H: \4 W' r1 l" u$ F
         tree[j]=-1;//初始值为0
! F0 f6 V5 Q' e2 y: d5 W. ^5 G       }6 k; n3 C& t) m" e  q
}  for(var i=0;i<aa*aa;i++){8 Q3 X& Y4 v5 I
      isling=[];% s* Q; b7 v  p4 z( E. g1 u
      for(var j=0;j<aa*aa;j++){
. D% p) s, p  A  H          isling[j]=-1;//初始值为0
7 v2 _6 ]5 w9 d( T; R6 I       }" R0 j/ @3 y- L% A# t' s0 C- ~
}
1 ~9 {2 z  Z: k) B8 M) v! [. t; g% b( @' ^5 q7 i( d
function drawChessBoard(){//绘画1 Q  i8 x' @6 k# j6 h$ ^* j
      for(var i=0;i<aa+1;i++){
) N+ _) R' g4 `. n2 R4 j          context.strokeStyle='gray';//可选区域
0 {! {4 z4 e4 p          context.moveTo(15+i*30,15);//垂直方向画15根线，相距30px;
$ J; |! k7 c' m5 r  U- {- a          context.lineTo(15+i*30,15+30*aa);- \# D, t! x5 Y1 `8 p# R9 F
         context.stroke();5 K9 K, ~# G9 }8 b
         context.moveTo(15,15+i*30);//水平方向画15根线，相距30px;棋盘为14*14；) S) B, j2 s! `$ u+ l+ v4 T& N9 I
         context.lineTo(15+30*aa,15+i*30);7 ~1 q7 W' q2 V4 Z- D9 O6 N" j
         context.stroke();
$ x7 @1 y3 i7 k" Z       }, B# a/ [. w. {8 v: s6 s# V
}
* M& [- U0 |. Y, c drawChessBoard();//绘制棋盘7 A7 M/ \' X; {( v- d

( K, s  Q3 L/ @1 A' V' o. z& x //    var mymap=new Array(36);& o. z+ u1 j% h8 Y2 T+ p/ h, t
//    for(var i=0;i<36;i++)" j# r; g8 ?' q! ^
//    {mymap=-1;}
" X1 j/ j7 T3 o, |3 L2 g  x) q
; f7 {/ S7 a8 D# }. N/ H3 z9 e) R
3 q7 e3 O, C' p) S0 m+ O# j9 D  </script>
' p, i6 T: _2 w0 j</html>
  ~! n6 O) f% p8 S6 B
& e# L* n4 W- ]6 M! d! }
  ]) K" a2 ]6 s/ E实现效果6 l8 F  P& m, v) Z- l: u9 s7 I

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

  C6 d' S  w+ D- m! B% }2 u/ y

- f9 d' w/ Z! W6 C画迷宫8 }& E2 f' Q+ i! L
* a0 X1 T5 c6 @  v0 F7 G
随机迷宫怎么生成？怎么搞？一脸懵逼。
3 M' i) C$ v8 Z6 A
/ \+ a6 P9 U  M. s9 d: f* K因为我们想要迷宫，那么就需要这个迷宫出口和入口有连通路径，你可能压根不知道迷宫改怎么生成，用的什么算法。小声BB：用并查集(不相交集合)。
' @8 |% k/ Y+ e迷宫和不相交集合有什么联系呢？(规则)
/ a. {( z4 g' ?* J+ \/ u, n; H2 x" ?0 z0 }8 @
之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合)，它的主要功能是森林的合并，不联通的通过并查集能够快速将两个森林合并，并且能够快速查询两个节点是否在同一个森林中！
+ V8 Y' ~7 q( Z2 H: V' D3 r而我们的随机迷宫：在每个方格都不联通的情况下，是一个棋盘方格，这也是它的初始状态。而这个节点可以跟邻居可能相连，也可能不相连。我们可以通过并查集实现。9 w" X* {( @8 s" {0 T' h7 K4 ]
. N" [7 b% w! v+ }- V. A) r
具体思路为：(主要理解并查集)
( _4 `3 Y* X0 E2 X2 }$ P  L
" N# E* j, b6 k* m- w5 H1：定义好不想交集合的基本类和方法（search,union等）* t: p5 n5 u9 T( h9 p
2：数组初始化，每一个数组元素都是一个集合，值为-11 S5 U6 u8 |8 D: }7 K8 x% m
3：随机查找一个格子（一维数据要转换成二维，有点麻烦），在随机找一面墙（也就是找这个格子的上下左右），还要判断找的格子出没出界。
% c& q& i' \4 z5 _3 T9 _具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界
9 e  y/ b9 d. S# [8 E9 ^4：判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在，则重新找，如果不在，那么把墙挖去
* `! a, C1 t5 ?& E8 `5：把墙挖去有点繁琐，需要考虑奇偶判断它那种墙(上下还是左右，还要考虑位置)，然后擦掉。（根据数组转换成真实距离）。具体为找一个节点，根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。9 m2 J" z. W0 i7 Y5 n
6：最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙，但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据，并查集操作。二维是位置。要搞懂转化！
& g+ e0 H' K) }1 V* m- l注意：避免混淆，搞清数组的地址和逻辑矩阵位置。数组从0开始的，逻辑上你自己判断。别搞混淆！
& |( ~$ l+ ?+ i. N3 @

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

" @; \" q! L' T
主要逻辑为：
0 {! c6 d! ?4 G; n! q2 w6 Wwhile(search(0)!=search(aa*aa-1))//主要思路# v/ b8 j( z4 J
{6 Z8 z/ y" a" H  k  A
      var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数9 e+ l% ?; B# p1 @
      var neihbour=getnei(num);- |0 f2 m; L2 l4 b: n+ h
      if(search(num)==search(neihbour)){continue;}9 X+ q: ^9 c4 N  H" K4 d& s2 d; f
      else//不在一个上9 k- s7 _3 w* i# u! U; T1 k3 \  F4 \
      {
8 G! ^; Z7 C( |9 y( Z  T- T- m          isling[num][neihbour]=1;isling[neihbour][num]=1;) e/ r) G2 T1 z8 g2 m
         drawline(num,neihbour);//划线! f) p) B! D' l9 F( i
         union(num,neihbour);- X9 J+ p2 G1 B+ T* n/ q
8 V: i; L% z1 n" y
      }
7 T# e% Y$ t2 W7 @: ^, X }
+ F% F8 |  r+ V+ Z/ |0 C
8 B* ^" J) P9 A' y$ f0 O$ r& O0 i8 q5 r
那么在前面的代码为
3 D5 i% R8 z0 S1 c' x& l0 s8 c<!DOCTYPE html>
9 t0 |6 I6 r9 a( l<html>
8 {( I' O- I* V  <head>
! u/ J% K7 v) T0 J <title>MyHtml.html</title> 9 \2 ~! [( ]6 C$ A0 e
  </head>
( i! _6 L) }& Q1 @( e  <body>& s* P: N/ H0 r. W
  <canvas id="mycanvas" width="600px" height="600px"></canvas>
. b2 y% g! q. ]9 H" ^9 B
* I( b7 \! ^' J0 u, j' k1 b3 o  </body>
2 \4 X$ _& [, `, L3 t6 k7 D+ S  <script type="text/javascript">
( z5 K; {& o$ g( i" j, i//自行添加上面代码
8 z, r5 z. _) j1 g) \" k/ J //    var mymap=new Array(36);
/ d; @$ J& _4 ~2 c2 S //    for(var i=0;i<36;i++)$ n3 n) S; D, i; V2 {" u
//    {mymap=-1;}
7 l/ T" N3 s, ^* V function getnei(a)//获得邻居号  random
/ K1 L6 J- S1 y0 e" j& ]8 r {% ^# x1 V" h: L8 R, ^, p. r/ s
      var x=parseInt(a/aa);//要精确成整数4 M4 L! \6 ?5 {; B- Z8 s
      var y=a%aa;& |0 h0 K. r8 O5 E1 c' F
      var mynei=new Array();//储存邻居
7 D4 {. ^/ d) q; W2 A8 X# k       if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点6 p: i) {! n4 X% }) A, |) V. F
      if(x+1<14){mynei.push((x+1)*aa+y);}//下节点+ {+ }5 @: s" e" r5 O
      if(y+1<14){mynei.push(x*aa+y+1);}//有节点( ^8 i1 q) a4 W
      if(y-1>=0){mynei.push(x*aa+y-1);}//下节点
1 I  k" Q# F! U4 [4 |- a       var ran=parseInt(Math.random() * mynei.length );. }( [/ u& V5 X  ^6 C9 V; U$ Y! A
      return mynei[ran];  n" X+ A. o* w# d3 l5 B' [0 N
$ U9 d  B# [$ Y9 C( |  X$ c
}! N( Z6 V1 x/ C! r
function search(a)//找到根节点
' E: M. _: V+ J) ~3 r {" O* A4 ?: ~# v4 T1 ]
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点4 r- b; w! X" F$ Z6 y) E9 w7 a
      {: R. ~7 e& E% ^8 z
         return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩
3 ~+ d( U) Z8 n! \       }9 u9 Y0 G0 B9 N' L
      else
7 b9 v  Y3 p. C2 s9 q2 Q( p+ t          return a;
* y- E2 d7 W0 N1 K1 E9 N, ?: b }6 q! s! C( _* r7 p) @
function value(a)//找到树的大小( Z. {5 d7 `! f! L. a. {! B% C+ N( e
{9 B3 b5 D+ n' L. k/ E, `% p
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
0 ]: r4 t7 E4 q9 n7 L       {' G( K% i+ o- y" C
         return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩
5 s" J# Q7 r& M* P4 Z7 ?) F! L       }
4 C$ y- w: A! {+ Z2 s1 a       else
" |% z/ D/ l7 c3 q  D! O! f          return -tree[parseInt(a/aa)][a%aa];& c8 S) \' |: u& g# j0 N
}
8 g0 P7 f7 A6 q% O0 @. g function union(a,b)//合并6 i+ `. \5 }3 ?3 j2 P3 v% B: P  Z! u
{) R8 ]* X4 X2 e& a
      var a1=search(a);//a根, K" n8 g. ]' ?  P- d1 I. x4 M
      var b1=search(b);//b根1 }, B; y8 l: G' V6 M7 C
      if(a1==b1){}. R1 p' ?- h' r1 Q1 u2 H+ K
      else
" n+ Z1 I0 b3 b. a) f       {
! |# a  r6 F  `( c) S$ {0 R          if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数()，为了简单减少计算，不在调用value函数
4 `( x, C5 j- I# J5 {# w          {
! l  w4 |5 D0 O# D' m- n4 c             tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加  注意是负数相加' ^& C9 Q, P- W( C9 {4 k0 p
            tree[parseInt(b1/aa)][b1%aa]=a1;    //b树成为a树的子树，b的根b1直接指向a；
3 |( f/ r3 \6 @6 e; v8 L          }4 W3 A5 n, v+ W9 P8 k, y8 h
         else
5 g  }+ g5 C; U5 V, Y- @4 I          {
6 s- d4 F' K2 l# }/ N* r             tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];
! ~$ @  T$ q$ E6 H4 o/ K             tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树; M) q. _0 b+ |3 S' y, g
         }
/ W! q+ v& d" T/ Q$ Z% h       }# r  R& ^6 r3 E' V6 J. U
}
$ p  a' B! M- I1 e' M9 Z/ g; D) @: n0 S4 P
function drawline(a,b)//划线，要判断是上下还是左右! w& |. @- [& d9 m3 q9 }
{
. _' x: ]  k& B1 l. @1 W
9 ?) N2 `& Q" H- I4 Y' _       var x1=parseInt(a/aa);2 }) O7 j. q" z: `: S
      var y1=a%aa;
& e7 W+ N5 q0 \/ X& z" E       var x2=parseInt(b/aa);
6 O6 t" _& U" `+ r8 U  i# z       var y2=b%aa;
; `' u$ G0 j% D! m       var x3=(x1+x2)/2;5 v7 I# j1 Q& e3 ^0 C& e" f
      var y3=(y1+y2)/2;
1 P9 B% t) n( d2 ?       if(x1-x2==1||x1-x2==-1)//左右方向的点  需要上下划线
" T: V6 k- d1 Q       {
. B0 P6 R/ Z4 r$ x3 n          //alert(x1);9 V- }4 K% L- K# ^  `1 a' \2 c6 d
         //  context.beginPath();
' {0 _; d. |/ I$ j5 t2 i          context.strokeStyle = 'white';; S% e/ q0 Z  ^1 k, i6 {
         // context.moveTo(30+x3*30,y3*30+15);//) F8 X+ q5 z5 ^2 k7 M3 y2 f
         // context.lineTo(30+x3*30,y3*30+45);( m1 F) Y/ Z; k
         context.clearRect(29+x3*30, y3*30+16,2,28);' r/ p0 o* O* J4 a3 Q# w9 l
         // context.stroke();4 }$ E% \7 C+ f) F
      }) _: V  F, m1 I# N* J
      else! ]& ]: {$ J5 Y- y6 B, ?; e
      {
: B$ ^! j9 N. p6 C, c) X          // context.beginPath();( v: K( ^# k9 x; O' C* F
         context.strokeStyle = 'white';5 t# v' j  x( G
         //  context.moveTo(x3*30+15,30+y3*30);//4 k7 @  R0 I( s
         // context.lineTo(45+x3*30,30+y3*30);3 g; V$ {( O, w, A
         context.clearRect(x3*30+16, 29+y3*30,28,2);
  C! S* w: e7 y% |# t1 q: T4 C# K" z          //    context.stroke();
9 u5 p# Q0 {3 |- C" Q4 N5 G7 N       }
1 l1 K% E: y% b. P }# l$ {. I9 a- S

' H3 _1 U) H) |) R0 e while(search(0)!=search(aa*aa-1))//主要思路
' c; W9 E  L3 {; ]. ^. K {& q2 [5 @2 Y/ |8 l+ M
      var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
: X5 m$ V" q# x: ~2 Q+ E       var neihbour=getnei(num);
! i* v: x0 a2 z; Y       if(search(num)==search(neihbour)){continue;}
  ]$ O  U2 H# @) n+ i       else//不在一个上
; f. o, x, M, h) C9 b1 W       {  P- X+ u3 r2 O5 B7 p- }
         isling[num][neihbour]=1;isling[neihbour][num]=1;- j+ R0 s2 P9 c2 ^# a1 W/ r5 v/ l
         drawline(num,neihbour);//划线* F9 Q6 u/ t3 p9 p+ ~- X) O
         union(num,neihbour);1 j2 ~" @1 K( ?  D/ q1 t" Q+ Q3 g/ j

/ o" X5 }5 k5 J, M  U/ r       }
/ t. R# W* L3 x# j }% x" M* B3 P$ \. w' }  u$ r
  </script>7 d4 V, W( {" p7 x  e
</html>3 o; M7 ]2 F1 {$ |1 Y5 q

+ P; L4 K$ j# k+ W5 k& {, I) D: c, }' X6 P! |
实现效果：
( `: A1 a" O" s& T6 f
8 r5 W+ x) R5 E7 }

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

# b* d1 h" w1 o* Z
3 r! U' O, Y+ c: }6 S+ h( [4 _

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

' M% C- j8 y/ G, A: L# j9 V: k
方块移动
( ?7 h/ [* ^9 h- h5 ^9 F  G1 p6 M
. b2 [1 I6 c2 h, g& Z8 W. ^2 V这部分我采用的方法不是动态真的移动，而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉，在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除，可以根据像素大小精准擦除。; X9 l* K, H4 ?; \5 S
5 j) x, k( Z% b/ k1 h
另外，再移动中要注意不能穿墙、越界。那么怎么判断呢？很好办，我们再前面会判断两个格子是否联通，如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组)
+ G- J) A5 s7 A5 X( Z" z* w1 X2 f$ T/ q$ Z" T
另外，事件的监听上下左右查一查就可以得到，添加按钮对一些事件监听，这些不是最主要的。
6 l; B/ W+ Y1 Q  n' e7 ?$ e# @8 P8 z' i/ P$ ^) {& a9 g2 F
为了丰富游戏可玩性，将方法封装，可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外，如果写成动态存库那就更好了。
3 d( N; ?/ a. e

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

5 R/ L5 |% H: Y" Y; d) L, K

, [' ~, f. m3 J0 ^6 V9 Y! |
' L9 H, \; y0 h) L————————————————
0 G/ h* H  Q3 C0 M' E/ S版权声明：本文为CSDN博主「Big sai」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
) O; X9 I9 F- i' L# S3 e原文链接：https://blog.csdn.net/qq_40693171/article/details/100716766
& w; L, m: |  A8 S6 e2 I* h& D- X

7 m+ v9 J* A# Q: F; }0 t