查看: 2627|回复: 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=[];
$ m9 ]+ B2 R2 B' b5 p6 |- C# `0 E" v       for(var j=0;j<aa;j++){
% R) u4 C4 X  ?8 F          tree[j]=-1;//初始值为0# K+ F7 x; Y" |, ~& P7 r8 n& H8 h
      }4 `% m( Q' s  d$ _, c1 e- [
}  for(var i=0;i<aa*aa;i++){
* s  C9 i8 J8 u2 X7 p9 l: h       isling=[];% A" c; ^* Z" B
      for(var j=0;j<aa*aa;j++){2 f! D8 x* x3 |# T) S
         isling[j]=-1;//初始值为0$ d: [+ b  O  B" u; n3 R3 u
      }
9 r6 @) Q& z# X: K8 w, L }
/ F2 s3 }6 T5 q- D: I" k( k" e$ m8 j( \6 i1 }, R# u
function drawChessBoard(){//绘画( y) H" T" I4 g6 t, B; Y
      for(var i=0;i<aa+1;i++){
* Y6 Q0 C0 u8 e" h" I! F" H          context.strokeStyle='gray';//可选区域
; _! W! o: _% ~/ c9 o8 M          context.moveTo(15+i*30,15);//垂直方向画15根线，相距30px;) n6 M* [! f# y
         context.lineTo(15+i*30,15+30*aa);
& q$ y1 K1 N& S- p  p! H1 [          context.stroke();0 k- u5 E1 U/ d0 I$ ]: d
         context.moveTo(15,15+i*30);//水平方向画15根线，相距30px;棋盘为14*14；
  C& E9 l! A1 j  s6 i$ m          context.lineTo(15+30*aa,15+i*30);8 t8 Z' I1 c, ~1 b+ Z" ]: [
         context.stroke();8 `' N0 a: @, x
      }
6 \/ M: z" V, r' }% N& X# a1 c& _. B }
7 ~3 k( |2 z' O6 g drawChessBoard();//绘制棋盘& v" J' L# Z% J+ `# e

1 M# ]' `. n) c. Y) { //    var mymap=new Array(36);
7 d) a. Q  f/ o4 _5 t //    for(var i=0;i<36;i++)
: ~7 V! q- C- W( \$ |! d //    {mymap=-1;}
2 L! c& ]3 [, ?2 N1 i' |1 Q3 M& e  A0 ?7 {; h% Q* h

) K1 z7 L& [* M+ q  </script>* h5 Y- z$ Y& o
</html>8 Y* |! I0 g* o) I4 J

, v* M' i; t3 G- h8 D3 x& m/ [  ]3 v
& x' x" u& S. {2 O2 Z( p实现效果
" Z7 F+ {; T$ i  L2 @, s

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

: z* j& `: D$ [, |
7 z, p4 P1 u# C" a8 D/ E6 w" ?" e4 A
画迷宫# C$ c& D' S9 B+ t2 }7 Y' ^# m
  }7 E5 @2 p5 q( ?& z5 e9 U# C$ }
随机迷宫怎么生成？怎么搞？一脸懵逼。
9 x" A  a( V0 a6 s: v( s
- y2 T4 a; {, Z因为我们想要迷宫，那么就需要这个迷宫出口和入口有连通路径，你可能压根不知道迷宫改怎么生成，用的什么算法。小声BB：用并查集(不相交集合)。  ^) H) g) o) [9 p  H6 @; `* I) O
迷宫和不相交集合有什么联系呢？(规则)
0 D4 l5 m2 e: h+ b
6 `! a4 @5 b5 p2 I之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合)，它的主要功能是森林的合并，不联通的通过并查集能够快速将两个森林合并，并且能够快速查询两个节点是否在同一个森林中！( S6 O5 k# t2 i; M$ o' l" |# D' o
而我们的随机迷宫：在每个方格都不联通的情况下，是一个棋盘方格，这也是它的初始状态。而这个节点可以跟邻居可能相连，也可能不相连。我们可以通过并查集实现。- z. X2 R+ t5 T3 m6 ~

$ U, `- C' Z. o8 H具体思路为：(主要理解并查集)9 E2 J6 L$ t# y. q0 K4 P- Q* q

