数学建模社区-数学中国

标题: 我花了一夜用数据结构给女朋友写个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=[];" B8 S3 ~: N- O. J4 \
      for(var j=0;j<aa;j++){
( o2 u# Y5 m5 [6 Y! D( J          tree[j]=-1;//初始值为00 `0 M& n% s0 ~; F# a
      }
; Q) l) r' Y; [5 @3 b+ j }  for(var i=0;i<aa*aa;i++){5 z  B3 n" Y4 _" C
      isling=[];
" Z/ T2 t- r# t7 @' n+ B" r       for(var j=0;j<aa*aa;j++){# V: R0 h3 s0 P
         isling[j]=-1;//初始值为0
+ u5 B5 Z. E7 N3 q& z; _0 k       }5 A  m1 m3 T) R, |0 J
}8 A  l9 Q( O% y8 e

! y, h0 [4 R' L/ i: X$ t8 w6 P1 t function drawChessBoard(){//绘画
& {6 `$ L; w4 D0 p       for(var i=0;i<aa+1;i++){5 u, V$ U' Q) h7 ~% b2 g/ C; \
         context.strokeStyle='gray';//可选区域
4 m# j( q) h, ~. {          context.moveTo(15+i*30,15);//垂直方向画15根线，相距30px;
" }% \# S) \$ W; |# U! ?          context.lineTo(15+i*30,15+30*aa);
7 z& l8 A$ d) Q, B          context.stroke();
$ L# [  s- w! b          context.moveTo(15,15+i*30);//水平方向画15根线，相距30px;棋盘为14*14；: \. a7 K; j1 e
         context.lineTo(15+30*aa,15+i*30);
! O; @. b- \: s7 a! p/ x8 K0 G) P% U1 J          context.stroke();+ {. r( K: D: c
      }
2 d9 u$ g" E5 H! d. A }
: g0 D. W' B2 ~* E drawChessBoard();//绘制棋盘
+ y% Z" f: Y9 S9 q1 G  q  `2 b( O* q7 ~  ~  {
//    var mymap=new Array(36);; L6 |1 f3 {2 d& M6 J, m
//    for(var i=0;i<36;i++)+ @/ Q+ c2 n( B$ O
//    {mymap=-1;}$ J& N2 j" p0 P# G$ _" Z. I1 h

( y% U9 `; @" }2 k& {! l7 ^3 o  X. u6 R, z1 G; b) X6 `, Q
  </script>: J, Y, |9 d8 @. _* S9 V
</html>7 r5 P' V6 h  A) f, u8 V1 {
2 N0 U8 \3 ~# ~
0 d2 P% ~& u. `- P- t/ F4 L
实现效果
. E& u" O" J1 C

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

6 h) a+ v  X6 l/ ~' Z

9 _  H$ O$ z/ w, }$ \  u画迷宫# c0 c  u, B; R, y4 }! P+ A  Z
( e" M  C' x+ [) A3 r9 P
随机迷宫怎么生成？怎么搞？一脸懵逼。
+ K4 R  F. K) X6 `! m  R, c- B+ I1 ?6 ?4 O( k
因为我们想要迷宫，那么就需要这个迷宫出口和入口有连通路径，你可能压根不知道迷宫改怎么生成，用的什么算法。小声BB：用并查集(不相交集合)。6 X: H& j% V( h! A$ e
迷宫和不相交集合有什么联系呢？(规则)
3 P8 Z) ]* e  k/ ]' R* ~/ S' B" I/ ^- \; S
之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合)，它的主要功能是森林的合并，不联通的通过并查集能够快速将两个森林合并，并且能够快速查询两个节点是否在同一个森林中！. P2 l' u3 k2 U
而我们的随机迷宫：在每个方格都不联通的情况下，是一个棋盘方格，这也是它的初始状态。而这个节点可以跟邻居可能相连，也可能不相连。我们可以通过并查集实现。2 t3 n$ C* k0 s
% f7 n; p" ?0 t) |
具体思路为：(主要理解并查集)
# Y" f6 y/ T3 V2 T2 j% }0 u
+ q! H# |9 V) P# M1：定义好不想交集合的基本类和方法（search,union等）( ?$ R% }- i. J
2：数组初始化，每一个数组元素都是一个集合，值为-1
) M0 O4 y" g1 t$ D" D' Q3：随机查找一个格子（一维数据要转换成二维，有点麻烦），在随机找一面墙（也就是找这个格子的上下左右），还要判断找的格子出没出界。
# m3 f) Z" Q( f6 J% Y; b0 _具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界) _5 @" h0 K/ U7 \9 z
4：判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在，则重新找，如果不在，那么把墙挖去
0 D4 S2 E6 Q4 Y( \( e5：把墙挖去有点繁琐，需要考虑奇偶判断它那种墙(上下还是左右，还要考虑位置)，然后擦掉。（根据数组转换成真实距离）。具体为找一个节点，根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。+ V; m) S1 `. f- ]  a- Q) b9 i
6：最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙，但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据，并查集操作。二维是位置。要搞懂转化！
6 ^" z# ?  d/ @4 O( F: v) E注意：避免混淆，搞清数组的地址和逻辑矩阵位置。数组从0开始的，逻辑上你自己判断。别搞混淆！
5 `& Z0 {: t  n% K1 S$ k

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

  z1 y9 S) e! s. a2 K: x, Z* o主要逻辑为：
9 v6 `- u$ m$ {7 S  H; f1 Swhile(search(0)!=search(aa*aa-1))//主要思路
6 J$ A, |, q' K8 a4 G" R5 b& V {/ ?0 C  N, r7 S/ P$ w. {3 W! H9 A
      var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数3 I; @% h0 u7 }, J
      var neihbour=getnei(num);
9 p$ j, Z: B* j( c2 D+ J5 R. o$ T       if(search(num)==search(neihbour)){continue;}
* s8 X  B% t; u' I* T/ A! f       else//不在一个上
4 V+ a+ Y3 Z: ~8 G       {
1 v8 F: _: }# _/ y( x          isling[num][neihbour]=1;isling[neihbour][num]=1;
7 g. ]: p  S5 t8 I2 z) K6 u          drawline(num,neihbour);//划线
% O* }" w% l$ b: Y& s/ S          union(num,neihbour);- ?, F& i4 S* Y$ q! p& \
) i5 Y+ p1 @" D+ Q
      }. z0 C- n) ~+ b! k+ ~
}' L, w- B& ?/ I" j4 j

1 D. q$ j! [+ p: ?; ]" y
  S4 g- o, A& `3 C- K" [那么在前面的代码为
  \$ [/ c% P0 J' R+ s<!DOCTYPE html>
& s/ d& m& l$ a# z. w<html># u: }8 m" `8 h/ h3 ~
  <head>
) w5 }2 R2 K+ `: }, Q( i <title>MyHtml.html</title> / W7 r( L+ ?2 t& X
  </head>
# _6 H8 \, P. I* `6 r3 u  <body># N5 d$ Z, m' s1 P1 s8 s: l
  <canvas id="mycanvas" width="600px" height="600px"></canvas>
0 N/ c* g5 Z, z4 L! E$ h8 |9 }" w3 B) D1 B* k. ]2 k* L5 d
  </body>
- E( w: M4 u+ |  <script type="text/javascript">
4 G* [+ X+ P/ V5 r//自行添加上面代码
$ i# E  ^8 V" L4 H7 Y* h //    var mymap=new Array(36);
: k: U$ @* a, g/ K2 y4 B //    for(var i=0;i<36;i++)
- f, N5 i& u( k% r- H& X //    {mymap=-1;}
3 h5 t8 R1 I/ Y function getnei(a)//获得邻居号  random
; j( w3 ^) A, H& U0 H {
$ d; ]9 x. B  H0 U: P/ s       var x=parseInt(a/aa);//要精确成整数
  d' Z' z* ^, B! [' ~2 F! n       var y=a%aa;8 v% g' F) H6 ^+ Z
      var mynei=new Array();//储存邻居
. a' i' v4 q& ?  q- {7 [       if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点% x& j7 n* I6 y% n
      if(x+1<14){mynei.push((x+1)*aa+y);}//下节点
" Z2 }2 S- @" ?% S       if(y+1<14){mynei.push(x*aa+y+1);}//有节点
8 k$ o/ \1 e, R       if(y-1>=0){mynei.push(x*aa+y-1);}//下节点% d* @6 \& I* P! [
      var ran=parseInt(Math.random() * mynei.length );/ N- t) V# V9 L2 B* e
      return mynei[ran];8 w0 V6 R: }3 `) V( i: K$ N5 z

2 m, b; F0 N, X/ A2 q }
3 v7 S9 _! B" o. Z6 @! V$ Q7 z" L function search(a)//找到根节点/ h: B( L- T( G" E6 N
{6 A; f  C3 J  X- F% S" R: \' H
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
! @; @3 G1 [+ H7 B# Y  q5 V& G       {
; O: F% i) E' i0 V" z% A7 z          return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩; x1 H# _7 W( p- h/ g8 {
      }
5 Z' W  V6 L* C2 e# E# \       else3 I: Q5 d" e' x5 ^% c4 P
         return a;6 a6 f3 T7 D. M3 M
}
, ~& l( I/ x) w4 b function value(a)//找到树的大小3 h0 J3 V  X( \4 q5 y
{! V- e; d. D' W! I* I
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
' w7 M4 l7 R  }& v& {       {0 @! A4 Q. w2 r1 K: U7 {% J5 N: v
         return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩
+ M. T2 c7 G0 u4 t; Q. ?       }
5 a/ L# m4 \9 I# x- K       else
/ p& e5 p, G5 g4 m6 e) r4 P( Q          return -tree[parseInt(a/aa)][a%aa];9 _* w2 w& I+ I& M. u7 N: U5 [2 j
}
5 y1 r9 S, h# B; p function union(a,b)//合并
4 |+ ~# o* r# }" o {1 {5 Q7 i, i' L- @. d
      var a1=search(a);//a根
& ?9 o. _5 J5 Y* h2 Q2 j7 ^       var b1=search(b);//b根7 r" V+ Y- u/ J) h4 K1 s, G3 q
      if(a1==b1){}
% E8 r$ Z4 m4 q: N  |3 M2 C6 o       else
( d& C* X$ m$ |3 o4 n2 f% \       {
& H5 Y) S+ R' k7 T# @$ p0 ^          if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数()，为了简单减少计算，不在调用value函数8 l1 S- r' g# [$ x' h; D
         {
. ~7 ]2 T+ J& y% _, O8 Q             tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加  注意是负数相加
( v+ D$ g; L# S! {1 I+ Z# e' |# K             tree[parseInt(b1/aa)][b1%aa]=a1;    //b树成为a树的子树，b的根b1直接指向a；8 P* c# `8 X# P& O" ?5 O- i
         }
$ B$ I! F5 k. K1 e% G          else
/ c* ^! G# k6 \# S' K0 q          {
8 t2 |* L6 M" W; [+ z3 O$ Z& d             tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];
) O1 }( H. X% l  m6 B             tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树$ P7 W' P; K1 O. C, M; z8 J. Y
         }$ r5 g1 W+ D0 j+ [- i6 \9 v
      }
9 ?, ~% W; E2 `+ u' X# B: D3 y# o }
3 E8 u* x$ [% B5 F) i
& |9 @* |2 ?3 \ function drawline(a,b)//划线，要判断是上下还是左右3 M3 `: F& p2 @) N1 P" p
{
# @$ y1 G/ i9 `; T: Z
' [, i' A, |' _. T8 Q6 b, ?) k       var x1=parseInt(a/aa);
  B' o' t; b9 c- k$ F  z       var y1=a%aa;2 a1 L  @% @  l
      var x2=parseInt(b/aa);
0 Q3 s( w7 g5 g) \9 J' g9 r       var y2=b%aa;
      var x3=(x1+x2)/2;; z; J/ e2 R( ?) {9 k: x+ C
      var y3=(y1+y2)/2;
9 P) e$ P( s- G       if(x1-x2==1||x1-x2==-1)//左右方向的点  需要上下划线" L- R0 ]# \& P8 j- Z: x( f
      {
0 m8 U8 q; h: Q+ ~$ E" B& Q8 j          //alert(x1);
- r, d  h( N- v' m6 ?          //  context.beginPath();# P0 X2 o; _1 _
         context.strokeStyle = 'white';
; L9 ^  g" G. s( p  O          // context.moveTo(30+x3*30,y3*30+15);//' l4 E% X9 g) x; N4 x  W7 B. p& j/ P
         // context.lineTo(30+x3*30,y3*30+45);- p* F7 @3 z4 F0 p8 C
         context.clearRect(29+x3*30, y3*30+16,2,28);
6 p9 J3 Q: M! r          // context.stroke();
5 E1 k4 s& U( q3 k! [: P       }7 s2 u: o0 V4 d; m+ j) D) b, f
      else: a6 ?% j" W2 Q( ^. o
      {) K" n$ n4 e; |
         // context.beginPath();1 a4 K3 O0 L& g  Z8 r" ^$ U
         context.strokeStyle = 'white';$ i( y; o: D* w% Q- @
         //  context.moveTo(x3*30+15,30+y3*30);//
5 D& K& d" Y* r          // context.lineTo(45+x3*30,30+y3*30);! W, V+ T. i1 S1 y( v/ A9 A0 n2 e# f
         context.clearRect(x3*30+16, 29+y3*30,28,2);
7 @+ P% j- c8 m8 D8 {( I          //    context.stroke();. {6 K. q6 D1 u7 D3 R3 _
      }
$ a3 M3 u7 Y7 K1 s4 P0 X/ {+ O }
& r0 M; N% h% Q" ^- D! s+ [: Q$ g. ]' t+ Q. \. U. g8 \
while(search(0)!=search(aa*aa-1))//主要思路
+ ?* d$ u; {- U3 c; \ {5 u- X2 ?0 b$ P9 h' M+ b
      var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数. b7 t0 i0 I2 x: O" B# M
      var neihbour=getnei(num);7 i0 [* s" P5 w& c) g
      if(search(num)==search(neihbour)){continue;}% \8 p* ]* M$ J5 q: E
      else//不在一个上
5 I! Q8 u, S' F. [/ y       {6 n! T* b6 j& E" @. b$ A3 X. v
         isling[num][neihbour]=1;isling[neihbour][num]=1;9 z8 v3 A: ^, W! n0 b  e
         drawline(num,neihbour);//划线
. z; i2 T( b: X          union(num,neihbour);
& e; v8 \8 c! I$ C, B0 X. U5 I( j6 I$ N2 k1 w! o
      }, l4 P$ a, }6 L( T8 q
}- I: X9 m' j+ `% j/ F7 M
  </script>9 i; x/ ]7 B8 h/ G( d( W
</html>1 v+ D" N4 j0 g/ j8 \* ]

) q7 s( j2 v% J4 A3 n/ U% a$ Y7 \4 W
实现效果：
# P3 Y% M0 |7 y: [( n2 U$ h6 m* p1 r' h9 |" _. r4 u8 X

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

5 P& E6 C2 [1 G  `& E0 S: \
( H0 V/ p# p* |7 _

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

- |# c/ l$ G4 s方块移动
& c/ N+ k  J- P; U- x3 T
1 {) C+ A$ ]: e, s; i这部分我采用的方法不是动态真的移动，而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉，在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除，可以根据像素大小精准擦除。
3 O" F5 y: P& c
! ^7 |# W  g! W  z" M另外，再移动中要注意不能穿墙、越界。那么怎么判断呢？很好办，我们再前面会判断两个格子是否联通，如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组)
& J  p. O& g+ Y- `$ _
, Z8 |' x& p9 i另外，事件的监听上下左右查一查就可以得到，添加按钮对一些事件监听，这些不是最主要的。; ^5 i) z) M8 Q6 o* f, C* x. r. r
, \5 B' t9 A" x& ~/ C
为了丰富游戏可玩性，将方法封装，可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外，如果写成动态存库那就更好了。8 I" b; O- t' q% T2 X7 b4 G7 A

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

: e  o9 R8 ^7 c5 r, d. E
+ Q4 B6 _- r. [; W: D( ?! L" c( y9 d* A2 I
————————————————
* x8 r$ n8 m: f2 ~8 g. T版权声明：本文为CSDN博主「Big sai」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。6 ?3 i6 C* o  P% L+ }$ w
原文链接：https://blog.csdn.net/qq_40693171/article/details/100716766
) R8 x7 @/ X- `) m, u5 c5 X* c) v/ T- z) ]2 @# C
" \: q2 B9 \& |) O; R) G

作者: madio 时间: 2020-4-1 12:39
牛人！
& Y) x" t- m2 q8 @% Z

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