查看: 2630|回复: 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=[];
. t; e! K8 n  {9 z- I/ [8 v% \       for(var j=0;j<aa;j++){
1 A4 t6 e! ~# \9 ]9 f# i* l5 i/ e          tree[j]=-1;//初始值为0) `; z) P1 i, @1 S* k, N
      }
1 u5 i1 H7 z5 T: U2 S9 b }  for(var i=0;i<aa*aa;i++){8 r* j3 [. T8 v
      isling=[];& _) ~. {' h- E5 H
      for(var j=0;j<aa*aa;j++){
. ]. O/ f3 j$ ]4 t: C5 z+ y7 ?5 v          isling[j]=-1;//初始值为0
. r) g9 W" L; W' Q5 e& w) S       }" ^7 U" s0 L# n' G
}" I' \4 S% w4 _4 G9 `, P
) p5 ?0 V' G1 G$ X* G* S0 ^
function drawChessBoard(){//绘画9 C- C9 E7 a7 G4 P2 b! |
      for(var i=0;i<aa+1;i++){4 @1 }& b3 {) X: d. x0 w
         context.strokeStyle='gray';//可选区域0 |8 t3 W& E. K0 w+ x
         context.moveTo(15+i*30,15);//垂直方向画15根线，相距30px;( u+ z( x. a, [. j
         context.lineTo(15+i*30,15+30*aa);, Q" I/ ~4 z: n9 d, V6 b
         context.stroke();6 e) _+ U  i. ]4 B
         context.moveTo(15,15+i*30);//水平方向画15根线，相距30px;棋盘为14*14；  n7 s( E7 p; l- ~% }3 z9 Y, ~
         context.lineTo(15+30*aa,15+i*30);
  Z' [1 N4 D0 N( V          context.stroke();* Q+ T4 Z2 _$ P  i1 T+ \+ _
      }/ m8 Y6 N# Z6 ?6 a5 }: T
}, _# P: {+ I% B3 N* M8 V
drawChessBoard();//绘制棋盘
: a. A5 x+ C* U9 J: t( j( @" H2 h5 e7 V4 N1 \5 K3 I( Y2 X2 h
//    var mymap=new Array(36);' B  b0 Q: E1 I, Q& X4 y' S
//    for(var i=0;i<36;i++)6 u$ m. o. l/ F: a/ A2 `
//    {mymap=-1;}
8 z$ [& f& D/ t8 L! S. \% u- ~4 C' X! ^/ Q# l# w
( Z5 q5 g$ X( d
  </script>) [0 C/ {; a  }/ x
</html>
+ \9 Z' J, W# A8 o3 e) Q
$ M% x6 z+ e# u/ C/ N% ^* O) E5 K3 ?# N' |+ c1 p: e0 B2 o5 c
实现效果& j) e" e7 N7 G  m8 x) v! M% k) l7 E

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

) @" l3 I# u7 d) [
! w! I8 }* L( `4 Z画迷宫
) O+ g! N; J, N- J3 Y! J: z
% ]& ^0 \+ p7 e4 O6 Z% `& |; c0 F随机迷宫怎么生成？怎么搞？一脸懵逼。/ o/ w, l0 ^: y9 B; h

! G. a7 i  N8 A3 k因为我们想要迷宫，那么就需要这个迷宫出口和入口有连通路径，你可能压根不知道迷宫改怎么生成，用的什么算法。小声BB：用并查集(不相交集合)。
0 b: D! h, J+ v0 G& T8 H迷宫和不相交集合有什么联系呢？(规则)
9 d$ i6 C( v- l* E$ J
3 W6 {* {! R6 k. F8 \之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合)，它的主要功能是森林的合并，不联通的通过并查集能够快速将两个森林合并，并且能够快速查询两个节点是否在同一个森林中！; D! G( y( M( C; m: v! b( o
而我们的随机迷宫：在每个方格都不联通的情况下，是一个棋盘方格，这也是它的初始状态。而这个节点可以跟邻居可能相连，也可能不相连。我们可以通过并查集实现。: }5 @. g) y7 a0 i& @; X, n

1 {! f" L- D( n* E0 y3 O) N- u具体思路为：(主要理解并查集)
9 O( n7 e- K" {; _' H% |; q% A7 T& t$ _$ i$ [4 F# v
1：定义好不想交集合的基本类和方法（search,union等）  a# n% h7 u. \( t
2：数组初始化，每一个数组元素都是一个集合，值为-1
# t0 t5 _+ Z) F6 G2 e" T9 u3：随机查找一个格子（一维数据要转换成二维，有点麻烦），在随机找一面墙（也就是找这个格子的上下左右），还要判断找的格子出没出界。" o. u3 p; U  @# i. n( Y
具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界
5 p& Z: _2 k* h* Z; e4：判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在，则重新找，如果不在，那么把墙挖去
" Q6 D. \' @! L$ f" J) Y5：把墙挖去有点繁琐，需要考虑奇偶判断它那种墙(上下还是左右，还要考虑位置)，然后擦掉。（根据数组转换成真实距离）。具体为找一个节点，根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。' k1 }( X% c/ P0 {5 {, _
6：最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙，但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据，并查集操作。二维是位置。要搞懂转化！
! j/ P. A) H$ B) I* i注意：避免混淆，搞清数组的地址和逻辑矩阵位置。数组从0开始的，逻辑上你自己判断。别搞混淆！
, E* P) }9 j( Q' L# j5 j# @

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

- w$ m# \0 @0 v. ~  [) J- w. i' U
主要逻辑为：
- ^. }  u4 q1 R9 A" \+ }: y0 @9 zwhile(search(0)!=search(aa*aa-1))//主要思路/ }" I( M9 u: o. b
{2 t5 E1 w( ~/ i7 A; l" s5 C6 B$ o' y
      var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
/ m+ w, y4 W& e4 w* \: G       var neihbour=getnei(num);& S) A6 r0 F& X' h4 {
      if(search(num)==search(neihbour)){continue;}
! s8 v3 s7 z5 g       else//不在一个上
5 S$ e% D& q* P- x# R9 W, R+ _; n1 ^       {
2 ]2 R8 l* s# l4 p          isling[num][neihbour]=1;isling[neihbour][num]=1;
6 T. p5 D* J% b          drawline(num,neihbour);//划线
9 U8 k+ L8 }$ d+ N& `) h, B- i          union(num,neihbour);
' G( I" ~) R( ?0 Y0 v, L7 s, c" R5 R% F" N5 Z, m$ g0 _& M
      }5 c& U8 K( J& j6 c) E/ M
}: l9 j  a: y7 @- X6 ?% u0 G

( F+ E; i; D1 a
) `" T" Y% {0 r! \那么在前面的代码为
( @! R1 Z4 H7 H, E. t7 F6 r<!DOCTYPE html>
7 B6 {, W2 u# a9 c' ^<html>2 Q/ Y& ]! q1 @" ?
  <head>+ \. ~; u# ?. c3 N4 Q( g2 ]
<title>MyHtml.html</title>
" F* y$ S4 U8 C1 d$ S# G9 t  </head> 2 \7 D' Z! U( w+ Q
  <body>
8 v* \& Z) r; _0 W3 R  <canvas id="mycanvas" width="600px" height="600px"></canvas>
7 V4 s+ V1 _1 o: b# Q/ X; E0 G% L0 c1 ^; P
  </body>+ P! O) N# m) F; t9 F3 t  i* j
  <script type="text/javascript">3 \% `2 _" U+ g( a/ F+ l
//自行添加上面代码
" i/ j" [+ w3 S$ o" x) K/ b8 `$ R //    var mymap=new Array(36);
8 ^6 f+ \+ _) H# _# P* ` //    for(var i=0;i<36;i++)
* {* ?( f) U' B- s //    {mymap=-1;}
: A" C' a" U. D0 Q3 ~ function getnei(a)//获得邻居号  random- H/ D+ w$ R. F
{
: ?8 z# U: Q# R  |9 H       var x=parseInt(a/aa);//要精确成整数
- W# E* N- @6 m0 j       var y=a%aa;
. @8 H" T  M+ R( _9 r. L       var mynei=new Array();//储存邻居
7 d9 v: Y/ X5 S8 _& |- ]0 [) b8 }       if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点
" o2 s* W( D6 w" b; @, F8 C       if(x+1<14){mynei.push((x+1)*aa+y);}//下节点
& a/ X! F5 W+ S) s5 N       if(y+1<14){mynei.push(x*aa+y+1);}//有节点
( \" ^( C+ E. B: v' Z. ^" [( h       if(y-1>=0){mynei.push(x*aa+y-1);}//下节点$ _( f3 H" K1 [8 j  ^4 h1 P/ c" }5 K
      var ran=parseInt(Math.random() * mynei.length );
2 N9 L; C, n& J) i2 z& d       return mynei[ran];( Q) G/ q% u2 d  O/ _1 m
' n$ d" _) D$ [; {( _
}0 `1 U  O; l2 Y) Y7 f
function search(a)//找到根节点
/ C' Y  L/ a7 a2 k {- p  Q* X( E+ z8 r/ o* u
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
" d4 D. I! G! ~% P; F2 a       {! F; t: f- `& _% W2 q
         return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩
2 z5 e+ |! A+ j# [' E# U; C       }
) u9 C( c- \, J$ ~- S" I' G. }/ \+ J       else; J. {! I/ V" m% d9 J# {$ a
         return a;9 e! R" y, s# X
}
; s& Z' z! p, ~$ q function value(a)//找到树的大小9 z+ n4 B; p" y! \! [+ }: F4 S9 P6 b
{
9 _1 x* Z3 q+ m# F! ^       if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
$ ]/ ~1 z. I' d0 S; W4 a+ r       {
/ M) d9 J* M& h2 |: C          return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩0 H3 `1 D# |% @) D1 M
      }9 u5 q( k( s9 @/ v: M3 _
      else
4 f* L6 [: x/ y& ?  [          return -tree[parseInt(a/aa)][a%aa];
6 Y! L( {4 R5 F; Q }
5 `1 r  Z1 n) p. _- i# j1 ] function union(a,b)//合并/ }! s# L& B8 Z0 k
{) k5 q+ q4 m* O; j
      var a1=search(a);//a根
% y7 b' F& l) j2 n       var b1=search(b);//b根
; q$ n3 V! @6 o+ f) T       if(a1==b1){}" q1 l" f* Z2 F9 Q6 x1 \
      else
