查看: 2606|回复: 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=[];- Y* `; W( ^2 e' Y0 D# }
      for(var j=0;j<aa;j++){
2 u& Y# W2 r, J# [/ I% f: f# n( I          tree[j]=-1;//初始值为0( _& g+ u- s& U6 x3 O
      }8 I0 U6 S8 x1 j$ b1 j# i' I' x
}  for(var i=0;i<aa*aa;i++){
& D+ F) C- V; T& L' n& m       isling=[];8 ~% K: t" Z4 G+ k6 B) j
      for(var j=0;j<aa*aa;j++){
  a, m# w/ ]' C5 O& R$ c2 C* O          isling[j]=-1;//初始值为0/ E9 `9 K( e) k' M1 M9 E
      }
9 {4 E9 j" \3 |8 P# n* @! ]+ i }
8 v( P# W! u- @& ^/ z+ d/ b+ |
5 y* u6 t+ ^. R5 k function drawChessBoard(){//绘画
1 h9 D. Y* K- M9 k5 u, J       for(var i=0;i<aa+1;i++){7 z/ N+ Y7 k# Z: {2 C9 n
         context.strokeStyle='gray';//可选区域
/ u# _8 W# Q( S          context.moveTo(15+i*30,15);//垂直方向画15根线，相距30px;
) h/ [6 z0 v! M# @1 X* Q) x          context.lineTo(15+i*30,15+30*aa);
. h. q+ Z$ ~9 N3 a. L2 ]5 e* q          context.stroke();6 P/ P0 b$ E$ E
         context.moveTo(15,15+i*30);//水平方向画15根线，相距30px;棋盘为14*14；' \+ g* r6 ?$ w: T1 O; R
         context.lineTo(15+30*aa,15+i*30);, l9 O' v% p8 e
         context.stroke();
" w6 B2 i' _) a. w2 [% f5 J       }
% F! U$ ~3 Z9 S: V7 z }
9 @! Q/ Q) s  k$ {8 E# E7 O$ | drawChessBoard();//绘制棋盘! u3 M' s6 K* k/ ~6 d$ m+ V

- D$ q' r' R# T1 ^% Y" K //    var mymap=new Array(36);
* ]9 J& x( y' ~2 X$ N" S //    for(var i=0;i<36;i++)& x$ w8 F3 F6 G( G: N
//    {mymap=-1;}4 N+ v# j9 M3 C
1 c' t5 @; F" P. J) a  _

5 R' `. C! }5 e2 e/ m  </script>
+ B7 ~6 l& Y2 b# W( N1 q. C" D. m</html>
1 P3 Q7 j( U1 u  v: M6 |4 D+ }. n) ~7 \; r, y7 v6 m. q/ I
6 L: J) X! e+ ^1 Q' f
实现效果

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

