查看: 2583|回复: 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=[];  s5 ^: F5 Q4 g0 u' _
      for(var j=0;j<aa;j++){2 c0 Y2 P- |1 N# z/ A7 ^7 h
         tree[j]=-1;//初始值为0% L. \& T' P- _% l* V- H
      }
1 U" F1 q$ S5 W7 v- c) ~ }  for(var i=0;i<aa*aa;i++){
3 Q. g* o& a* L) s( ~/ O       isling=[];
# D$ {2 u2 k2 i; w) a       for(var j=0;j<aa*aa;j++){5 s/ l$ m: Y9 {2 r
         isling[j]=-1;//初始值为0
# I1 w1 ^/ Q9 K8 W6 L3 a       }, O$ b* r1 v( b. ]# W; q6 m  f
}
* d4 w: U1 l0 e% l* K4 ?+ {' B2 l$ ?$ S- y: \  {( f% W6 P
function drawChessBoard(){//绘画: I4 h2 C6 @; s* F
      for(var i=0;i<aa+1;i++){
# o/ W% O' {* p4 `          context.strokeStyle='gray';//可选区域( d# D( u: ~; |3 M4 j
         context.moveTo(15+i*30,15);//垂直方向画15根线，相距30px;
5 s7 B! s4 }) y& ?4 v; o) o" U& V          context.lineTo(15+i*30,15+30*aa);7 f0 B/ ?+ ?/ T7 I
         context.stroke();
, X- G+ p& L" a$ V5 e+ h9 H          context.moveTo(15,15+i*30);//水平方向画15根线，相距30px;棋盘为14*14；# Z; c5 Y7 [. d% U9 ?3 C7 L
         context.lineTo(15+30*aa,15+i*30);
$ Z1 e  |0 v) V# O7 w          context.stroke();+ @- _9 a; L( C& u6 ~2 ]
      }' c) C8 H1 Y+ I3 X8 x0 \6 C6 b
}8 B; P! q) b  Z# b
drawChessBoard();//绘制棋盘
5 B; w  q2 L5 ]( l8 b  A4 O1 c* }6 b) F, A
//    var mymap=new Array(36);
; n- J1 T+ |. |. p //    for(var i=0;i<36;i++)9 a1 e& }7 j. F- w8 Z: v  s
//    {mymap=-1;}4 R- m. U- Z1 D  r7 g

. v9 X3 v& N& C7 {/ k1 Y) i* [  _" V  K5 T$ B4 M
  </script>
4 z5 o% l0 h8 W" D. ?  s9 D</html>
& `" `( E/ P4 |) I" i/ F3 Y9 ]; |) J% `' v1 w0 n# ]! v$ q) a4 h
) x/ n: j4 S$ N0 _% B% Y! j
实现效果% l# @* {/ t' s7 C

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

