查看: 2597|回复: 1

我花了一夜用数据结构给女朋友写个H5走迷宫游戏

字体大小: 正常放大

杨利霞

5273 主题	82 听众	17万积分

TA的每日心情

	开心 2021-8-11 17:59

签到天数: 17 天

[LV.4]偶尔看看III

网络挑战赛参赛者

自我介绍: 本人女，毕业于内蒙古科技大学，担任文职专业，毕业专业英语。

群组: 2018美赛大象算法课程

群组: 2018美赛护航培训课程

群组: 2019年数学中国站长建

群组: 2019年数据分析师课程

群组: 2018年大象老师国赛优

电梯直达

1^#

发表于 2020-4-1 10:57 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

我花了一夜用数据结构给女朋友写个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=[];0 n1 K* y& C+ w' J# T4 }+ [1 s8 C
      for(var j=0;j<aa;j++){
8 \6 Q2 Y& S1 e* Z  q' g* ]          tree[j]=-1;//初始值为06 Z. t( h# z: s* E: H# O
      }
8 D  A" N' B/ |' s }  for(var i=0;i<aa*aa;i++){
- Z6 S1 @* H/ U4 P) Z! h       isling=[];, n, k; x. b1 v' a3 w6 g& j
      for(var j=0;j<aa*aa;j++){6 F& f# m9 r8 z! R! {
         isling[j]=-1;//初始值为05 A8 b6 N" b3 m+ X
      }5 I0 w4 V, o) T0 u# z- ?
}! s2 H2 l4 S/ o" H( }; l# A

3 N/ z1 Z: u- ?) | function drawChessBoard(){//绘画% f* l% g! ~, o4 x
      for(var i=0;i<aa+1;i++){
9 U. j( Y0 X, g& v& _& b7 W/ q          context.strokeStyle='gray';//可选区域% u9 A, H8 {+ V6 z" x, C
         context.moveTo(15+i*30,15);//垂直方向画15根线，相距30px;7 Q& L( T& {: \9 {0 P- T
         context.lineTo(15+i*30,15+30*aa);% y! w, z9 y$ u' }2 |( O
         context.stroke();8 e) q2 ^  `3 Z! `+ [/ V
         context.moveTo(15,15+i*30);//水平方向画15根线，相距30px;棋盘为14*14；
7 [- x: X6 Y1 D7 P, V+ G          context.lineTo(15+30*aa,15+i*30);. P- G# L. L5 M( B* Y5 p
         context.stroke();  Q4 g1 `' T5 E
      }' ]1 g) o' y  E; `& q
}
! S$ `3 j" L" X drawChessBoard();//绘制棋盘. j' c- E, P+ P& e# k
6 T. v* g, G2 S0 ^( X* j
//    var mymap=new Array(36);; O3 L$ M6 P' [1 E4 c' h9 U) z  T
//    for(var i=0;i<36;i++)
* L) B. `7 K" C6 G" A5 i4 P8 \+ N //    {mymap=-1;}
0 E9 V1 }$ b6 t' B. s: \
6 V5 {7 E0 c) L1 m' i
% G' H2 Z0 h% N* ^3 r$ x  </script>$ ^, K' Y! J5 B8 [
</html>
2 X! f; ]! y- p3 M) l& L' `: V+ E+ e& E4 d: ^
, x  ]: Y7 K, }* L# O# J
实现效果
% p: k6 X! L: ]# H8 A. [

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

* Y$ r7 ?9 j8 C  [6 U$ P7 i
, G) L8 @' I* L* p! O% b画迷宫+ Y" q# J# V( H) n( y0 z
% \, S- U* u# N* [2 Y
随机迷宫怎么生成？怎么搞？一脸懵逼。: C% |. _7 q2 f4 W5 s+ e

