数学建模社区-数学中国

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

作者: 杨利霞    时间: 2020-4-1 10:57
标题: 我花了一夜用数据结构给女朋友写个H5走迷宫游戏
3 K7 ^6 T  P) ?2 I9 _
我花了一夜用数据结构给女朋友写个H5走迷宫游戏
% u9 \1 a" H' l3 R& a文章目录% @1 |8 n# B0 E# R- m; c/ Q
5 q. ?1 F# O3 D
起因& n% q: K7 \. n* q6 O. a
分析
9 U; h: Y8 u5 y2 q画线(棋盘)
: W8 Y) E+ @1 M1 M( e( t/ C画迷宫, H$ X* w( b& r% ?+ N8 Z. I  ?7 g
方块移动
$ U* u- a9 D. \结语1 h" M1 o* i2 V0 j' ?) |/ @6 M
先看效果图(在线电脑尝试地址http://biggsai.com/maze.html):
1 g7 C* h& H) Y  k" D" D 1.gif
' [% s( Z- o- U: h9 T0 R3 @/ O) B& }0 a4 I! W! G
起因. X( e* j+ ~3 ~! ?( y. W
2.gif
" i4 ^& i" \( h" q' f* [' t& O' N
5 @' f  N$ a8 p* }6 A* K又到深夜了,我按照以往在公众号写着数据结构!这占用了我大量的时间!我的超越妹妹严重缺乏陪伴而 怨气满满!4 I- E, {: I9 N/ ]0 _8 v0 U
3.gif
/ O7 S6 i" t4 ^+ G% f" v超越妹妹时常埋怨,认为数据结构这么抽象难懂的东西没啥作用,常会问道:天天写这玩意,有啥作用。而我答道:能干事情多了,比如写个小游戏啥的!5 q, Q& \1 S7 G0 _/ Y
4.png ; X' S, n+ I, o. Z: |: t8 q8 p
当我码完字准备睡觉时:写不好别睡觉!$ L5 ^3 v7 [+ e# }, `3 w2 o/ r

' }" {! }1 }3 V. R* M1 |/ E0 R& i6 H 5.gif ( W$ L+ T9 ~4 u
分析
8 t: W: W/ i- E: `$ r# U& O, V
" ^8 O$ Q8 n1 S如果用数据结构与算法造出东西来呢?
3 I6 l* W' K7 B* l% c, F
9 ^- [9 f7 [  ^+ ^什么东西简单容易呢?我百度一下,我靠,这个鸟游戏原来不好搞啊,得接触一堆不熟悉的东西,搞不来搞不来。
" c6 @' g. V7 B7 x6 u5 i有了(灵光一闪),写个猜数字游戏,问他加减乘除等于几。' v/ l$ w2 R5 j8 t" Q

5 f+ G; ^4 a4 [0 f超越妹妹又不是小孩子,糊弄不过去。6 ^6 i. Y: d. R  I
经过一番折腾,终于在半夜12点确定写迷宫小游戏了。大概弄清楚其中的几个步骤。
+ O9 k$ y9 B8 i9 }" W+ @. R8 c* `9 O7 @5 I4 f# f
大概是:8 @8 z; h8 N0 L. E" W0 m
; k5 \: L8 Z$ L, B  X
画线—>画迷宫(擦线)—>方块移动、移动约束(不出界不穿墙)—>完成游戏。
& h. ]  E* T, l6 L5 A0 s1 x: `画线(棋盘)
: i0 U  s6 }( \" E9 S3 R  z5 q6 f) ~4 @
对于html+js(canvas)画的东西,之前学过javaswing应该有点映像。在html中有个canvas 的画布,可以在上面画一些东西和声明一些监听(键盘监听)。
! T8 m" b3 y. p% I* o1 [% _3 s' _: i$ n
对于迷宫来说,那些线条是没有属性的,只有位置x,y,你操作这个画布时候,可能和我们习惯的面相对象思维不一样。所以,在你设计的线或者点的时候,记得那个点、线在什么位置,在后续划线还是擦线还是移动的时候根据这个位置进行操作。4 l5 B8 Z+ Q" l0 y$ U2 p. B
<!DOCTYPE html>
+ x7 j! S0 s  O! P! b% X<html>
# I0 O, u' w# Y! q7 A  L  <head>
9 `0 l- t, |# _! P  ^4 z    <title>MyHtml.html</title>        1 v1 I/ P+ m6 \$ ~. o& l: B
  </head>
, U! g5 ^* M% p$ i0 k3 x% r  <body>
9 M6 s7 ?1 P" [( [: b  <canvas id="mycanvas" width="600px" height="600px"></canvas>: l- P/ H- D+ X' R7 C6 ?
7 u8 H, ]) `7 l# b% j3 X& q$ Q7 Z
  </body>9 `7 w. c& h" ?- V
  <script type="text/javascript">
. K+ E# n1 \+ `; u  J2 L+ ^: G' p4 B. ?
var aa=14;6 j6 D8 p+ T: a. \" ^
    var chess = document.getElementById("mycanvas");8 m' J1 a; c6 L& ]/ I+ k; D( L
    var context = chess.getContext('2d');
+ o( |7 H" Q) t, a  a1 W2 u( |$ g, [3 Y; C7 U2 b
    //  var context2 = chess.getContext('2d');7 p0 ~0 b3 g$ @" i$ c# I/ I
    //      context.strokeStyle = 'yellow';
! a* q. v( w- `" G% P/ [" l0 R    var tree = [];//存放是否联通$ n* p& k+ F; T' D; l5 \
    var isling=[];//判断是否相连- H* |: w5 E  M! Q: Q
    for(var i=0;i<aa;i++){1 R5 E0 \' E- b' x
        tree=[];
. R8 @( c' Q! Q5 G9 G  u; ~0 `        for(var j=0;j<aa;j++){4 L9 U* M5 ?/ w5 C
            tree[j]=-1;//初始值为0
: L: ^& x+ k7 w# `' N: u8 Q2 I        }  a8 L- \, s5 ~1 w( ?
    }  for(var i=0;i<aa*aa;i++){
$ C; V7 a8 @5 F9 S- s7 g        isling=[];5 r- p+ y  K% \$ Q1 h& I1 V
        for(var j=0;j<aa*aa;j++){
+ Y. c. O% B: M8 T5 z2 P6 w% Q            isling[j]=-1;//初始值为0% W, ^1 P. T" N# x1 e& w6 i! U# `
        }6 W, i% z  M1 c  N' ?6 V
    }6 M; q( k& @6 c+ v2 p/ P

7 p3 r6 g+ Y# [) R1 H. A% G    function drawChessBoard(){//绘画
+ j9 j  `" j! U3 h3 `1 |        for(var i=0;i<aa+1;i++){
' [: X7 n2 B+ E  n; H! N+ u3 x3 r2 V            context.strokeStyle='gray';//可选区域$ x3 W; w* e# x. G# |% M
            context.moveTo(15+i*30,15);//垂直方向画15根线,相距30px;5 `6 m2 ]' F' d9 {2 a
            context.lineTo(15+i*30,15+30*aa);
( l+ Y8 V, b  Y1 T8 o            context.stroke();0 ?3 X, f1 Z7 N- R  ]: P: R
            context.moveTo(15,15+i*30);//水平方向画15根线,相距30px;棋盘为14*14;
6 K0 A* |4 _3 u$ c0 |; z            context.lineTo(15+30*aa,15+i*30);
4 K- ?& ^3 l* B9 q            context.stroke();4 ~, \$ m( c4 W+ y" L% Q
        }" ^# G/ ^' K7 |; B6 X+ ^
    }
. e% p) v4 `5 K, u) V1 D' J4 Z    drawChessBoard();//绘制棋盘
( l+ b% ~/ ]/ d2 K5 S/ Z$ |& f  N2 g" V: q0 G' o
    //      var mymap=new Array(36);
: Z/ B3 C% j6 X; F: R4 @1 U    //      for(var i=0;i<36;i++)' ]8 @! r8 y8 \0 u; l
    //     {mymap=-1;}8 ^1 D* c; h9 z: x$ y
# N: k; h- z4 z$ c% k6 b/ A

& F+ p/ l5 D" M/ c6 r1 }  </script>
* n8 B* A* I* `  T% W* T</html>
0 }8 Y9 }4 n: S( U* Z
( e2 a$ h# e9 y' m8 C9 j: A7 ]" m9 {. e# s+ b. M0 w3 h1 l) U* r! A
实现效果
* `7 s8 x  B; c, V9 A6 Q 6.png 9 s# @+ g7 b+ N6 d! l( M
- H9 U% b  G+ C
画迷宫" L* l% M/ r  H6 s+ B$ {" {

) R1 r$ w) d+ m随机迷宫怎么生成?怎么搞?一脸懵逼。# }9 S. I) Z& l5 H7 e. y5 H

8 q1 m5 v( o5 P7 I6 z因为我们想要迷宫,那么就需要这个迷宫出口和入口有连通路径,你可能压根不知道迷宫改怎么生成,用的什么算法。小声BB:用并查集(不相交集合)。
9 l9 _8 Q. c0 m8 X迷宫和不相交集合有什么联系呢?(规则); n0 J5 F, b, @5 G
# ?# u( W1 g" [! H0 L! p
之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合),它的主要功能是森林的合并,不联通的通过并查集能够快速将两个森林合并,并且能够快速查询两个节点是否在同一个森林中!
; D% \4 _& ^* j; Z而我们的随机迷宫:在每个方格都不联通的情况下,是一个棋盘方格,这也是它的初始状态。而这个节点可以跟邻居可能相连,也可能不相连。我们可以通过并查集实现。
; E7 y' d! f/ c" O- M; n' y1 |5 @5 k
具体思路为:(主要理解并查集)' o8 o' I' v8 e9 e. ]1 V7 C' k

( ]+ _- m$ `) p$ ]6 ]1:定义好不想交集合的基本类和方法(search,union等)8 K" |# V( f# t# E
2:数组初始化,每一个数组元素都是一个集合,值为-1
$ B  Z; W% E" ~) H8 A2 z6 i3:随机查找一个格子(一维数据要转换成二维,有点麻烦),在随机找一面墙(也就是找这个格子的上下左右),还要判断找的格子出没出界。; ?! I1 ]1 O. V/ ^) Y
具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界
& }# Q; S5 [' M6 e3 V4:判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在,则重新找,如果不在,那么把墙挖去5 t& ]; h3 }0 E7 \4 a
5:把墙挖去有点繁琐,需要考虑奇偶判断它那种墙(上下还是左右,还要考虑位置),然后擦掉。(根据数组转换成真实距离)。具体为找一个节点,根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。8 |0 l* r! o# e+ y
6:最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙,但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据,并查集操作。二维是位置。要搞懂转化!
: V  M" H; e- S3 J注意:避免混淆,搞清数组的地址和逻辑矩阵位置。数组从0开始的,逻辑上你自己判断。别搞混淆!
% Y/ L) O0 D( n  ?3 `' Q# Z; ~ 7.png
8 b9 K6 ~) U8 X2 t" r主要逻辑为:
2 V; R3 r8 z! A* C1 ~) h* m* ^while(search(0)!=search(aa*aa-1))//主要思路$ S- N" x5 D! q" ]/ l
    {
& R2 F. `+ t/ y        var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数/ ]( G( ^6 f8 Z  \8 o6 O
        var neihbour=getnei(num);; m4 D6 p9 `3 r+ T, e6 x; F  w
        if(search(num)==search(neihbour)){continue;}
+ G( c( a9 |2 p. Q, q/ `# k        else//不在一个上
( h/ u7 t, _: l' J        {
1 Z. C- [8 q" V           isling[num][neihbour]=1;isling[neihbour][num]=1;% E" Y" i! q! v; p
            drawline(num,neihbour);//划线0 A, c/ F  Y% ?" Z+ N8 w
            union(num,neihbour);) s* {$ T$ }9 ^7 w
# O4 K, o* ~. F/ z
        }
) z. m$ Y( ]' |: X' U1 B2 D9 h% Q& q& H    }2 ^1 i: I' c/ ]
. W- A5 P; @0 g% }% l* i4 z4 m) A6 _
; u/ L8 s( n' _; X: S' D
那么在前面的代码为
& \6 I8 U  }6 W, F% Q. h5 o<!DOCTYPE html># V# f( T9 J! |$ X/ ?) L
<html>
, y7 X& ^: s' ?0 O  <head>
* y: X4 ?) a$ K& T8 T    <title>MyHtml.html</title>       
# j, O2 _2 P0 }7 V  </head>
! b# y% S0 h) x) j* k# B+ d5 f" L  <body>
% B! j8 u4 ^* B" @/ W" a  <canvas id="mycanvas" width="600px" height="600px"></canvas>
3 l& ?* l4 ^, C' p  ]3 [4 y! F! m* ^& T8 G2 h
  </body>
