查看: 2555|回复: 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=[];: s" |; o" t2 G  @. Y
      for(var j=0;j<aa;j++){
0 A, M( n6 b7 R7 D) V" F          tree[j]=-1;//初始值为0& ]/ [' U) t" _* R1 G8 a* R5 r- b
      }
5 Z* ?0 K4 X8 H$ q' X" Q! H! t. O }  for(var i=0;i<aa*aa;i++){. i' _& c; g" ?
      isling=[];
1 o) o0 l, ^) ^/ [/ @9 J7 \       for(var j=0;j<aa*aa;j++){
+ m) l2 `2 Z8 i! X" x. D          isling[j]=-1;//初始值为0
8 A& c4 |/ A+ T       }
+ b2 f; i- k1 R6 k }2 h% c7 B: n& _- C) s0 O
) N0 v" l- c. ^3 `0 W
function drawChessBoard(){//绘画
! E, D/ I; ]; Z+ b       for(var i=0;i<aa+1;i++){9 Q. D  r3 J. l& m0 l/ {, i
         context.strokeStyle='gray';//可选区域
9 l: S1 S$ ~2 C$ B* e+ G0 U! T          context.moveTo(15+i*30,15);//垂直方向画15根线，相距30px;
; Y9 c2 `& k& Y$ k          context.lineTo(15+i*30,15+30*aa);
; l; t# L9 Q- h1 C) z          context.stroke();5 ~! i7 g7 `  N. V
         context.moveTo(15,15+i*30);//水平方向画15根线，相距30px;棋盘为14*14；# f. k9 F4 M7 M
         context.lineTo(15+30*aa,15+i*30);
# B  @' m7 }( U) U          context.stroke();; \, k9 ^7 a% I9 d1 O) ]
      }
2 R. ~1 j+ m  }+ F+ ~9 E/ C }/ \* D0 P) p* ?6 v+ ?" {0 t5 [2 b
drawChessBoard();//绘制棋盘$ O$ v. D& s* J! T- P. }

