查看: 2584|回复: 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=[];: I" R$ n0 p8 S% i: O6 {) g
      for(var j=0;j<aa;j++){9 O8 E8 `8 k+ U: j
         tree[j]=-1;//初始值为0" l+ I' B& [' w( x' T
      }# \4 R+ y8 @& n0 Z$ u. F: i
}  for(var i=0;i<aa*aa;i++){
5 u) T* c' L; ?% d) f& t       isling=[];
3 I5 L! G" I! D. W7 s3 c       for(var j=0;j<aa*aa;j++){; h& r6 W. t- f  s+ v' t) Z
         isling[j]=-1;//初始值为0+ o1 ^/ D/ w( ?. G5 t% G) K' U4 }
      }6 q  X9 c4 t! J. f$ A: r5 b
}
3 |! ?: m! L2 M9 b( @
3 M/ ]0 P/ A2 R function drawChessBoard(){//绘画
! X5 R' Z1 ~5 R$ j       for(var i=0;i<aa+1;i++){
, T) m8 ?& B7 [: h3 S( h9 v          context.strokeStyle='gray';//可选区域4 F) j, B! f1 A3 q" }3 }0 ~: O
         context.moveTo(15+i*30,15);//垂直方向画15根线，相距30px;' T3 A$ z2 }' x# F4 d$ [
         context.lineTo(15+i*30,15+30*aa);
6 Q0 d, }7 h: C2 K          context.stroke();
% d) Y7 u' k: t, {" ~) Y  m          context.moveTo(15,15+i*30);//水平方向画15根线，相距30px;棋盘为14*14；
0 P& s+ E+ _3 o8 B8 M          context.lineTo(15+30*aa,15+i*30);# j- v9 I! c, ]9 z
         context.stroke();
: c  X$ c# ~3 e  L       }5 ^& f6 M' u9 W
}
9 P2 ~6 v. O0 c! m% K; K- | drawChessBoard();//绘制棋盘( r! X. k0 N+ r4 E8 U

0 q; V: R& ?( p% q  C6 J //    var mymap=new Array(36);
' B4 [. @* z' A //    for(var i=0;i<36;i++)
1 G# T% \% y' ~/ m+ e //    {mymap=-1;}
1 Q: B) T* e9 Z: r1 s6 \5 L& n) N6 i/ }: z2 e% X+ T
& q$ @& v: E  U4 E1 Z
  </script>, A+ I2 y3 c1 d5 T7 U* h; t, x
</html>
- q+ ]' a# C( J* D9 X3 r4 ^% ?3 q& O' X- k0 p; ^; c& S
, A1 y$ c6 ]4 T# ^) V0 _( \
实现效果, I0 V# T3 J+ ]+ l

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

: R. G9 {; [  [) |+ U; f2 g

) I  Q+ a8 \/ B8 E% [4 Y画迷宫
  `$ i6 |4 s* d4 W$ m8 h4 p
% [# |7 e5 x# m" l3 Y* M随机迷宫怎么生成？怎么搞？一脸懵逼。' {% x* p2 j3 s/ g+ w

0 _$ b6 q- E7 c3 U, k因为我们想要迷宫，那么就需要这个迷宫出口和入口有连通路径，你可能压根不知道迷宫改怎么生成，用的什么算法。小声BB：用并查集(不相交集合)。
& h5 u6 c' U, K2 K/ A迷宫和不相交集合有什么联系呢？(规则)2 o% }4 o6 h  W
( h# e) _, ?1 y1 H  O4 m! i
之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合)，它的主要功能是森林的合并，不联通的通过并查集能够快速将两个森林合并，并且能够快速查询两个节点是否在同一个森林中！. _5 r( L, x& F
而我们的随机迷宫：在每个方格都不联通的情况下，是一个棋盘方格，这也是它的初始状态。而这个节点可以跟邻居可能相连，也可能不相连。我们可以通过并查集实现。
8 Y, h4 w3 }5 K' n' \' n2 t) ^4 m7 `5 M; \
具体思路为：(主要理解并查集)' {$ ?0 c6 C" v
3 j' Q0 _3 Y  A
1：定义好不想交集合的基本类和方法（search,union等）
) r- z7 x; D8 x$ A/ u2：数组初始化，每一个数组元素都是一个集合，值为-1
5 d! a1 M! E  T- ~1 e: {3：随机查找一个格子（一维数据要转换成二维，有点麻烦），在随机找一面墙（也就是找这个格子的上下左右），还要判断找的格子出没出界。& Y8 @& C. B! i1 G# M0 G% C
具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界
  Y- j/ e) `0 Y+ C% S; a& L4：判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在，则重新找，如果不在，那么把墙挖去, _" N3 I  e& R9 j7 r- l, [
5：把墙挖去有点繁琐，需要考虑奇偶判断它那种墙(上下还是左右，还要考虑位置)，然后擦掉。（根据数组转换成真实距离）。具体为找一个节点，根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。
& R  ~' R" r6 e& s5 i$ E9 ]6：最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙，但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据，并查集操作。二维是位置。要搞懂转化！
5 K- Y+ l- @% n: f" D3 r5 `1 r  D注意：避免混淆，搞清数组的地址和逻辑矩阵位置。数组从0开始的，逻辑上你自己判断。别搞混淆！( Q5 q) \5 O% m6 v, ]

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

, t& s' {7 A5 {. F7 W# l, E
主要逻辑为：
9 [- ?  G$ q! U! j: Uwhile(search(0)!=search(aa*aa-1))//主要思路
  r8 B$ h/ u2 M' a9 _ {% d# c0 g. @' k5 n7 E7 G
      var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
: Y! w2 c1 D# T9 |       var neihbour=getnei(num);
: m# s! B* P" N. ^       if(search(num)==search(neihbour)){continue;}% d1 ^# P" h7 l- Y
      else//不在一个上
/ j* z  T2 q# G+ x/ ~6 ?       {
* b6 S9 Y: @' G; r( d; Z          isling[num][neihbour]=1;isling[neihbour][num]=1;
8 A; F5 S) B& m          drawline(num,neihbour);//划线  G% ~3 q3 Z) ?& n3 ^0 w
         union(num,neihbour);
, ~' s) T* H& ^1 U7 b/ {
  a& c: q( Y: ?) T" P" j3 p4 B9 G2 W       }8 U. _" U3 m# q. O
}
; m6 x2 R2 F2 D7 |+ c9 A* d7 d' y/ g% {5 b7 C

