查看: 2548|回复: 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=[];
- R* ?) `  i( J; [& H# L       for(var j=0;j<aa;j++){
- d1 @5 x2 K+ E4 x8 {' P& }          tree[j]=-1;//初始值为0' K4 }! ?; a3 c8 o& Q
      }
/ i0 t, b) U! m& g  f& L }  for(var i=0;i<aa*aa;i++){
# p; E( n3 A" |- y       isling=[];
! r4 Z! t( f5 j$ C7 y       for(var j=0;j<aa*aa;j++){: F  F# Z8 p# q& z2 X
         isling[j]=-1;//初始值为0. k( ^0 a4 x+ n+ l) x  y
      }  E7 `" H8 u6 J# P1 ]$ E" J
}% V/ j  {) g+ v# W2 N

7 D0 r! o% `& G. s function drawChessBoard(){//绘画
! ~+ f0 j2 c0 y. N) O( |% a1 p2 A       for(var i=0;i<aa+1;i++){
8 z5 ?" }# L  [+ c# `          context.strokeStyle='gray';//可选区域, F( ^  T2 V/ s/ a9 h1 a) o# X. n
         context.moveTo(15+i*30,15);//垂直方向画15根线，相距30px;2 t# E5 L: {5 s8 i: B% G
         context.lineTo(15+i*30,15+30*aa);
; G, P. }8 y2 {2 m. o% j7 |7 h  V          context.stroke();
. p* _% ]+ i- ~+ z          context.moveTo(15,15+i*30);//水平方向画15根线，相距30px;棋盘为14*14；- ^& D1 }. y# Y* m" N8 b
         context.lineTo(15+30*aa,15+i*30);