, k. {# ?+ r2 p) c4 P* r: P. }2 Z //    var mymap=new Array(36);
; K' q* h* Y% K$ k+ L //    for(var i=0;i<36;i++)
% _, U# l4 @4 Q0 z //    {mymap=-1;}
0 A; L1 A5 R) X1 j( T8 M) b* ?
) w% Z8 I; [' l: o1 g1 e0 _; D. ?5 a: h+ z$ t8 \3 @
  </script>+ ?- C: _% N0 t7 K" g7 t
</html>
4 q3 v& N: Y) q! O: M+ H
! {5 e4 I2 R& ]" v1 y7 g% ?% Q$ j& s& C$ ?8 R; X4 L
实现效果/ r4 Q: n4 }; p  `- z

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

' q9 R2 p( A! d  p

5 T3 N+ }! D1 j" q画迷宫9 T) C2 e: a) S, _( h$ Y; a( H
' T1 P9 q" Z! L& R, W, R
随机迷宫怎么生成？怎么搞？一脸懵逼。
% Q0 d8 z. b! S" `% Y5 W: T
3 S6 J1 V- [  p. m  |  J* b因为我们想要迷宫，那么就需要这个迷宫出口和入口有连通路径，你可能压根不知道迷宫改怎么生成，用的什么算法。小声BB：用并查集(不相交集合)。4 W3 N6 Q: `9 k; ]4 f, z$ T
迷宫和不相交集合有什么联系呢？(规则)
! Y# y4 T2 K5 p/ W& L7 x
  _, T" R% [" H) U9 G: S之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合)，它的主要功能是森林的合并，不联通的通过并查集能够快速将两个森林合并，并且能够快速查询两个节点是否在同一个森林中！0 O! z$ p5 }( _
而我们的随机迷宫：在每个方格都不联通的情况下，是一个棋盘方格，这也是它的初始状态。而这个节点可以跟邻居可能相连，也可能不相连。我们可以通过并查集实现。
/ z9 G% C# p1 a* c& X& n. @, f& B& }; E
具体思路为：(主要理解并查集)
7 r: p5 _3 z* m3 O* r2 j9 w9 O1 Q$ I! Z* [: R
1：定义好不想交集合的基本类和方法（search,union等）- N7 U, z! N7 o% _
2：数组初始化，每一个数组元素都是一个集合，值为-1
4 F' e0 |9 \+ o( t0 t- ^3 h. l3：随机查找一个格子（一维数据要转换成二维，有点麻烦），在随机找一面墙（也就是找这个格子的上下左右），还要判断找的格子出没出界。
3 R& R5 O+ i& M- f4 }- l/ P具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界
& x9 ]2 j* k1 G* Z4：判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在，则重新找，如果不在，那么把墙挖去
) Y9 C  `8 V, C. B* p7 C$ V' q5：把墙挖去有点繁琐，需要考虑奇偶判断它那种墙(上下还是左右，还要考虑位置)，然后擦掉。（根据数组转换成真实距离）。具体为找一个节点，根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。
( x+ e2 \$ W5 v6：最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙，但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据，并查集操作。二维是位置。要搞懂转化！, R( A! q* ~3 x) w6 k8 K1 c
注意：避免混淆，搞清数组的地址和逻辑矩阵位置。数组从0开始的，逻辑上你自己判断。别搞混淆！/ b0 k6 F8 ^0 E3 _; K- v* v

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

( y! o: V" p6 N9 h" {( T' X主要逻辑为：) S' M0 p4 D) n! A* ~  f+ l
while(search(0)!=search(aa*aa-1))//主要思路
$ t8 ]: z* e; q5 A. K {- |5 A+ ?# ?+ R7 \( e
      var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
0 y3 o/ ^- r9 c$ D8 h       var neihbour=getnei(num);
9 g2 |- \: o" I! J$ x) A* {       if(search(num)==search(neihbour)){continue;}
/ K( I$ z8 |0 }; C- E       else//不在一个上
9 w* c# z* o8 B1 E       {2 Y, ]" h' V1 g) ?& s9 ?. K
         isling[num][neihbour]=1;isling[neihbour][num]=1;
! p7 L6 ]* p8 H/ G          drawline(num,neihbour);//划线' ]( ~; w; y7 K  L
         union(num,neihbour);. u2 q! j; o; \8 q  h

% ^3 F% f$ y1 g% o4 J( d       }# |  r' |6 F% O. \0 Q
}
! }& {  Q# J; x, M# V: `2 ?
* S& D" s3 G8 G; _# t
5 z( K9 ^% |' Q$ G& r那么在前面的代码为* j' z4 g6 ~! d2 n
<!DOCTYPE html>
: O& n1 J1 ]/ A7 r& V5 s<html>* C# _  u/ [$ H5 `
  <head>
/ s% {& A- k. ]; F% z <title>MyHtml.html</title>
6 l/ [! Y9 g# Y7 ?) Z/ Y( F( p4 |  </head>
$ m# X% s& ~- ]: G7 U% j  <body>
( g* ~6 A/ p8 N5 B  @: M" K. {  <canvas id="mycanvas" width="600px" height="600px"></canvas>
, x2 u) X, O, P1 a" V# P
# i5 C& T+ g$ A1 T, V- b8 R* Y4 ^' m  </body>
( u" |% U: X0 f+ e# r% `  <script type="text/javascript">- {  |' a2 M+ p4 {4 a
//自行添加上面代码
1 r7 H8 l( f! C6 c; |* b //    var mymap=new Array(36);" j# n* ]& Z2 V5 f9 @
//    for(var i=0;i<36;i++)
' S$ \9 N- j- X& Q$ r4 Y  | //    {mymap=-1;}
% e5 U5 _6 Q$ h6 Z function getnei(a)//获得邻居号  random) E  E- \/ Q3 e6 R6 Y
{
8 ?5 o6 m# C0 t: P$ q$ W( c( o6 c       var x=parseInt(a/aa);//要精确成整数
+ N& x9 J) o: X       var y=a%aa;" P5 j5 Q8 o% n. Y3 l6 ~
      var mynei=new Array();//储存邻居
! g; B7 e% H! I3 o1 x5 b       if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点
3 w* f9 [8 s2 X! |. F       if(x+1<14){mynei.push((x+1)*aa+y);}//下节点
6 O, Q: W9 G6 Q" k+ Y+ z0 Y  {       if(y+1<14){mynei.push(x*aa+y+1);}//有节点" \1 r' A& W. J7 Q. a* @$ I
      if(y-1>=0){mynei.push(x*aa+y-1);}//下节点
; `5 a8 i, M; ]7 [" t; V% W       var ran=parseInt(Math.random() * mynei.length );
4 @+ |3 ~& G' {9 c& C* \       return mynei[ran];
  _- O9 f- J& x% D
# X2 I) k7 a( _$ b# x }
: W3 I) g- N+ B# d( u& Y+ ?6 N: ?; n function search(a)//找到根节点
& k: [. `/ f) `9 P9 D {& k. O; U7 ^( a- L- S# j5 N
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点3 S& m. v8 B; W+ V- k
      {
0 q% E1 x7 A* n: A8 R( ?% G          return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩
, O) f+ `# l" H% o       }% K" n! U" i" C# W
      else
' a* C4 V9 \: t- x          return a;! P9 i+ q$ i/ h4 x
}# z9 h, n& S) n2 g0 \
function value(a)//找到树的大小
" g  n/ }# ?% \9 R7 I4 m {6 e  f! D: O9 g. w
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点0 \" `. w! P+ t* @1 Q9 E; \) b
      {& W! m( P6 X9 H2 V
         return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩% H! J, {! y* n3 q" g( d) A, p
      }0 p! u' K! b0 S5 h
      else
4 f9 |5 |% C2 _1 x% j          return -tree[parseInt(a/aa)][a%aa];
4 b) x7 y  q  D5 k6 S* T }
/ V! ?; {: O  u  x. @( @ function union(a,b)//合并8 B9 B9 x- p# O3 y
{. X/ Y, E% A/ N3 Q
      var a1=search(a);//a根
+ d+ g# n5 u8 F5 W3 `7 }! a6 H       var b1=search(b);//b根5 V. F% G7 _& ^: I
      if(a1==b1){}' ~# ]2 E! F$ t( J
      else
3 i, H" a2 F' O4 U6 [       {& ]9 G3 J' c" @9 b
         if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数()，为了简单减少计算，不在调用value函数
1 @8 [$ g7 h1 T$ t  q, [0 S          {
6 ]' z3 w6 {& X" E. h4 F7 {" S' t1 Y             tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加  注意是负数相加! u# S6 m5 B; q' N: l2 [% l2 ]/ f
            tree[parseInt(b1/aa)][b1%aa]=a1;    //b树成为a树的子树，b的根b1直接指向a；
& j5 V& [) l1 T2 z' N  p          }
; c+ h( |6 N% V6 B# u" F          else( O% x1 O# S8 X, r; q4 l
         {
$ T8 s* r% E# n1 z: z$ w             tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];7 `6 u0 I( g1 ]1 B, s# S! B( h
            tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树
+ _+ W* R: U8 M8 O          }
( I/ ]" }; ^6 `       }
4 z+ y; n. Z+ } }% c# {2 ^9 T/ b
$ A4 c: p8 |( `) T& I- H8 R6 {; o
function drawline(a,b)//划线，要判断是上下还是左右9 l. Q8 g; l/ y! M; N7 M* U
{
+ j6 w8 y$ G# b! U2 \
" ?% ^$ ?# H3 [/ D       var x1=parseInt(a/aa);
+ R. q% C! m/ z) o7 i       var y1=a%aa;
      var x2=parseInt(b/aa);9 @4 g0 R( `: p0 R) m+ D& |" }
      var y2=b%aa;       1 p/ X0 b; M- }2 M4 A
      var x3=(x1+x2)/2;4 M2 V7 V1 M- w/ N& X
      var y3=(y1+y2)/2;+ l! H! e7 O% L$ M
      if(x1-x2==1||x1-x2==-1)//左右方向的点  需要上下划线7 N; Y) `/ C& `8 z. c5 D
      {
  N7 n' Z. ^* I/ z, A0 A! x          //alert(x1);* S9 P' ]3 w/ G' E; h; L! [. t
         //  context.beginPath();7 C. z9 }& A" [4 I3 z. [
         context.strokeStyle = 'white';+ e, o' j- U: i2 Y' g
         // context.moveTo(30+x3*30,y3*30+15);//
3 x0 y2 M6 s, G: v          // context.lineTo(30+x3*30,y3*30+45);" F2 p: ?6 Q6 T4 w2 F" y+ B
         context.clearRect(29+x3*30, y3*30+16,2,28);4 a! o% D. d9 c  D/ l
         // context.stroke();
; i; f( v/ O7 |& }) C0 M, H       }  y; H8 \) }8 r# L5 Q5 @
      else5 \. u  }) T+ U" c# ^0 N
      {
6 [) Z) Y7 q1 `+ z7 d) ^          // context.beginPath();& L/ U6 ?1 {! }: t: I# l7 T# k
         context.strokeStyle = 'white';
2 K8 V, P3 M3 ^% ^; @- t" d' \          //  context.moveTo(x3*30+15,30+y3*30);//$ x1 u  F2 B$ M# d  A7 ?
         // context.lineTo(45+x3*30,30+y3*30);
1 h& x' ]7 a# @( {% W          context.clearRect(x3*30+16, 29+y3*30,28,2);
. U: ~. w- }  U" ^4 H. v( I          //    context.stroke();
% z1 G8 S" {' v6 f$ ^  A% P       }* ~" }& }5 l1 |: M
}3 }$ V7 G4 ^; Z8 i1 ?: Z$ _. N

% b+ |( {6 u' m while(search(0)!=search(aa*aa-1))//主要思路$ u( c. e* u9 T" O
{
8 Q$ d( n$ w8 @9 E/ C) O# i       var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
4 q2 d- D5 a. c& P" @6 o  ]       var neihbour=getnei(num);
# A# z$ O# u5 v# f: p0 S" _7 u) b       if(search(num)==search(neihbour)){continue;}) A0 \4 k5 p5 X9 B: a2 s
      else//不在一个上, B6 ?/ x; ~7 X1 n
      {
9 U$ Y  m# V! C! A/ v. U+ }          isling[num][neihbour]=1;isling[neihbour][num]=1;
  E7 N  L7 `5 U          drawline(num,neihbour);//划线
' K* l! a+ ^3 F+ }& \% ^: v          union(num,neihbour);
" ~/ N4 F( Q: |: e9 w; M
  T. H5 J+ @; O5 L6 G: Z       }
