数学建模社区-数学中国

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

' Q$ v, B! f3 ~8 P) @我花了一夜用数据结构给女朋友写个H5走迷宫游戏4 w5 X( h0 Q' H" G
文章目录; e+ k) Y+ L% `8 N4 x, `) w
0 U6 w+ F1 Z3 ?* a2 Y4 ]
起因
* v- S9 p, Z) k. {0 ^分析
- E2 V# O& `/ y+ @5 Z画线(棋盘); h. g) \( W/ {, U1 g
画迷宫
! I! x7 @% |* E1 Q方块移动% V, }3 v/ W3 k( j4 l. d, V
结语
1 c% k# D# A- j* T* P% {先看效果图(在线电脑尝试地址http://biggsai.com/maze.html)：
% J; l- G3 F- ]# d8 L 1.gif 6 Q* w6 ?. a0 i+ z& u9 m4 A2 u

$ d; i* ~% y5 m  y. f& d/ p( o起因2 j* w- g3 H, ~- q4 }: e+ _
2.gif " a2 B' ]0 V# I
" D0 V0 ]1 T; }
又到深夜了，我按照以往在公众号写着数据结构！这占用了我大量的时间！我的超越妹妹严重缺乏陪伴而 怨气满满！. @7 m) L; b& y- w) n
3.gif
9 `& I8 K! L. }/ H! g超越妹妹时常埋怨，认为数据结构这么抽象难懂的东西没啥作用，常会问道：天天写这玩意，有啥作用。而我答道：能干事情多了，比如写个小游戏啥的！
& `# a- s9 n8 @. B& t 4.png
  z1 n) k1 O( u/ Z当我码完字准备睡觉时：写不好别睡觉！
' p9 E* I: Y1 J, @0 ]: U* l9 C& Z( _- ?0 o
5.gif # O" `+ K! l; v6 p
分析( c1 P' }2 ?, U6 z- z

. x; P0 h' F8 s# W- ]7 {如果用数据结构与算法造出东西来呢？4 o/ H8 t6 z+ f6 }! Q; B

: T" T7 M7 Y5 I1 }$ k什么东西简单容易呢？我百度一下，我靠，这个鸟游戏原来不好搞啊，得接触一堆不熟悉的东西，搞不来搞不来。  i) }0 f2 y9 ]9 H8 j4 W
有了(灵光一闪)，写个猜数字游戏，问他加减乘除等于几。1 L; I! c: H3 u/ y$ X

1 b! c- Q$ P7 z  q7 z5 _超越妹妹又不是小孩子，糊弄不过去。1 E0 Z6 N1 p& j) @/ Y
经过一番折腾，终于在半夜12点确定写迷宫小游戏了。大概弄清楚其中的几个步骤。6 E1 w% Q+ o" z* p- M( J. A

( y7 U$ @$ z& t; R) Z) P2 o大概是：$ ]+ S; c1 C' v3 N