/ Q, p0 `- f4 D1 o4 S2 n1：定义好不想交集合的基本类和方法（search,union等）
, u, D  ~3 E3 |% q* ~5 q2：数组初始化，每一个数组元素都是一个集合，值为-18 r' W. e# a3 j( W7 V
3：随机查找一个格子（一维数据要转换成二维，有点麻烦），在随机找一面墙（也就是找这个格子的上下左右），还要判断找的格子出没出界。' A1 n- L" L7 a
具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界
: f- f$ ?' |* V) E* V1 Y4：判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在，则重新找，如果不在，那么把墙挖去; a) z! h( O" ?  A7 G# _
5：把墙挖去有点繁琐，需要考虑奇偶判断它那种墙(上下还是左右，还要考虑位置)，然后擦掉。（根据数组转换成真实距离）。具体为找一个节点，根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。: T5 c$ m- E9 L3 l7 L9 v0 e
6：最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙，但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据，并查集操作。二维是位置。要搞懂转化！4 j6 I; M: l3 N$ W7 T0 P) X0 E6 ~
注意：避免混淆，搞清数组的地址和逻辑矩阵位置。数组从0开始的，逻辑上你自己判断。别搞混淆！1 H2 i! D3 Z* l" {( Z9 c

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

+ q* e2 w9 Y* _6 p- Z3 |主要逻辑为：: B8 d: {  I; q0 }( S
while(search(0)!=search(aa*aa-1))//主要思路2 f! r' u7 h: q  P
{
4 x% G' i- C  L! T" [' J& r       var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
2 y; ~- z- ~4 l: L       var neihbour=getnei(num);1 M! ?7 j& a* a" {1 n" m9 Q
      if(search(num)==search(neihbour)){continue;}; P7 |0 t: m+ S
      else//不在一个上
$ Z" G4 y* I: \+ Z, E/ {  K       {
; g2 D2 X# \! ?) M; X          isling[num][neihbour]=1;isling[neihbour][num]=1;8 o) {- y5 U+ \( L# H* _4 D
         drawline(num,neihbour);//划线
& q: a3 C5 I  T  ?9 e* c4 l          union(num,neihbour);
8 g9 B  Q/ k  z
& ?- G3 Y( d# F- U- g) q3 S       }
" W; F5 O- H, d* h+ P }1 J: n+ Y0 B" o* j

, p! x+ ]; C- x& y; H- {$ q7 b1 Y0 y4 M0 f: K% y
那么在前面的代码为
4 U& L1 A3 |% W5 `<!DOCTYPE html>/ q" S& N# }9 L4 [4 r: f) y/ z
<html>  Y7 M7 g4 g9 t* N' m5 g
  <head>
