数学建模社区-数学中国

标题: 我花了一夜用数据结构给女朋友写个H5走迷宫游戏 [打印本页]
作者: 杨利霞    时间: 2020-4-1 10:57
标题: 我花了一夜用数据结构给女朋友写个H5走迷宫游戏
/ c4 h4 J) U, X
我花了一夜用数据结构给女朋友写个H5走迷宫游戏
9 b+ N# X" f( p" G" X文章目录
* O" P! Q5 m# R1 K: X  i9 L1 S1 J0 Q: L/ ]+ J3 m, J
起因
0 [5 w1 f) l+ k3 @* r9 o. C分析9 j, P: Q2 x3 M
画线(棋盘)
; h/ H8 F# Q! n; E& V+ K  |- |画迷宫5 ]0 K7 C8 V( |8 F  {5 k
方块移动$ p2 O4 v$ w& |# m* o& }
结语
, G$ A1 K, c; D2 Z8 X1 M( @( w先看效果图(在线电脑尝试地址http://biggsai.com/maze.html)：" j9 ]! }. }* R  ^  o; C
1.gif * j3 }& S( L3 R( w" L$ x( o; ]
/ x/ |& K1 r& Y& D8 \
起因
8 X2 E& n& w1 f: Z6 h 2.gif
, r( U- n& b/ C' u) `" R# ?% O
0 t7 L( v$ g; l# ~8 s% s又到深夜了，我按照以往在公众号写着数据结构！这占用了我大量的时间！我的超越妹妹严重缺乏陪伴而 怨气满满！+ Q, }7 L9 Y( a' S' q7 A% [" o2 }
3.gif
6 P/ d  S+ N/ R4 ~: g/ m超越妹妹时常埋怨，认为数据结构这么抽象难懂的东西没啥作用，常会问道：天天写这玩意，有啥作用。而我答道：能干事情多了，比如写个小游戏啥的！: ?& L/ O- [9 E0 X% ^" a9 @
4.png 1 j# B. _5 V  [3 `
当我码完字准备睡觉时：写不好别睡觉！
+ K4 O7 a4 y+ E# `8 Z
8 Q+ y: s5 q$ u* n7 M4 G( ], r/ H+ ~( [ 5.gif
/ h, ?; a8 |+ V  K( ?- Q4 K分析
3 e! L! ?$ }$ ^0 P; |9 k8 h# ?" @
7 E) f" L7 H9 V& ?" J1 |如果用数据结构与算法造出东西来呢？2 z# l9 t& w1 l0 }8 z9 w7 ?# N" w" U

4 N; }  C8 m8 z什么东西简单容易呢？我百度一下，我靠，这个鸟游戏原来不好搞啊，得接触一堆不熟悉的东西，搞不来搞不来。
# }; Y- x; e7 L7 e  n  j: T! o: E有了(灵光一闪)，写个猜数字游戏，问他加减乘除等于几。7 e/ R# G% Q4 W
$ m3 }( K+ N. H" h4 S
超越妹妹又不是小孩子，糊弄不过去。1 l* ?" q' c, g6 S
经过一番折腾，终于在半夜12点确定写迷宫小游戏了。大概弄清楚其中的几个步骤。
5 f5 r! Y2 U: u9 `4 L% w' H' ~9 o; P
大概是：9 N7 o# }, I; {  p. b7 ~& X
! ?8 E+ w' [% ~  u, e& F& A) I
画线—>画迷宫(擦线)—>方块移动、移动约束(不出界不穿墙)—>完成游戏。
. g! E  K1 k: H) Q画线(棋盘)
, k) c/ Z% v/ j9 ~7 l1 S7 J5 b. ~' N3 T7 N3 O* f
对于html+js(canvas)画的东西，之前学过javaswing应该有点映像。在html中有个canvas 的画布，可以在上面画一些东西和声明一些监听(键盘监听)。
1 _2 r8 D7 G+ @& _
, N0 A# U+ {+ A. W( _对于迷宫来说，那些线条是没有属性的，只有位置x,y，你操作这个画布时候，可能和我们习惯的面相对象思维不一样。所以，在你设计的线或者点的时候，记得那个点、线在什么位置，在后续划线还是擦线还是移动的时候根据这个位置进行操作。: m/ C- E6 H8 }/ C7 b
<!DOCTYPE html>0 Q! D; g: W8 P1 w( V
<html>' J  u! t5 O' B4 _' d
  <head>8 l. g* \+ v2 x  D5 a
    <title>MyHtml.html</title>       
. U# j) u& x% Y% Q7 [  t/ L  </head> " x" D+ D6 J- M% Y& `$ l) `  V
  <body>' s2 p0 e8 O4 R* w" c7 ^8 F
  <canvas id="mycanvas" width="600px" height="600px"></canvas>5 b% i9 Q  J0 F( ?# F- R4 D
4 p  Y2 K( B+ A
  </body>
( e" ]5 ?7 v  b: h# Q9 M  F  <script type="text/javascript">7 e, y+ z, q& J; h

& B3 f9 D6 `, ]( z: Ivar aa=14;
( F; E. s. g" X    var chess = document.getElementById("mycanvas");/ r' B2 z5 n' \1 h0 G3 H1 ?
    var context = chess.getContext('2d');0 s) ~& z9 w/ k6 F( F3 D

' r4 @2 h8 S6 ~( Z, a, S' H9 n1 s  R    //  var context2 = chess.getContext('2d');
( C0 ~( B" J+ t$ O    //      context.strokeStyle = 'yellow';
" G  ~7 n1 y% L. M6 J% q( l    var tree = [];//存放是否联通
7 K% ~1 @# o9 b- K    var isling=[];//判断是否相连
( L1 ?8 x) O0 z8 K% O2 |    for(var i=0;i<aa;i++){
8 `0 L* \) c+ I        tree=[];
. U6 f: n$ O# \4 M3 F# ~) V        for(var j=0;j<aa;j++){) Z* V% o5 X& K" n/ Q- N
            tree[j]=-1;//初始值为06 K# K& [/ K* z4 c
        }
- [; a: T# o" ]# Z' R  G* _    }  for(var i=0;i<aa*aa;i++){
: O& F& B2 Z$ F  b, H        isling=[];
$ K4 I4 {) ~# A        for(var j=0;j<aa*aa;j++){; n8 t8 q# X/ K( d' Q
            isling[j]=-1;//初始值为0/ U7 |9 p: A2 P: E7 A* Y8 e# n
        }+ Q( i' I) y' \: n% ?
    }$ k+ m0 U( ?  L4 z6 F# V

! J5 Y. b5 X4 u1 a0 i: I3 r% w4 o    function drawChessBoard(){//绘画" ^' j/ T4 @) C/ m, m+ G
        for(var i=0;i<aa+1;i++){
6 A; ]. [3 b8 }' B. {# O$ S  @0 M( {            context.strokeStyle='gray';//可选区域
: W) }/ F) K/ j, i% D            context.moveTo(15+i*30,15);//垂直方向画15根线，相距30px;
3 `6 l: e; c' w            context.lineTo(15+i*30,15+30*aa);- a3 y" |' h% A- A8 W6 S/ w* q9 f4 M! N
            context.stroke();
- h* R* g$ c4 q, y! a; f2 \            context.moveTo(15,15+i*30);//水平方向画15根线，相距30px;棋盘为14*14；
% f% h# b+ o' U+ b! J6 {- ^            context.lineTo(15+30*aa,15+i*30);
" E2 H, ?9 f* I; x: o- ~4 \6 P0 O* ?            context.stroke();0 N$ a: ~  K: B! d
        }
8 P. Z5 J& ^. n0 Q; B8 V    }3 {0 K/ N, h7 [( ]
    drawChessBoard();//绘制棋盘
7 ]) L. \1 o5 r' d' g' ]
% u9 B/ \2 b0 y" f2 t8 v: Y; y. X    //      var mymap=new Array(36);* C, d. D+ O# R4 x: N
    //      for(var i=0;i<36;i++)2 H6 D2 ?! G2 F! @# y1 f9 `
    //     {mymap=-1;}. q9 m4 A: D( V/ Y  f! `& u6 I  ]  {0 H
9 k4 b  k8 r4 w1 Y' I

0 |5 {! Q0 e' m, o  </script>
$ R' @' Q9 u& N" s; c( J3 W1 N</html>; T- q; N3 ~  r( J1 q

1 x% H& c/ k' n  x: U; {# p* F& g* J5 {: @7 P0 e
实现效果
. X1 B2 D( f) z9 t% L  n 6.png   R$ O/ b3 k8 r0 e3 t' _
# \( o  _7 x* N7 @
画迷宫
. b# Y5 a- M; ?- M+ ?5 i3 P: K9 z2 P3 f4 v' ^
随机迷宫怎么生成？怎么搞？一脸懵逼。
; v& q  N* a2 R( O% @/ h; J; d' U6 m
& p4 c9 {2 G+ t因为我们想要迷宫，那么就需要这个迷宫出口和入口有连通路径，你可能压根不知道迷宫改怎么生成，用的什么算法。小声BB：用并查集(不相交集合)。+ T& [4 s9 h" |1 D
迷宫和不相交集合有什么联系呢？(规则)
* r4 s! C5 n- M1 |
/ A) F1 _9 P( G" p之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合)，它的主要功能是森林的合并，不联通的通过并查集能够快速将两个森林合并，并且能够快速查询两个节点是否在同一个森林中！2 U  V- i% z5 b- z7 O& ]
而我们的随机迷宫：在每个方格都不联通的情况下，是一个棋盘方格，这也是它的初始状态。而这个节点可以跟邻居可能相连，也可能不相连。我们可以通过并查集实现。
# C9 O, j+ T! |0 e1 M! l: s% s: d6 E, ~
具体思路为：(主要理解并查集)7 _1 E1 M' O$ p$ J0 M( c; V

' E/ V/ X, b: a1 x6 v9 e& T1：定义好不想交集合的基本类和方法（search,union等）
& _& ^1 K; u! O. A8 Y7 E2：数组初始化，每一个数组元素都是一个集合，值为-19 t% e- V7 U" m
3：随机查找一个格子（一维数据要转换成二维，有点麻烦），在随机找一面墙（也就是找这个格子的上下左右），还要判断找的格子出没出界。$ l4 x2 P7 Z7 N
具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界
, {& w! d% L2 y8 Z" |+ f; a3 g4 f4：判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在，则重新找，如果不在，那么把墙挖去6 X8 r& h9 q& v
5：把墙挖去有点繁琐，需要考虑奇偶判断它那种墙(上下还是左右，还要考虑位置)，然后擦掉。（根据数组转换成真实距离）。具体为找一个节点，根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。/ ?3 b5 Q4 m, Z$ Q% P$ v( P
6：最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙，但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据，并查集操作。二维是位置。要搞懂转化！4 ?4 `: q% V# L* h+ B8 [+ C# q8 P
注意：避免混淆，搞清数组的地址和逻辑矩阵位置。数组从0开始的，逻辑上你自己判断。别搞混淆！! @0 q2 F: Z" |- }3 r" c
7.png - ]$ x1 l5 w% L5 y3 l
主要逻辑为：
6 t0 A. g4 ]  a8 y* w1 f+ Mwhile(search(0)!=search(aa*aa-1))//主要思路7 |) }5 L* b' r8 I5 e8 I
    {
7 F2 H6 ^+ }! u( G        var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数# n- f  z! _4 R6 u4 b
        var neihbour=getnei(num);" v7 e- U) Z4 L% B
        if(search(num)==search(neihbour)){continue;}
) [6 U# B# @0 w6 y* z" P$ m        else//不在一个上% |$ ^5 m: }+ t+ M$ Y4 {! i
        {- M9 g' H5 H: J  V2 e7 D3 I
           isling[num][neihbour]=1;isling[neihbour][num]=1;
1 E7 W1 r: ^5 Y3 [, Z) [            drawline(num,neihbour);//划线6 D9 r- A& D& E5 O$ a% m
            union(num,neihbour);( I, ?/ p- q5 o* C

+ A. |$ {% K* J7 o; |        }
. W. T1 \! w6 V3 m: \* a; Z    }
4 C0 a: D* u% ~2 }% @- w- T2 t, c: w& p2 G( H$ J( f$ }. Y
3 ~  E$ P* y1 B  t3 Z  j
那么在前面的代码为- @% e+ I. U' @# O  s4 I
<!DOCTYPE html>3 u5 a7 B2 n% W- Y6 \7 a( a3 @- e
<html>
# _: Z) N5 z! p! E8 d4 @  n  <head>
! K3 O9 [% W% Y$ V1 m  M    <title>MyHtml.html</title>       
. C- V6 h, R- ~$ l$ ]4 S; A  </head>
. ~* l/ K5 H4 G7 Z7 P) Y; {( m  <body>2 J6 I, r1 K( u7 B& r. {1 q* {
  <canvas id="mycanvas" width="600px" height="600px"></canvas>
* q" ?& Q3 E( E* O1 {$ ?2 u1 C3 v7 u4 s/ G5 J  w
  </body>
$ b) }4 O! x: e& ^  <script type="text/javascript">+ E! K" y2 e; ?
//自行添加上面代码- }  ^5 ]( c0 E7 L+ i9 s! L" g1 p* ~
    //      var mymap=new Array(36);
/ A& z% Y2 i3 w: x1 t" W2 ?    //      for(var i=0;i<36;i++)/ Y" w. C- ?! P" R& K! h
    //     {mymap=-1;}  b9 w" ?7 a4 ^" \5 r
    function getnei(a)//获得邻居号  random! S8 s* I; }4 F/ q0 g
    {' E$ L/ {9 _! A. X( n- |
        var x=parseInt(a/aa);//要精确成整数
! L" [$ s6 ~( s# Q# S) D        var y=a%aa;8 r  @! M+ {- W  ^
        var mynei=new Array();//储存邻居
: z0 R% }: g, w9 A. v        if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点( O0 N6 U. t# M0 k) p1 n
        if(x+1<14){mynei.push((x+1)*aa+y);}//下节点% @4 m* {" ]) O6 e
        if(y+1<14){mynei.push(x*aa+y+1);}//有节点* `6 B1 T% \. y# G. ]$ H
        if(y-1>=0){mynei.push(x*aa+y-1);}//下节点  I( y( s6 _0 w# S% c
        var ran=parseInt(Math.random() * mynei.length );
+ f4 {8 _4 B6 {: T        return mynei[ran];/ _# F! x0 o+ M, y
6 F3 J2 }* i5 e
    }
5 \! ^( g: e2 p& ?    function search(a)//找到根节点, ?3 B1 ~  W7 ~" W) K$ S: l/ Q
    {
9 t; f; F5 h& F" j        if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点4 H! T+ z; N6 `  \7 ^0 q7 X
        {
) _5 e! J1 S& y( R8 I3 c) V            return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩
3 e0 P, t# X& u* j. q4 |' r5 @        }
# R: h9 z6 E+ V' ?6 z. Z        else
' ^4 _* y" `1 V1 `" C+ }7 P            return a;
; \8 f' l* p' v' c% W% D7 x/ N4 }4 j    }8 b: M! I9 H0 T" ~
    function value(a)//找到树的大小
1 i* ?- v) `9 \; b3 C    {
4 T3 C1 [# t$ P% y# _7 I1 \- f        if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
- p; @, O7 |0 g! a/ M* R, s        {
, i' w5 H( v9 I7 R            return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩0 _) B$ y/ C3 c& O+ S9 a# L+ L
        }
+ L( e% l" V% _6 w        else+ z# v5 M* n- s2 Q: v1 l
            return -tree[parseInt(a/aa)][a%aa];
$ e; \, f) N7 H4 M# s4 Q* M    }
5 k/ |$ \2 c( _9 c/ {) d    function union(a,b)//合并
# H3 f5 B( m% F! @    {* W# N( w, N6 K# }( a) R" L
        var a1=search(a);//a根
# s. i/ s+ T4 B5 C        var b1=search(b);//b根
, N2 ^& m# n! z* ^7 X7 U9 ~0 h6 S        if(a1==b1){}
3 F1 I1 w% I% F$ q1 O4 P        else! y7 S' I$ i0 C; x6 l- X
        {" m; [8 k8 }" Y# Z, k7 @- E" P
            if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数()，为了简单减少计算，不在调用value函数
/ X0 P" {0 w6 L3 J4 Z0 I- ?            {  l0 r: B" [: i% s1 F, z) v# U
                tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加  注意是负数相加
2 T) g" s! O* T                tree[parseInt(b1/aa)][b1%aa]=a1;       //b树成为a树的子树，b的根b1直接指向a；$ `  A5 d2 X  p3 {+ p
            }5 k' {( T/ B0 d# k! P5 E6 r5 j0 w1 ^
            else$ V" s5 J0 ^# E2 `
            {' y0 E3 a/ B5 j& Z, h- t, Y
                tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];/ j+ \. Q# T) d- y; D& N
                tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树
* z( k1 R! d1 p4 z: Y( K8 R* }            }
+ U6 f& F' P  o# _' \) e        }: s$ _% x5 F! I5 G3 Q
    }4 w# _, r  `% Q3 R/ _2 I; M. j1 o7 b" H) V

9 U( U" b  j8 o3 x$ g, s    function drawline(a,b)//划线，要判断是上下还是左右/ {* z8 {- t3 m9 w/ x# h/ O# D
    {. J5 x) f  A) f. G

% {2 \. }! U- [8 Y2 z) E        var x1=parseInt(a/aa);
8 D- \! s- m- u8 h  h        var y1=a%aa;
) w1 C9 v/ s2 [9 s4 h3 V        var x2=parseInt(b/aa);
) ]1 E9 g  n1 @        var y2=b%aa;        3 F) u1 W; m# D/ H1 G" O3 i4 Z2 r
        var x3=(x1+x2)/2;
7 j2 M1 l& D2 R  v        var y3=(y1+y2)/2;
4 N# q& e# P2 F        if(x1-x2==1||x1-x2==-1)//左右方向的点  需要上下划线
1 d9 @! d' P: f- j$ \! g/ L% V# B        {
4 L7 ~8 P4 H. Q            //alert(x1);
6 ~1 |6 R" f1 B$ g) @* p            //  context.beginPath();% W0 Y' _# Y# o& C) e( h
            context.strokeStyle = 'white';' |4 U8 \5 \5 x# m
            //    context.moveTo(30+x3*30,y3*30+15);//6 g1 i8 H) \3 O. e" ^
            //   context.lineTo(30+x3*30,y3*30+45);
1 L8 y5 Z) G/ s& U( c7 d8 N            context.clearRect(29+x3*30, y3*30+16,2,28);3 ?0 V3 y0 p" @
            //    context.stroke();
* F) b' ^& K$ x/ i* u" ?/ B        }
/ c) W: J2 `( |7 [6 N- A6 f        else) n; d* Q' a  R; D8 F) N
        {
8 w) N& h1 j4 m5 ^' ~% |            //   context.beginPath();* ]6 {, R2 u/ }1 X5 y
            context.strokeStyle = 'white';
4 K3 ~! g; x6 }            //  context.moveTo(x3*30+15,30+y3*30);//' \8 S" |! d2 j; u' T
            //    context.lineTo(45+x3*30,30+y3*30);0 _( U. z0 l- e( S+ I7 B0 t0 ]
            context.clearRect(x3*30+16, 29+y3*30,28,2);- v; z4 p" N6 o. e
            //      context.stroke();" p# j0 N7 k$ s
        }
9 g* M' T8 f; m+ ?; G    }+ U+ }* d, y* ]' d( b: ^
* O, K! t1 c  `& X9 A+ I
    while(search(0)!=search(aa*aa-1))//主要思路, d4 N" P) j% }6 V# ]! a
    {
: L* Q1 p2 }% d& t$ s* X" W        var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数7 |/ a( ^% B# i  z
        var neihbour=getnei(num);: R: F! n' B3 m$ j8 [: `& s
        if(search(num)==search(neihbour)){continue;}% \1 c2 H3 {0 J+ k! P9 K9 |
        else//不在一个上2 d+ W# j# f& y" s; r5 u
        {$ Y% e  K& s/ K) F% u$ s6 B8 y7 P
           isling[num][neihbour]=1;isling[neihbour][num]=1;5 Y: H7 D8 Q5 p' ~6 g
            drawline(num,neihbour);//划线
% x0 ]5 b/ I6 H8 h9 t$ u            union(num,neihbour);
' J" z) T  y' \& s' p
; s! u( B2 H  N( C6 D        }! a, s6 Z- F) c/ E5 |# \$ l% \
    }
# S4 W: h) L9 q' D+ w' r  </script>
# T( f- @+ n  O' D: P# r( k</html>
3 _1 p5 A9 D7 E
0 b; E6 T$ Z6 Y6 p' Z" ]) @" u1 J  u: \# |% a( ~
实现效果：6 k/ v6 c' n% H. o# c  t! b

% w# h6 b) u/ N2 C# ?+ x* c: @7 w 8.png 9 A' A! g& [2 v: [: U& {

, A4 w7 @' H+ r 9.png 6 n" y0 F: p, w
方块移动4 j" h# {$ U2 X8 z3 ?: k" ?) Y2 y
+ D, M2 U! s9 R' o
这部分我采用的方法不是动态真的移动，而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉，在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除，可以根据像素大小精准擦除。1 c% p! K2 B$ y* ~6 G

) L0 B# M( v, L# U7 [9 R另外，再移动中要注意不能穿墙、越界。那么怎么判断呢？很好办，我们再前面会判断两个格子是否联通，如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组); p- }! u  a" n5 R9 u
5 ~4 B( ~* R; e% C9 J
另外，事件的监听上下左右查一查就可以得到，添加按钮对一些事件监听，这些不是最主要的。
  c/ n6 D& q& c( L: Z& |% U% B; L  F3 z: U1 X8 _& p$ T
为了丰富游戏可玩性，将方法封装，可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外，如果写成动态存库那就更好了。% h2 S# h, F3 i1 U; t& Y
10.png # N2 W4 E( o" D
  p9 i; r  g4 S$ s( F8 _

7 ]0 j* I* V6 \, H. P————————————————  M5 U4 W1 F  q8 Q$ @: Y" ?
版权声明：本文为CSDN博主「Big sai」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。- @! S; b6 Y$ |! M
原文链接：https://blog.csdn.net/qq_40693171/article/details/100716766$ b; Z; Y* S) b$ A! T
* t% U, U. q# }+ i

; h1 o' Z" l6 K$ a% S! V% n$ p
作者: madio    时间: 2020-4-1 12:39
牛人！
$ o* X# _' E3 c# G% M% G7 A& S



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