数学建模社区-数学中国

标题: 我花了一夜用数据结构给女朋友写个H5走迷宫游戏 [打印本页]

作者: 杨利霞 时间: 2020-4-1 10:57
标题: 我花了一夜用数据结构给女朋友写个H5走迷宫游戏

我花了一夜用数据结构给女朋友写个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=[];- a4 y' h  N4 A' a$ e$ G3 }2 T
      for(var j=0;j<aa;j++){% m$ G* k5 f' M" s* m  M+ R
         tree[j]=-1;//初始值为0+ \: t# G( V" A- Y3 O. t
      }* l* I  J! R" d! y5 I* N( P7 W
}  for(var i=0;i<aa*aa;i++){! e: J/ n* s3 D
      isling=[];6 e5 B" o7 z, B7 Y$ Y0 ?% Y
      for(var j=0;j<aa*aa;j++){
8 c6 E# Y% j& Z& K' l          isling[j]=-1;//初始值为0
5 Y+ n) t' ?9 ~" X2 y8 R       }
4 {* R1 f) r' b$ P3 M7 n# v }  G* c: P1 Y" S( X- p. i

9 |. R# v7 b- r% c! Y% `2 O function drawChessBoard(){//绘画
9 Y* |5 R. G  A  ]8 D       for(var i=0;i<aa+1;i++){! o; f- Y0 L2 r7 ~: T
         context.strokeStyle='gray';//可选区域( L+ Q+ I1 p# z$ c
         context.moveTo(15+i*30,15);//垂直方向画15根线，相距30px;8 t2 V3 j, _7 L4 _
         context.lineTo(15+i*30,15+30*aa);
0 c- h+ K  G* _( o' Z: W          context.stroke();
         context.moveTo(15,15+i*30);//水平方向画15根线，相距30px;棋盘为14*14；
! x  M; H; L2 G( R; L, N: J: [          context.lineTo(15+30*aa,15+i*30);6 v: }+ w9 }  D0 L) v9 f: Q
         context.stroke();
2 u/ B/ V% ]8 [4 V       }
) \2 A& `3 q1 i$ |7 s2 B4 f }* G' ~! f( t; d/ ]0 w: a
drawChessBoard();//绘制棋盘
( R* B# h+ ]( t) _4 ?  u
/ v  X6 g2 F' k( K. f- s/ w //    var mymap=new Array(36);5 b, U+ n% `# b
//    for(var i=0;i<36;i++)2 B9 a/ C( O; A$ N
//    {mymap=-1;}
! ]9 ^2 A5 x1 a6 E
5 A/ Y) ?! N9 `# G
* @0 [+ n7 Z; m. T. e  </script>
3 v- }* N. T; P0 L</html>% ?5 ~' A- p& X8 T, k$ k, A! ?

/ L0 r6 g- n" L, j; `6 I/ u" Z
$ M- {& Z6 L* }) o1 {: I实现效果7 m2 c* G. `5 k- l" g- ]* G, \

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

% d; Y2 P6 @! N$ H: G
! u* X+ c1 o. z& @* M3 y
画迷宫" B7 H! Z5 R3 S- u* v/ w7 I+ j
. C& r, j, ^) ]$ ^  W
随机迷宫怎么生成？怎么搞？一脸懵逼。& ~' T" E9 e7 I* `! d1 F) I4 `0 k# P$ `
$ z- k0 v: s1 T! Q. _
因为我们想要迷宫，那么就需要这个迷宫出口和入口有连通路径，你可能压根不知道迷宫改怎么生成，用的什么算法。小声BB：用并查集(不相交集合)。
9 P- r6 l0 o. v( y迷宫和不相交集合有什么联系呢？(规则)9 c3 u3 x8 Q2 y; u  |) f  W