- z6 M+ B7 _5 {* r  i# Z       {
8 @8 m% T4 Z3 P$ l, i          if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数()，为了简单减少计算，不在调用value函数
- p! Q4 A! r/ U2 O% X. `" ?9 X          {( Q$ h- G/ ]7 d+ y  K
            tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加  注意是负数相加: ~% R* A  }5 S% u. N7 E3 M' q$ a
            tree[parseInt(b1/aa)][b1%aa]=a1;    //b树成为a树的子树，b的根b1直接指向a；/ x- K* @4 ]# ]2 Q: D! L2 p/ v1 R
         }' r$ U* c1 w+ U
         else3 c0 V, G: x7 K7 w4 D8 e
         {
2 y1 l7 d3 L& }, L4 ]7 S+ R: T             tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];
  W* w- v3 |" y! b' B& x             tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树
  y' `& B5 O, K# R          }
, Z  T! `; C: h4 \- ~) S4 Q  A       }
' O7 s- m8 y2 F2 i9 p% ?& v }
1 i2 i# d* c  O! H& h
: T' C- b) W6 g: } function drawline(a,b)//划线，要判断是上下还是左右
# }1 L2 e! K# G; Q- M) S) k {' X; a0 X9 |* v- g
+ C& F3 T. T) u& [8 C
      var x1=parseInt(a/aa);
  \% u1 M) w, s- f       var y1=a%aa;
9 J% s9 i) ~/ ?) W+ r       var x2=parseInt(b/aa);
8 U, T9 y" _; Q! n( ]+ t/ \! r0 }       var y2=b%aa;       7 |, I1 C; q$ m: {
      var x3=(x1+x2)/2;8 G/ E5 z; m4 K  u8 E
      var y3=(y1+y2)/2;7 i, `% k. [5 Q) w' C' k& I
      if(x1-x2==1||x1-x2==-1)//左右方向的点  需要上下划线0 i% w2 [( z' A6 S8 k9 E2 f
      {. k- d9 p* [% I
         //alert(x1);
9 Z) S, J# B* c, n3 @- ^          //  context.beginPath();2 z5 ?3 l& ], v
         context.strokeStyle = 'white';9 H9 ]3 y4 k- t( M0 X* v
         // context.moveTo(30+x3*30,y3*30+15);//
& S& G. H4 M  P4 U: H0 g          // context.lineTo(30+x3*30,y3*30+45);
# M4 m1 L6 J0 J5 X          context.clearRect(29+x3*30, y3*30+16,2,28);
6 x! ?1 \* L8 E) W. O+ j          // context.stroke();
7 I. @  x0 R' _       }+ H! h0 U6 E# L4 i3 a2 K% E; N: K
      else
) q" i; N" e* m, f       {: W6 }9 c( v- x: I# d( Z
         // context.beginPath();: ^" ~& m. Z& ~2 d
         context.strokeStyle = 'white';) o! t; I/ S+ r4 X% _' X" d% h
         //  context.moveTo(x3*30+15,30+y3*30);//