9 e( ?$ c- t; E: ~6 W+ ?9 @, B

6 g. b8 A" U2 d0 D+ {画迷宫/ D; |2 ]! d8 [+ ]
" c% h5 Z; L$ `0 a
随机迷宫怎么生成？怎么搞？一脸懵逼。
% B4 \! ^: Q/ H- m8 Q
; I4 v7 ^2 o1 e4 g( p- }8 R4 T( K, ~因为我们想要迷宫，那么就需要这个迷宫出口和入口有连通路径，你可能压根不知道迷宫改怎么生成，用的什么算法。小声BB：用并查集(不相交集合)。
5 |6 h" c, @9 Y( q7 o迷宫和不相交集合有什么联系呢？(规则). c$ n0 ?# M  C2 x' y9 [& r

+ h3 M- i1 c, ~9 }之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合)，它的主要功能是森林的合并，不联通的通过并查集能够快速将两个森林合并，并且能够快速查询两个节点是否在同一个森林中！: N' N4 E7 Z9 V" _; ~7 h
而我们的随机迷宫：在每个方格都不联通的情况下，是一个棋盘方格，这也是它的初始状态。而这个节点可以跟邻居可能相连，也可能不相连。我们可以通过并查集实现。7 x& `* w4 Y3 a2 M& J

+ P7 q5 J7 |2 Z1 }; @具体思路为：(主要理解并查集)
# L3 [& k9 G7 f6 Q, i* M) p8 s4 ^+ ]
1：定义好不想交集合的基本类和方法（search,union等）. t; h3 g) m9 x
2：数组初始化，每一个数组元素都是一个集合，值为-1
. I& S/ J: |4 d7 W# Z: ^' b3：随机查找一个格子（一维数据要转换成二维，有点麻烦），在随机找一面墙（也就是找这个格子的上下左右），还要判断找的格子出没出界。
$ u  P- e4 K" t0 D2 \9 {. S# ]具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界, s: K9 g- O' [; N% }+ H
4：判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在，则重新找，如果不在，那么把墙挖去; n3 ~! I; C0 k+ I2 y* y
5：把墙挖去有点繁琐，需要考虑奇偶判断它那种墙(上下还是左右，还要考虑位置)，然后擦掉。（根据数组转换成真实距离）。具体为找一个节点，根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。
- |4 ]( W: o4 H: w6：最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙，但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据，并查集操作。二维是位置。要搞懂转化！
/ q! Y. Y0 y3 D6 i5 \注意：避免混淆，搞清数组的地址和逻辑矩阵位置。数组从0开始的，逻辑上你自己判断。别搞混淆！
. j- L) o& B: W

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

1 \( l  T: z+ @6 G, J$ D/ C: h/ w) @主要逻辑为：
5 R6 W* f+ k$ Hwhile(search(0)!=search(aa*aa-1))//主要思路
/ r* U% y. _. N7 P {6 E! M7 Z+ K: v
      var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
2 n! L6 J4 I: Y" g8 O       var neihbour=getnei(num);
' |% ^/ A1 f0 m' P6 A# D/ f& a       if(search(num)==search(neihbour)){continue;}* p+ L9 o3 w3 E# P9 M3 l
      else//不在一个上. t9 a! T5 v+ Y* P
      {
2 r& `2 b9 n6 o          isling[num][neihbour]=1;isling[neihbour][num]=1;/ y9 [5 q7 b+ A3 `
         drawline(num,neihbour);//划线: ?) W$ K; i7 W: E% }/ v7 b
         union(num,neihbour);
$ \9 n2 s+ x& u) D1 W# h5 x  B; e6 f
      }: V8 ?- m1 K4 r! e0 P2 Z
}
: H9 ]3 \2 c% f. \. I
, |; d8 p* h0 h6 b$ k8 ?8 g# P* R) C7 o8 A1 N
那么在前面的代码为
' T* F( T9 S8 g( ]8 M1 ~<!DOCTYPE html>
0 A$ }. l% q( t) b<html>
* m" l! J* \. ]; Z  <head>- v0 d6 B' r) r: }; [7 s
<title>MyHtml.html</title> 4 x/ A3 [% _+ d
  </head>
6 v0 ^* f2 T9 _  <body>
! d3 e4 }* ~7 ^  <canvas id="mycanvas" width="600px" height="600px"></canvas>, D" ]8 q; K0 i9 x2 A( s0 T

/ b' [' _( a& M0 B  </body>
7 z0 k0 b2 B: r  D: R  <script type="text/javascript">
5 U% [& r$ k' e& o( w/ U//自行添加上面代码
& Q8 s$ H7 Y/ t* p/ V9 e2 L //    var mymap=new Array(36);
# t5 m. C: @& v" s7 Q; a: M //    for(var i=0;i<36;i++). \- m  F) ~5 e6 u4 V$ w
//    {mymap=-1;}  i( B, k" C2 R- W. T# c
function getnei(a)//获得邻居号  random
/ s% c6 A3 b- Q& f+ Z {+ m  K7 k# W6 R+ _$ K& U
      var x=parseInt(a/aa);//要精确成整数
. I, ~4 ~6 Z7 r/ g% G       var y=a%aa;
" s8 U( D- @# y4 U& }       var mynei=new Array();//储存邻居
7 ]3 `# g) r# y% D- B$ I       if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点
/ G' @3 R* k* g  L: I" T. N$ \' U       if(x+1<14){mynei.push((x+1)*aa+y);}//下节点& ~1 v) \. @6 G) {9 [) I
      if(y+1<14){mynei.push(x*aa+y+1);}//有节点
) ?$ F3 j; ]% E       if(y-1>=0){mynei.push(x*aa+y-1);}//下节点
% o9 R* d, ^6 ~8 _" Y+ j       var ran=parseInt(Math.random() * mynei.length );
* m! H$ O1 B' I3 i       return mynei[ran];
3 c- J$ ~" I7 R" y$ m0 Q1 |3 r5 H; a( y' |/ _
}
9 Z7 ?% s6 w- u& u$ i function search(a)//找到根节点. w) `# H; a+ T
{5 r( D1 a2 R8 u$ L9 f! K6 ]
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点# d3 D. }9 f( \
      {
6 p3 M7 O: h- }          return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩
; W: B4 m  g9 [% `( n7 a+ v7 Y       }
3 W* z5 u+ f( J1 ?% G$ h0 H  |       else
0 D4 v' u7 X+ v# d          return a;
* K7 ?$ j( l0 r" K' ]. o% L. g  L2 G }
- \% a: l# x1 o$ a( |  m' N function value(a)//找到树的大小9 ~$ C* |* ]4 j
{( D% S+ {0 Q) T  o  f8 \
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点1 p" \3 E5 Y$ ~0 `  m$ ?' s$ y
      {
% c# D: a4 A8 k% S. p          return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩
; J1 Z- i: I" y- Z9 H, W' e       }: a8 k7 l$ K& d7 A9 M
      else
; k9 S' @  h/ B$ D. v6 g: ^          return -tree[parseInt(a/aa)][a%aa];
( i+ a& ~5 c" ~8 h4 r' \ }
) R2 z9 Y8 s9 Q. T; d% m function union(a,b)//合并0 v( u* Q. y! W' g6 W5 ?
{6 a0 W, y" g* e$ j" @
      var a1=search(a);//a根
; q) D# b7 ?3 P- |( D       var b1=search(b);//b根
+ x( K: @6 L& W2 r       if(a1==b1){}
( P+ n4 m( c  N9 h( s/ U3 W7 {+ ^! [       else
+ L& R9 U! j/ u. `( T' L1 i! N       {$ o, a2 H5 k* w: U* e
         if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数()，为了简单减少计算，不在调用value函数
" t/ v9 Q6 `" N* v# W  n+ b5 s$ _          {, K  v* o, \7 v8 o$ T: j
            tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加  注意是负数相加
; G- x5 ^' z# M# n' A% S  z             tree[parseInt(b1/aa)][b1%aa]=a1;    //b树成为a树的子树，b的根b1直接指向a；
* R* d( M; F6 U- n# \          }
+ K& E) a5 l( w. X; S. ]" V          else
# I8 V2 C: J$ N          {
; _, S3 _, i: I% z% C             tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];
+ L5 Y6 ]/ S5 U4 w. T             tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树
/ Y# W, o* E4 {: S- u/ U          }
4 E8 Q' {9 Q' U1 Z, c! v' S       }& h/ a- ]( d: ]6 C7 [
}3 C9 O3 M/ G$ k

5 u0 _2 u! l; U3 g; g function drawline(a,b)//划线，要判断是上下还是左右
+ c8 h0 p4 }0 L( a5 Q8 i% R# b {
4 g7 n% b0 F0 h5 E3 A; r' j8 E! G  \# S6 c4 a7 q  g; s
      var x1=parseInt(a/aa);
5 t6 }) D( k) Z* e: Q2 x       var y1=a%aa;
% n# y) e; B' z- _/ v) E4 ~       var x2=parseInt(b/aa);  e+ Y9 r3 z( L; J
      var y2=b%aa;       0 w0 F4 ]7 D: H) o' K
      var x3=(x1+x2)/2;
7 A, x' Z; e$ D; v/ C! f+ x5 k       var y3=(y1+y2)/2;; S. a) q' C$ `/ Q6 v5 w  @+ i
      if(x1-x2==1||x1-x2==-1)//左右方向的点  需要上下划线
( x# M' D$ j5 _( v% J! a       {
0 _8 ?* w2 ~( C+ S% P$ ^          //alert(x1);
( ^& [0 R, B8 @! w8 e          //  context.beginPath();# p6 ^6 z8 G6 x0 y7 N' @  X
         context.strokeStyle = 'white';
) b2 v& x; ^2 C+ O          // context.moveTo(30+x3*30,y3*30+15);/// K" }: b: ~4 D! [+ p8 j
         // context.lineTo(30+x3*30,y3*30+45);$ G. g1 `& A6 l  a0 O
         context.clearRect(29+x3*30, y3*30+16,2,28);; I9 H5 Y# ?$ J, E: e# ?* \! u
         // context.stroke();
# r' A' o  Y, \& b+ C6 B       }
5 A4 o6 \* K* x( L6 M6 h. @9 V       else8 K2 ?1 c! i; `) D. ^# u
      {( y9 A' d$ O& _3 Q
         // context.beginPath();
6 ?* V4 K, {+ d$ f4 I( q          context.strokeStyle = 'white';7 ~" _; D. ~' a) p4 {# T% q) P
         //  context.moveTo(x3*30+15,30+y3*30);//* W! T, z. k0 ~: J. G! x; r8 E
         // context.lineTo(45+x3*30,30+y3*30);
' _7 D! C; I1 s4 L; d& f0 e          context.clearRect(x3*30+16, 29+y3*30,28,2);
& e' b, y  i$ }( i( V, \1 l4 O          //    context.stroke();4 k) z6 x6 }5 U/ u6 _' @8 j7 p
      }; v+ C8 S% b) N* Q
}3 f8 O( X5 Z$ v) H+ l% \& |# Q+ v

0 Z3 T5 M  y1 F; J: a while(search(0)!=search(aa*aa-1))//主要思路* g% x( c8 p* G6 L
{
$ l8 v2 y  M+ E+ [) z, ]       var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
2 ]1 @& R9 z) w3 B0 j       var neihbour=getnei(num);
. T+ {& M" s7 `0 K       if(search(num)==search(neihbour)){continue;}) z8 C2 _$ S# [) F
      else//不在一个上5 G& M0 {' x9 u1 @) i2 D! X
      {
9 s, g* B+ Z" y1 S& a          isling[num][neihbour]=1;isling[neihbour][num]=1;
: t) F! E" f- ]% T/ A- B3 U          drawline(num,neihbour);//划线* f1 V& z# e$ T& @1 C
         union(num,neihbour);0 u6 g, c6 F( u
! f' G6 H% [1 q: i  ]# A
      }
: {) M# v6 W* E! N  k& ^' n7 I }+ D- y" P9 G2 q: I  O
  </script>
8 U5 v9 a! K4 c! L</html>- g9 z8 `" m- ]/ `  ?
% P9 ^' |- q: H9 M3 h- R

" U& C2 O2 P' X  Y4 `+ Z. c; C实现效果：1 u+ U, C4 P2 F& F5 o8 q/ `

' t8 f, u" w, h+ r% b# q+ p

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

9 T6 M9 R4 X) K2 m' ?
4 Y4 d. ?/ ]' b+ |

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

  _; w0 ~, z8 o$ Y" c7 L+ D* K
