查看: 2550|回复: 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=[];
4 f$ {: w! z2 S1 K# j       for(var j=0;j<aa;j++){
: Z" Z7 n+ M, [          tree[j]=-1;//初始值为0
) p7 ]7 y$ l, ~* z6 `/ W+ c2 g       }
. C5 Z* K3 P. q. } }  for(var i=0;i<aa*aa;i++){9 S. G) u; G; @# u; J# }4 ~
      isling=[];/ |6 U  `: \$ S9 m$ R
      for(var j=0;j<aa*aa;j++){+ l. I5 q: r1 [& [
         isling[j]=-1;//初始值为0& W) W- g) x5 O0 m3 n+ y
      }
' H+ p) m6 Y2 L& y }
$ q  d# u# s: H0 ?0 @$ a+ T: Z
* c3 }& ?% t3 ~) m function drawChessBoard(){//绘画
7 v6 X7 L6 {8 T$ v7 T8 C6 }: ^3 R       for(var i=0;i<aa+1;i++){, H2 D( h1 {1 u3 {$ q
         context.strokeStyle='gray';//可选区域
( o) H& l# E! B' L9 W, b          context.moveTo(15+i*30,15);//垂直方向画15根线，相距30px;
9 C1 N5 Z& B6 K1 p          context.lineTo(15+i*30,15+30*aa);4 e# L8 V3 |9 S' M* y& }+ {
         context.stroke();! [: Y6 E7 p! E$ @7 o1 X
         context.moveTo(15,15+i*30);//水平方向画15根线，相距30px;棋盘为14*14；& Q$ K) W8 @+ p# K/ Q2 j/ Q
         context.lineTo(15+30*aa,15+i*30);. Z  p, ]3 C: P9 b
         context.stroke();7 V' n( z$ V) ]% j  |, N
      }- D! o6 A# `( o5 H$ R; w1 _
}
; J2 H+ l5 i, w+ \3 L. s& j! c drawChessBoard();//绘制棋盘
: {) M$ z& ~, |) k* h; `; W
, Y. o! S$ v3 {, m9 V: @$ ^; U) O //    var mymap=new Array(36);
. a7 ^% P( L1 C3 n# f //    for(var i=0;i<36;i++)2 d3 i0 l7 e2 C/ `) H' `
//    {mymap=-1;}
, K" u" C; r+ q8 v
1 H% ~7 P' j- ^
  F% |  G1 E- q: A9 Z3 Z, s3 k2 H  </script>
$ @5 e# [- Q, X# q</html>5 ?) `: l  ^+ P; M! ?# Q

$ `( O4 Z( ^9 o" X: m5 a9 G" W
7 U# l& J; B( T; X8 N8 A2 a实现效果
7 F' g1 \/ Y% ]

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

2 W$ j, Z( S% L. C3 r3 s
& |$ F' Z$ {$ d: A% x+ _. n! O; Y画迷宫$ z8 I3 O# t. W+ G& V! _0 \

  v$ G! e3 V2 A9 C) {1 I, j/ x随机迷宫怎么生成？怎么搞？一脸懵逼。
  G* u$ a2 \' |! I) }1 j, b6 p% U/ G( P1 X  q( h5 o  p4 e
因为我们想要迷宫，那么就需要这个迷宫出口和入口有连通路径，你可能压根不知道迷宫改怎么生成，用的什么算法。小声BB：用并查集(不相交集合)。) K; E) U$ Q0 u
迷宫和不相交集合有什么联系呢？(规则)
7 W' a% j+ I# H2 G
+ x5 i2 y: s- q+ q" y之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合)，它的主要功能是森林的合并，不联通的通过并查集能够快速将两个森林合并，并且能够快速查询两个节点是否在同一个森林中！
$ i* O: Z8 h& i7 H而我们的随机迷宫：在每个方格都不联通的情况下，是一个棋盘方格，这也是它的初始状态。而这个节点可以跟邻居可能相连，也可能不相连。我们可以通过并查集实现。
2 G# C% f" L: E9 `: ]9 D' R: I  X% i3 X% [
具体思路为：(主要理解并查集)
  k* D7 j! Q2 k* J8 T/ j