+ R+ K$ _7 m8 \那么在前面的代码为8 p9 g# W# B( y
<!DOCTYPE html>9 a3 L% C: q; `' m. l: ?! B2 k1 s/ r
<html>" \4 f$ C4 [& s" [9 Q" p( E, z6 \0 U
  <head>" i$ E  _! `+ @
<title>MyHtml.html</title> / c3 n0 U6 p; v- d
  </head> 4 H7 F3 z6 Y$ N: m, \
  <body>
7 p' x+ U( ~$ b- R! Z  <canvas id="mycanvas" width="600px" height="600px"></canvas>5 Q" U- i+ f* }9 w0 ^  A5 H9 o
& r4 m' h' W8 g. h! W
  </body>' A: e! t2 c( S/ k1 h- c
  <script type="text/javascript">/ C2 D# x+ h( n
//自行添加上面代码
* S# N# ^! @/ C; m0 r! L* x. L //    var mymap=new Array(36);
( ]  t1 f/ g- v# M3 O+ l/ ] //    for(var i=0;i<36;i++)  |( e, N, ^$ {0 u
//    {mymap=-1;}
0 V! @  |- Q& j, @& m/ t! k. p function getnei(a)//获得邻居号  random
% N* \+ Z$ \! E1 o {7 Q, _% E5 r4 I5 C
      var x=parseInt(a/aa);//要精确成整数; o  E+ B; D/ w& U) `  \9 \
      var y=a%aa;
9 _& Z& S7 G  R  D6 m# a& G5 b       var mynei=new Array();//储存邻居
7 c5 D5 m/ ~7 o# c+ n       if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点; g  f0 Z$ j) ?' U7 Z! s# ^2 E
      if(x+1<14){mynei.push((x+1)*aa+y);}//下节点6 O2 l" R$ f1 h+ }2 W3 l
      if(y+1<14){mynei.push(x*aa+y+1);}//有节点
% v; I/ ~4 _" P       if(y-1>=0){mynei.push(x*aa+y-1);}//下节点
! C% B: ?0 T$ P! a4 ~0 y  o' `       var ran=parseInt(Math.random() * mynei.length );
( ]& u2 _" X! f3 q* ~% C7 Z$ I       return mynei[ran];
, z+ H2 m/ X5 V  Y6 i
, N& C0 P4 I; b; A0 B$ l }7 j- o" z  Q& ]" f6 G
function search(a)//找到根节点
5 m! B5 G; }; P% X( M) u {
5 A" t" ^& z1 n1 S; h5 ^       if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点" Z" Y+ u/ j) p( f
      {8 p* Y1 T4 ^- q* X; ~  \( j2 ]# g
         return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩% h" \8 [/ D7 H& y& N
      }
# t$ r) D6 ]6 n0 z       else1 i/ m; b, w; i/ f
         return a;
" I4 A! A( k9 K8 r' A' p1 w }# K* V* ^4 j5 D
function value(a)//找到树的大小
  t- K" s; H. Y" f4 W' ] {
( F$ l4 M# x4 x* r0 D7 r       if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
$ q* ]; g( ^3 S" S# O0 A2 [       {
- n: n* G" ?# @( {          return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩
  t+ C% j2 D2 r6 y# b       }& p) M5 @& F, r1 N& C
      else
0 C& t, c6 M4 s# H0 w# B          return -tree[parseInt(a/aa)][a%aa];: I2 F- e/ ~+ C' |
}
! W8 @* Q/ m' a, [6 B( r# k function union(a,b)//合并
; J$ ?( C/ O/ _; c) U1 D; Z {/ B/ X! Y$ m9 F+ l4 `2 o# ?
      var a1=search(a);//a根# B1 J' X0 v: A" G" f3 k/ E
      var b1=search(b);//b根
" R' ^$ @2 p. S3 x1 e  k& [       if(a1==b1){}2 X3 f+ r4 q5 I4 {0 e2 l
      else. c7 O! z3 k2 z3 Z: @
      {7 G2 I3 z# l4 N% ?( e
         if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数()，为了简单减少计算，不在调用value函数0 v6 l! P" W" h4 Z
         {
2 S" _  k+ n' o             tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加  注意是负数相加
/ b, q; Z3 K5 @; A( j" \3 a$ m             tree[parseInt(b1/aa)][b1%aa]=a1;    //b树成为a树的子树，b的根b1直接指向a；3 S0 ?& p: ?% q" T: i$ {( K
         }
6 k8 j2 i% r; x& _) M" \2 s          else
/ i2 K/ f4 K0 B2 ?! F          {% N- M) r. Z7 J# B+ i; H( L& }9 `
            tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];. B2 W1 }9 }. G( [, h1 ?* q. y
            tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树
) k. Y/ C3 r( H& w          }! J7 i" Z4 D! S% b
      }  ^% }' A- {; M, o% A
}, J$ n. q/ s! }& C) b/ H8 g' V) i* h: z
$ a/ @3 H, l9 I" ]
function drawline(a,b)//划线，要判断是上下还是左右, w+ X" `$ l& |9 e
{  Y: k) W2 M4 K7 g$ v, l

