查看: 2607|回复: 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=[];2 o. a) A8 b* n% V# N: j
      for(var j=0;j<aa;j++){# K/ M1 u) I9 s8 @  s* W
         tree[j]=-1;//初始值为0- ]" Y# D( @3 `5 D3 R
      }
  V8 p* d* T( O5 B$ ] }  for(var i=0;i<aa*aa;i++){
: N7 A& }: A: i! m& L9 f4 F1 X       isling=[];
2 a- \3 A) |+ ?0 v+ M# a8 m       for(var j=0;j<aa*aa;j++){6 e1 [' M9 R) T
         isling[j]=-1;//初始值为0
. g' N/ O6 h4 L5 i7 I, k       }
$ h% B" t7 r5 ~8 H, Y8 x }9 X8 l- j& q/ ]

! o; y" O) z5 \  t7 y' U; @ function drawChessBoard(){//绘画8 n4 B8 c! J8 b  D( b0 I
      for(var i=0;i<aa+1;i++){% {: T; |9 F4 W
         context.strokeStyle='gray';//可选区域
' @# }: m9 f% d5 x  K5 S& [          context.moveTo(15+i*30,15);//垂直方向画15根线，相距30px;
6 B  h2 O3 u7 N+ u0 i' v          context.lineTo(15+i*30,15+30*aa);
+ X  X4 O1 c6 k. o          context.stroke();
9 Y: D- p# \9 @' E4 t" b          context.moveTo(15,15+i*30);//水平方向画15根线，相距30px;棋盘为14*14；2 a; q. d& _. h( A* P
         context.lineTo(15+30*aa,15+i*30);
+ d% K: q( I& p% ~0 m- Q          context.stroke();4 Y9 s% V; d3 R/ ?" \
      }- v. R  g5 @6 A' {% i- e& Y+ B
}  P  a8 p- w( C8 c1 K
drawChessBoard();//绘制棋盘1 d/ ~$ x7 \4 D3 d# G+ i
- |& r, R% a  x
//    var mymap=new Array(36);
4 J( I2 p" p4 W7 o8 T' d //    for(var i=0;i<36;i++)5 v5 e) }- ^0 n
//    {mymap=-1;}
' l' x7 Z  ~; }% `2 a. b7 F' [$ @2 L' R# f0 K7 J3 X

" U8 M$ @! Q8 v$ G  </script>6 s0 B* T+ _$ S
</html>  @: F& x/ f* ]2 c

7 c. K; Z* I; e9 v6 ~
1 t" Z( f$ J; m8 A( \实现效果
1 x" W+ w$ w( `# A: G

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

7 ^: `, N: b; W. ~0 c" Q$ |

2 H2 \$ z4 K* h+ c画迷宫
6 a" C1 T0 A! A( ~3 m/ N9 r0 }0 w) V8 n9 i$ M+ K2 n' G* o" s
随机迷宫怎么生成？怎么搞？一脸懵逼。
1 Q- a: W8 n  h( x# L0 {% g) ^& Y! n# e8 v" M. ]' `
因为我们想要迷宫，那么就需要这个迷宫出口和入口有连通路径，你可能压根不知道迷宫改怎么生成，用的什么算法。小声BB：用并查集(不相交集合)。
5 @  b& r) ~3 c1 k; P迷宫和不相交集合有什么联系呢？(规则)
: s! Y0 l8 m, l2 d5 w# `: e
7 u5 d3 Z+ _- V: d之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合)，它的主要功能是森林的合并，不联通的通过并查集能够快速将两个森林合并，并且能够快速查询两个节点是否在同一个森林中！1 n5 Z! k1 v) N0 g6 E2 x
而我们的随机迷宫：在每个方格都不联通的情况下，是一个棋盘方格，这也是它的初始状态。而这个节点可以跟邻居可能相连，也可能不相连。我们可以通过并查集实现。
1 s: C+ }% F; Q
; l% s2 w2 |, b0 F2 F( W具体思路为：(主要理解并查集): K9 Z- V3 o" R& b- [

, c5 I" F" ~; V$ c4 T1：定义好不想交集合的基本类和方法（search,union等）
( m& h, t- g2 _! d3 G/ R; p2：数组初始化，每一个数组元素都是一个集合，值为-1' ]; T: A7 B8 t) s0 _1 a! b
3：随机查找一个格子（一维数据要转换成二维，有点麻烦），在随机找一面墙（也就是找这个格子的上下左右），还要判断找的格子出没出界。
$ H+ h# d9 n$ y具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界
. R3 M' M' R5 c) a# `4：判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在，则重新找，如果不在，那么把墙挖去, |2 H' E; q6 ~! n3 N! O5 t' ]( ]& c6 y
5：把墙挖去有点繁琐，需要考虑奇偶判断它那种墙(上下还是左右，还要考虑位置)，然后擦掉。（根据数组转换成真实距离）。具体为找一个节点，根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。
% W0 k" `* O) s6 f8 M' a' l7 F6：最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙，但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据，并查集操作。二维是位置。要搞懂转化！1 U- d" ]( G- P* r1 l* G! W
注意：避免混淆，搞清数组的地址和逻辑矩阵位置。数组从0开始的，逻辑上你自己判断。别搞混淆！3 O% U4 b" R' X5 i" Z

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

6 t+ N5 A, w9 S3 G主要逻辑为：9 [( C! O7 y# \9 s
while(search(0)!=search(aa*aa-1))//主要思路
; m4 Q% [; b+ H% J) A. L {
7 j; H- ?% C& h       var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
* D8 r: _$ R+ s% \6 y       var neihbour=getnei(num);
- m) {4 Y% X/ q" \# o: S- c       if(search(num)==search(neihbour)){continue;}3 n9 a; w. \7 ^- h6 T2 b
      else//不在一个上+ N! s- X1 U& M- j
      {
( Q! w7 ]' Y6 L2 h2 n% D          isling[num][neihbour]=1;isling[neihbour][num]=1;
5 O$ T$ {0 z/ [1 C- u          drawline(num,neihbour);//划线
8 z, h7 F4 _; @! f( i' w: ~          union(num,neihbour);2 i" x% p3 |9 r; i7 o  o

1 ?2 p" F/ A3 p; ^, t6 h. x& D8 g       }
* v+ g' Z+ r8 d# u' j  [ }
! T5 t! M$ [! \; D$ Y5 q& [6 y1 g: @" Q  U$ V

( H( V0 E0 o  c/ b那么在前面的代码为" O3 t4 C$ }4 A
<!DOCTYPE html>
  K  j: M) f7 V/ c<html>8 W! e. B/ X! p
  <head>. _, C# {" t' ~3 |) [* J5 d! z
<title>MyHtml.html</title> ! D) q7 \; S7 r# j/ Q
  </head> 5 m4 v$ ]% q  z6 [2 u( h
  <body>
3 {+ }- n0 D% \" m( o+ k. z0 @+ @  <canvas id="mycanvas" width="600px" height="600px"></canvas>' F' s% j1 ^" ~8 W. C7 Q
& h& K3 f8 C; R2 w
  </body>
2 j$ _( p. |) s1 ^4 ^6 ^  <script type="text/javascript">4 Q% l& ~; M/ ^4 K4 W. [
//自行添加上面代码- c/ ^; W  ]( ?& W
//    var mymap=new Array(36);
- E3 n5 j* F# F //    for(var i=0;i<36;i++)
" \" q+ o8 Y: p: c //    {mymap=-1;}
6 ~8 Z( ~5 ^9 A- O( X, C function getnei(a)//获得邻居号  random
7 |1 S0 _# p. Y; ]0 [* X+ h {: b# U& O& Y; N- _
      var x=parseInt(a/aa);//要精确成整数* u7 H6 l; s0 _$ n# U) e$ ~( A& m8 Q
      var y=a%aa;
* o3 u2 e1 A0 l' D       var mynei=new Array();//储存邻居
) H2 c$ b, }+ |. _% X8 f( h       if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点7 F* Q7 q" p* u2 p+ E: }
      if(x+1<14){mynei.push((x+1)*aa+y);}//下节点
0 l4 Z( o: ~- h/ h0 S& y( F8 `       if(y+1<14){mynei.push(x*aa+y+1);}//有节点: \" s0 x3 w. V5 @# u
      if(y-1>=0){mynei.push(x*aa+y-1);}//下节点+ q- n5 N" O2 c8 C' n- \
      var ran=parseInt(Math.random() * mynei.length );. c4 y7 d  H% z2 k# {
      return mynei[ran];+ z5 y% k9 u0 r* B( ]0 V# |  w

6 J' q3 h9 ~' S+ f }
- X4 h9 l; B- H1 T. O function search(a)//找到根节点: N# ?9 Y3 ]0 T& Q8 s  Z
{  n% w8 I3 p( N0 n; L+ x( m
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
, p1 P8 r. i( R7 J4 H       {
  b" x* H, y2 k! i          return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩
% j. f# R, t: Z, r8 _  g       }
4 i& d$ s3 C2 d% B5 `2 ~, ?. C/ t       else# @1 L! t- E4 I. \
         return a;2 I  }+ k! p) [, ^* e7 Q
}
; H# G6 e- w$ X, @8 ^# @# Z function value(a)//找到树的大小8 m- V7 Q) V3 @
{) b2 h$ O7 |. J5 J7 O* k
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
5 m9 N# s8 ?! j7 d$ a2 ]  h! S! I/ V       {
; q3 l4 L/ o; j/ |. H$ z5 R8 t          return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩
5 a, c5 L4 e- q6 L. Z3 |& F6 c: G       }/ M% G; T' i8 L% s
      else$ R' V, E; v' d3 f" _
         return -tree[parseInt(a/aa)][a%aa];
  C( Y* w8 [4 l+ s+ n9 f1 t+ w8 i }
: _* h4 s% O7 f2 L function union(a,b)//合并
% w( w) U2 l: Z& j/ D {$ k. I; s% _& c
      var a1=search(a);//a根
( v) x8 c1 k: _* {. k       var b1=search(b);//b根
$ S2 `2 z/ ]4 Z  `3 [+ M  c       if(a1==b1){}
( `% s1 R4 ?' Y& \$ L+ E& R; |1 O" f       else
8 h0 Y( P8 }( f2 \- p, t& t8 g       {
5 r$ m# c/ a4 {& q          if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数()，为了简单减少计算，不在调用value函数1 b4 S( ?2 }! @9 E( T9 B
         {; Z2 b: m% V, L% h1 O3 V/ U
            tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加  注意是负数相加  b% d' D" o  X5 K. v5 N
            tree[parseInt(b1/aa)][b1%aa]=a1;    //b树成为a树的子树，b的根b1直接指向a；1 n3 i; r! I6 v" i; S7 T; E
         }
         else
2 A9 b+ A1 v1 V! ^          {2 k9 a9 w5 R+ r$ U& b# }$ q
            tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];7 z8 o! @4 T. _/ [: @7 h
            tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树8 c8 `( z8 G  a6 n
         }4 b/ ]1 _1 A2 ^
      }! [  ^, M  Q1 e; O
}+ u9 w( k4 m7 K' q; m' l  v6 K
' A+ F+ Z2 z) M/ m
function drawline(a,b)//划线，要判断是上下还是左右
; P& e( ?) C2 s. f5 ~! ?0 m8 c {
2 `  g9 Q5 r9 U2 ?% r4 G7 p$ a0 D. i- g& z. ^
      var x1=parseInt(a/aa);
8 I( h8 [, w% R( S, D       var y1=a%aa;
' ^8 t/ c4 H" C8 |. A       var x2=parseInt(b/aa);- t6 j4 J6 ^' l4 Q! t6 _6 S5 A  J
      var y2=b%aa;
' A. q8 C" n" J4 d( V' ?1 u       var x3=(x1+x2)/2;
3 {+ h# X2 h! b: c4 _       var y3=(y1+y2)/2;
/ h( j; A9 H4 r# y, u       if(x1-x2==1||x1-x2==-1)//左右方向的点  需要上下划线' e+ H; {- O' g! b! v
      {; _# x5 @6 I. i! W" q' i+ x( i2 Y
         //alert(x1);# |9 `# t1 C9 T
         //  context.beginPath();; z2 y6 B$ K2 _( {
         context.strokeStyle = 'white';8 f! r; n. T6 b4 ^2 @
         // context.moveTo(30+x3*30,y3*30+15);//7 X, l% e* I( n& n: {% G
         // context.lineTo(30+x3*30,y3*30+45);
! p8 S7 W8 e) g3 c. P) |  m          context.clearRect(29+x3*30, y3*30+16,2,28);5 I4 F" _% U) P! E8 X$ M
         // context.stroke();
$ Z. `" h, I- j$ ~" ^$ l       }
+ L/ |; S) `, V0 C4 @$ ?       else
# }( x$ B6 n$ w       {# |: M1 T& H- k  g+ t. f/ {8 A
         // context.beginPath();- W: U# }# Y  k6 B* \
         context.strokeStyle = 'white';
% `0 j: `, ~" R# w: B  r: R          //  context.moveTo(x3*30+15,30+y3*30);//
4 R& q% D: ]0 I4 G          // context.lineTo(45+x3*30,30+y3*30);
0 m! D2 {0 x9 q  j) z          context.clearRect(x3*30+16, 29+y3*30,28,2);
. `/ B% H6 t0 u# {          //    context.stroke();0 C, C, T, a3 v9 \1 O. l! p
      }6 _* t6 D6 b0 A. x- {/ Z0 g& R
}9 G0 C! x, {. k# N. r. [$ e
- \7 v1 b" T1 _. q- z; ]
while(search(0)!=search(aa*aa-1))//主要思路+ U0 {" ]( U! A
{$ e* _0 C, Y# j( n
      var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
6 a/ k/ J  H' M# Z1 S" ^4 ]       var neihbour=getnei(num);
$ K% v* r6 e# {" V* ]       if(search(num)==search(neihbour)){continue;}
* v+ ^8 ^4 K$ M1 l       else//不在一个上
. G, b$ G2 U! o* X8 [' T       {7 \3 q4 c- S/ C
         isling[num][neihbour]=1;isling[neihbour][num]=1;4 B7 e) i& H5 L% s
         drawline(num,neihbour);//划线
, _: c" g4 l6 P5 ^) P0 v          union(num,neihbour);
) ~5 y1 ~; ], k8 k% A/ O4 S4 h
4 d  t2 F( y% ^1 s6 M, I* a3 {( R       }
) T4 d8 \  G: w/ F* k% q }9 L" W7 E* D& H. t# h/ g4 D
  </script>
) w8 A! t- V8 Z</html>' ?0 n6 w9 H( i

  E, \# q; B2 J! \3 b4 Y
7 A2 X( a4 F' W: z6 ]5 m实现效果：
( O/ _" m3 F& f' A4 n1 I7 |$ H4 G5 C
8 o3 X) v7 M0 r2 f5 C% t, i

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

& U% G1 u! u' @$ R
. v9 \: ~3 ?' w- D% k3 O% K

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

8 P4 ?' b; e, U& F/ {/ O
方块移动: |% l, w1 M5 ?1 T: y: i+ F0 p- o& h

' V9 h' W2 L& Z这部分我采用的方法不是动态真的移动，而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉，在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除，可以根据像素大小精准擦除。
3 D7 G. _- C" A" A0 E  p7 R9 ?9 Z/ g% _" K: [3 w1 k
另外，再移动中要注意不能穿墙、越界。那么怎么判断呢？很好办，我们再前面会判断两个格子是否联通，如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组)( J. B; Q* `) y" g0 p: E( p

# \& M$ T/ z7 Z! l  V5 s" l) H另外，事件的监听上下左右查一查就可以得到，添加按钮对一些事件监听，这些不是最主要的。9 N" T, R  }+ H7 w

8 T- c- t  f) f" s为了丰富游戏可玩性，将方法封装，可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外，如果写成动态存库那就更好了。
/ ?$ d) X2 U! A0 r3 B( D

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

3 e: S  T: o( x, W  G8 U! n$ t# M

- x5 k" b7 U& g2 g2 B
* c5 a( q% J2 U3 o. o1 A0 E8 z————————————————
# Y) U! L' a* V3 w; o& L版权声明：本文为CSDN博主「Big sai」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。2 V, }9 q( ^7 p1 _4 O, }1 d! V% g, h
原文链接：https://blog.csdn.net/qq_40693171/article/details/100716766
7 c3 i& P" ~- C1 r; M: M: u! e1 n- U$ e: q% X

4 `- Q* c6 |; l+ u# ]