( h0 W" C5 h4 N9 u0 ~6 }2 ]
/ i; ]  h3 a* }# t7 R9 l# J7 M画迷宫
) a: I$ J+ ~# Y4 O/ M, B6 H7 `. a( i2 B( g/ ]! ^( Q2 w1 Z
随机迷宫怎么生成？怎么搞？一脸懵逼。
0 ~2 A# R) r/ b8 U8 B9 y8 m) D! E! j9 k, {
因为我们想要迷宫，那么就需要这个迷宫出口和入口有连通路径，你可能压根不知道迷宫改怎么生成，用的什么算法。小声BB：用并查集(不相交集合)。! O: e  k4 S% Y( M7 i; b
迷宫和不相交集合有什么联系呢？(规则); f. d8 X! t! T2 ^

4 _3 i) a  _0 {0 v之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合)，它的主要功能是森林的合并，不联通的通过并查集能够快速将两个森林合并，并且能够快速查询两个节点是否在同一个森林中！
/ j' B8 j5 f9 o! Q, F而我们的随机迷宫：在每个方格都不联通的情况下，是一个棋盘方格，这也是它的初始状态。而这个节点可以跟邻居可能相连，也可能不相连。我们可以通过并查集实现。' V4 r6 ?7 b/ e+ n' G7 k
( q% h- n+ l) V( p+ x% S: V' Q. o
具体思路为：(主要理解并查集)/ R# H. o5 H* y7 {& u5 V5 Q

4 @6 Q' t+ c& v' E1：定义好不想交集合的基本类和方法（search,union等）
# T* \( k4 d4 l1 z. ~& R2：数组初始化，每一个数组元素都是一个集合，值为-1
' m7 {) R, T( ~; ~3：随机查找一个格子（一维数据要转换成二维，有点麻烦），在随机找一面墙（也就是找这个格子的上下左右），还要判断找的格子出没出界。6 U* q$ i/ w7 g5 ^' Y0 t) A8 K- k
具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界( D9 `# S+ X1 }, r
4：判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在，则重新找，如果不在，那么把墙挖去
# i# T1 q8 [5 z! _5：把墙挖去有点繁琐，需要考虑奇偶判断它那种墙(上下还是左右，还要考虑位置)，然后擦掉。（根据数组转换成真实距离）。具体为找一个节点，根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。# h) W1 }' V- u' z1 F* |
6：最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙，但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据，并查集操作。二维是位置。要搞懂转化！
( T% F- D, ^% x注意：避免混淆，搞清数组的地址和逻辑矩阵位置。数组从0开始的，逻辑上你自己判断。别搞混淆！4 J- Q6 x; w4 \# Q2 x1 ^

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

" j) V6 x+ y- U* O; x% Q' e. x  j+ G/ N
主要逻辑为：
) u5 B( l7 G) e; y" f, n- a) jwhile(search(0)!=search(aa*aa-1))//主要思路
- J6 n; d7 i) d# }) r: R {
8 {) N' u8 i  j$ I" q3 Q& h       var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
. T  s1 j" M! |# D8 l       var neihbour=getnei(num);9 @1 B# w9 ~* v  Y" E& [) C
      if(search(num)==search(neihbour)){continue;}2 E6 v. C6 d; q1 C7 a8 P( ]: R3 \
      else//不在一个上1 l6 p( H2 N7 f8 f/ C0 Y
      {: G" \" h9 h3 S, {- R0 t
         isling[num][neihbour]=1;isling[neihbour][num]=1;: m' C) Q' P' K
         drawline(num,neihbour);//划线
0 R  k% z5 t6 C, @. r) Y          union(num,neihbour);
/ E1 r3 F0 ~$ w! {2 w, W9 }+ ]7 g) f/ ?! r3 }& d- B' Z+ J" m0 g
      }" {2 U2 S( J5 L& S/ W  A0 G
}
. Y5 `3 }' y- a9 o$ U1 }* j" [" t: D" k9 C+ b: j+ ^
$ E: z4 X: J2 t8 c4 [( Q; Q
那么在前面的代码为
; G; W4 Y$ @; }0 E& D<!DOCTYPE html>0 ~; L' x6 F7 s! a/ m
<html>
- v# j/ b: V3 F2 g% m+ b. Y  <head>
& ?3 O+ y: r2 s" _  E. @ <title>MyHtml.html</title>
7 y- j( L% ^5 G8 K# T8 J  </head>
9 s3 p& f% q% }  <body>
5 o4 X7 C4 Y( _% o, p9 b8 P  <canvas id="mycanvas" width="600px" height="600px"></canvas>
9 o- a: m8 t- H' p9 C: W7 q) T: t1 @. G5 Z
  </body>0 w% _/ i7 y6 E* s. S
  <script type="text/javascript">
4 O. Y1 R! z8 T//自行添加上面代码
3 ?3 F6 t( [; f2 y6 z //    var mymap=new Array(36);
# t# Z# I! x) P' x5 o5 v, c //    for(var i=0;i<36;i++)6 H2 D7 c, l# `: |* P- H8 h8 I9 p
//    {mymap=-1;}
1 j) L1 c2 |( _9 a$ k# G, w function getnei(a)//获得邻居号  random
8 r+ ^8 g" A- W {& {; W, A3 C) `* u7 L; X9 \1 f; K2 o
      var x=parseInt(a/aa);//要精确成整数9 d+ Y9 o  r1 l8 J' ?& x0 ]* q
      var y=a%aa;8 S8 x$ F8 K- T4 f# k+ c3 r8 c; h
      var mynei=new Array();//储存邻居
2 b" K& z1 ?9 D4 u- b8 m5 W       if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点
: q% ]; X& E" q' u7 D       if(x+1<14){mynei.push((x+1)*aa+y);}//下节点. b  T4 {0 t9 c6 j3 }  f
      if(y+1<14){mynei.push(x*aa+y+1);}//有节点6 R* C4 e! ]# g/ _* d" e
      if(y-1>=0){mynei.push(x*aa+y-1);}//下节点
7 C( G! k0 p# Q+ O# u3 n       var ran=parseInt(Math.random() * mynei.length );
  c6 P7 N' E0 N! a$ {       return mynei[ran];  K  A4 o: z2 h
: t+ y1 X# N4 X  x2 }; m9 _" H0 p% G% a
}. K+ x  S* }+ e" d2 ]: e% A; A. I5 w
function search(a)//找到根节点
6 p7 g2 R' u$ g2 b2 p {
" k, @) [; K3 ^       if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
& P2 {4 q* t- p; o       {
' F) q3 e( ?$ Y$ g2 w7 ^7 P- Z          return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩1 g2 Q+ L% o9 W5 h
      }$ I! f1 w1 }% [; r
      else+ F3 t- i1 Y) _4 E
         return a;3 g% i9 ^# v) P- {
}" _0 v+ \7 i* a- G2 ]# A
function value(a)//找到树的大小4 ]) J* d9 b- `0 \( R
{" l, _: j1 I+ q- |9 J% ~; A
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点: Q  \. X) R6 }% |7 M* e; v
      {* U6 D) V* @. k  C
         return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩8 |% I$ a6 U) z
      }