, Q# s! |$ H; H! W% e }
1 ^3 j$ R1 k& P/ K  </script>
" u& U* R5 k1 p% B7 C, m  }</html>2 S( \( J' P* {+ U7 B; y
* E7 g  @6 w5 ^
7 g6 B# p9 o4 a
实现效果：0 S9 F+ O8 e7 \
, R2 U" C" N/ N0 W/ Q; b

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

2 [" I  K! a- D% @5 X5 J) O
: C5 I0 D) S) Z

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

; O2 E* d/ W# @& f% U- J方块移动! t! i7 l: h$ B  |, v

, x5 [3 _4 R/ h' V这部分我采用的方法不是动态真的移动，而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉，在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除，可以根据像素大小精准擦除。  x1 L) ^0 ?. y" z; k- X
8 e" R5 Q. c. F1 i
另外，再移动中要注意不能穿墙、越界。那么怎么判断呢？很好办，我们再前面会判断两个格子是否联通，如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组)
5 p8 i3 Q, [- g: v% [  M
% V* Y: e5 n& }& p另外，事件的监听上下左右查一查就可以得到，添加按钮对一些事件监听，这些不是最主要的。! k: X# ?* ^8 p; v  X# d

6 S: ~: p0 J, |+ g6 C8 I% W为了丰富游戏可玩性，将方法封装，可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外，如果写成动态存库那就更好了。6 A. B) f9 F3 G

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

1 k! V. q! L8 @

5 ?( V6 R4 \2 g( {; g" q
1 S0 G8 J+ A: X) `3 `1 g————————————————( N2 n' q1 O$ Q! T
版权声明：本文为CSDN博主「Big sai」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
0 k# E2 j* {) r2 x" T/ {: N: u- U原文链接：https://blog.csdn.net/qq_40693171/article/details/100716766; t' ~; I7 e. b' |; q

% w, y8 z  _, y! p: V2 Z: c
( z7 ?0 k3 ^" m$ ]. v% m