6 [% \$ j2 R$ h9 q: {) M0 j3 N          context.stroke();
9 Y. ^! T3 ?: W- ~       }# d& B$ y: Z8 ]7 U$ y
}
3 |$ t! N6 W) [$ N  U( b9 b' q drawChessBoard();//绘制棋盘
/ m7 r& R7 D* o# g4 d  r+ q
/ {" C& u9 Z5 Z! m0 l" W! y //    var mymap=new Array(36);
! A2 N+ R2 x$ W/ _6 C# a //    for(var i=0;i<36;i++)
. W/ r3 v. _# s; Z1 @9 s* ` //    {mymap=-1;}
5 I! N1 q; [! Y& Z, Q( b5 U0 m/ c3 W: a; Z3 C- c7 t4 k' Z8 r

& Q4 u) A" C9 O! L% N0 S1 ?  </script>
3 R- N9 y, ?! k</html>9 Z- K" V6 H2 L! C, Y: Z
6 {$ W" X$ r7 W, a0 t6 c, @

  f+ N. @6 I8 v  Q  f* v8 P实现效果
! n/ {! o7 F" d* a& H

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

9 _7 k1 y! G5 o+ ~) ?6 S& K
画迷宫# z6 s" R; n& S

0 T/ a6 r# \( Y- f3 _随机迷宫怎么生成？怎么搞？一脸懵逼。
4 [; F! g: Q2 Y8 ?& k
) E' s. E% v. I1 r4 D* X4 @$ B  R' B因为我们想要迷宫，那么就需要这个迷宫出口和入口有连通路径，你可能压根不知道迷宫改怎么生成，用的什么算法。小声BB：用并查集(不相交集合)。0 T9 w6 H, @, b. Z3 o6 p
迷宫和不相交集合有什么联系呢？(规则); `, Q* x  J7 F8 c2 O
3 G$ X. c* @. A' s
之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合)，它的主要功能是森林的合并，不联通的通过并查集能够快速将两个森林合并，并且能够快速查询两个节点是否在同一个森林中！  e% X0 A; k5 |- Z9 X+ \
而我们的随机迷宫：在每个方格都不联通的情况下，是一个棋盘方格，这也是它的初始状态。而这个节点可以跟邻居可能相连，也可能不相连。我们可以通过并查集实现。6 G7 M7 t0 u4 X5 U% b' ^" }* _
/ |6 l+ _( G+ ^
具体思路为：(主要理解并查集)
' e/ G' }0 K/ ?$ C0 R9 F" ^9 y' o3 P& [1 G: [7 t
1：定义好不想交集合的基本类和方法（search,union等）' G; @5 L, z& _
2：数组初始化，每一个数组元素都是一个集合，值为-1. y5 N' k/ I' t5 P; N
3：随机查找一个格子（一维数据要转换成二维，有点麻烦），在随机找一面墙（也就是找这个格子的上下左右），还要判断找的格子出没出界。
8 I  S6 w. B- C3 t* X6 ^6 I  [& Y具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界, a7 v! U2 M+ I5 b3 o1 q! H
4：判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在，则重新找，如果不在，那么把墙挖去. O# g, E7 V, N' ?  v
5：把墙挖去有点繁琐，需要考虑奇偶判断它那种墙(上下还是左右，还要考虑位置)，然后擦掉。（根据数组转换成真实距离）。具体为找一个节点，根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。8 ~2 r% E# I8 x) ^( {4 B3 W2 Z
6：最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙，但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据，并查集操作。二维是位置。要搞懂转化！
, i$ R' ?7 u; T  V% a* n7 H# l注意：避免混淆，搞清数组的地址和逻辑矩阵位置。数组从0开始的，逻辑上你自己判断。别搞混淆！5 r8 i8 ~( h3 {) V

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

5 ~, l- k+ O( _
主要逻辑为：
) f7 t* ^. h4 i$ s9 k1 ?" vwhile(search(0)!=search(aa*aa-1))//主要思路3 F9 ~' Z  m, l8 [: |# B+ @
{3 q' [0 n+ m; [& x  Y( s
      var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
- M. k' L, {0 G       var neihbour=getnei(num);
" z" ~; t6 Y( \" L7 ~       if(search(num)==search(neihbour)){continue;}
! W# T0 y9 P" p' L       else//不在一个上
+ ?# l$ e; @* Y- b+ ~7 g7 Y* X       {
3 A* C- v2 q  T" }4 C& L% W          isling[num][neihbour]=1;isling[neihbour][num]=1;' n$ U. c4 X- Z( v% L, U
         drawline(num,neihbour);//划线
$ S* B) o( H5 r# e  C4 ?' j6 ]          union(num,neihbour);! R( [% p7 X2 ?

8 v$ m( k& r( S/ w* g3 U0 r       }6 K- Q) I( b! Q6 I5 ^2 r& B
}* v1 I4 v4 l/ ?# b( f
' B2 B9 y  U4 p$ o
8 M  C$ y. l, Z! I  M( ^
那么在前面的代码为
/ V, c# x1 V- U- x7 U* T& C<!DOCTYPE html>
) V( H  y6 K% V0 z" [<html>) I3 p. |" A# h7 B( ?/ u3 b
  <head>
2 w# A+ I6 s2 D <title>MyHtml.html</title> # P+ b; W6 s% n( z3 P1 b
  </head> " Y3 o! b5 _) b8 e* D
  <body>
& j  q1 V/ X  u( ]3 ?  <canvas id="mycanvas" width="600px" height="600px"></canvas>+ y2 o: |/ y+ @

  H/ l5 G( j9 c8 @# A8 r4 e  </body>
1 }6 r4 L% q1 z# w6 F- X4 G! W! a  <script type="text/javascript">
, E' f9 z- J. x, H, n//自行添加上面代码
2 W4 \1 ^" ?1 P) O; P& o( I //    var mymap=new Array(36);
5 x$ C. U& K" F7 ?# N4 C8 Q //    for(var i=0;i<36;i++)
# i" f% P) y+ Z& A: ~; k //    {mymap=-1;}: W: l0 e5 A" ]6 k7 }/ p
function getnei(a)//获得邻居号  random1 A  b2 x& J$ I3 [& e* M! ^. F
{
( F# o1 ?8 d: D, [       var x=parseInt(a/aa);//要精确成整数' u5 v8 s$ b+ x- `5 X
      var y=a%aa;
/ `% c; z. D! m! i% j) ?       var mynei=new Array();//储存邻居: ^  `6 b& a- ^: k' ?
      if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点
& ?2 B6 U9 H  C# _9 A7 E       if(x+1<14){mynei.push((x+1)*aa+y);}//下节点
$ N2 P1 `! J" v       if(y+1<14){mynei.push(x*aa+y+1);}//有节点; J- V8 \+ A5 g1 f
      if(y-1>=0){mynei.push(x*aa+y-1);}//下节点
' i: z. _+ E& _5 e( J3 d       var ran=parseInt(Math.random() * mynei.length );
. `5 B2 G" \8 e( D4 i       return mynei[ran];
: r$ {+ L$ m5 l8 ~. P1 A. u9 s# A% v1 n# c& M9 V
}# K) v! j# P3 D* }# H
function search(a)//找到根节点
* k5 r. N  E+ @ {
1 W! I; K5 i: f: x: G' b       if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
9 I% ^* q! x# b3 o% [1 |! J       {6 K, R5 h) r( M0 m
         return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩
: @2 x; ^5 K- y# y* G       }- ^# [4 ~# T% Q; \9 k
      else
7 S) G7 V1 z; v' ^2 i! `          return a;
: i# s* ]9 ~8 m) @* N; F }2 M+ b1 \; Q+ O
function value(a)//找到树的大小
4 G/ g  `( D% W {, L+ k! ~3 `5 n. z' \) u6 [; j# ?
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点/ P1 k( h$ z( M% x6 u% {
      {8 s5 M+ W/ T6 B4 v9 C0 k' [6 G) A
         return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩
. @# {! o) `% O4 }       }
" g  Z; b, i: g$ z       else
" f5 e. d* K) S( Z9 G5 G1 j          return -tree[parseInt(a/aa)][a%aa];
* S, r0 M0 R! a# u0 B4 N }; e  B1 i  r1 N) C$ a# ~  D
function union(a,b)//合并
: G) p' W* [" y( K {9 p0 P# M' f* S3 }" |
      var a1=search(a);//a根* y* f% f) ]% ^3 j
      var b1=search(b);//b根
* P/ W: n+ z; \: c* F/ }       if(a1==b1){}
: R5 x' [7 y6 V! z- M       else
; h7 @1 g/ u8 j5 Y2 C7 ]& Z       {
7 v+ d1 ^1 j/ U7 s( q" S  K1 s          if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数()，为了简单减少计算，不在调用value函数  c" _, \, H0 e. R& K/ s
         {
  n; S6 Z, P1 b; P" i             tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加  注意是负数相加: x" L5 H  d5 K1 K. x! `
            tree[parseInt(b1/aa)][b1%aa]=a1;    //b树成为a树的子树，b的根b1直接指向a；4 t7 Y0 u( e8 I
         }* n& u$ s7 A4 |7 G6 l
         else# p- s0 ]5 {# I: {% K5 i5 g
         {; F4 K. ]; u. \  ~2 G
            tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];3 j5 g# X, |; c) Z, c
            tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树
" B+ C; w- B4 G2 e4 v5 |; C' N# U$ V          }0 r' o5 ?+ C5 y) R
      }
4 U! x7 B& [! o) G; ~" f }7 _# m9 D1 ?* o& o$ r% [6 r& |1 q

* w: a' w" E# w( H5 |1 ] function drawline(a,b)//划线，要判断是上下还是左右
5 ~  Z( p7 {" {6 [/ K- H5 p1 V {! X- e4 H. U% O8 N
7 j1 b; x0 I4 t7 s2 [- w
      var x1=parseInt(a/aa);
, {) T9 {7 [  \/ h" p. ~' g       var y1=a%aa;
9 D; i8 Q% p4 g       var x2=parseInt(b/aa);, }  j8 z3 @4 ]
      var y2=b%aa;
4 F5 a/ B1 W/ l       var x3=(x1+x2)/2;
1 U+ K) w& h3 B9 f       var y3=(y1+y2)/2;
5 E3 U" ^1 o5 q! n  i       if(x1-x2==1||x1-x2==-1)//左右方向的点  需要上下划线
. Z" Z* L# i- z8 |* x! m1 K       {
( o5 X; L, ^/ n          //alert(x1);7 I3 I0 l) Q$ o
         //  context.beginPath();
5 ?6 g2 D/ Y% Q# {          context.strokeStyle = 'white';
  \  Q  x' V& i- v; P7 D          // context.moveTo(30+x3*30,y3*30+15);//
# H( C6 _" k$ P  R+ ^          // context.lineTo(30+x3*30,y3*30+45);  M2 I/ l' D0 H2 _% p
         context.clearRect(29+x3*30, y3*30+16,2,28);" s& Q( L" \- s
         // context.stroke();
: z2 [( ]! l$ t4 U       }
8 E" J# [  V- p/ H9 {# w       else
  Y; G& v/ P+ I5 O       {
$ Z& X; t1 W8 j/ L+ ~          // context.beginPath();7 i7 M  o" t4 \
         context.strokeStyle = 'white';3 E. S1 @5 X& H, s
         //  context.moveTo(x3*30+15,30+y3*30);//
, x+ L/ m& P/ ~$ w          // context.lineTo(45+x3*30,30+y3*30);
( {, s. r* ?: }4 b3 {) t4 F          context.clearRect(x3*30+16, 29+y3*30,28,2);; x3 r5 J7 ?' c* m- W" |8 A7 T! k
         //    context.stroke();& ?: a$ ?4 k9 r4 E" z- o
      }
8 M0 v  y6 ~: { }
4 J+ H! n% j8 o, ?9 ^* F! K, j9 O1 H8 H
while(search(0)!=search(aa*aa-1))//主要思路+ S% v( p# n2 c" M8 I
{
$ q! J1 L! B# n& ~- T       var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
$ y" P6 m4 S" B; ?& y" \       var neihbour=getnei(num);2 b6 \# y4 ^% R! Z
      if(search(num)==search(neihbour)){continue;}
6 l1 ]  j( X7 P& k5 d; T       else//不在一个上
$ i2 E: M  w* Z; b6 w% q       {* G) E  M& R# h5 }! z* g. f! C) Y
         isling[num][neihbour]=1;isling[neihbour][num]=1;9 _% q! F4 n2 g
         drawline(num,neihbour);//划线
* V" j2 i5 W/ b. q* n3 B# r          union(num,neihbour);
5 ?- ^, F4 Z/ y" O& z! o; j7 D7 I# V% _$ Z
      }
% G0 o# R6 }: ?4 F }7 J; N1 f+ E- O( ?
  </script>! s* I( w4 w6 U) J
</html>  O/ S  ], V, P2 }6 R. a$ v
) H* u6 A) N* F. w- D

5 n7 T2 v$ T3 J) t1 a$ X4 R实现效果：
& A' m$ r) [9 n, [, |/ P( t4 H; L/ K) n+ R2 L4 w" B& ]2 d. t

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

, k) J, W1 i7 d: c. D9 a  l
, }8 B; `2 _7 v/ f2 `# p

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

' \0 Y( w* P0 z5 H方块移动/ w' o7 S) m7 X3 d! n

  `1 C  L* _) j3 y( ^& M这部分我采用的方法不是动态真的移动，而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉，在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除，可以根据像素大小精准擦除。
: h% T0 S$ Q5 ~! U7 A" a1 }  u
) E: Y1 g% z; A+ K! ~) h% D另外，再移动中要注意不能穿墙、越界。那么怎么判断呢？很好办，我们再前面会判断两个格子是否联通，如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组)% c% W( d$ q% C  ^6 o( {- C

# ~% w' N9 n4 \2 A' t% g" A5 j另外，事件的监听上下左右查一查就可以得到，添加按钮对一些事件监听，这些不是最主要的。5 G3 ?" g& h- \5 ^9 P2 W. W

: S/ M+ G, e& h" p8 e为了丰富游戏可玩性，将方法封装，可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外，如果写成动态存库那就更好了。/ u' T* @7 K- G; ^2 l+ E% r

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

# }$ K, k) @0 M' b( h# h( E% E
# f9 Q2 Q5 d+ b  }1 U, z8 \

: n( {" ^4 W5 @+ z) B————————————————
" E" r1 ^) t5 ~8 \: i; W版权声明：本文为CSDN博主「Big sai」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。! F4 S% j- S+ j. X* x% v6 @
原文链接：https://blog.csdn.net/qq_40693171/article/details/100716766
, Y) ?7 v: L: n! \' Z
1 o1 r2 r9 }* D- G$ ?/ g7 R% B" D& k0 i2 j- X9 ?! F+ d5 }; t