: ~2 o; T) D. b3 m+ L( P1：定义好不想交集合的基本类和方法（search,union等）
. o4 @6 h4 c, F' H+ b) T& {2：数组初始化，每一个数组元素都是一个集合，值为-13 }" R$ v/ i8 k  u, F! g( A: l
3：随机查找一个格子（一维数据要转换成二维，有点麻烦），在随机找一面墙（也就是找这个格子的上下左右），还要判断找的格子出没出界。. R" ]' `( M9 x
具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界" ~: V3 L  f- N! P
4：判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在，则重新找，如果不在，那么把墙挖去
9 T6 C- I% Y9 F5：把墙挖去有点繁琐，需要考虑奇偶判断它那种墙(上下还是左右，还要考虑位置)，然后擦掉。（根据数组转换成真实距离）。具体为找一个节点，根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。: J3 E! w4 m5 t8 p% d" R$ ?" z
6：最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙，但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据，并查集操作。二维是位置。要搞懂转化！
4 Z3 l6 ?7 A9 y9 N5 G注意：避免混淆，搞清数组的地址和逻辑矩阵位置。数组从0开始的，逻辑上你自己判断。别搞混淆！
( S! I; h9 E  ^# a6 k$ O

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

* n1 O2 D4 w  I& D. w. ]. k3 F主要逻辑为：1 P6 }8 t% J1 ^5 h/ _# Z+ E3 |
while(search(0)!=search(aa*aa-1))//主要思路
6 U* Q, x9 K1 @5 q0 X2 q1 i {2 I) P6 z% t; E: `+ |- O3 y2 m
      var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数4 T' b3 @. ~9 j7 X
      var neihbour=getnei(num);3 c! k; n4 _/ d- \
      if(search(num)==search(neihbour)){continue;}& C+ e$ |& ]. i: L1 A
      else//不在一个上
; _8 ]) p! W( w+ O- V       {* {/ ]$ Y" O9 Z# F7 k
         isling[num][neihbour]=1;isling[neihbour][num]=1;) x+ b0 o0 V# p/ s- G( t# R% k
         drawline(num,neihbour);//划线
1 [( l: P5 P, ~% C! `          union(num,neihbour);
: }; q: A  U+ T. i+ q! V- N) o) L4 d1 f' k) `0 ~! p* P
      }
* a3 N% H, b; M }9 n! U. _3 i. I+ N& @; c9 r6 Q9 B
9 f# H& E, P/ @; l/ i+ i6 ]

4 d: d! C5 O4 ~" m: y6 Q那么在前面的代码为. y( P6 L# S0 o. b( O1 {
<!DOCTYPE html>. d& [  G6 c$ R9 ]' [
<html>1 @1 s' G6 G8 l( E# k
  <head>
" x9 i$ F7 u$ b  o' U/ N- s. a: B <title>MyHtml.html</title> % k- I: P; Z, R" v+ L
  </head>
