查看: 2629|回复: 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=[];3 _: S7 H, k& _
      for(var j=0;j<aa;j++){
7 h+ \2 S; u. q" J$ H1 A          tree[j]=-1;//初始值为0
2 T; D* c0 _' r$ O       }
6 H% c% V8 `9 n1 e }  for(var i=0;i<aa*aa;i++){2 H# Y  y9 _( `* [5 H
      isling=[];- H" `: Z. z8 Z  ^! U
      for(var j=0;j<aa*aa;j++){
/ M+ a* t$ Y8 p1 F% U0 b          isling[j]=-1;//初始值为03 S  o4 u" L5 H0 e/ Y$ K
      }) o  _% f6 c# v- }! x
}
: P! x0 }3 F3 g; B, @) Y- U" [. v7 a( R/ V# O( a
function drawChessBoard(){//绘画$ T* a" n5 O& c' P
      for(var i=0;i<aa+1;i++){
' w6 z% c, J8 g& e& _          context.strokeStyle='gray';//可选区域0 @7 f! m( |$ f( t
         context.moveTo(15+i*30,15);//垂直方向画15根线，相距30px;
  B! W. ?& b9 r6 I2 N          context.lineTo(15+i*30,15+30*aa);- Y% Z$ m6 P- @
         context.stroke();
- U8 [4 r  Q+ v          context.moveTo(15,15+i*30);//水平方向画15根线，相距30px;棋盘为14*14；1 g" C* Q: t! t: a4 ~' K! m% a
         context.lineTo(15+30*aa,15+i*30);
; s. i, z3 Y3 o* g          context.stroke();
3 p$ o2 i9 B2 f$ i: f- X$ O8 n9 N       }
/ B# ?5 u5 x9 I4 x9 @( y0 C0 z( g3 ] }; A' D, m5 x- k9 b- q6 c. n
drawChessBoard();//绘制棋盘
7 h- C# m7 ]3 X& n) h* d4 B
3 g+ D. L6 C/ U& E/ L! f( c$ w% c //    var mymap=new Array(36);# V' ]4 H8 x6 Y( d: w
//    for(var i=0;i<36;i++). |: |( [3 v3 O5 n: m9 k
//    {mymap=-1;}/ m) @( X2 n  g+ g

% J  o5 g/ t$ g: G  `8 L* P1 d3 d2 O- C% ~$ I5 b$ e8 E
  </script>) i: W1 t( u. b: D& V5 m: o
</html>
# Y  L! \# M" i0 t% F; g+ J( r0 i8 H& j" e
' t1 t9 K7 T+ X: K& L' c9 j
实现效果: {7 V% _6 ]1 O- w5 q2 @0 n

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

. U3 j2 N% l; G- [! ~  m
! {  B$ w/ Z) H: Z- x7 C
画迷宫8 o7 J) ^8 n) F7 A

: F, e$ F5 R, A, I( ?$ n1 J随机迷宫怎么生成？怎么搞？一脸懵逼。! h/ W$ b" M  C7 w9 n+ P8 s

3 Z7 c/ I9 e2 b- d) b5 D! y* Y因为我们想要迷宫，那么就需要这个迷宫出口和入口有连通路径，你可能压根不知道迷宫改怎么生成，用的什么算法。小声BB：用并查集(不相交集合)。$ h: r6 k7 C6 C9 i: |4 l
迷宫和不相交集合有什么联系呢？(规则)$ \3 R1 q$ B2 H9 m6 }& g

1 d3 U* G# |1 b9 B/ Y: G! \1 v6 k7 G之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合)，它的主要功能是森林的合并，不联通的通过并查集能够快速将两个森林合并，并且能够快速查询两个节点是否在同一个森林中！
5 K; I5 J0 P7 k2 R2 H而我们的随机迷宫：在每个方格都不联通的情况下，是一个棋盘方格，这也是它的初始状态。而这个节点可以跟邻居可能相连，也可能不相连。我们可以通过并查集实现。
& H, d6 z: `8 ~5 ]6 O, L2 N
- h9 R2 y4 |1 T; f/ z具体思路为：(主要理解并查集)
, W9 [  p9 W5 @$ _  E/ m' G# p
' U5 O- U- x9 I$ G! p5 `. l# `0 {1：定义好不想交集合的基本类和方法（search,union等）
- J2 ~1 F" C9 E+ C/ n5 D2：数组初始化，每一个数组元素都是一个集合，值为-13 s& c6 O( M9 y" y$ y
3：随机查找一个格子（一维数据要转换成二维，有点麻烦），在随机找一面墙（也就是找这个格子的上下左右），还要判断找的格子出没出界。
# L, r1 e0 W- e) _  V( ]$ ~具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界6 m8 I/ S' C* c* u& P
4：判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在，则重新找，如果不在，那么把墙挖去& y+ P0 _2 M/ B% X
5：把墙挖去有点繁琐，需要考虑奇偶判断它那种墙(上下还是左右，还要考虑位置)，然后擦掉。（根据数组转换成真实距离）。具体为找一个节点，根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。
" d* Z# T8 y1 w% b6：最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙，但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据，并查集操作。二维是位置。要搞懂转化！
, m# {4 ]4 B7 k# ]注意：避免混淆，搞清数组的地址和逻辑矩阵位置。数组从0开始的，逻辑上你自己判断。别搞混淆！
$ h1 ^) o; x$ V& f3 C$ P: j

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

0 u) `6 x5 H" X5 e9 z主要逻辑为：
9 b* U' M: `. |$ c. zwhile(search(0)!=search(aa*aa-1))//主要思路
1 p) U4 V: q* S3 |" [/ H {
* H) H. I# X+ D7 u, c       var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
) e, e8 H6 v$ c( W. X& @1 o       var neihbour=getnei(num);& z% A- c: ]: [& B$ T) Z
      if(search(num)==search(neihbour)){continue;}