; l  A" n  W! x# u( {画线—>画迷宫(擦线)—>方块移动、移动约束(不出界不穿墙)—>完成游戏。, U; u4 a: {! t" S- c) F
画线(棋盘)
: S! [- [( R2 g) x
1 G5 F( x8 |8 J对于html+js(canvas)画的东西，之前学过javaswing应该有点映像。在html中有个canvas 的画布，可以在上面画一些东西和声明一些监听(键盘监听)。% K# n3 {. F+ y
& a2 e5 n% F) n) U  u) C, C
对于迷宫来说，那些线条是没有属性的，只有位置x,y，你操作这个画布时候，可能和我们习惯的面相对象思维不一样。所以，在你设计的线或者点的时候，记得那个点、线在什么位置，在后续划线还是擦线还是移动的时候根据这个位置进行操作。" H  d! F& [8 R
<!DOCTYPE html>6 o. T7 d* @% O1 p8 O/ E4 T! _
<html>
. R( w+ l2 c, b2 L5 y' a  <head>. [! K8 U! `+ N. b) H* R
    <title>MyHtml.html</title>       
6 s/ u( a$ _# Q3 t2 H+ ^  </head>
( R2 |1 `$ T2 u  <body>4 A# `2 E, C5 _4 a; f3 v
  <canvas id="mycanvas" width="600px" height="600px"></canvas>
! B# i2 r# l9 c! Z$ U1 O! Y! t* L0 O: \9 J6 u# U
  </body>/ u& b7 T. I! k
  <script type="text/javascript">
! I; a8 o2 @( p1 ~. t3 |( ~" ~! S, l- ?# I3 ?
var aa=14;
5 G5 s" H' O" H0 q8 A6 |$ G5 }    var chess = document.getElementById("mycanvas");$ _! L8 i% ^; g3 m7 ~
    var context = chess.getContext('2d');
3 m" O% S. {, A3 _7 L9 T
* g' Z/ R' [2 c    //  var context2 = chess.getContext('2d');" H8 ~5 Y) U+ p# i0 U$ K0 B8 I
    //      context.strokeStyle = 'yellow';% ^" S* n  X, k+ ]/ ?
    var tree = [];//存放是否联通4 [& _6 g1 c: P/ `7 G
    var isling=[];//判断是否相连* ]# H6 a# [3 F' Y" d
    for(var i=0;i<aa;i++){
6 Q" y; `% X/ M, i! d        tree=[];
) J  q* e9 w$ p' p$ S" ]' i        for(var j=0;j<aa;j++){
$ h! E8 ?- E& C* q            tree[j]=-1;//初始值为0* Q; \; Y0 C: k
        }! ?8 }% l3 P& e
    }  for(var i=0;i<aa*aa;i++){" ?# k; M5 l" V! n% N
        isling=[];& K# r7 W, L6 H* q0 d" Z
        for(var j=0;j<aa*aa;j++){: p( T2 c2 c' J$ N
            isling[j]=-1;//初始值为0% K7 Q1 t6 Q' s' L; v, L% d; \) t
        }
5 X1 R/ E4 ]: Z* \, P4 k    }
& z6 D, F5 [! Z0 Q: T; C% E/ A! u) J$ o' |
    function drawChessBoard(){//绘画& j3 Q( b/ `$ w5 {1 z+ h
        for(var i=0;i<aa+1;i++){9 D8 l; u) d+ {0 _5 b
            context.strokeStyle='gray';//可选区域
/ X: t& W8 Y: P! }            context.moveTo(15+i*30,15);//垂直方向画15根线，相距30px;/ q( f* \; i5 O( L
            context.lineTo(15+i*30,15+30*aa);* B) W' G* @; p
            context.stroke();
5 n9 V, E( @8 Y5 `            context.moveTo(15,15+i*30);//水平方向画15根线，相距30px;棋盘为14*14；. Z) Z/ c6 z8 V# V
            context.lineTo(15+30*aa,15+i*30);
. {2 L5 X* d# q            context.stroke();4 V/ d' R7 `$ V# o2 h9 E: N( I" p) t
        }7 v, v: j' o) K: r7 I
    }/ \4 V/ j2 U! _1 b5 h
    drawChessBoard();//绘制棋盘! `  J2 |/ \( {' H7 P+ [
9 h1 j2 b9 F4 r  I6 p- t9 X
    //      var mymap=new Array(36);+ z  C1 G8 }' t$ e
    //      for(var i=0;i<36;i++)
. o% ?; A! e: n$ x7 x) s9 R    //     {mymap=-1;}
  N7 x8 ?1 H9 _. _( m6 v- ^! M; M: f+ O0 W/ Y- V: w4 o
1 K( c% L5 {5 W% H$ I% g' {- i
  </script>! ~: v! x/ k6 P: e1 F
</html>
5 M$ k3 x0 b1 M6 o  ^/ p& e/ o9 h! N8 R8 r: R+ O" T; ~3 D% U

# K' {, @5 d* M8 X实现效果0 Y! _3 x4 P$ S
6.png
: h( B/ e$ D5 r& l# \6 t
8 T1 f7 i' H( R# H画迷宫
' t0 p2 v- n% \8 H5 P: |. }2 c) j. ?  ~# Q6 d4 _9 m
随机迷宫怎么生成？怎么搞？一脸懵逼。! J3 Y% U; `" O

5 ~' K, Z0 m) p) F  d因为我们想要迷宫，那么就需要这个迷宫出口和入口有连通路径，你可能压根不知道迷宫改怎么生成，用的什么算法。小声BB：用并查集(不相交集合)。3 c. z0 x9 E( H0 o8 S: P
迷宫和不相交集合有什么联系呢？(规则)
0 _; p$ p: I, _; V' H
4 G$ C( }  e1 a  ~- u  B5 D0 q之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合)，它的主要功能是森林的合并，不联通的通过并查集能够快速将两个森林合并，并且能够快速查询两个节点是否在同一个森林中！$ b# y5 A( n3 q; Q
而我们的随机迷宫：在每个方格都不联通的情况下，是一个棋盘方格，这也是它的初始状态。而这个节点可以跟邻居可能相连，也可能不相连。我们可以通过并查集实现。5 `9 g: B* i& N$ y
  R: b) X% E) A2 U
具体思路为：(主要理解并查集)8 Y8 w" I/ B. y% E

, N, z4 D, C( q  k: H1：定义好不想交集合的基本类和方法（search,union等）0 m$ B! }- _& y: r
2：数组初始化，每一个数组元素都是一个集合，值为-13 G: r& C% g) G7 B! Y
3：随机查找一个格子（一维数据要转换成二维，有点麻烦），在随机找一面墙（也就是找这个格子的上下左右），还要判断找的格子出没出界。
/ D, ^/ B) h6 w9 e6 W# r( h3 e具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界9 ]  q5 V- d  d7 r
4：判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在，则重新找，如果不在，那么把墙挖去; M9 U$ \! Z$ C  z% W3 v8 N
5：把墙挖去有点繁琐，需要考虑奇偶判断它那种墙(上下还是左右，还要考虑位置)，然后擦掉。（根据数组转换成真实距离）。具体为找一个节点，根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。' g5 j2 p* h: B! m
6：最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙，但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据，并查集操作。二维是位置。要搞懂转化！
1 R0 S* W$ ^5 E) {! e: s9 ^0 O注意：避免混淆，搞清数组的地址和逻辑矩阵位置。数组从0开始的，逻辑上你自己判断。别搞混淆！0 M7 a# d5 d- _, \2 b8 v
7.png
4 d9 L6 P& R+ c8 C主要逻辑为：
+ q5 K( N: p" bwhile(search(0)!=search(aa*aa-1))//主要思路" H! Z* E! N# F0 r
    {
) Y# ?. O$ [# g7 }& ]' \' ]2 h        var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
  r' y, r7 a8 j1 |/ x( y' Q" {! O        var neihbour=getnei(num);
' z( c# C4 L: v        if(search(num)==search(neihbour)){continue;}
: S7 e9 ?6 \9 N$ r- ?: X& z" m1 Z2 b0 A        else//不在一个上- l3 W  N6 z0 ?) [! a6 o+ o- r
        {
8 C8 f1 I& j8 }5 L5 n, Q           isling[num][neihbour]=1;isling[neihbour][num]=1;7 ?: O4 U3 [- O, B1 e
            drawline(num,neihbour);//划线
, Y/ l3 ^9 F* g# j. F+ u            union(num,neihbour);3 j5 Q& {9 R. J7 q; X  F
# S( h5 |- F; f6 @. h
        }' k: X) P* Q; y1 q/ _
    }
. G- F5 S% u4 g( y
5 l/ |0 |8 g. G7 h" D$ W
4 D! G8 _# E  C4 v3 Y5 V8 {那么在前面的代码为$ A" [1 M$ C7 `, g( t6 r
<!DOCTYPE html>
; ?3 I/ C! a+ V( Y$ ~; f9 ^! T<html>5 S8 N& j/ D, Q
  <head>3 |, b% n/ D% \) ], h8 @  f. [( E
    <title>MyHtml.html</title>        3 y* R, N5 r+ K
  </head> 9 i2 |3 ?7 L, {, _
  <body>
, g* I- O; r3 y1 g( H; j" f, {: j  <canvas id="mycanvas" width="600px" height="600px"></canvas>
: c& g5 _$ L6 G) k) l/ [
3 @4 X# S& y7 D  T$ `3 Q' j  </body>
4 D' B1 q7 g8 v+ i8 d, l  <script type="text/javascript">
- b  L* E. ~8 U6 e! v+ V3 H//自行添加上面代码
% L6 t- m  q; e$ ]    //      var mymap=new Array(36);9 ^, @) m4 O2 z) O9 _  c3 Y7 {6 S
    //      for(var i=0;i<36;i++)
* ~! o9 f6 B4 o: z    //     {mymap=-1;}
5 Y& @8 ~. ~1 y6 r1 t. q$ C5 s    function getnei(a)//获得邻居号  random
8 z4 u4 ~. I" @- [) u. J! F    {" E; z. X9 \' `+ y& h
        var x=parseInt(a/aa);//要精确成整数
# W1 w7 p* |2 u/ k( V; S        var y=a%aa;/ Q7 f( F) {* ~# t6 H% ^; W
        var mynei=new Array();//储存邻居
. x; a- G6 |5 l2 ^  D        if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点" c% y6 D# T% g" f9 f5 e1 F) ?
        if(x+1<14){mynei.push((x+1)*aa+y);}//下节点/ Z6 y8 E% H: u  i1 J
        if(y+1<14){mynei.push(x*aa+y+1);}//有节点
; R2 f1 G. v( B( Q* i        if(y-1>=0){mynei.push(x*aa+y-1);}//下节点$ G# W! o2 w& |7 k; P5 H6 K& r
        var ran=parseInt(Math.random() * mynei.length );
" s  I! H1 ?9 T/ w' k7 i: {3 o        return mynei[ran];$ f% _; L5 M# E/ ]- h
9 A; K% C" a0 E# J# k6 C* x( A, w2 O
    }
) o) L% y) H: B, K    function search(a)//找到根节点
: A4 J! ^. N/ ]& @+ Q3 F: o    {
& F, U5 e. ~2 t5 L        if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
; n/ F$ r. N% j1 b& s- F8 i        {
5 F& r6 }1 C7 r4 ^7 m# M            return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩
" O1 c7 N% \* i% `0 p        }" F6 D& G3 E) c, T; t" L
        else+ v0 H- u6 f- ]3 |/ r
            return a;
