查看: 2625|回复: 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=[];
- B( T: w1 F/ x' C. P       for(var j=0;j<aa;j++){
  a  ]5 P' d9 V0 {1 w5 L          tree[j]=-1;//初始值为0
% O* R$ w) U7 i( v- ]       }4 f% V/ F6 Y+ r
}  for(var i=0;i<aa*aa;i++){
& e! G9 U) ]5 N, Z. ~       isling=[];8 m& A* {8 d! W7 n+ k$ ^6 F4 y+ B
      for(var j=0;j<aa*aa;j++){
+ v/ W; Y9 q( i- c7 M/ Q3 G          isling[j]=-1;//初始值为0
) C1 G" _. n; q+ b5 w7 s       }
! f7 u( w6 g" V1 U# r# F }& {8 G: s# a) x' }, D
9 z0 t$ M) S( Y' Z# ~3 U
function drawChessBoard(){//绘画; w7 x* e6 `! {+ m* V
      for(var i=0;i<aa+1;i++){
% `5 |# A. L/ e1 y3 G          context.strokeStyle='gray';//可选区域
% w+ ~$ r" r; v- s  t! S1 |0 |          context.moveTo(15+i*30,15);//垂直方向画15根线，相距30px;7 y- @! |# f" n6 @
         context.lineTo(15+i*30,15+30*aa);5 D) n2 M; H# L: V4 k
         context.stroke();
) N+ F8 A/ R) ~4 ~/ }% I          context.moveTo(15,15+i*30);//水平方向画15根线，相距30px;棋盘为14*14；
4 S+ ~! S" q: O7 i          context.lineTo(15+30*aa,15+i*30);& ?% s- w% h# c* O2 E& B/ d
         context.stroke();% i! O( c; C: x/ _
      }& P. _" z# l" Q
}; {8 I: O- x8 I( t/ B& ~
drawChessBoard();//绘制棋盘3 q% J8 O: ~. p
' H1 g4 D1 N! {& e; j
//    var mymap=new Array(36);/ K) L2 g9 E6 h4 }4 p; d
//    for(var i=0;i<36;i++)+ b- @. R6 g4 B: }: E  X
//    {mymap=-1;}& J+ y) x" p2 @) h/ q

8 ]; N% T0 ]( ~. ~0 z# }" ?
5 ^& S6 \: e9 o/ v2 r% f  _  </script>
1 r2 u4 F8 [1 Y9 W7 \1 v* A6 m</html>; w, [$ M9 y3 J6 e

9 y& I6 H. |* Z3 b. J, ?6 r! ^
. v* n9 {9 v3 m, E1 Y7 v% p实现效果
% g% u  [! F/ W+ v4 t; D" ~, ]

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

$ S5 b: E9 c* l( Q* S

( d. B" l  F( w# c0 X画迷宫/ k" O0 [9 h  @
! y" m: g0 l+ \: V2 \5 e
随机迷宫怎么生成？怎么搞？一脸懵逼。
" ?# x+ w/ ?& x$ j  `' I1 W
) r6 b4 {  v9 A0 [! J因为我们想要迷宫，那么就需要这个迷宫出口和入口有连通路径，你可能压根不知道迷宫改怎么生成，用的什么算法。小声BB：用并查集(不相交集合)。
* `; |% ]8 m0 }0 |! o迷宫和不相交集合有什么联系呢？(规则)
6 B7 U& ?/ G* n; L' ?; q: g# M" r) F
之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合)，它的主要功能是森林的合并，不联通的通过并查集能够快速将两个森林合并，并且能够快速查询两个节点是否在同一个森林中！, ^" s3 `3 s7 v* b( K2 M6 g. q/ ?
而我们的随机迷宫：在每个方格都不联通的情况下，是一个棋盘方格，这也是它的初始状态。而这个节点可以跟邻居可能相连，也可能不相连。我们可以通过并查集实现。
( F: o6 [& `4 ~6 S& [7 @
) p) T  F1 b0 `" ^( B4 n# t具体思路为：(主要理解并查集)
6 ^1 v9 k! `2 C% g" z% Y
7 M+ p& X* y( N3 C% ~4 t* k1：定义好不想交集合的基本类和方法（search,union等）8 E. ~+ I1 U7 r
2：数组初始化，每一个数组元素都是一个集合，值为-1' K7 n5 T+ c3 T$ K% \/ z
3：随机查找一个格子（一维数据要转换成二维，有点麻烦），在随机找一面墙（也就是找这个格子的上下左右），还要判断找的格子出没出界。! U  n! n: {# Z. r, m# h) E, l
具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界3 a9 ?' o8 Y, Z+ o
4：判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在，则重新找，如果不在，那么把墙挖去; x. m0 o9 _: Q% r2 B0 ~5 x' X
5：把墙挖去有点繁琐，需要考虑奇偶判断它那种墙(上下还是左右，还要考虑位置)，然后擦掉。（根据数组转换成真实距离）。具体为找一个节点，根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。1 M  [$ C. d/ M9 R8 ^# E
6：最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙，但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据，并查集操作。二维是位置。要搞懂转化！
; \4 {. _; C7 ^7 S! i注意：避免混淆，搞清数组的地址和逻辑矩阵位置。数组从0开始的，逻辑上你自己判断。别搞混淆！
. N; k* A( a; p0 h1 L0 h+ L

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

; \9 p3 T- }$ U5 N主要逻辑为：
8 y" a% t* |( p5 }while(search(0)!=search(aa*aa-1))//主要思路" a2 `  X, G' A" y
{
; i  z3 ^; t, ^% g       var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数3 r# e, Q4 F7 `2 e$ I! M
      var neihbour=getnei(num);
' x. {8 x+ C/ D+ W; t& o, U       if(search(num)==search(neihbour)){continue;}4 |0 t7 K, E4 d% r
      else//不在一个上& c# j3 d8 u& z7 G0 K! h0 D- t2 [" o
      {5 R: s" y6 `+ X
         isling[num][neihbour]=1;isling[neihbour][num]=1;7 T& y* h. b" ~- {# L
         drawline(num,neihbour);//划线
, {& j4 S  o" V          union(num,neihbour);
, j# F: ]1 T. ?5 [6 v2 y9 l0 |6 G) `! C# b* `- k( w
      }
. k8 d5 V" @0 o0 i3 |2 e }/ D" t( a3 @: E3 T, r8 ^
/ s8 ?8 M% i! s; Q5 d, A
4 y1 J3 J- k( P# c& Z, h
那么在前面的代码为
/ h! p! \# E5 T& W' B<!DOCTYPE html>& T8 \3 Q# r# d- }
<html>5 g  F, y: |) n6 L) c
  <head>& W  n- h5 J" D9 v4 T. ?0 a) M9 I
<title>MyHtml.html</title>
) |, G9 E0 F5 W/ s  </head> / e6 i3 [. `4 z/ I0 r
  <body>
, C6 ]; w* ~1 x  <canvas id="mycanvas" width="600px" height="600px"></canvas>8 r' d1 V; w( P

% [( p. \6 E6 Q/ S6 S9 m  </body>, `2 g) u2 W5 m- M7 h( G9 O
  <script type="text/javascript">6 p/ P% W0 u% n5 R' m
//自行添加上面代码
3 H5 l! }) N* ^) @4 I //    var mymap=new Array(36);$ o! b, N# }% Q: ~, S- N
//    for(var i=0;i<36;i++)& K7 F9 p; ~/ h+ ^4 r/ X
//    {mymap=-1;}
" V8 i9 `+ O  D function getnei(a)//获得邻居号  random- u& R& g! O# X
{
0 m$ ]% a% g# V       var x=parseInt(a/aa);//要精确成整数
4 S: M: G6 H7 ], z# Y4 [/ u% T       var y=a%aa;+ Q8 {8 ?3 N# g( |; s+ i/ |1 H. S
      var mynei=new Array();//储存邻居
( W8 [, S# R1 j4 A8 c. s       if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点% o* L$ C0 g/ F; o( A9 @3 B
      if(x+1<14){mynei.push((x+1)*aa+y);}//下节点% F8 {. A* B/ w% y* Y9 z9 }: U
      if(y+1<14){mynei.push(x*aa+y+1);}//有节点
# ]- F. Q) T( r2 C, y* e8 b$ l       if(y-1>=0){mynei.push(x*aa+y-1);}//下节点3 o; I' A- F: C8 S0 R  L
      var ran=parseInt(Math.random() * mynei.length );" U3 x% v. S1 m" U. O* k2 y. p" K
      return mynei[ran];$ s; t0 j$ |( k6 [7 O0 k

3 c9 M  I8 P+ V& n5 e }% L5 J$ C8 e( g8 J1 }- P
function search(a)//找到根节点
5 G, F* [5 b- r( [0 M# `! w {$ B8 `) s. e& r( ~- E! i
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
0 h  B$ }0 O4 U- B. x1 K       {0 k% m1 I4 v6 a) q2 C
         return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩
" [* _6 j$ F; B       }7 V$ Y3 b; g* y2 j" R
      else5 `) R6 W  X$ V3 J  g5 W& Q4 i
         return a;3 o7 L+ o8 E% r4 U1 g# \! _! O* H
}! x; {3 Z# _5 o
function value(a)//找到树的大小
! U# Y) T. \1 v! P4 W; x7 h {1 W3 g0 V! N1 z  ]# P* A
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
. p3 {, {( ]: q5 {5 q       {) b7 F; P7 A2 a5 e
         return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩
9 q! J- B- r3 I4 K       }
5 I# |* m& h" L' s$ _* _4 K$ }       else
8 L! ]5 L* _/ f3 H- @. n. l# b9 D          return -tree[parseInt(a/aa)][a%aa];: M4 {" @7 X- s: p
}
+ V' O. K5 ^1 V; L' e& } function union(a,b)//合并
; v7 D) v' f( {% T. K: w' w {/ D6 ?! Q% s$ Y+ k
      var a1=search(a);//a根) k: d/ _) b$ e7 }9 B- G$ J2 G" s
      var b1=search(b);//b根# T/ n2 I2 c# R
      if(a1==b1){}
$ h0 U9 w. ]4 |5 i( `+ q5 w       else
$ c4 z* V- [( {       {
: \+ J) H. \. \7 K- D0 ]! r$ {          if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数()，为了简单减少计算，不在调用value函数
/ Y, t4 U# n+ a' R* e, H          {5 Q! N1 e, M5 M+ \
            tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加  注意是负数相加) E2 e9 _: F' j5 }+ _3 g+ v. Y( U
            tree[parseInt(b1/aa)][b1%aa]=a1;    //b树成为a树的子树，b的根b1直接指向a；0 W: h! b: c" C/ E8 W* K
         }. O3 R$ L9 F5 C) z" b9 k+ a
         else
; C% l1 Q- \, `- g/ V          {) z0 T" [! r* B- r  U
            tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];
4 |( q0 f% @: q0 ]' U! e/ E4 r             tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树
! Y" K0 M2 l+ H4 l. e, |+ t          }
2 w1 Z$ M6 V* Q2 [       }$ m3 }$ G* @% r2 t
}% w4 A9 r2 @  u7 E1 p0 z
  k5 p, Z; Q" d: |4 N. R
function drawline(a,b)//划线，要判断是上下还是左右! }9 k7 z5 z# F' K2 R
{
6 B0 q" y: P: q: A* ^$ H, a( Y- c
1 w, ?) R5 Q0 ?' C5 p       var x1=parseInt(a/aa);9 n! V9 E. @; F5 L
      var y1=a%aa;
& |2 ^2 _% \" E+ b7 p; ?       var x2=parseInt(b/aa);
) p/ P$ \7 \5 g+ ?       var y2=b%aa;       ) c9 A' A% s- }) ]+ G
      var x3=(x1+x2)/2;6 F( z6 y8 w! K* v) ]6 v4 R7 d
      var y3=(y1+y2)/2;* g/ E( c8 k$ B0 ~
      if(x1-x2==1||x1-x2==-1)//左右方向的点  需要上下划线
8 {$ C0 h, z% M+ I       {9 M& e/ {0 |4 E, W' h8 z/ I( Y
         //alert(x1);
7 z6 _  L/ D, e! y4 T" w6 I- T          //  context.beginPath();
$ ], o/ R# G/ j5 i) x5 p2 x          context.strokeStyle = 'white';
1 p3 U6 a. O$ _9 K: N          // context.moveTo(30+x3*30,y3*30+15);//8 L5 }. R% _( L0 p
         // context.lineTo(30+x3*30,y3*30+45);8 I" N2 a6 q8 b
         context.clearRect(29+x3*30, y3*30+16,2,28);
# {) u2 [  P; Z: `2 R6 D8 X4 `          // context.stroke();
- ^' K- X! V- b2 N4 h) [/ X& t' \  H       }+ @' ^$ b) b, C, m7 m6 U- x
      else* R+ X: T: E" |# {
      {
/ T) J6 L" n! U4 W+ G9 E          // context.beginPath();/ v/ r( V, g+ T$ u! c  b
         context.strokeStyle = 'white';+ E3 H; p9 B; M5 D- \$ H' ~. E
         //  context.moveTo(x3*30+15,30+y3*30);//
/ v5 W6 b9 G) @# D; Q          // context.lineTo(45+x3*30,30+y3*30);/ E: X& M/ ?7 D
         context.clearRect(x3*30+16, 29+y3*30,28,2);
6 C' A$ W% ~8 q% `, B( P' V( ]! `          //    context.stroke();# q7 w0 b) n- Z3 K; W  f3 u7 Z
      }' E/ O4 g+ }- u6 }8 f
}
# E8 h: q! @! q, g0 T. C) \7 G( [" c- j& F; F7 t
while(search(0)!=search(aa*aa-1))//主要思路+ g6 |+ d+ }* ~4 @0 j) f2 B
{+ E5 [2 w$ }# V+ J! K! _% b7 |
      var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
+ B+ i; s6 x, E/ F& z, ?2 e. A  W       var neihbour=getnei(num);; y) ?3 X5 `/ s; P# M# t
      if(search(num)==search(neihbour)){continue;}
: S' D$ D3 p2 c' S       else//不在一个上
+ R/ V0 F: \& r0 K4 M       {' V5 m+ F. ^; Z; |, S5 p
         isling[num][neihbour]=1;isling[neihbour][num]=1;
6 P# H8 x8 H& _          drawline(num,neihbour);//划线
1 }; }3 l$ H- H- A# H0 t: \          union(num,neihbour);7 l8 b/ T* j& j" C- C! r

- o  G3 d2 e5 W8 G4 N" m1 L5 b       }( b, [& q% B# a4 [0 k0 N, [
}  m0 G5 D! p7 S0 L
  </script>
3 F$ ~4 E1 f; \& l</html>
3 A3 \/ A3 f7 D  y- n& P
9 @8 L3 N/ K7 C& z
. y/ x3 ]% z8 y. O/ U. F) J实现效果：
% N$ h0 \& ^) m+ ^0 O* W6 V" {/ z! v0 ]

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

. F4 L& T9 S4 u+ L( W. L# o$ g
% V+ P) s+ U. @3 j; S: Q

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

% L2 ^* `! m$ G/ F! S3 h7 m方块移动
( |' E$ j; o9 i7 [
* s4 U7 T% U1 a这部分我采用的方法不是动态真的移动，而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉，在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除，可以根据像素大小精准擦除。, X9 A" ?8 k$ T5 B

8 o3 I( v! v9 \" ^7 c+ S另外，再移动中要注意不能穿墙、越界。那么怎么判断呢？很好办，我们再前面会判断两个格子是否联通，如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组)% ^! s- w2 J6 l4 b: G# T0 e6 k9 h
6 J' [: Y5 G7 T
另外，事件的监听上下左右查一查就可以得到，添加按钮对一些事件监听，这些不是最主要的。
5 q% ?. H% f) J/ p; M! `5 |6 w% S+ n  d+ B8 _
为了丰富游戏可玩性，将方法封装，可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外，如果写成动态存库那就更好了。; F) `0 A) z( ]' o

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

2 Z4 Y& V7 M3 z- a% Q
3 w, }$ a, g" s2 _  d* I

# }% \7 l  E7 R9 S: c4 ~————————————————
/ P6 _/ n( ~( c1 K版权声明：本文为CSDN博主「Big sai」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。; B  k/ ^% r7 u: ~4 D: j0 B
原文链接：https://blog.csdn.net/qq_40693171/article/details/1007167662 B- m& ]' J# u

; F* j& N) t2 b, k, \; T! H$ i% Q% C: ^* ~$ L# @6 r9 ^$ `