, X" {" `/ \8 Q4 K& f! i       else//不在一个上
3 ^8 B' a8 }9 F* F; F       {9 w9 u, g5 Y7 C* X; K# a
         isling[num][neihbour]=1;isling[neihbour][num]=1;5 ^  p. ^; g: R  R
         drawline(num,neihbour);//划线$ T! O& L% `9 \( j
         union(num,neihbour);
  o3 K8 m" ^) V" B8 g+ N  s) ^/ C) l3 X  F
      }
: L8 x& Y  Y2 k! v9 I; x# N }6 w  M1 J% ?/ R7 c
  {% v. l. n- E1 A1 p
) x+ N- M: f2 Z
那么在前面的代码为1 _. F1 f# ^0 @9 t# c
<!DOCTYPE html>
" Q2 s0 q0 A& D+ o<html>
! U0 q! t' V7 m/ M  <head>
$ F3 }  V9 u- }4 I! Q. o& m <title>MyHtml.html</title>
  `+ [0 L, U- _  </head> - L! H* ^, f4 k# c# M' U9 q
  <body>
4 Z: ]" |! {0 n$ t1 T. f1 a+ w  <canvas id="mycanvas" width="600px" height="600px"></canvas>+ N: j' J6 [' Z2 E+ Q# N# B
$ w/ F8 w5 e4 L7 X/ E1 T
  </body>9 m6 A2 H6 _! n$ t( e: x& P9 \
  <script type="text/javascript">
; O6 }( o: H0 Z! U3 X3 U//自行添加上面代码# ~& g4 `# ?; G" v7 E
//    var mymap=new Array(36);6 H. h, ^. \1 h7 ~) \/ a$ ~$ P
//    for(var i=0;i<36;i++)
6 m$ |2 w* Q7 s9 C //    {mymap=-1;}
) u, e$ f$ L- i( l function getnei(a)//获得邻居号  random. T! @3 n6 T: D7 X- x/ ?
{. O+ B; U, f& ?* S/ a
      var x=parseInt(a/aa);//要精确成整数* S/ d1 u& y, ?' J. \4 j
      var y=a%aa;+ i: E2 I% w1 b1 [' n; I$ p
      var mynei=new Array();//储存邻居0 T! v8 C4 g; i' w
      if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点1 b7 d/ z8 ~# T1 C2 m" Y0 T! E
      if(x+1<14){mynei.push((x+1)*aa+y);}//下节点3 V& ?- ]- x8 e& d2 ~6 n
      if(y+1<14){mynei.push(x*aa+y+1);}//有节点
$ B- ~! b' c' B  Q' f% ?$ N) P       if(y-1>=0){mynei.push(x*aa+y-1);}//下节点
& m0 B, @( O: _- o2 u# q7 a, j4 I$ o       var ran=parseInt(Math.random() * mynei.length );
9 b, z$ `2 h: S2 w2 n9 l, d       return mynei[ran];5 t: n  K/ n' j) V  V

, |$ V; R% m1 Z! } }7 c- J" t9 v- q+ W% T( x
function search(a)//找到根节点
% `9 I# J  X3 A/ D. |: x) t: c% l4 i {* i' n/ R- B5 R& g. V
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点& r$ C0 k+ C: ?$ i
      {
8 @4 D. Y1 ]' N1 N. X          return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩
- K+ P3 m+ Z+ P  v- [/ a       }
' Z. K6 m4 s' n7 p3 s0 [( v       else, h4 T; _" p' M. M  B+ u% \
         return a;
4 f8 u4 o0 N0 t+ K! ^2 c/ x! s }
8 p4 H7 ~+ |. o/ v function value(a)//找到树的大小# u# R/ b5 N# V. a5 Z
{5 E& W  e: z; h$ ]$ S( H8 m
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点1 i& ?4 u4 x* B9 b
      {/ u4 f/ Y: ]& w$ i6 B4 p4 @
         return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩
( M2 i8 p- e6 W, r       }: M% P6 F$ Z- $ q  E  a! S& I8 o
      else
. j; m, c: W9 ^: \9 s3 b  K          return -tree[parseInt(a/aa)][a%aa];& O# Z- l$ Y5 F# H1 G4 E5 ]) \
}# z1 u7 w. X, v# I+ $ r! i
function union(a,b)//合并
6 v/ @$ J' X7 ]. [% x5 B {( b8 t1 m' c. B& H0 n' j; i2 `
      var a1=search(a);//a根5 o3 i9 e8 \. r! f# u( h% V, h1 o3 y
      var b1=search(b);//b根
4 E% \) Q9 }1 J       if(a1==b1){}) ^/ G4 ]. L4 i, o0 ]7 V& j
      else