5 h9 ]  J$ N- S2 I6 {1 \6 Y  <script type="text/javascript"># v( X( X: N1 i5 r6 q; A7 Z$ B
//自行添加上面代码5 T  {0 z6 V: V+ K/ Z9 I) X0 ]
    //      var mymap=new Array(36);
6 U& \# O+ `/ T0 E1 ]. d* |1 p9 t    //      for(var i=0;i<36;i++), S9 h* G7 H" Q8 ~
    //     {mymap=-1;}
9 b: g$ K/ a" X* n0 V( F    function getnei(a)//获得邻居号  random2 a9 n+ B! s, T4 e0 l6 m( O" b
    {
. f% M3 N$ u( N; b  z        var x=parseInt(a/aa);//要精确成整数2 ^* x6 |, O% H* |
        var y=a%aa;" b6 K+ B; k+ l+ M% B, |0 k
        var mynei=new Array();//储存邻居% o9 Y' v8 Y# @
        if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点& _. r8 S5 j+ L2 C* D
        if(x+1<14){mynei.push((x+1)*aa+y);}//下节点
. f; w/ l- f7 U: L8 w" f        if(y+1<14){mynei.push(x*aa+y+1);}//有节点7 Q: r. v  W6 \: g
        if(y-1>=0){mynei.push(x*aa+y-1);}//下节点: k3 i' B: u$ H, O
        var ran=parseInt(Math.random() * mynei.length );
7 |. x( k6 K3 \& V6 P        return mynei[ran];
6 L) }' @; ~, v! s5 Y; P0 k! v* @  Q$ x; m; {( H! L& I
    }* i$ `/ b! U* J' I
    function search(a)//找到根节点
4 ~& ~" M5 S0 O* q0 A    {8 ~$ J/ W! L$ X% P* w( C
        if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点3 r, m5 J" @9 X7 S$ v7 a+ [8 D: E
        {
" E: y% y  ~) {+ v( l, s            return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩
! b" U( ]3 {$ V3 w* u+ A        }
. l3 l# v# E! `9 d% r        else# e' d/ K  _; q. E) I. A" Q
            return a;
! t9 U$ A& G! n, B8 p3 N/ _" U    }" X( N$ w9 _1 ~
    function value(a)//找到树的大小
9 F: Z  b! F. s7 P  |% n4 B, Z    {
4 V/ s- Z+ |. i- c' Z        if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
/ ?+ Q* w. o/ F2 B, f' \- H  ~        {" [4 [& k+ k* F/ C- G
            return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩* N! a6 U! L# V6 [, @
        }! B! N! |& F7 n! E8 [9 O
        else
3 `. W9 X! G7 {) I            return -tree[parseInt(a/aa)][a%aa];
. C6 d4 G" {6 l) L/ X    }. z) W* u- D$ T* {# J
    function union(a,b)//合并
5 _: Q( Y  }- G1 |    {% M6 J9 c& _7 y5 V9 V0 Z) @
        var a1=search(a);//a根
0 _, E/ N0 q9 x4 f- y0 J' ^& J        var b1=search(b);//b根
$ v# z& a: m) C& U$ U        if(a1==b1){}8 \4 a& ~' m# {% c
        else( g, o: A6 L% A/ {- Q
        {4 A7 A; p$ D1 o( U* ~1 O
            if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数(),为了简单减少计算,不在调用value函数% a" L7 u: f# ], t- s' ~
            {
8 z2 Z& j( K1 O$ I9 ~6 h                tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加  注意是负数相加4 O* ~8 W. ]# s1 \8 o& G# O+ v
                tree[parseInt(b1/aa)][b1%aa]=a1;       //b树成为a树的子树,b的根b1直接指向a;% Z4 s& `# A4 h, X! J0 Y
            }" h, k6 H. Z' h2 w( |
            else
  e! ]9 O; F0 u            {
- t! _& U# b" J3 Q                tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];; q! }" ]! R) G7 @! C+ M  O- r
                tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树2 w% o" d2 _& e) \' O; @
            }
1 D  T* w- F* f7 R- D8 e! F        }4 C# Z8 [" X1 n7 z+ W; D
    }