+ ^0 s  J2 k' @* Z$ A    }9 ]& Y6 F+ _. s. F; I
    function value(a)//找到树的大小
+ r) {+ G% a) c2 s1 a( ~    {" U5 T5 s1 r6 W$ L3 m2 i, B/ v* \
        if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点% `' X. q& t' S4 [6 `9 `5 w2 y
        {
" {  `$ @& F% Y- ^( F            return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩. O& s( X* |' Y1 u! P4 N
        }  R3 x; j' s& R& |; D$ u3 _
        else
* R8 n, D! z( M! n% q+ [            return -tree[parseInt(a/aa)][a%aa];# F1 O. M1 t: i" v: f
    }9 M$ [; c; c- D6 o; j: e
    function union(a,b)//合并* f6 F. f0 L1 L# n9 p0 y
    {
( r* v) r' r1 w$ e        var a1=search(a);//a根7 X" B5 z. _5 e; i; w3 h2 D
        var b1=search(b);//b根
5 R6 `1 _2 C" j+ |& N0 s3 z+ j. N  u0 Y        if(a1==b1){}
+ r3 v& x9 E' v- V- S/ g        else1 j$ Q* r* O$ F# F: m- W
        {
$ R2 i! z! y7 I            if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数()，为了简单减少计算，不在调用value函数7 q  l* i% `% ]) U) d$ k
            {& V3 [& i+ K. D4 ^
                tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加  注意是负数相加
* a- J7 [- k- `( M. Y                tree[parseInt(b1/aa)][b1%aa]=a1;       //b树成为a树的子树，b的根b1直接指向a；
) L/ y3 T8 y) l  Q; p5 M& g6 F2 Z            }
6 f. f7 R, b* x6 g9 f            else* ]( @: ]2 V  c6 H- T
            {, O9 F. H- n  B9 f) ?: G- x
                tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];
' A% N3 x0 g5 ^. k" |/ Q                tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树
0 D2 q. E: v8 N" ^- ~            }
! a0 ^5 E6 g2 F; O1 n        }8 V8 O2 ?+ a! _8 B/ `9 `
    }+ j6 z) |) Y+ l( N
1 R% r4 h& e. ]  B8 n9 Y3 X+ G
    function drawline(a,b)//划线，要判断是上下还是左右
* `; Q. h: v8 r$ M9 p1 W    {
7 P$ ?) c" P+ v* i
# {/ I6 Q& a, I2 ^! x: j7 ?        var x1=parseInt(a/aa);  ]5 ~( S# c+ g" W1 J% o1 Q; C. R
        var y1=a%aa;
. d" y; L9 p( z7 ]4 W5 h  Y0 W: f+ t, n        var x2=parseInt(b/aa);+ _& r$ b7 R# _; C+ J5 K) K$ r
        var y2=b%aa;        / u3 s, ~. A5 _' e
        var x3=(x1+x2)/2;( T9 K+ B+ E+ F
        var y3=(y1+y2)/2;5 G# Z# [/ O- @9 Z4 c' ?4 V6 e- l
        if(x1-x2==1||x1-x2==-1)//左右方向的点  需要上下划线
/ u" p4 k1 P+ x        {
. B0 }( z4 R$ H1 A3 J# Y' U            //alert(x1);
0 U1 w# i$ i6 Y6 l            //  context.beginPath();
( J4 V4 h7 q! D0 ]& I            context.strokeStyle = 'white';
2 w* F4 n' @% F            //    context.moveTo(30+x3*30,y3*30+15);//' ^; k5 R6 f4 i% z4 x( J7 @" h# o8 M
            //   context.lineTo(30+x3*30,y3*30+45);
# _2 ~; F# p# A+ S; Q" j& e& n+ `            context.clearRect(29+x3*30, y3*30+16,2,28);
$ x( k9 z( w* L, l0 \            //    context.stroke();
) ?4 p4 j9 z7 E* P, |        }4 |5 o9 k% P2 t( H7 Y& F4 K6 l! ^- o# P
        else
% O- }2 d& {; g, X% n& N1 w, B, w        {1 j6 P; @' S- ]* }' w- V) t
            //   context.beginPath();
2 V! P6 y7 B" p: D" D) W' w$ Z9 t            context.strokeStyle = 'white';5 N+ ^! O* L2 v, y/ \
            //  context.moveTo(x3*30+15,30+y3*30);//
* u& a9 o/ m, @$ Y( w9 @! o6 L# w            //    context.lineTo(45+x3*30,30+y3*30);( ^  @) u! P. h$ B# a
            context.clearRect(x3*30+16, 29+y3*30,28,2);
. J& \. Z3 l( T# X0 L            //      context.stroke();
& O9 f& M4 M9 o7 v" s$ Y  q# g6 e        }4 _' k) f( s% }# o
    }
. Z. m+ R$ b/ ~6 ^. i# @  y
& |& w( O; G$ m- F! {. ?    while(search(0)!=search(aa*aa-1))//主要思路
- W( [! a. ?" ?    {
/ t+ Y) p& _. d6 V& H& O" R& i" ^        var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数% _5 O3 p* D* z3 W
        var neihbour=getnei(num);
! `1 {, j- I) g7 ^7 T3 N        if(search(num)==search(neihbour)){continue;}
9 X8 J% Q2 O# ~9 P: R        else//不在一个上
5 K* e1 H& c- C+ s) C, W6 h        {/ }; F) K) U' h( g
           isling[num][neihbour]=1;isling[neihbour][num]=1;
4 I: ^  R& X% ]' l* C; O+ r9 U            drawline(num,neihbour);//划线
# v2 Q+ e: A2 @4 x0 P            union(num,neihbour);
% l' W0 D( e. D4 Z2 n
% Z4 N2 e% W# @& E% f3 i        }9 H* q) _0 ]- H6 `" [+ K8 ]
    }
5 N/ O4 Y( X7 S% s& T  </script>2 [  q1 _( m* I1 A
</html>- o# u4 X# D# h- W. D

: ?9 G% `" Q. d
8 m6 v* v; a- v, U实现效果：5 Q7 I) j  ~% ?' Y( q9 M2 {) K# z

' x, t8 ]* ]' v' k! n+ P: n. a+ Z7 ^ 8.png " Q' ?$ @3 W: J: z5 Y% S
* N( Y; z8 l: U. @8 ~. x
9.png ; ]2 Y4 `$ h: j5 ^* y/ x( t# o
方块移动. v8 e3 E4 r" z+ M- s* P# _
9 {+ s2 L' S" K) d- F
这部分我采用的方法不是动态真的移动，而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉，在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除，可以根据像素大小精准擦除。+ {5 ?! v1 x- A
% W- q4 Z. t$ z& Q
另外，再移动中要注意不能穿墙、越界。那么怎么判断呢？很好办，我们再前面会判断两个格子是否联通，如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组)+ `8 q! F  R  L3 w/ x9 S. K
, r4 }. ]4 \* m+ X" }
另外，事件的监听上下左右查一查就可以得到，添加按钮对一些事件监听，这些不是最主要的。/ v$ O/ x' ~% ^- w# H; L# m  e
1 Z! C# |4 e: t7 x
为了丰富游戏可玩性，将方法封装，可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外，如果写成动态存库那就更好了。! [; _4 ^! A4 c1 m
10.png - H: c7 B6 Q/ u$ }
7 M' L. B8 A" W. U+ w

: v6 G% d" s3 J" [" P) i% o————————————————
$ Z9 s  H( j3 ~- {, o版权声明：本文为CSDN博主「Big sai」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。6 P/ h( P% h* c/ |
原文链接：https://blog.csdn.net/qq_40693171/article/details/1007167667 ~4 ?+ y# z8 b* X2 }
. I+ Q1 B/ m: g2 V' m

/ k; `2 H6 w: ~' A/ ^
作者: madio    时间: 2020-4-1 12:39
牛人！& ], ~' P! J6 `9 Z! i; d: u




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