2 T' L: j7 P5 D6 M7 W0 j9 o因为我们想要迷宫，那么就需要这个迷宫出口和入口有连通路径，你可能压根不知道迷宫改怎么生成，用的什么算法。小声BB：用并查集(不相交集合)。
9 b  |, J5 ?3 `迷宫和不相交集合有什么联系呢？(规则)
2 O1 r, x% y8 Z" J& ~4 R0 V$ k. |2 @* N% i0 k; I9 W
之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合)，它的主要功能是森林的合并，不联通的通过并查集能够快速将两个森林合并，并且能够快速查询两个节点是否在同一个森林中！( V$ Y2 i" ], U
而我们的随机迷宫：在每个方格都不联通的情况下，是一个棋盘方格，这也是它的初始状态。而这个节点可以跟邻居可能相连，也可能不相连。我们可以通过并查集实现。7 X: T3 ^  d1 ]) ~

8 j' @. n3 y4 p6 Y. u具体思路为：(主要理解并查集)
1 L, b% u$ d8 z. q9 s6 `
$ n% F0 X$ C5 k6 F, c% X1：定义好不想交集合的基本类和方法（search,union等）, ]' i  q- ]/ W3 R2 V
2：数组初始化，每一个数组元素都是一个集合，值为-1+ P# ~* {& }7 f5 j
3：随机查找一个格子（一维数据要转换成二维，有点麻烦），在随机找一面墙（也就是找这个格子的上下左右），还要判断找的格子出没出界。: |6 y+ F  o( C$ P1 d
具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界
7 n/ a; k5 s; [: x/ Z4：判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在，则重新找，如果不在，那么把墙挖去& d$ _' Z. o, _' U# X
5：把墙挖去有点繁琐，需要考虑奇偶判断它那种墙(上下还是左右，还要考虑位置)，然后擦掉。（根据数组转换成真实距离）。具体为找一个节点，根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。/ o+ x) Q0 h& ?4 w9 m9 C
6：最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙，但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据，并查集操作。二维是位置。要搞懂转化！
" h- l  _' a2 ^0 x: m% w注意：避免混淆，搞清数组的地址和逻辑矩阵位置。数组从0开始的，逻辑上你自己判断。别搞混淆！5 g  |) e1 J- V! |; k$ ~/ @

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

4 `$ V6 ?. i) Z1 `: E8 B
主要逻辑为：! S1 Q4 _$ X) @- }2 p
while(search(0)!=search(aa*aa-1))//主要思路
  c, H, m- U6 t7 K% d: ] {
+ v5 r9 I+ k* Q       var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
* L+ O9 Q7 f: s3 |6 {+ z7 p  F0 e       var neihbour=getnei(num);
1 p5 f, i+ F( ?' V3 Y# t       if(search(num)==search(neihbour)){continue;}% E) k8 m: t5 I' B( o. q
      else//不在一个上
& y7 [8 I  S3 i1 h0 y4 L       {% ^$ r1 ?( W8 W- X( B; d
         isling[num][neihbour]=1;isling[neihbour][num]=1;, G3 n2 [3 \: i5 w- j
         drawline(num,neihbour);//划线' _, x- M* z% c7 Q1 {/ K8 g
         union(num,neihbour);: l1 F4 b1 v5 v" D6 ]5 @# I
* u* `1 v1 m* x7 n( ^: m
      }
4 }/ x& K$ K3 J) @2 ]( I }! s) e) l" k2 G. ^3 c% K2 u
$ ?" e  M" U/ Z) ]6 x

5 P* F+ P- e! b, s那么在前面的代码为
( h9 [  v: \$ Z% f" i5 A2 d; G<!DOCTYPE html>
9 G; ?* U. n$ r; u<html>
- O% t% Y2 E$ m  R5 I/ P  <head>/ P: y3 o6 ?$ ?
<title>MyHtml.html</title>
/ R6 \$ R; J5 p$ l5 E% ]- g  </head> 9 ]: k9 |# N7 \: D& t
  <body>6 }& D  e/ n' @  n* Y: k
  <canvas id="mycanvas" width="600px" height="600px"></canvas>
6 ^4 K* H4 |1 _# l' h9 W" `6 Z, R1 k( Z0 e! t
  </body>
6 {" x$ }/ S; c8 Z1 }: q4 Q* z  <script type="text/javascript">
: J( q. H# |: w0 J; v' S//自行添加上面代码6 {3 H0 v) J+ ^0 ]% B# b
//    var mymap=new Array(36);# }% n1 A. H8 j% f! B( B  w
//    for(var i=0;i<36;i++)
! L/ l) p$ k: q$ j& U4 @ //    {mymap=-1;}
, n, i" T5 U" u6 q8 ?8 L/ z3 n" @; N function getnei(a)//获得邻居号  random
$ }5 x' v" i  q% G; b8 d4 d: F7 M4 K {
2 k/ j" M2 H/ p5 Q       var x=parseInt(a/aa);//要精确成整数
2 A6 U- g- k- x       var y=a%aa;, z$ @" g# A3 f6 z( M
      var mynei=new Array();//储存邻居
7 F% g) a! C' q$ [6 K       if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点
' C# o4 Z2 J7 S" Q       if(x+1<14){mynei.push((x+1)*aa+y);}//下节点: |, [- N; o  T8 |% s0 i+ F' C0 S+ }# ^
      if(y+1<14){mynei.push(x*aa+y+1);}//有节点) @5 P8 Q$ b% l9 \8 B# F, V8 b
      if(y-1>=0){mynei.push(x*aa+y-1);}//下节点* \# R1 }9 y& Q  ~  u( t6 r
      var ran=parseInt(Math.random() * mynei.length );
2 C3 @; S: u- D       return mynei[ran];. N* O  P) i( G# y# v4 W* {7 f" e
* W) d  L: e0 ]8 s, M0 Z
}  l8 K" O9 O& B' z. f
function search(a)//找到根节点' I1 B5 v  e6 G$ p0 Y" C5 t6 f
{
% R5 E9 Q; ~+ A4 S, F5 W1 P       if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
  v/ B) C2 T4 r" z2 Y3 D4 ?       {
; Q; K3 O* ]! \5 Z* _& W0 @          return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩2 D& {# [- u' l5 C& w' ~$ I1 s
      }+ a) W% n5 n1 W. O
      else
$ n( s* v& z, k# q3 U9 Z$ s          return a;
: N7 }: E1 m( N3 m# Y4 X }
5 ]! F5 Q  \( u2 C1 k& j function value(a)//找到树的大小6 L$ x7 @9 Y. s$ S* U- C( ^
{
. F& i5 ~5 t0 `. Z% _2 H, ^: Z       if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
8 m" q  Z3 o) J9 Z) Q0 k  k       {
- U7 P9 B% f5 a+ S2 t# J          return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩. U+ `; z5 `# v9 U3 S1 M, B& v/ T- ?
      }
* E# E/ A4 H6 r5 V' b; i4 P) V* m       else& Z0 m: g1 h0 N2 }
         return -tree[parseInt(a/aa)][a%aa];
+ _# T9 U2 i3 q }6 o  R; b  d+ n1 g; Z
function union(a,b)//合并
/ s: d- G  w5 x, r9 D6 d. @7 h {# m3 f# t9 V: J# l1 L
      var a1=search(a);//a根
) |. A8 }* H  `0 l* |; _$ Y       var b1=search(b);//b根
8 |2 U6 [$ U! s       if(a1==b1){}9 Q- {, `% V$ f! s6 Q% D8 I9 m7 W
      else
, }- C5 A' V5 V- J9 A  X       {. p# y2 R: V. o# s6 ^8 G& ?6 p
         if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数()，为了简单减少计算，不在调用value函数% |# }& ^# }9 c3 \
         {  U9 ?& w  h* V5 Q/ h  ^
            tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加  注意是负数相加
( w& g" n7 x3 K* u             tree[parseInt(b1/aa)][b1%aa]=a1;    //b树成为a树的子树，b的根b1直接指向a；
  H3 O$ m8 c% ~4 Q# r% U7 J          }6 R) x; f$ m0 ]  L
         else" ]) \: T! G$ T
         {
$ d8 Z" t. M/ f6 T2 T( _             tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];' p7 e- N0 N7 q) J6 y) }) T# X
            tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树
* T+ z* W+ C" h9 y8 i! N. O* a' i) b          }
# I, v# _, h. U       }
' H& E. E+ c' ~& t }
; h* O0 c0 J3 V1 I- J
1 M: O2 E. F$ J1 q. a* C function drawline(a,b)//划线，要判断是上下还是左右
; I' c' W4 V1 s# k# g {
0 s; F: ]& ?7 c! E
6 s5 I, i8 S& I       var x1=parseInt(a/aa);
* j( h' W& q/ ~6 u) D5 w- t       var y1=a%aa;
0 H  m5 F  g: E, z. d) W       var x2=parseInt(b/aa);
: X% h5 A( f0 H0 M7 Z& |& V       var y2=b%aa;
* N. m7 v6 r7 V! H7 a- X0 L       var x3=(x1+x2)/2;
8 U/ s# d4 L/ t9 e* X       var y3=(y1+y2)/2;
6 ?! J& B/ V8 m/ ?) {       if(x1-x2==1||x1-x2==-1)//左右方向的点  需要上下划线: S# @" W. _0 ]
      {
& r+ m6 i9 M/ q          //alert(x1);
4 ~+ t7 v9 f7 ]# p          //  context.beginPath();; E* _9 t. ^) T3 l
         context.strokeStyle = 'white';8 ]& {( M# c0 o' Q# s* \  C
         // context.moveTo(30+x3*30,y3*30+15);//4 q* ~7 ]% i/ p0 _: T
         // context.lineTo(30+x3*30,y3*30+45);
( J, ]8 Z6 Y( s1 @          context.clearRect(29+x3*30, y3*30+16,2,28);
& h2 q6 @* Z' o+ D% o          // context.stroke();- F+ B1 h2 S+ l. p& B6 E1 {5 s( x5 o
      }
/ b, [3 ?# K0 q  @0 `- z9 S       else7 b- `7 c" l& k! |) q
      {
# P2 [. N8 V* ]- Y( f          // context.beginPath();2 o, N/ p* P$ R* e6 Y
         context.strokeStyle = 'white';
3 a3 I: R% G9 E% ?% Y          //  context.moveTo(x3*30+15,30+y3*30);//( U. e9 L* t# p" N% G
         // context.lineTo(45+x3*30,30+y3*30);# `+ ]' ?) X9 |5 G" r% \
         context.clearRect(x3*30+16, 29+y3*30,28,2);! M6 Z6 b, z# ^- S' r
         //    context.stroke();
$ |; ^' y3 R; g- V. O' Q       }
- K. C8 W  A$ b  E+ n, e- R- ` }' \& S" p& d. E! E% }8 W
* K0 u! V  i1 d" ]# c
while(search(0)!=search(aa*aa-1))//主要思路! o: h; e0 c: f5 n+ G
{
+ J% c, l0 g" A  c0 ?2 h       var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
! K) W; \. h& E$ K5 I" \) u       var neihbour=getnei(num);
5 V5 r- r  j$ D' D! }  ^6 E       if(search(num)==search(neihbour)){continue;}- X4 @, `4 e2 ~( Z* E
      else//不在一个上) i: R5 m5 [* n3 q8 k
      {
, ?8 Q4 R2 I" g* ~          isling[num][neihbour]=1;isling[neihbour][num]=1;$ ]5 Q# K  V$ i  e
         drawline(num,neihbour);//划线& S6 Q% k  o: G; m) S- Y
         union(num,neihbour);
" H% b3 E- J& [
3 \9 i$ Z8 Q0 q2 Z7 r       }  R: P" i3 \; A# l
}
+ p8 M& @" u- U$ y& U  </script>) ]: Q+ ~& S3 j" C7 i
</html>: v( N+ d& a: y6 q

9 d  o6 ^8 u  `/ R) }* m8 _3 i, s: M' }
实现效果：
3 j6 O9 K6 s& s- L3 i. {  v' [$ F  E6 C7 m! p( R

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

2 X) `9 w8 E7 W- y! ~) K! u
/ E1 G$ v( d2 T# E

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

( F) Z/ R& S9 W7 e2 M
方块移动" n4 n- G8 n; s1 _5 G
" L+ [/ C  V, w& X
这部分我采用的方法不是动态真的移动，而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉，在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除，可以根据像素大小精准擦除。
9 Q8 b) q7 _' O* w6 k0 ^) N/ x7 \
/ }( y" N9 W9 D5 a2 l, g7 P% ]1 ]" M另外，再移动中要注意不能穿墙、越界。那么怎么判断呢？很好办，我们再前面会判断两个格子是否联通，如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组)
0 l; V* R9 Z- O. i  i& o  I+ a
) ^% ~5 f% o; Y$ F另外，事件的监听上下左右查一查就可以得到，添加按钮对一些事件监听，这些不是最主要的。+ P3 Q( X. k' {: s* y: S6 d; i
9 `. |- O. i3 E+ S" n5 z
为了丰富游戏可玩性，将方法封装，可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外，如果写成动态存库那就更好了。; _' k% m  D( r8 n- [

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

' r: w/ T6 ^* r
9 ^5 D$ l) l% q& i) r0 l. U
  D1 _! p2 |, X0 X3 @* e) Q& X————————————————$ f+ l9 Q! i7 [) h% i
版权声明：本文为CSDN博主「Big sai」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
4 R, h, |# K9 `5 l8 O$ X7 D; A4 O原文链接：https://blog.csdn.net/qq_40693171/article/details/100716766) m- p9 J% D; Z' G0 I

8 [2 d* E9 m! ^. Z& z1 D1 d4 N: Y. J% }6 i* v) d