( H% I! y, \# b       {8 Q, @; L  g: A
         if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数()，为了简单减少计算，不在调用value函数" O2 Z9 n& k$ Y
         {
+ C5 |( c! U' [7 ]             tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加  注意是负数相加
4 e1 c1 x, v4 }             tree[parseInt(b1/aa)][b1%aa]=a1;    //b树成为a树的子树，b的根b1直接指向a；4 P2 l# V! Y6 v0 S& w: q- O+ l
         }
  U7 F: ~8 e) P- x8 r  o3 R" i          else7 ^2 x8 x/ |! ^, A) ?& U6 T; R
         {
/ x4 F$ Z. G1 G; Q8 m) F' M# B: {( e             tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];1 e$ M2 t+ Q5 U2 y$ I0 R
            tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树
0 X7 O, f0 L) J% q2 m+ j          }6 v" S$ I, _  P, r. k
      }: k9 B1 ]7 ]  x5 x* Z2 ^! H; j% w! M
}) q% H# l+ v! B: e4 k* Z+ ]
* Y. \3 j, |, X" U" z# I/ l
function drawline(a,b)//划线，要判断是上下还是左右4 \& ?4 {/ H, Q# S( ?- a
{
1 R' M0 f* \. a9 Q# B; V0 ^3 r' y4 n0 S3 D9 u8 ~
      var x1=parseInt(a/aa);
) n5 N6 X4 L8 q& ~. M9 ]4 `       var y1=a%aa;/ q& U9 d2 \' ]+ N' A, x+ c; q
      var x2=parseInt(b/aa);
  H* ~1 V5 @* H: K. d! S       var y2=b%aa;       5 D8 M1 {7 @' N% Z
      var x3=(x1+x2)/2;
6 r: m+ {8 F9 X' ]" U' p, c       var y3=(y1+y2)/2;
' ~( [; S; ?- L1 v       if(x1-x2==1||x1-x2==-1)//左右方向的点  需要上下划线
  `) ^. A* n. f6 M. _* o       {: V) z6 S7 I: B% i% I3 H4 `; T& S
         //alert(x1);
4 D( t2 B' q- ~          //  context.beginPath();  r0 A7 Z. n$ U( l. h+ r7 F" @& m
         context.strokeStyle = 'white';
+ x5 \- N1 I( l4 y" G2 k: F" T          // context.moveTo(30+x3*30,y3*30+15);//
0 u& A) R/ i  O$ V          // context.lineTo(30+x3*30,y3*30+45);
7 J5 R" q8 Q$ H7 @+ o) Z' P3 S          context.clearRect(29+x3*30, y3*30+16,2,28);
3 M# T) n# V" D' ^( O          // context.stroke();
; A0 J, p3 G, e: Z4 c6 X" T- G  x% {       }! u* O# e4 t2 d+ c- K; d% F) ~& M
      else! z  u; q1 P0 O# z0 v& N
      {4 V  k/ M9 I+ U- I; ^
         // context.beginPath();
& \6 s1 @( O; ^) |: f0 O          context.strokeStyle = 'white';
* F2 F, J( Y8 U( q9 u          //  context.moveTo(x3*30+15,30+y3*30);//* g, x1 ^1 d$ S3 n8 i
         // context.lineTo(45+x3*30,30+y3*30);7 @- s5 m$ e0 D8 V: E# c
         context.clearRect(x3*30+16, 29+y3*30,28,2);
6 k& [8 \4 Z; H- j" ^$ o) ]) C1 O- f          //    context.stroke();
0 l: }6 g  |. p" l       }6 A' o3 H/ _& X' v- g$ g
}
/ w+ R% D& `$ g( B/ k6 Y
2 X  d6 Z" J* P while(search(0)!=search(aa*aa-1))//主要思路
; `& G) ~' N  B+ Y' v3 ^ {+ C0 G% N7 F- R3 ?
      var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数- ^- I: o6 Z$ c  Y
      var neihbour=getnei(num);
; `5 I' E6 \; L$ s9 B       if(search(num)==search(neihbour)){continue;}
) [# J' z! b# U( L# A+ U       else//不在一个上8 Q+ H! f- y1 j* N
      {4 d4 V4 E+ m: y( n
         isling[num][neihbour]=1;isling[neihbour][num]=1;4 z" X" i1 |9 B5 y' @
         drawline(num,neihbour);//划线
6 C* `6 i9 I/ I  v5 J          union(num,neihbour);
' Z( p! ?3 C, B  V8 C! J1 g
* Q9 X, p4 E7 ?       }- Y& D; ?- S8 L+ u* _4 b# p
}
* y! P4 u* M1 Y+ \4 @( Y7 k  </script>- {% S+ H& L: e6 ?
</html>
6 r" O; {4 n, z; H  A0 v$ o/ Y8 ^+ {6 b0 s& L6 _1 g
% N- ~. }  ~( E- a
实现效果：
# g7 c6 w# w4 I7 n5 H- f1 n& {% e3 `

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

9 f8 m3 _/ I, D- K

, }8 J4 \$ W9 w9 Y; M/ B( v

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

9 |; m# P) `0 l/ s* _" ?1 W6 u方块移动
" ~/ O# }' [% [2 L( h% w! K; _2 I% t7 @/ n
这部分我采用的方法不是动态真的移动，而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉，在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除，可以根据像素大小精准擦除。
, }8 ]8 W; q$ R, _  }: R& V- B: T8 H* p  g5 ?" H
另外，再移动中要注意不能穿墙、越界。那么怎么判断呢？很好办，我们再前面会判断两个格子是否联通，如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组)+ ~9 k8 c' w( S' i+ C( H  Y, S* k

5 `+ ]8 V+ _; Z. U. P- @' R另外，事件的监听上下左右查一查就可以得到，添加按钮对一些事件监听，这些不是最主要的。4 Y# H& W4 A0 E9 S9 F+ [: ?
  D7 s: ~( w2 G( S2 G9 M4 I( L
为了丰富游戏可玩性，将方法封装，可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外，如果写成动态存库那就更好了。% O0 v. B4 C9 g' [" o8 @1 Y1 p" @

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

# ?% u/ M+ w0 y7 ?6 A
. x) f) k' R# u0 J

/ G/ I" f$ m4 b, D: G( v————————————————$ v. q( P: \4 C
版权声明：本文为CSDN博主「Big sai」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
$ t+ w7 @% F* s+ E; J2 S9 v8 d# h原文链接：https://blog.csdn.net/qq_40693171/article/details/100716766
& [4 R5 @6 }( e4 s- d6 `( s4 e4 `0 ]) n1 s7 u" d) x0 g  K

( d  A$ {$ |+ E- x  C& v* z