5 z' T2 S$ I, K+ m          // context.lineTo(45+x3*30,30+y3*30);
( g7 ^( i* o1 a9 U" A& o          context.clearRect(x3*30+16, 29+y3*30,28,2);
: J4 ]. e$ S; R3 i. e6 z% ]' f          //    context.stroke();
" I6 P* Q8 C% @5 o3 q; L* ^! }       }8 [1 G- u8 r1 y2 m
}8 ^( ?+ R* Z* N# P* B  m/ ^
- x4 e/ Y  F/ }( C% z
while(search(0)!=search(aa*aa-1))//主要思路; B; h) p" P3 l- J$ _3 ~2 u
{
. Y* @$ A& B0 s2 P9 ^* [" I5 I       var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
; H4 K$ ?/ j0 ]7 V3 E+ ^       var neihbour=getnei(num);; l; @- `# X4 R, G1 v0 n  z- E
      if(search(num)==search(neihbour)){continue;}
* X7 G! {  }7 r* h       else//不在一个上
9 H' Q- r' d$ H/ D4 T# d       {
3 U$ p2 @# {  {          isling[num][neihbour]=1;isling[neihbour][num]=1;, o, @8 ]6 m9 r; \# @
         drawline(num,neihbour);//划线" z2 X9 r" h% Y4 N- _: i
         union(num,neihbour);
' R& G3 ^& l" p) u/ ~$ }
' }6 Y# D! l* F+ \- u# q0 C       }
/ @5 C; S7 y0 F }
+ _$ t  E# ]/ ]3 _  </script>6 Y5 H7 L5 i5 P" o2 H
</html>
# }4 c/ E& c2 C( u0 v3 c: F/ i$ k# A
  F9 I1 m* `: e9 ~/ f
实现效果：, J% ^# A& Q: N+ G( H0 _( H
$ m, }/ s, d# M

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

# g# k: _7 u7 s) E7 k0 D. ]: e9 l& U8 z* b8 X: }+ q' a9 A

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

. ~3 V+ K! c0 O8 }
方块移动
& H) D: n- m( ]5 v7 c3 F) k7 i* n4 ^2 s( j% S
这部分我采用的方法不是动态真的移动，而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉，在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除，可以根据像素大小精准擦除。
7 d. _- {8 ?- \! |
+ T2 c' y6 M/ m0 {另外，再移动中要注意不能穿墙、越界。那么怎么判断呢？很好办，我们再前面会判断两个格子是否联通，如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组)9 s: S. Y. F/ j1 W7 l4 ~; c+ ?, K

# Y$ h. H/ w/ C+ F# x  c. V9 v另外，事件的监听上下左右查一查就可以得到，添加按钮对一些事件监听，这些不是最主要的。
1 r; P* V+ Q# O6 p# v1 y  P( H+ u. K6 c$ L% Q, N4 h% z
为了丰富游戏可玩性，将方法封装，可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外，如果写成动态存库那就更好了。
' c+ B' m3 e1 `3 l$ b% m3 R

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

+ t) H4 }9 E2 `8 `2 |6 v6 k
, }# g, I) Z, m
# Z7 `$ [% C1 r& x
————————————————9 Q% k& N4 [* ~/ C
版权声明：本文为CSDN博主「Big sai」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。. t# y" M6 y7 O( Y) |: U' w! k
原文链接：https://blog.csdn.net/qq_40693171/article/details/100716766! T3 N/ E+ a, O6 ?
# h$ ^0 d$ r! {, R$ @6 _# _. @  o

. J( P0 G0 `8 b1 Z5 M