$ }: t8 c" `; M; z       else( d& n1 S! T( B
         return -tree[parseInt(a/aa)][a%aa];
; L4 ?# @# A( {) {2 G5 e- p. p }' z. X2 w; u( k8 W8 [
function union(a,b)//合并! T3 T- c& n" B  Z8 Q* ]* W/ g
{
! q3 N1 V0 W0 ~+ u+ K$ R       var a1=search(a);//a根
3 Z' d, ^2 J* x  h5 P3 E/ l# N7 h/ L       var b1=search(b);//b根
' Q2 |# h4 ^& ^# {* r) I       if(a1==b1){}7 U3 N  m0 B% ^6 O
      else
. x$ [4 X7 Q+ x7 H9 d) [% C4 q, @       {
8 s6 G, t- ^% o3 _1 v          if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数()，为了简单减少计算，不在调用value函数+ a, Q' I2 E5 ^. F& z) W. c
         {
( C$ l9 b% k6 N4 V4 c9 W; }             tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加  注意是负数相加, Z) G: |7 G( ^* W& q  W" [
            tree[parseInt(b1/aa)][b1%aa]=a1;    //b树成为a树的子树，b的根b1直接指向a；
) k# W  ?5 z  [! I          }
6 Y- \4 a4 D# y3 \( D' K1 Q6 \3 k" H2 j          else
# H+ j, d1 t: X3 ]& x$ P0 |7 ]          {# t' [( n; V$ y
            tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];
0 D! c$ O# M0 V0 j: {             tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树' Y: a8 }$ r" T
         }- i, _, j2 I% f. {8 T. o% N
      }* f' ?( M# j0 z5 T
}/ z9 ~- z  |* q& n2 I) _) j% Z
& |& h. g3 H& V- t
function drawline(a,b)//划线，要判断是上下还是左右/ u& p; D* }& `( r9 q# l, q
{
6 w. H$ [/ G/ n8 c1 P
1 D" d! Y& ]  Y       var x1=parseInt(a/aa);0 ]8 r: E/ i5 e
      var y1=a%aa;8 d! s! e, l8 @9 |$ u  D
      var x2=parseInt(b/aa);
5 d, e& f3 O- a# {# N* M       var y2=b%aa;       ! u6 y" Q9 U2 |6 p, I& B" H
      var x3=(x1+x2)/2;
1 u9 q6 T6 _! @& x: \       var y3=(y1+y2)/2;" w! n  J  l5 V1 s
      if(x1-x2==1||x1-x2==-1)//左右方向的点  需要上下划线( @& r  f, D% d7 Y+ [
      {: d5 I% u& n' X( c% \
         //alert(x1);
$ |$ f& V4 `+ j* I* H" M" j5 `- z          //  context.beginPath();0 i- V% P; y- i" f, m2 R
         context.strokeStyle = 'white';2 T% D# f1 g( s" t% E0 F
         // context.moveTo(30+x3*30,y3*30+15);//7 s# H3 {, i. j' F9 Y
         // context.lineTo(30+x3*30,y3*30+45);
/ [( y/ t7 P8 ^$ R$ k" K( |          context.clearRect(29+x3*30, y3*30+16,2,28);
  g$ I' u" H5 D2 M, l; J: ]5 t          // context.stroke();
, W( c  l1 g" ~- H* B3 M' l0 P       }
4 a) n/ s5 W# L" w4 c  D5 S       else6 Y$ p% n7 l9 g2 [
      {
1 w8 y7 }1 z: X; h          // context.beginPath();9 _. V& ~1 B3 b
         context.strokeStyle = 'white';" m2 }& s8 S' L$ n( I
         //  context.moveTo(x3*30+15,30+y3*30);//
* ]' k4 s- D  i0 I& a          // context.lineTo(45+x3*30,30+y3*30);1 ?0 |1 X9 [% R; A; S, F
         context.clearRect(x3*30+16, 29+y3*30,28,2);
/ T1 l: ^  D3 h) ?. ^% Z; J7 w          //    context.stroke();
' b9 z: L4 x6 x       }
2 C$ D6 t6 |" \8 Q% t' G5 T5 | }
+ q, k& |$ C6 t0 Q- ~- @; l4 s* U+ i! ^3 a8 ^9 X4 t6 g
while(search(0)!=search(aa*aa-1))//主要思路+ d. U" q6 u  C4 n% q3 j! e
{
' T, a0 s( ^8 C* @* U' {       var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
      var neihbour=getnei(num);
; v# q7 c' t) S1 E* k2 K' n       if(search(num)==search(neihbour)){continue;}
6 `- a$ @$ W2 i       else//不在一个上2 m3 ~- M9 ]: d
      {! y# s5 F0 _9 [
         isling[num][neihbour]=1;isling[neihbour][num]=1;
& v7 O; J8 v( x) `6 T- V          drawline(num,neihbour);//划线* T# ~: ~; R1 T  n5 D
         union(num,neihbour);6 ?, C. d1 h- q1 T; _5 c
  G% R# N8 s' V" |- W
      }6 @+ i( n: m: u2 g5 f( W* y
}
: f2 w* p5 B& _: o+ Y  </script>
- }( [' A& s9 @7 K% I# R0 S</html>4 Z, G: v6 o; a$ Z, S
5 i: T; ]! c3 X
" v3 q& X/ x% F
实现效果：
* A; |* M* Y9 F) U4 W
( N$ R' I8 }, w) T: ^: F  `

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

+ S9 _% {; g) P! f' S6 ?9 U: v4 R. h0 H; l8 D

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

  @2 |- u7 ~7 C: w
方块移动
; }, c' N. ^. R0 T, s' w
# I( ^* A6 t. }- I! {这部分我采用的方法不是动态真的移动，而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉，在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除，可以根据像素大小精准擦除。4 b0 g; Z4 T2 l+ b! N2 H

( g1 A/ x2 h7 [+ n: j2 h" ]* x另外，再移动中要注意不能穿墙、越界。那么怎么判断呢？很好办，我们再前面会判断两个格子是否联通，如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组)
/ ~. Q1 N# w; b" i
1 u  p1 E. z% [& c( C9 s! E4 W另外，事件的监听上下左右查一查就可以得到，添加按钮对一些事件监听，这些不是最主要的。
/ j2 j' n2 c' E/ D* V
, J) T4 |6 m$ i9 b9 U. F$ z为了丰富游戏可玩性，将方法封装，可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外，如果写成动态存库那就更好了。) F0 ?) a6 z: M2 d1 Y

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

8 F$ Q. p$ A/ V, Q

; d- |# S( Z8 C$ _0 Z- _" N9 a' o% |7 p  s; ^* I5 X
————————————————4 o2 L% t1 G0 n. V/ ?- g) {
版权声明：本文为CSDN博主「Big sai」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
, [( z$ _" i5 _- W% k# q  ~原文链接：https://blog.csdn.net/qq_40693171/article/details/1007167660 {  e, e; T/ P) b  n
4 H# L; @" X  w

6 I/ ~1 _% ?7 B* i, q5 K