数学建模社区-数学中国

标题: 我花了一夜用数据结构给女朋友写个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=[];
. 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

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

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; ~

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

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

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

! \9 e' s0 {: m' T# f. G
* y0 P4 r3 U3 b% e5 T$ Z# c1 V; w% M- }

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

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 \

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

% 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