( A5 j3 E( S/ @4 N! w" o
/ F) k2 d# }+ s1 ^6 c% i    function drawline(a,b)//划线,要判断是上下还是左右
. `- W6 o2 i& R  N2 |8 e    {
1 |8 {3 Z& }+ }0 I# k  f/ p: r% `9 [, G0 H7 K& @
        var x1=parseInt(a/aa);: b$ O7 r  x( b1 Y+ b$ `- F- m' r
        var y1=a%aa;# u5 E- x+ V+ m2 [; r
        var x2=parseInt(b/aa);
3 m# d% Z& L3 B  T        var y2=b%aa;        , _+ M- H8 B' c3 P5 X# w7 I
        var x3=(x1+x2)/2;* |3 n  k% E2 e$ u! B3 B
        var y3=(y1+y2)/2;
2 g" ~. [- f8 ~6 d2 r3 w% E        if(x1-x2==1||x1-x2==-1)//左右方向的点  需要上下划线
) g/ {/ N! N9 Z7 j- ]+ _  m. D" {- u        {
6 _# V% x/ {+ `* F            //alert(x1);
. S: c4 F1 [5 ^* J' z* K! Y" x            //  context.beginPath();3 x& {3 R5 P9 R8 X, q9 j' n/ B
            context.strokeStyle = 'white';( q( ~4 ^4 M4 }4 T& K4 p! l5 J
            //    context.moveTo(30+x3*30,y3*30+15);//; A6 F' R/ q0 o  {. a
            //   context.lineTo(30+x3*30,y3*30+45);# c* J& B+ n* b2 ?0 f; y
            context.clearRect(29+x3*30, y3*30+16,2,28);
) b0 V: O- |& {: Z  m3 l            //    context.stroke();
9 O1 S+ Q& d4 z8 ^/ ^$ O        }/ \7 U, l8 n5 _7 `
        else9 _# @; m: h1 C$ e; g& {  f
        {
) F; Z5 g- }- J. I            //   context.beginPath();
6 r+ g8 h! J3 i( |            context.strokeStyle = 'white';
: h, z0 }0 x8 n/ z* _6 R            //  context.moveTo(x3*30+15,30+y3*30);//+ u' o! h5 \. u7 P' R8 c
            //    context.lineTo(45+x3*30,30+y3*30);6 x4 [# V3 I% t2 {9 R
            context.clearRect(x3*30+16, 29+y3*30,28,2);. q7 d  S; w9 ]
            //      context.stroke();) a- u; W) h6 K, ?0 C7 ?
        }
6 t7 V- V' o! ]2 X9 D4 S    }1 R2 x, X1 D5 q7 J  b
% h' a; F% E% g4 Q7 ^; I3 D
    while(search(0)!=search(aa*aa-1))//主要思路/ D& x& T- |7 {( M) q
    {
; g# ^7 y) J. P' G: v- ?( J        var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数- E; ~: `5 H' F5 D8 h2 F
        var neihbour=getnei(num);
( |1 @4 u; h: o, _2 g9 ~3 f        if(search(num)==search(neihbour)){continue;}: G! ~) z  h2 u
        else//不在一个上; l! B* s$ q4 `, \5 [3 @
        {
' `0 W% {1 l+ i! w6 U: S           isling[num][neihbour]=1;isling[neihbour][num]=1;7 k; g" i( `6 Z
            drawline(num,neihbour);//划线
) X: x* ]( J- s' Q            union(num,neihbour);# f' b. H# F0 [! ~2 G

( V4 c& z8 P$ v. B        }+ B2 r' v( f, T% U
    }/ f( H' r: D/ [; D& G$ }
  </script>
! b7 G# z" ]" b3 }& Z- ], k</html>
  @. I" \% _0 k3 H$ X6 q8 m) b# X" `# }2 F, h: a" _
+ f8 H4 d( S4 T' }. Q$ R
实现效果:6 {: x" l3 Q8 {2 N. U5 C& u5 U
0 ^% e. U- ^# z3 b" h
8.png
! \9 e' s0 {: m' T# f. G
* y0 P4 r3 U3 b% e5 T$ Z# c1 V; w% M- } 9.png
2 M$ K6 i/ y( k( Q& k4 C5 v8 r方块移动2 I# |. R% j% s2 z6 w

/ M% V: r2 E4 Z) m" Y: A' B这部分我采用的方法不是动态真的移动,而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉,在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除,可以根据像素大小精准擦除。
2 D, C( U( }5 D0 P
9 ^6 B& T2 G: c! C另外,再移动中要注意不能穿墙、越界。那么怎么判断呢?很好办,我们再前面会判断两个格子是否联通,如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组): w. m) @# |; ~; n6 G8 j  D

. |( q7 K2 d+ P3 _4 D4 i' c另外,事件的监听上下左右查一查就可以得到,添加按钮对一些事件监听,这些不是最主要的。. @" z. q. `8 x! M7 I! h6 G

( D: n+ n* }, U! S% L8 v; ]为了丰富游戏可玩性,将方法封装,可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外,如果写成动态存库那就更好了。
& [- A3 \$ U9 \ 10.png
% m$ T7 w& U1 v8 v* n$ m+ Z2 u- W1 F+ |4 b
# e6 Q: i! I; H8 E5 y, y1 `2 v
————————————————
, l  y8 b. E: H6 \  B# E版权声明:本文为CSDN博主「Big sai」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
8 O# \' A7 T+ W3 Q5 d原文链接:https://blog.csdn.net/qq_40693171/article/details/100716766
* p6 g4 ^  d0 l6 J- ?/ A4 _' |
' M6 `4 C( \1 E2 f6 Z5 U" d
) W0 ?1 h) u- c4 s" ~& \; G
作者: madio    时间: 2020-4-1 12:39
牛人!9 t# u# E2 m/ g  R9 k7 C1 H





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