查看: 2398|回复: 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=[];( u- j" b! o2 I/ R% h. S) R, t
      for(var j=0;j<aa;j++){
; i$ x/ q" j& P+ g% a          tree[j]=-1;//初始值为0
1 d) f  N, t; ~; }& \0 K       }% ]9 H$ V  q. q9 S
}  for(var i=0;i<aa*aa;i++){; V7 F3 f6 m$ l8 |9 Q: b* X, Y2 b
      isling=[];7 ^* G* {! [( i4 @/ z
      for(var j=0;j<aa*aa;j++){( W* _% H) X# d" c
         isling[j]=-1;//初始值为0
! ]" N3 ]! v; a& `8 M0 w       }+ J4 J: W5 j/ u6 t0 p
}, p/ u. M9 I- @! f# h8 u; b
" a, q0 [3 g+ F; Q" S" U# g* n3 D
function drawChessBoard(){//绘画3 w1 o, `) g8 z% c" Q* s
      for(var i=0;i<aa+1;i++){- ], m$ c/ \! W, w  T7 ?9 i
         context.strokeStyle='gray';//可选区域
. y, n. x# V* q          context.moveTo(15+i*30,15);//垂直方向画15根线，相距30px;
. L! Z: a# N" [: ~  I          context.lineTo(15+i*30,15+30*aa);3 z% o7 m) ?9 ?5 F& l5 c
         context.stroke();
! ~, q! g3 n0 X: I          context.moveTo(15,15+i*30);//水平方向画15根线，相距30px;棋盘为14*14；
; _) U4 e2 @$ x: A# S          context.lineTo(15+30*aa,15+i*30);" y& z" E7 k8 x  ]
         context.stroke();
% h. ?2 Q! h- O       }
5 y& f( A; D1 y8 t+ m3 r }
3 Q$ z: z+ {6 d4 Y/ y; C drawChessBoard();//绘制棋盘1 S& N! M7 }! N1 q6 A

$ C  o- t$ f. ~9 l //    var mymap=new Array(36);% V7 L; h9 Q4 _% p: Y: O1 ?& Z
//    for(var i=0;i<36;i++)
0 K& I& ?4 x; [ //    {mymap=-1;}) P# @! e5 Q' X- H7 S
, B9 _" q# v: O7 {" d4 T1 G
( X, A% c, g! P: A) j0 j( ^% c* B  U
  </script>
4 K! f# S0 K! Z/ q' B: p3 C</html>
- M0 o  ~' Y% Y/ o, o+ h& S
; R5 y8 d, U! S5 F( w' u" b2 D/ ]5 o2 `; Y9 B* c9 C' D
实现效果
0 Q/ ~& }1 A5 g

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

. j2 H' Y- M5 W9 ?, K$ N0 W$ J: U
6 \2 }; J. o4 Z. H: \* Y
画迷宫7 v! p; j) r1 X8 D
' y9 L6 f2 B2 M/ a4 j" R" A" Q
随机迷宫怎么生成？怎么搞？一脸懵逼。) a- k4 S& `. m$ I8 x! v$ f

* r- P4 r  t0 V* ~* ^因为我们想要迷宫，那么就需要这个迷宫出口和入口有连通路径，你可能压根不知道迷宫改怎么生成，用的什么算法。小声BB：用并查集(不相交集合)。
# b2 t, Q6 `$ ]1 o, J迷宫和不相交集合有什么联系呢？(规则)
: C% e9 H: J$ h7 @7 k, l
2 ?. a& H6 M  j: ?2 V0 e% B; h9 P之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合)，它的主要功能是森林的合并，不联通的通过并查集能够快速将两个森林合并，并且能够快速查询两个节点是否在同一个森林中！- u8 d$ p; {" j/ L
而我们的随机迷宫：在每个方格都不联通的情况下，是一个棋盘方格，这也是它的初始状态。而这个节点可以跟邻居可能相连，也可能不相连。我们可以通过并查集实现。1 W: B+ [7 K8 L) R. ^
# H+ @1 I1 O7 T0 m: h4 n6 f( r
具体思路为：(主要理解并查集)
+ H3 w3 m, ?: ~2 y+ s; ]
% E" d& d# i7 P# G& r# P1：定义好不想交集合的基本类和方法（search,union等）
2 S5 J0 K& u2 i/ g  o2：数组初始化，每一个数组元素都是一个集合，值为-1) ?4 X' C" s4 E
3：随机查找一个格子（一维数据要转换成二维，有点麻烦），在随机找一面墙（也就是找这个格子的上下左右），还要判断找的格子出没出界。
# ?8 c4 \  b4 S7 P9 f0 k4 @具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界
4 s4 j3 G' `* Y3 A- ^7 p- w& p4：判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在，则重新找，如果不在，那么把墙挖去  C5 F. E: h3 D% r/ ~
5：把墙挖去有点繁琐，需要考虑奇偶判断它那种墙(上下还是左右，还要考虑位置)，然后擦掉。（根据数组转换成真实距离）。具体为找一个节点，根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。8 |+ M( V4 U. L  r
6：最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙，但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据，并查集操作。二维是位置。要搞懂转化！2 r0 @  O0 n( @! b
注意：避免混淆，搞清数组的地址和逻辑矩阵位置。数组从0开始的，逻辑上你自己判断。别搞混淆！5 I+ }" G: }. c2 ?

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

' S$ R2 z7 c- h主要逻辑为：$ o6 P1 p1 |! b+ w' F
while(search(0)!=search(aa*aa-1))//主要思路  y6 N" X* r( e. R( x5 e/ n* t& V$ e
{; Q! v6 U+ K# x# s. R
      var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数2 N- X/ Q  M3 {; n% d
      var neihbour=getnei(num);7 @9 E" V) }1 w
      if(search(num)==search(neihbour)){continue;}7 s& W% `" I4 l5 o7 c& Y9 ^
      else//不在一个上
' x) D) y( m  Z       {/ _. p- V# K3 Y  L, l" |1 {+ k! d
         isling[num][neihbour]=1;isling[neihbour][num]=1;
4 Y2 y0 r! r& h- `          drawline(num,neihbour);//划线- I2 w9 ~4 S$ n$ Z
         union(num,neihbour);; R0 e8 s! q8 x% |# t2 V0 \
; k! {4 w8 C" u; {4 G
      }
" z8 ]' I# E- _% F8 L2 r }
/ k' |' k( Q: [% J, v" j# g5 i$ o
- j# U2 B0 [2 k1 D( Y; I+ `1 Q# h' w: T7 X9 v; K+ v0 y2 r
那么在前面的代码为
* F$ p+ c6 M7 l1 o. @6 ~+ G<!DOCTYPE html>4 e) ^) Y, _6 s, y6 b( \' ]+ `
<html>6 p2 u9 C4 M: T
  <head>
- {2 \' }3 u1 a, C- _& I <title>MyHtml.html</title>
9 ?/ F/ h% N5 p9 u4 i& B8 N( J. z  </head> ( S% X5 ^- D9 u
  <body>
9 o2 J# s; ~4 E! j  <canvas id="mycanvas" width="600px" height="600px"></canvas>$ y. x4 S. Q% ]

! Q' a# |! \5 A: x+ h  </body>& f' m' b; }' @4 @
  <script type="text/javascript">
7 E2 M0 E% E3 C$ T; V//自行添加上面代码
0 ]' y3 r/ K! C3 K) O$ N1 X) S( v/ Q //    var mymap=new Array(36);
* I% P2 Y2 h0 ^: V  k" z7 Y! T //    for(var i=0;i<36;i++)# I3 j) ~2 \4 l
//    {mymap=-1;}
- D. R& V; D: r4 N: J function getnei(a)//获得邻居号  random3 v* ?, c7 ~1 \6 A
{, _" |6 \5 ?4 m  O, Z! ~6 _
      var x=parseInt(a/aa);//要精确成整数3 q) n$ L) b$ c* T( D
      var y=a%aa;& `: J9 I0 U% j2 {0 O! ~# Y% T' z/ C
      var mynei=new Array();//储存邻居
- X) U  a3 X# ?. E; G5 J* u; j       if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点- t3 k1 N9 {0 j+ e
      if(x+1<14){mynei.push((x+1)*aa+y);}//下节点0 d( E& o; w+ }+ Q6 ^5 I
      if(y+1<14){mynei.push(x*aa+y+1);}//有节点' K7 U. @2 j) W. m; @1 v* U3 I( c& Z
      if(y-1>=0){mynei.push(x*aa+y-1);}//下节点
" ^' ]' H7 q) `, T       var ran=parseInt(Math.random() * mynei.length );4 V" j  S! M* L+ F2 X" s+ |3 c, a1 e
      return mynei[ran];
" ~# E& G2 M% }$ L0 _/ i, @
$ m. J, U3 G* f, w6 K# ]) [/ D }' ^1 j2 P1 z( s' t# d5 ~
function search(a)//找到根节点5 z5 t8 f. X8 o  ~8 b9 ^" g2 z
{5 B9 y4 ]  }. n6 ~2 ~3 s
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
* r; {9 r; ]" o+ r7 D+ L% A; @, @- h, U       {
4 V% g0 P% Z' H, Q+ v3 m* J& }- c; f          return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩
; x  m1 E) P5 A0 j' e% ?       }
* x) Y, [0 i. h( D       else
9 {8 S) E6 y: F/ [5 z          return a;
6 i0 r+ }  t! M  ~ }8 g7 C- e. t' i% i, ~4 r
function value(a)//找到树的大小! I) Y. n, X2 B5 H) ?. i+ H' [
{6 q8 J( `$ a9 S$ w* M% x; b
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
, [9 P! }7 |% @/ ]       {
. ^6 O& H- j- E/ q- B2 ]          return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩
" m8 L7 k/ z: j0 a, `* x5 a       }$ R  g; |1 B( P8 g% W9 |
      else
& k; B3 u) E  X: y          return -tree[parseInt(a/aa)][a%aa];" |& W/ V7 U9 a
}- P/ y; s5 P8 R! x# f  n
function union(a,b)//合并1 r( A2 i% S7 [3 y/ m% D2 D
{) p6 o1 \1 u3 o/ d
      var a1=search(a);//a根
/ O( K0 r2 m1 r       var b1=search(b);//b根
) t0 F5 u" \$ ^7 d       if(a1==b1){}: I' O* J- \% p2 Y. i, [- |* t, ]
      else0 i& J' J% b  }/ }4 Q9 N
      {$ G1 G1 S/ o2 K. I1 ]; A; e6 B/ g
         if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数()，为了简单减少计算，不在调用value函数
2 c4 {# T# s9 [' s          {/ {# c4 ]) A7 h! H* q
            tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加  注意是负数相加
+ @( d* V: R5 E; S' _             tree[parseInt(b1/aa)][b1%aa]=a1;    //b树成为a树的子树，b的根b1直接指向a；
: e4 D, e4 G- ?3 R: m          }8 j0 j1 Z+ t: \% c* t
         else' L# B! u1 Q: g, Y: `% ?
         {
" G7 T4 {" s: Q/ s+ j. V             tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];+ y8 u6 X  u1 l3 S, q* t4 P
            tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树3 [) T9 P% R/ A. Z+ A6 H
         }) e5 n; ?5 S5 v) @' }$ R
      }' ~* s7 o/ T8 @; c
}' S9 o) V& ]) Y, ^- @

6 U( b* ?- S) k  l function drawline(a,b)//划线，要判断是上下还是左右4 L" p% |" r" ^9 x9 k( Y$ }' {
{2 L: ^$ N0 `" f6 s4 N& H3 o

, H- G6 p) A4 Q' |8 Z6 x2 N" }) P       var x1=parseInt(a/aa);
4 P* p6 y* S8 ]% l9 J7 [/ g       var y1=a%aa;
& n* Y+ x( G) g0 s" F       var x2=parseInt(b/aa);
- T9 {5 z' R2 V8 e- r       var y2=b%aa;       : t4 y7 S3 T$ i4 v, Q) O
      var x3=(x1+x2)/2;
! w  B3 {: B- U       var y3=(y1+y2)/2;
# g& G0 q0 S! w, N$ u! `5 D3 T# Z& ?; x       if(x1-x2==1||x1-x2==-1)//左右方向的点  需要上下划线7 R6 {: N  j& c5 s! x* ^( b& V
      {; h3 I% T- e; F' G  a  P8 g. Y
         //alert(x1);
. L( ]7 m- A6 u9 _3 k& ^7 N          //  context.beginPath();% u8 d* r. p5 C- v) z& [$ [7 z! Z
         context.strokeStyle = 'white';
6 q# x: ^! u- T" b; T) }4 s/ ]          // context.moveTo(30+x3*30,y3*30+15);//7 K5 q1 O3 W. h' y
         // context.lineTo(30+x3*30,y3*30+45);& }" p# o$ K9 l* P& B, D
         context.clearRect(29+x3*30, y3*30+16,2,28);: R# S  ~$ X: a+ x3 d1 R
         // context.stroke();
$ k8 @" l4 ^$ U8 ?8 y* R- @       }4 w/ `& y7 O4 [& ?$ u  u. [+ h/ y
      else8 A: p) C9 Y' \% u2 A4 V( G& P
      {
, G. t! E5 U0 W+ N# d* w" t5 `          // context.beginPath();
+ e. U! ]4 Q( ^- J          context.strokeStyle = 'white';
7 T3 f" z, t# z/ N4 S8 v1 p          //  context.moveTo(x3*30+15,30+y3*30);//9 J5 Y6 K8 j6 S
         // context.lineTo(45+x3*30,30+y3*30);
. {9 [. q$ g5 J7 e6 m/ ?          context.clearRect(x3*30+16, 29+y3*30,28,2);2 b+ `+ s/ E* x& ]. C/ j
         //    context.stroke();8 m  W+ q% {+ J) u( O# v
      }
% X0 ^0 s, g3 h% ~/ j7 g }; J7 d6 l  c. }' I" ?

  o+ B# k% |. T while(search(0)!=search(aa*aa-1))//主要思路
7 ?0 e) N9 T) y2 i$ U {6 D/ j+ D- T! @) o8 I( |0 D
      var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数( L9 k; }% b; f+ Y/ M7 Q& L
      var neihbour=getnei(num);
      if(search(num)==search(neihbour)){continue;}
7 K3 V) C& Q  v# S- c9 u       else//不在一个上
; F) G. B4 }# A8 c       {# f$ A) v$ Y) `/ L$ Y" O
         isling[num][neihbour]=1;isling[neihbour][num]=1;9 `. p" t6 q- ]* G2 _# H
         drawline(num,neihbour);//划线
% [: K8 \/ E9 g% U" K: S          union(num,neihbour);) B1 Q8 O' V6 m- ?* D; Q
4 `+ X# E0 t. D8 L! }2 O! B
      }
1 `( Q" W# u" F" [/ m* s1 n }
$ E1 s3 {- N) R! b  </script>4 a7 O9 L6 }1 z; G9 T
</html>+ a* R, F' ~/ c2 m

: }% O  @% r7 A0 J5 k) Q
4 \: C+ d1 x) k$ b实现效果：& z& O; U: a( I& X6 g# U) b! l
1 ?* x- Y9 G3 q' h$ ?

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

: I6 x8 {& [# H0 N0 `6 `$ F5 g. D6 A* B4 }$ B! R. }" T& W2 t, z' ^6 ]

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

# {( R6 U# x6 q
方块移动" k$ L- f% I  P, y' D, {# P
  T0 d% j$ P& n4 f* j. G$ {5 A7 c7 [
这部分我采用的方法不是动态真的移动，而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉，在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除，可以根据像素大小精准擦除。: L4 D- t, s; |, |* V' c7 b* \2 N
( O/ n" p8 j  s. n4 q
另外，再移动中要注意不能穿墙、越界。那么怎么判断呢？很好办，我们再前面会判断两个格子是否联通，如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组)
$ c/ v" p8 G9 X% A
0 g: W+ S% |' u另外，事件的监听上下左右查一查就可以得到，添加按钮对一些事件监听，这些不是最主要的。$ D0 {5 _; X9 v0 Q" d5 [2 A
) t( Z1 y2 x1 O, T
为了丰富游戏可玩性，将方法封装，可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外，如果写成动态存库那就更好了。
% ~5 j8 i, |8 w1 l8 `

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

& m% W, j9 n3 G$ D

2 y: `0 {7 Y4 ^8 k% K& |5 ]5 c$ _+ l6 _: t" b3 _
————————————————
1 z4 ^  Q& A5 K7 r版权声明：本文为CSDN博主「Big sai」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
/ j0 _- c  h. l. M原文链接：https://blog.csdn.net/qq_40693171/article/details/1007167669 [1 M; p  E* Q- o

$ F6 b1 }( o# z% o7 K) K, ~4 Y, Z1 F
. a, c! i4 q$ t6 C" T# q