8 m0 P, I: H/ Q3 c6 {; ?  <body>; {) i3 Z1 E+ t+ C3 |2 j
  <canvas id="mycanvas" width="600px" height="600px"></canvas>0 q6 d& i! U7 v8 e
  X& U" U& e/ V
  </body>. ~- M- O- q5 O2 L2 n; @/ f
  <script type="text/javascript">
( ]9 O! v1 V* t, ^( O4 b//自行添加上面代码
1 C5 l2 L3 K/ u& U //    var mymap=new Array(36);
8 X) w0 A& Z( f9 [/ F6 s //    for(var i=0;i<36;i++)
) m; Y$ Q: j1 h. q //    {mymap=-1;}
, _. w1 g/ i# b' {  j5 V2 E function getnei(a)//获得邻居号  random. Z( b) q) a% y( c+ }: H& r! G! @# ^
{
! ~) i: S$ W, [8 w( A5 q       var x=parseInt(a/aa);//要精确成整数
( d+ g9 Z6 k; o       var y=a%aa;
8 H% q8 p2 G, t5 J# E* z       var mynei=new Array();//储存邻居
, q+ Z$ J5 B8 }* m8 D       if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点
) U/ e! ?! h4 B& D' K       if(x+1<14){mynei.push((x+1)*aa+y);}//下节点$ l7 W, I' f2 m5 \: e0 c
      if(y+1<14){mynei.push(x*aa+y+1);}//有节点' l+ @) V  p9 R' C
      if(y-1>=0){mynei.push(x*aa+y-1);}//下节点
: M/ @7 m' H) L9 T9 b( Z       var ran=parseInt(Math.random() * mynei.length );
9 L. O/ f) R# W, {$ ^0 p  K. b       return mynei[ran];
+ }. L8 y- g/ I2 b+ @4 l' l4 F8 [/ @* v
}
# g8 e: M3 d7 `6 V function search(a)//找到根节点4 ~& P- u7 ]) T! z* n0 E1 W6 c; \
{: `( f! r9 s, u  o# O: V0 y' d  w
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
: B  v6 k2 k" |4 Q; p$ O       {; o- O" b: @! ?3 z% }; b
         return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩
" ]3 E" @3 m' J       }8 S2 w. i, F# r2 d
      else$ ?5 O- H! e+ ?5 R; w6 D* e
         return a;
5 H7 h& r* L, W# J/ h6 l }
* `9 D( @5 h+ W' l. T% X. r function value(a)//找到树的大小, g' c1 ?, Q+ K  M( l; d3 l
{
- O8 H/ y+ Y! W% X% w) q       if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
, s, L% [! Z( i- l+ {/ A- O       {
! X6 }' j5 i% d- d! `  [          return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩
* r, G0 H/ d7 {* H6 U1 V       }5 p% N% d% H7 g" A3 M' i
      else; a0 _; M& ^9 K4 f$ I+ x
         return -tree[parseInt(a/aa)][a%aa];
: u9 v, @; x4 M }2 r& \7 N* g: y- J
function union(a,b)//合并$ _( |: }6 e: ?6 Z
{
8 t0 Y1 t  {2 O, n) B7 @  n8 A5 [       var a1=search(a);//a根
! k# O: Q: K  v$ _4 ?0 f5 |- Z       var b1=search(b);//b根
1 t; U& X8 ~7 t" O3 N) N       if(a1==b1){}
0 d) v2 A6 z3 c9 D& @, r  s! ~       else5 A( ]8 q4 O5 a8 O* _' G: z6 k' s: d
      {1 D, N7 f! w: s- ?$ A
         if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数()，为了简单减少计算，不在调用value函数
: c$ e7 p) y. X2 N2 z0 J5 t          {7 g3 ^' ?( u4 k2 j. m
            tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加  注意是负数相加2 O- ?8 s$ @5 g" v% r& d7 D
            tree[parseInt(b1/aa)][b1%aa]=a1;    //b树成为a树的子树，b的根b1直接指向a；+ l5 W% Y. T- J- w$ A# f
         }$ Z7 t9 X; p( Q. [) E8 Z
         else/ L3 [2 t$ Q  R+ r# i! O+ w! u
         {
5 e  C$ O9 W% w9 i# I% C             tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];  L: [4 F9 l: h2 J( r4 j( h2 s. L
            tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树
; D% c' o; i% C( P          }
4 l& z3 M7 P9 O& [8 q8 f' Q' e8 ?4 Y       }
$ z5 T* \8 Z& |. G }0 ]& I; s9 G, M8 U/ N. A

) J8 t" Z) b3 w0 B" Q* t& I function drawline(a,b)//划线，要判断是上下还是左右6 u( v/ f+ S( q5 s( P
{
# s+ j% t  j1 p' d+ I. w
3 y6 T) i0 `+ l  q# ~4 E       var x1=parseInt(a/aa);
% l2 W: t, _! X# t( _7 m2 J: I       var y1=a%aa;1 c" H1 t7 M7 E. ^: G' ?/ o: `
      var x2=parseInt(b/aa);3 {$ C5 W& Q7 G1 j
      var y2=b%aa;
% h$ E# [1 N* L3 L       var x3=(x1+x2)/2;8 ?3 {" s* M; z/ y
      var y3=(y1+y2)/2;' u$ |7 Z0 V4 |. m
      if(x1-x2==1||x1-x2==-1)//左右方向的点  需要上下划线( b5 u2 X8 y  U8 `: [1 p: F
      {
6 f8 e# ]2 N  z9 g" W  h) h          //alert(x1);
: [5 k% m9 G6 h+ [# n          //  context.beginPath();* i& j' E$ @) {& J
         context.strokeStyle = 'white';
+ M* b+ Q) p0 Y# n$ P$ V+ U          // context.moveTo(30+x3*30,y3*30+15);//! t2 a* @; P. |* q! ?4 W8 Z+ W' ^
         // context.lineTo(30+x3*30,y3*30+45);
2 s1 O8 u: Z( u          context.clearRect(29+x3*30, y3*30+16,2,28);
* z# h9 S/ \, r. Z2 x          // context.stroke();; s( [$ ?" a) O( x- l
      }
  u9 o: g; E5 ^       else  [  B( a. y+ h3 e
      {% n2 J5 C% c4 i% }  @& W# K+ o
         // context.beginPath();
  {; V/ e8 {0 r, D- {& G5 I          context.strokeStyle = 'white';; `! o1 `+ \. G9 G+ J1 X, D
         //  context.moveTo(x3*30+15,30+y3*30);//
! W. Q" d" Y6 r3 B8 E          // context.lineTo(45+x3*30,30+y3*30);
- F6 k6 v/ X7 Y+ T/ q( V8 [          context.clearRect(x3*30+16, 29+y3*30,28,2);1 {+ z" y9 c$ A: `( B: C. G
         //    context.stroke();
7 X" f; [. G* a) }$ K6 J       }5 R/ |( W# r3 v+ j$ F" ~; V
}% L( U/ h) N* `2 {  }) E5 E: a
6 Q+ b! G% ~; Q# L$ {1 b
while(search(0)!=search(aa*aa-1))//主要思路: f7 M0 H  _; U1 Z
{
# @% v1 {6 ^3 i5 T$ l       var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
8 K) _0 Q+ [/ O! Y       var neihbour=getnei(num);
      if(search(num)==search(neihbour)){continue;}
+ S4 w3 L8 j! o0 u; z       else//不在一个上
* R, [* G  r4 u$ k       {
2 l% a" \, L' [: r5 I3 u          isling[num][neihbour]=1;isling[neihbour][num]=1;. b$ h1 Z: v" P( a8 X
         drawline(num,neihbour);//划线
% w. \/ p5 Y. w0 V8 N& ~7 k          union(num,neihbour);
0 y- Z9 f/ s' |3 L( M8 S: z
: }- Q. L& f! B* ?8 o9 _       }( |4 ]' ^6 }3 P
}
. C+ U4 c; g7 M2 N9 q  </script>
! Q* N% W# S' P% N4 K- W" R</html>. m, M7 h# l, W0 U2 j8 }  e
0 W1 P) m% N: @& }

  _  Z; E& R: b6 _" a实现效果：
% ?' y9 E  g9 t9 |( o$ i' r
# `5 _) ]7 a* [( X0 s

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

$ k4 K: F0 ]) E9 j; ~# f/ L0 ~. p$ c- t5 U: Q8 j

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

) D+ _! R. ~% r- `& M方块移动# H: \! D% ~1 ?$ a" P  u$ m' D
7 H7 k) r6 z3 N3 i
这部分我采用的方法不是动态真的移动，而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉，在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除，可以根据像素大小精准擦除。. |' [/ _  l; x- i( w, h

! V6 Z4 N/ ~  ?+ r  z* u6 p另外，再移动中要注意不能穿墙、越界。那么怎么判断呢？很好办，我们再前面会判断两个格子是否联通，如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组)
1 h7 g3 W* c) S# S$ m: d4 L3 _/ a8 C- ]6 U- N# C
另外，事件的监听上下左右查一查就可以得到，添加按钮对一些事件监听，这些不是最主要的。, a1 j/ Q5 a- E% C1 P$ V  e" I
) J& ?% r' Q# M4 R
为了丰富游戏可玩性，将方法封装，可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外，如果写成动态存库那就更好了。
! h3 _$ x% P& o  X5 X, U. J  H  o

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

8 q( Q9 @6 ?6 A3 l$ j* W: F2 P7 V; b4 n2 @) W7 i4 N3 i* [% N

# r/ E7 n4 n4 g% d4 i————————————————
. j1 [4 O6 V8 n) ?0 K版权声明：本文为CSDN博主「Big sai」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。& ]2 }( w4 {0 x
原文链接：https://blog.csdn.net/qq_40693171/article/details/100716766: W0 @7 P+ k6 a: f! g+ b. i3 h: \
  Z5 `2 U( r' c9 g- S7 z

* o% P4 B, o; l+ b) u$ W