( e: x1 l2 O) K* D <title>MyHtml.html</title>
% C3 h) R# t7 R' f! G3 |% }  </head>
5 N4 N! R5 A( I0 U  <body>
" T6 t" ^9 R. [. e, m5 V& n; ~- X  <canvas id="mycanvas" width="600px" height="600px"></canvas>6 R+ r2 W5 X' R! m

+ u; G- N- r4 b2 x* @  </body>
! H1 V, b/ d1 _  <script type="text/javascript">7 b0 X5 {- [0 p( z/ k4 H* s
//自行添加上面代码
8 A1 u: p7 i/ S$ y& ? //    var mymap=new Array(36);
" m& T  Z* w# [1 w. p. w3 l! G //    for(var i=0;i<36;i++)
2 n6 a4 R- j) x3 D* \  ~* K //    {mymap=-1;}
5 C/ K/ S4 u/ ~+ A$ ~# ` function getnei(a)//获得邻居号  random, }( P8 Z: _# [# R. \6 Q) B* Z
{: Q8 Y4 _7 P8 Y
      var x=parseInt(a/aa);//要精确成整数
) `$ y7 u9 d( j: }; b. M4 Z       var y=a%aa;
5 T, k  J# Y4 I- g3 Q" l& T       var mynei=new Array();//储存邻居/ N' K- h/ e, o  e& P
      if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点
$ O* W0 {5 y) ]/ \       if(x+1<14){mynei.push((x+1)*aa+y);}//下节点
+ ~6 ^9 q& |" E) `( x# T       if(y+1<14){mynei.push(x*aa+y+1);}//有节点% m$ \% G( [+ L6 x
      if(y-1>=0){mynei.push(x*aa+y-1);}//下节点
6 p, S' p& ^1 M9 k' T       var ran=parseInt(Math.random() * mynei.length );7 b* @; c9 W8 \+ x  P, W1 v) v
      return mynei[ran];
6 z  q, g* e6 o- H5 U: s0 n& e+ H- O0 X  x3 |+ Z$ s
}& E& c3 r. q0 q) \: \4 F2 N
function search(a)//找到根节点5 d# l! q  G. e3 G, l" ?
{. P5 w0 x! n/ ~1 z7 D4 G! j
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点3 j" [# a; S/ |: W0 \! \3 |  \" S, f
      {8 G: u: \( b  x0 A" K8 L5 x
         return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩# W5 W3 _2 h3 v0 V" q8 h
      }2 H- c+ h7 h. y
      else, p3 C* X1 _; J2 ~2 x4 ?9 ?
         return a;# N4 x; L3 t, J
}* T0 Q9 L+ H4 o, i) c6 N
function value(a)//找到树的大小4 j) e- ~" g* Z# v
{
3 G7 t5 J. w3 g' M' d7 A: j       if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
  ]6 ?5 y4 m  a: g/ N5 ]+ R, L5 d       {, j( m3 [$ H9 x5 `
         return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩
8 R, h) s% T$ {% f3 s6 Q       }
) D8 `1 A9 h% t/ O* M8 r. D       else
9 Z0 t9 R$ X: `" s- q          return -tree[parseInt(a/aa)][a%aa];
2 e; V4 M+ A9 |& J- x }
3 g8 q0 F! D8 ]0 f4 b function union(a,b)//合并
) m: f# }8 P$ D/ ` {" D0 S  H  R- d$ ]: ?5 g8 v: O* s
      var a1=search(a);//a根
: h: Y+ L3 {9 b! K8 n       var b1=search(b);//b根
$ H% _, m9 e& z       if(a1==b1){}" s9 ]1 D4 q0 J" l& y! O) V
      else5 k$ E6 j8 T+ U' L- |& p
      {& L9 M# y/ ^5 A$ q
         if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数()，为了简单减少计算，不在调用value函数
0 U5 `; Z; z3 W  V7 k) M          {! i! ]7 {& e# j- F) |# F
            tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加  注意是负数相加$ l# p1 @7 }+ {7 t" D1 P
            tree[parseInt(b1/aa)][b1%aa]=a1;    //b树成为a树的子树，b的根b1直接指向a；: ^6 \1 J1 o; C" c: A
         }
$ m  B, c( g5 H# B; R) i          else
) P& _& c( Q& }          {2 P7 n- P( c/ \& ^* ~
            tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];
# X! l5 H( B; P& W  M$ T9 Y! e' Z8 H             tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树5 }! b) j/ ^8 K7 C
         }" `3 L1 b6 U) ]: w
      }6 x9 n8 J, `) ?2 g
}
& L0 P1 U. `( Q/ N
4 [9 e4 b7 d' t5 M0 e! Y function drawline(a,b)//划线，要判断是上下还是左右
1 z- q+ p, k$ h& ]! e5 {  P6 x7 x5 q {
% ~# L/ X3 _) P9 ^8 Z+ m- c% L1 \3 W6 W, K# f8 c- }! o( I. U
      var x1=parseInt(a/aa);' \! i7 k* G1 c4 m
      var y1=a%aa;, ?' S( |* H2 m9 A1 G( H5 N; {* E
      var x2=parseInt(b/aa);
: C7 \' J8 t$ c4 @! }$ g       var y2=b%aa;
9 n4 R7 a3 K4 ^3 [0 p6 W       var x3=(x1+x2)/2;& E3 S- h; f2 B. g; F8 W
      var y3=(y1+y2)/2;" t" |8 J3 T3 `0 Q" J
      if(x1-x2==1||x1-x2==-1)//左右方向的点  需要上下划线+ i# D5 `7 \! z
      {
) k* R, ?7 M; i. b3 K: g3 w8 d) U          //alert(x1);- ^, d! f) S4 n+ D( i
         //  context.beginPath();5 _; S0 m' }$ _6 B+ ?0 W! O
         context.strokeStyle = 'white';
: s9 x6 V  A1 a          // context.moveTo(30+x3*30,y3*30+15);//# ^+ w$ A5 D" B' G4 z. y
         // context.lineTo(30+x3*30,y3*30+45);8 T$ _8 c" d8 ^  t  b- n
         context.clearRect(29+x3*30, y3*30+16,2,28);
4 g, A+ b4 y$ ?9 X) G          // context.stroke();
3 S' m6 i) P* i0 H       }
* i* Z+ M+ [# |: o9 N- l       else3 v' ?2 o. B! Z: ~
      {- s. h  g* B" w2 E# d* d
         // context.beginPath();! S% P% [9 d/ B& F- w8 L$ @
         context.strokeStyle = 'white';
  C" A4 D0 E. o. M2 V1 M          //  context.moveTo(x3*30+15,30+y3*30);//* n* v- E; w$ B/ E
         // context.lineTo(45+x3*30,30+y3*30);
4 c2 O4 h4 D2 g# r0 Z          context.clearRect(x3*30+16, 29+y3*30,28,2);
' p% T! _; d+ ^, |: I$ G  q          //    context.stroke();' c  W' H" A8 e" L
      }4 ?3 L& P4 P; k; [* I" A
}' h# }5 W: l: l* Y2 {
# d( t& i( H7 y- j
while(search(0)!=search(aa*aa-1))//主要思路
4 T/ ^' E' b- w: B! X) B {8 Z6 B4 G3 V2 o2 p- M
      var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
5 C& w4 ^: }7 g       var neihbour=getnei(num);- P  X. `5 ]9 A$ g: S9 ^
      if(search(num)==search(neihbour)){continue;}& A8 e: {: C! T+ C2 I( \
      else//不在一个上
5 v; e( }) H- e- D& Y! Y1 b- v' E/ M6 z       {$ q, u& ]( O) U( k( l. ]" _
         isling[num][neihbour]=1;isling[neihbour][num]=1;1 M' }) T( u3 W1 n+ @& ~4 {+ M
         drawline(num,neihbour);//划线* q5 t0 h( v8 \! `1 H7 V
         union(num,neihbour);
/ e! V  K+ |# J( x
7 k, c0 X3 y! w/ t3 y$ u       }: N) \7 Q+ F) d4 n
}
- s, `1 ?) v1 R  </script>
% H1 P& t4 u# E7 O</html>$ A1 @( n' K) U& A% Q

, w" l* l. t0 j$ b
% ^* B( q' ?& j1 R* c& a实现效果：
% B& ]/ W$ S# I2 h2 j' @) H" @, C* r# i: d+ z% l

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

1 E, R8 g# Q& |) S/ U8 k
( g2 r6 F$ ]* n$ b, w3 G

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

. Q" U0 ?7 I. x/ {7 o方块移动
7 }, p) Q1 h3 \3 S) ?# z" e1 B1 f+ N$ F8 c+ B/ U4 C! O
这部分我采用的方法不是动态真的移动，而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉，在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除，可以根据像素大小精准擦除。# s: e2 h; w; O3 G) X5 ?! u
- Z! ]. F  M* c
另外，再移动中要注意不能穿墙、越界。那么怎么判断呢？很好办，我们再前面会判断两个格子是否联通，如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组)
9 c$ ?! z2 z# K8 o! u" }# n. R; o! ?! o, I8 q
另外，事件的监听上下左右查一查就可以得到，添加按钮对一些事件监听，这些不是最主要的。) b2 \- M$ j9 Q4 T  G  V& V5 a
& r' O. u& f( _8 \
为了丰富游戏可玩性，将方法封装，可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外，如果写成动态存库那就更好了。5 F2 k( Q% @6 S* ^8 b# l, u

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

, D2 X( F* i; {* ~- T9 ]4 J. t' K
5 G+ S5 c. G3 `0 J" h
8 i: x# N, l9 a————————————————6 I3 f+ D1 u, T
版权声明：本文为CSDN博主「Big sai」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。* `: r. `5 _8 \" S
原文链接：https://blog.csdn.net/qq_40693171/article/details/1007167669 L0 A+ p# P. Q  O( q. K! A1 h

+ z* j8 x2 x1 e$ e* T$ \9 @8 {) g1 Y& k3 H0 c# e