8 B) |# A1 n2 R8 K  E, C4 i       var x1=parseInt(a/aa);( n1 w& I, ?9 s) P& q$ x! \
      var y1=a%aa;0 }$ e4 M4 O+ n1 T/ B; y$ T: E; j
      var x2=parseInt(b/aa);# ]+ S9 q. i, k6 o3 D4 t  G
      var y2=b%aa;
1 |0 s$ y  g$ v" h3 P9 Y       var x3=(x1+x2)/2;0 a- S' ], f9 f. O1 t! ^
      var y3=(y1+y2)/2;
2 \' D# L! d6 i' @& l       if(x1-x2==1||x1-x2==-1)//左右方向的点  需要上下划线
: W) z& E8 o) F4 U( j! R( X# @       {* Z+ U* c, D0 T, C: @( H
         //alert(x1);
9 i; x( o' A6 N# \          //  context.beginPath();
* U- c+ i. [# t1 I          context.strokeStyle = 'white';8 L: E8 X( j. N% ]
         // context.moveTo(30+x3*30,y3*30+15);//
2 o( c4 |" i1 S# O' r' w' |' q* W- T          // context.lineTo(30+x3*30,y3*30+45);
' t# X% o3 R0 x+ V! B7 S          context.clearRect(29+x3*30, y3*30+16,2,28);
' k) h2 W+ P$ [" V8 I6 s: ?% A          // context.stroke();
9 l$ S! H  D4 N/ F! H4 d       }6 i% [- c# N: I6 y' c
      else
& n3 O; \) s/ w; V0 f( X7 u1 K       {3 V3 Q: m! Q9 O- e4 k6 }" L
         // context.beginPath();
# V+ g" _0 O3 l4 U) s          context.strokeStyle = 'white';3 I$ z9 g$ b/ j. _
         //  context.moveTo(x3*30+15,30+y3*30);//
1 m" t- L5 D+ K7 w          // context.lineTo(45+x3*30,30+y3*30);
, R2 Q& p6 i" v' A% o4 _( g) o          context.clearRect(x3*30+16, 29+y3*30,28,2);
3 I5 q% W7 M( q: v          //    context.stroke();
8 W& P& O4 F2 o1 v' T# E% C. O       }
5 J! K4 D0 T1 w( I% x. _: Y* f }
4 D% m/ ?; h! h) d- }% q( B3 k, h' J; x. o! Z) W# r
while(search(0)!=search(aa*aa-1))//主要思路% B  U$ t. w' H, O1 ^2 H& j: ?
{
. e( p& L2 n+ h& ]) b       var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数' E) Z' g( Y0 O" q' L
      var neihbour=getnei(num);
' U# F6 W; q) a9 M3 T+ r       if(search(num)==search(neihbour)){continue;}
0 t8 u. ~6 E6 V  E6 O4 L7 o       else//不在一个上& C# Q) A3 j& W3 R! M$ v7 n
      {
) O& O: O& x+ G( G' G% {8 n          isling[num][neihbour]=1;isling[neihbour][num]=1;
- N) j, |0 t, W1 u9 M" E% Q          drawline(num,neihbour);//划线
* @$ f$ ]9 W2 \+ d0 \          union(num,neihbour);
; N4 H; D3 I; U6 P0 j
2 a, A. W0 Q; Y) P% u- ?       }) D& }  v, E9 y# n+ r' t
}/ {; S5 h* {- p* Z: W2 Q
  </script>
. T- G) P- e; _' |) x2 c- A: V7 z</html>; u& o/ g' f1 X! R1 ~+ i! s
9 A  U2 D' `: j( t

2 d7 C- {: T' d实现效果：
+ k  t! |2 h3 ~$ L  r  G
! }/ [2 o1 p4 Y+ u

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

% o! u% b9 X2 Z* |: U5 M0 ~- a
9 N, T9 @+ `& o0 Z; g

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

- Q! H1 H8 @. \; c. b& m# z- j
方块移动5 d1 T7 x9 Z4 c7 ^' ^

% {8 ^; K1 B: t8 b% J这部分我采用的方法不是动态真的移动，而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉，在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除，可以根据像素大小精准擦除。" O5 o' |& ]8 w

( ]" }$ q1 I8 n+ y- ]另外，再移动中要注意不能穿墙、越界。那么怎么判断呢？很好办，我们再前面会判断两个格子是否联通，如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组)  U- C6 Q  e9 e: ^. [2 e$ {

% ~8 q5 r5 ^( m. b5 x5 i另外，事件的监听上下左右查一查就可以得到，添加按钮对一些事件监听，这些不是最主要的。  U/ Z# ^# i5 _+ i- O) m

/ M, q: Y& U! u为了丰富游戏可玩性，将方法封装，可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外，如果写成动态存库那就更好了。( h8 H( S: V; l  E; p

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

9 E" i) v+ y  p

* u- {2 B1 Q, w& E% F, z
8 d' Z/ N5 @5 k# k# |# S————————————————/ S7 \9 z9 q! z, m& U! g- z
版权声明：本文为CSDN博主「Big sai」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
/ k3 ~+ R6 T* j* z' l7 J! A原文链接：https://blog.csdn.net/qq_40693171/article/details/100716766
% A; P% D9 l' Y! d# v
/ {* w& m! S: b4 ?8 _, W6 V( s0 {0 r( q8 a. e