# {- @4 I2 t+ S+ z# v; f* p之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合)，它的主要功能是森林的合并，不联通的通过并查集能够快速将两个森林合并，并且能够快速查询两个节点是否在同一个森林中！& Z' X/ l' l9 ?; C9 l
而我们的随机迷宫：在每个方格都不联通的情况下，是一个棋盘方格，这也是它的初始状态。而这个节点可以跟邻居可能相连，也可能不相连。我们可以通过并查集实现。
) J0 E# X7 ^9 l- b; l5 A- z
! w9 f* f3 }& x! B1 E- I: a具体思路为：(主要理解并查集)
- V9 t1 R% @1 J# j) x
5 i2 W! L( c0 Z+ B- A2 i- `; X1：定义好不想交集合的基本类和方法（search,union等）
1 u% k- w, }. p' t2：数组初始化，每一个数组元素都是一个集合，值为-1
' T& e6 f- U, X# c3：随机查找一个格子（一维数据要转换成二维，有点麻烦），在随机找一面墙（也就是找这个格子的上下左右），还要判断找的格子出没出界。* I+ N+ e" `3 S8 O& Y
具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界
+ ~, h/ N9 ]: O) a' v4：判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在，则重新找，如果不在，那么把墙挖去
% B2 _" }5 v) z2 g5：把墙挖去有点繁琐，需要考虑奇偶判断它那种墙(上下还是左右，还要考虑位置)，然后擦掉。（根据数组转换成真实距离）。具体为找一个节点，根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。
; R# E$ l  J/ W' K3 Q/ |6：最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙，但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据，并查集操作。二维是位置。要搞懂转化！) V% Q  q# [- d, H
注意：避免混淆，搞清数组的地址和逻辑矩阵位置。数组从0开始的，逻辑上你自己判断。别搞混淆！
7 d! R4 Y+ n9 C" f; f& M

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

0 o3 e# q) F$ k
主要逻辑为：% I0 w* P9 J, o' \3 ~- `1 f
while(search(0)!=search(aa*aa-1))//主要思路8 R$ z8 E3 Z" z2 B5 r) i2 Z$ h+ I
{
) ^# V1 s% U! R( c, J9 y; {# B       var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数5 @  }2 S, {3 @! w$ D# ]( j) x
      var neihbour=getnei(num);
0 F6 L6 U4 p0 m0 O/ Y       if(search(num)==search(neihbour)){continue;}" H* g8 n7 o# p+ R" H1 Q
      else//不在一个上
$ f* K5 y- y' Y6 s) I4 u, V       {: _+ R4 h8 m; z% h9 q1 D
         isling[num][neihbour]=1;isling[neihbour][num]=1;" c/ C- o* S& m( e7 \/ \  ?
         drawline(num,neihbour);//划线
! U& c( ]1 f6 N          union(num,neihbour);0 `8 t( s9 c2 X$ E% z5 \
1 h2 j, p6 m* Y# e
      }4 b9 [- t" z3 w$ c& g# r! E( ~) c
}  n1 [( \6 V- q- t  ^4 F# e
, F2 F5 A& F* z9 _, V: r- d# k8 b5 i

1 j; M, m& D5 p5 l那么在前面的代码为; T# ]5 K! z6 g, P( x
<!DOCTYPE html>
5 b! p. ]) e! v3 S+ b<html>
  h4 M+ H! a2 E- n( k  <head>* g7 I0 s! P7 C
<title>MyHtml.html</title>
0 I3 O; d) X. }- \% f  </head> 3 `0 C- o, T# R$ x# @% _. A5 ~
  <body>