方块移动
3 m) y) e9 L, r9 P/ o! r; t6 v9 U! K' \, M8 Z. ]* J) \! B
这部分我采用的方法不是动态真的移动，而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉，在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除，可以根据像素大小精准擦除。
! _/ l& @  t0 o5 E. `: h
5 g7 P' b; {  \# A另外，再移动中要注意不能穿墙、越界。那么怎么判断呢？很好办，我们再前面会判断两个格子是否联通，如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组)/ u! S& m7 B: e. o
/ [7 P# V3 u' _
另外，事件的监听上下左右查一查就可以得到，添加按钮对一些事件监听，这些不是最主要的。: q( t+ q0 `4 i3 |6 [& I

$ ~- l% B9 i. X- R/ X' Q- n' R为了丰富游戏可玩性，将方法封装，可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外，如果写成动态存库那就更好了。! g1 }& S; z( y! t( D" f$ O* B

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

  I- f5 K* v; j9 `% F6 h# z, I0 F" E

1 a5 G$ X% n/ }0 b5 ]! E
/ ]% r9 @9 P# k% s5 G————————————————0 z0 U: D3 g- \7 w5 k4 P
版权声明：本文为CSDN博主「Big sai」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。- W6 U0 c# W  \: }4 q
原文链接：https://blog.csdn.net/qq_40693171/article/details/100716766, }  k1 `7 O% ^& s) L: x

- M* e) N0 ]& Q$ l1 z2 Y
" R% u+ Q+ s2 |+ A1 F- o