数学建模社区-数学中国

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

作者: 杨利霞    时间: 2020-4-1 10:57
标题: 我花了一夜用数据结构给女朋友写个H5走迷宫游戏
+ G' L$ F3 d% F5 s
我花了一夜用数据结构给女朋友写个H5走迷宫游戏( @. Y; |" w* B
文章目录
% T& {) o: T6 s5 a5 N4 z3 g2 {" E" v- S4 w( [
起因  p6 X6 p" G7 D; T
分析
9 R. g$ q0 b+ F0 y5 v画线(棋盘)
8 o, D! ?- w. z5 U画迷宫6 ?% y( C& W& [) ]5 ?
方块移动
) T1 v) B  s# y- V: {结语8 Q7 P: w; T; J! X9 j' y
先看效果图(在线电脑尝试地址http://biggsai.com/maze.html):
8 ]3 P9 l1 s, E# C* g+ G; b 1.gif 5 \/ ?7 S5 q+ P
' p* l0 F3 A, z$ W7 ~
起因
4 d. u! P. ]: b% ^ 2.gif ! P( r$ f5 H5 g

2 J& T4 w  X+ l2 Q  ?3 F. f又到深夜了,我按照以往在公众号写着数据结构!这占用了我大量的时间!我的超越妹妹严重缺乏陪伴而 怨气满满!
: t* _; R- X; v+ `- ~" |% B 3.gif 8 p7 ^( W3 ^* e% ^; T
超越妹妹时常埋怨,认为数据结构这么抽象难懂的东西没啥作用,常会问道:天天写这玩意,有啥作用。而我答道:能干事情多了,比如写个小游戏啥的!
' ?$ Y# S7 |& H 4.png
! s5 O- I- V% [当我码完字准备睡觉时:写不好别睡觉!
+ Y3 {. u5 x% {6 d$ U6 n# f* z9 M- l
5.gif
. N" K& k, B' z4 @) s3 I分析
+ q+ T( ?. @& G
+ u+ S0 E5 M" X# a; \5 L如果用数据结构与算法造出东西来呢?
- h5 c7 E8 S  x' i& i; T! o, X3 i
* X. L$ d+ a/ q" ]" u# j什么东西简单容易呢?我百度一下,我靠,这个鸟游戏原来不好搞啊,得接触一堆不熟悉的东西,搞不来搞不来。
  o: Y8 M7 u1 B6 T有了(灵光一闪),写个猜数字游戏,问他加减乘除等于几。
- q4 V* h* g* n1 n2 v# F  m/ d2 r( K+ R! t7 w" l+ G9 F
超越妹妹又不是小孩子,糊弄不过去。
1 j8 b" P* x9 M; C+ U* a% c经过一番折腾,终于在半夜12点确定写迷宫小游戏了。大概弄清楚其中的几个步骤。
2 Q3 `; m1 A3 n* S$ h9 }" s
( M3 P& k8 j8 d/ {- W3 s大概是:: l& I! _+ m( h+ B1 _
2 q) K2 N  @) D( w# X5 S- |: U
画线—>画迷宫(擦线)—>方块移动、移动约束(不出界不穿墙)—>完成游戏。' Q( N! E/ |& Z% |% U
画线(棋盘)5 q8 {4 Q: R: a# U& p
5 t# M4 f1 O9 F8 y7 F  ?( [  p
对于html+js(canvas)画的东西,之前学过javaswing应该有点映像。在html中有个canvas 的画布,可以在上面画一些东西和声明一些监听(键盘监听)。. M  L" z& d1 g0 J; ?: \( S

7 w( g1 t5 v. v  M$ ~1 F对于迷宫来说,那些线条是没有属性的,只有位置x,y,你操作这个画布时候,可能和我们习惯的面相对象思维不一样。所以,在你设计的线或者点的时候,记得那个点、线在什么位置,在后续划线还是擦线还是移动的时候根据这个位置进行操作。
9 d+ v+ }& x7 j <!DOCTYPE html>
- X+ b. h( J/ N; b) N9 B& Z<html>
. K4 U0 d3 G% e$ e+ F  d  <head>
* M3 ~- V" O8 S9 ~6 D, o  [% e    <title>MyHtml.html</title>       
+ d8 c1 J! o$ w6 S0 d" L$ _1 U1 k  </head>
& c! r" I, y; ?- c$ Y& A) d  Z  <body>
* D& {* S# G  V0 z9 D  <canvas id="mycanvas" width="600px" height="600px"></canvas>- t/ k! v& v* j" H4 Q7 t
. [% b, i% |7 a3 ?+ c; K' j7 n7 Z
  </body>: b- C0 L/ N- Y
  <script type="text/javascript">
. x' k6 F) ~6 l/ U  D5 r6 b5 E
+ l; Y/ U2 @- U1 dvar aa=14;* l6 P8 x4 g3 o* J
    var chess = document.getElementById("mycanvas");
  d! N7 x) k" e$ g2 u! r& n5 o8 }8 q$ B    var context = chess.getContext('2d');
& Y$ _+ q8 _! S7 k0 l6 f" c4 h9 S  l$ u1 ^) h' K. _
    //  var context2 = chess.getContext('2d');
5 }7 H5 G/ q! e: X  u, Y4 E4 b    //      context.strokeStyle = 'yellow';' t7 g# B! U4 H: d- M+ }
    var tree = [];//存放是否联通, k! G) d; U/ E( m* ]
    var isling=[];//判断是否相连
2 T; ]2 |9 e' |1 \    for(var i=0;i<aa;i++){
6 F. V* I5 a. |; Y9 Q- P# z* C! X        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 6.png 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 7.png
  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;        
, I9 e3 ^. T  w( M  s  _7 U( P' u0 F        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
8.png
5 P& E6 C2 [1 G  `& E0 S: \
( H0 V/ p# p* |7 _ 9.png
- |# 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
10.png
: 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