7 t! e  U6 b% }( h& V4 j1 i2 R  <canvas id="mycanvas" width="600px" height="600px"></canvas># z1 a1 k5 F" q- @7 ?0 j# E
0 Q, k9 \( i; c3 W7 {& m
  </body>
, j! o' Y8 }: H; f* x  <script type="text/javascript">
; I: x+ |( u( Z1 {9 w: l" V//自行添加上面代码
9 r. ~# h% [+ N) [3 l. \% V //    var mymap=new Array(36);
, K3 H- X7 b1 C( ^ //    for(var i=0;i<36;i++)
3 J( c3 ?; n6 w //    {mymap=-1;}8 a6 `5 U" C4 ~4 o6 v3 n
function getnei(a)//获得邻居号  random7 n/ c2 k# t% Q* p
{9 ?- ~4 e$ n% o* j0 y
      var x=parseInt(a/aa);//要精确成整数
2 S7 W; D; g7 h" t0 a, C       var y=a%aa;
+ k" i" N3 C0 }: C5 j: J       var mynei=new Array();//储存邻居3 x: t8 C7 b* o  u; T8 j
      if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点; ]/ ^! u/ {0 ?9 C3 g  i
      if(x+1<14){mynei.push((x+1)*aa+y);}//下节点
% Y3 }  o9 ^& O       if(y+1<14){mynei.push(x*aa+y+1);}//有节点
$ G/ R' ]0 M' m3 f. T       if(y-1>=0){mynei.push(x*aa+y-1);}//下节点
2 P6 o9 g. O6 U4 {5 E       var ran=parseInt(Math.random() * mynei.length );. M6 x2 p& N, a: S8 h/ s* h6 X
      return mynei[ran];6 w- W: ]1 I1 X$ O& ?6 ~
- r8 p0 z* s2 o% {" U0 }, s
}3 ?4 L+ D! J2 F7 ]' f5 D- x
function search(a)//找到根节点
  k( l: |3 }# e {
4 b! ~( c5 S) @       if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点  a; x1 x3 |. B7 A. y/ x) p
      {
. z3 Z1 J; b1 C$ g+ R& l6 e          return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩9 l7 M$ `9 O% b) ]! V" Y) y8 M
      }
. f& B! t. R/ j  H4 j4 r* |; [       else  t; y2 O- A- K
         return a;8 T" u9 h5 B' M, a! _! `" X+ l% K
}
7 J' E5 |/ q7 E3 [6 f function value(a)//找到树的大小# \5 G$ n2 |9 U
{: Z1 |/ a  Y* I% D8 B  t: p
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点1 c# E' m: M, J
      {3 g) Z7 t8 q2 s; f7 y  q
         return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩
5 a7 s( L) v' p; a% T       }
9 _( W' i& _, _8 k' j6 n       else
2 }& M  F2 J3 ~4 k) h2 T/ R( T7 \' T          return -tree[parseInt(a/aa)][a%aa];
4 ]' Q3 n- v# A- _1 @ }
9 {* g8 ^5 `0 o* ^9 t" Z function union(a,b)//合并
0 p' H+ {1 i% I) n {
, V5 |! x3 {( |$ B- K' L9 ~4 Q       var a1=search(a);//a根0 V8 @% {5 W3 p! `9 k: `
      var b1=search(b);//b根  B- F- S- J2 `) z) c0 K
      if(a1==b1){}
0 H4 L! O; K  [       else6 p# f* \; Y4 ]; M" d" ?: ~4 T$ q
      {
5 Q2 ]+ T! l& H9 z& s9 X" D9 E0 |& {          if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数()，为了简单减少计算，不在调用value函数  P& H: \' I- Y1 H& @7 z
         {! H) ~* O. N3 n+ ^/ `
            tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加  注意是负数相加  D  `( g( G( x- n7 |) o& k
            tree[parseInt(b1/aa)][b1%aa]=a1;    //b树成为a树的子树，b的根b1直接指向a；0 U, E  R9 A- ?& x
         }
! M( I! s" v% A7 G% q; r4 n          else
* n: r( ?1 L; n  t1 ]          {# f$ f& I0 {% F# L% ~' |; P
            tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];
* u$ r5 m( g& f, A3 p" W/ ~2 Q3 t             tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树* n8 x# d0 w" E
         }3 w1 U& `, d9 W0 Q
      }# k8 M- l2 r1 G1 t# `
}
# M/ n+ Y3 B& c1 C( t
8 d1 U; G( T/ ^ function drawline(a,b)//划线，要判断是上下还是左右4 v% A( U  F: ?, A4 b8 X4 h  L
{# d& v7 R# J% w# o, y% G' L8 G' B- \
" d# Z1 H6 N2 a( p! ~: j$ G
      var x1=parseInt(a/aa);
; y2 C# G1 {, i/ a4 d. I$ j       var y1=a%aa;% m& Q" u$ P3 y& a6 C; ]3 W2 m$ n* b
      var x2=parseInt(b/aa);3 O& k# r1 ]) b: @5 O
      var y2=b%aa;
3 M# X1 v+ c: F- N- N       var x3=(x1+x2)/2;5 o/ d- f' U: Q
      var y3=(y1+y2)/2;- ~+ v5 S- t5 r9 o& A
      if(x1-x2==1||x1-x2==-1)//左右方向的点  需要上下划线
1 d4 u6 f# a$ s7 r6 D3 ^       {' @2 @& i) B6 n- z! l
         //alert(x1);# x3 N7 v, G, l1 b
         //  context.beginPath();. B# z, q0 A6 t% Q
         context.strokeStyle = 'white';+ F4 k1 z8 O1 B- I
         // context.moveTo(30+x3*30,y3*30+15);//' V: X8 H- R, i
         // context.lineTo(30+x3*30,y3*30+45);
3 ~9 u; L4 Z+ B. Y8 `3 N          context.clearRect(29+x3*30, y3*30+16,2,28);2 B3 B/ E+ L) {; N. E2 C
         // context.stroke();. e+ h. G+ V+ v; a4 j- x% l
      }; u# T8 x1 k% s8 ~
      else
( z( W5 O- N$ J       {
: A9 N$ Q7 A" ], ~          // context.beginPath();% P& b1 ^5 j  s# w
         context.strokeStyle = 'white';
$ R- K9 r; S. x: r" Y4 ?          //  context.moveTo(x3*30+15,30+y3*30);//
6 ~$ P1 a4 b. D  n          // context.lineTo(45+x3*30,30+y3*30);# y( f# |' H  B
         context.clearRect(x3*30+16, 29+y3*30,28,2);; P( p/ c0 _6 Q  H, r8 L6 |
         //    context.stroke();) f) @" T8 v, x
      }) k8 z2 x: G+ J+ n6 j
}
4 E3 _- c' m8 w2 V# _' c
6 ?8 [, r2 O# G while(search(0)!=search(aa*aa-1))//主要思路6 R3 l0 |  w# ?  T
{
! ?5 p0 k7 s" w" a& g! f       var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数7 `; z2 y. w: U& U! }& Y* L, F
      var neihbour=getnei(num);
' k( U# N; u4 q! ~0 o' R0 K       if(search(num)==search(neihbour)){continue;}
4 g4 }0 J4 q4 ?1 B% I       else//不在一个上0 l1 p2 n% I  ]+ t; ]/ ]
      {. w; a! ~0 f6 @3 w3 M
         isling[num][neihbour]=1;isling[neihbour][num]=1;7 ^; J# m$ W6 z5 t+ L0 L. o
         drawline(num,neihbour);//划线. c3 Q- j  z4 D
         union(num,neihbour);
0 w# f5 P. N1 N8 |: `" q/ K
; @5 r1 B' B. L* S" _9 j       }* {7 h1 [1 `( k9 v' r$ S. c+ [/ |# @
}
" t; O8 _4 L  H- W  </script>
# m4 S4 c0 D. [1 r1 m: @$ L</html>
- M! z! }) I$ \+ ~4 H
4 `9 j, d2 H0 y
& I; T! R' U5 Q* U' \实现效果：
" X: x$ k7 k$ N' n# Z9 S8 `
7 S: @6 d( g$ O* {

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

" u8 y) z# v: T, L+ ^1 k" I- F
- ^/ |3 @" q1 \; a! ?! \

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

; e& Z, N: |: ?  H- T% V9 r* n
方块移动+ ^( O+ P1 ]' O
- x! G; X$ [) G, g- i
这部分我采用的方法不是动态真的移动，而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉，在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除，可以根据像素大小精准擦除。8 y+ x+ E3 e: G& l* R! g

  @. Z$ R; P3 }) s另外，再移动中要注意不能穿墙、越界。那么怎么判断呢？很好办，我们再前面会判断两个格子是否联通，如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组)
' b/ m) P8 ?# @. s* Y, k
3 @, B4 e; |; @) k# Z另外，事件的监听上下左右查一查就可以得到，添加按钮对一些事件监听，这些不是最主要的。; b* W! A' T. L8 {$ k0 U
, P- j1 G$ s& C$ C0 s! `
为了丰富游戏可玩性，将方法封装，可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外，如果写成动态存库那就更好了。
7 u# p2 }7 i/ k; d3 A

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

) z% k1 A0 X3 m7 P" L

/ p# p' v& p6 K4 C. S
6 f, `) }' G+ G' W3 r+ v+ u————————————————+ B: D  b% a3 Y* B7 w
版权声明：本文为CSDN博主「Big sai」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
' p: S. o) t( f1 N6 s, a6 T) @/ j+ R1 C原文链接：https://blog.csdn.net/qq_40693171/article/details/100716766
& T1 n: @$ l9 g: d, w: H2 ~- f. [& K# w& f1 @9 ^

8 V6 X8 B2 Q! s9 j! Z
作者: madio 时间: 2020-4-1 12:39
牛人！7 d. v5 q/ E6 n$ e

欢迎光临数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5