查看: 2585|回复: 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=[];% a$ P9 k' u; @' r$ H2 A" ^7 d
      for(var j=0;j<aa;j++){
9 y* o8 t' t* _' t$ i          tree[j]=-1;//初始值为0
5 I4 B3 R9 \' C5 y6 |       }' e; c/ ]( b$ o( ?* n7 ]
}  for(var i=0;i<aa*aa;i++){+ t; \7 T2 X  O- U
      isling=[];
7 Q) x, e& Q, T8 t' q       for(var j=0;j<aa*aa;j++){5 B  ]# F3 g7 I3 p$ }3 {
         isling[j]=-1;//初始值为01 b: {6 X' Q4 F# Z! A; O% J
      }" u( j/ o7 B( S# I7 m8 B  Z; F/ b( j' o
}
- W5 v. v7 t  u* Z) c& e* P! d. |0 `( P8 {$ n3 b
function drawChessBoard(){//绘画
$ W% T0 F2 n1 M2 F       for(var i=0;i<aa+1;i++){
$ e" K( D" i; A/ n8 Q* p% \5 v          context.strokeStyle='gray';//可选区域, ^( M- @$ K& _1 F. `/ {5 b
         context.moveTo(15+i*30,15);//垂直方向画15根线，相距30px;+ _, M: y: a* \) ^7 K4 K' ]
         context.lineTo(15+i*30,15+30*aa);
6 d7 Y5 c. c6 `6 x* f          context.stroke();
5 }2 r- r' F4 L$ O* u9 H          context.moveTo(15,15+i*30);//水平方向画15根线，相距30px;棋盘为14*14；% ]9 t) l4 N, v& q6 i
         context.lineTo(15+30*aa,15+i*30);
% _% M2 _% @# T' V          context.stroke();& J) v8 s; k8 D3 M4 t1 Q
      }+ A) Q* K) h* |( f
}8 X: u! H6 N' Z* X* N1 l
drawChessBoard();//绘制棋盘
; s9 C) \& `" O
' u$ Z% ~  V: } //    var mymap=new Array(36);4 b- r; Z7 }$ ?' H+ e
//    for(var i=0;i<36;i++)  @0 P! `. b8 k# F
//    {mymap=-1;}
5 L* n) a( u; z/ a  H8 q* Z
& ?5 z  f1 p2 z) y5 ^
& L  U2 G8 c- w, J  </script>
: u: r5 ^# Q1 `! L</html>2 a, ^$ Z5 |% K5 |8 ~. v( u

. }; O, F% _. [
5 o8 W7 S0 x0 X9 f( }实现效果
0 k  X9 f0 H, T' k* f

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

2 Q" m, m! @) L  F7 j
& s0 ^$ l) |2 R+ Y
画迷宫- o! {# x* H% n: M7 ^, p
* P& Z, h: o: W- H; n6 s8 D
随机迷宫怎么生成？怎么搞？一脸懵逼。
* @6 k$ I) u% b( C3 |& w8 v" r
因为我们想要迷宫，那么就需要这个迷宫出口和入口有连通路径，你可能压根不知道迷宫改怎么生成，用的什么算法。小声BB：用并查集(不相交集合)。1 ~* h2 G* {5 H
迷宫和不相交集合有什么联系呢？(规则)
+ N3 E; T( E8 U, n( u4 i: Y# @" _  R8 P' l
之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合)，它的主要功能是森林的合并，不联通的通过并查集能够快速将两个森林合并，并且能够快速查询两个节点是否在同一个森林中！
$ `1 x& ?5 o5 L3 u% {而我们的随机迷宫：在每个方格都不联通的情况下，是一个棋盘方格，这也是它的初始状态。而这个节点可以跟邻居可能相连，也可能不相连。我们可以通过并查集实现。0 R2 A5 s# b0 L+ s7 ]  Y% D1 K( U

; L/ h$ T5 q# d& g/ E; [' V具体思路为：(主要理解并查集)! K8 }/ ~. A$ h0 M
( [% x9 c! j- G% J3 m0 H  Y
1：定义好不想交集合的基本类和方法（search,union等）3 @8 F1 Q" }- {1 w) K
2：数组初始化，每一个数组元素都是一个集合，值为-1
. m4 u( d- S# Z4 u3 F5 O7 k# z, z; [3：随机查找一个格子（一维数据要转换成二维，有点麻烦），在随机找一面墙（也就是找这个格子的上下左右），还要判断找的格子出没出界。% W0 d, s& t; f! b$ @
具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界
: Y4 i6 X: S( p, U9 [2 D0 F1 B6 h4：判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在，则重新找，如果不在，那么把墙挖去4 ]: w7 s! q- ]3 T
5：把墙挖去有点繁琐，需要考虑奇偶判断它那种墙(上下还是左右，还要考虑位置)，然后擦掉。（根据数组转换成真实距离）。具体为找一个节点，根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。1 X  F" u9 S& |$ S7 P8 X5 s2 ^$ y
6：最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙，但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据，并查集操作。二维是位置。要搞懂转化！- y; G% s9 Y% I7 i
注意：避免混淆，搞清数组的地址和逻辑矩阵位置。数组从0开始的，逻辑上你自己判断。别搞混淆！* q9 ^7 Q5 H3 |( z

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

+ x' a6 b( o1 M: j( o主要逻辑为：
3 I: N6 Y% w8 d" O0 ywhile(search(0)!=search(aa*aa-1))//主要思路2 `. L8 D' y! `" ^5 p2 f+ y, z
{) y/ Y; S) g" ^: r( O, s$ K1 k7 d; X
      var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数; A4 x3 N; R1 C7 B
      var neihbour=getnei(num);
* g  V3 y1 f$ A% W       if(search(num)==search(neihbour)){continue;}8 k5 x7 `, J! D
      else//不在一个上: B* R* w" l8 T- s2 i# }- K; t
      {
6 }' e# v1 d+ n          isling[num][neihbour]=1;isling[neihbour][num]=1;5 k9 q( {% l+ u! j6 U/ x1 Z5 i- r- N
         drawline(num,neihbour);//划线7 K% G+ |9 `! U
         union(num,neihbour);4 K2 d7 v) U7 ?4 L/ H/ p
5 Y3 F6 ~1 b# z0 \+ d  v! J  f3 z5 ?
      }
1 Z4 z  H4 N! L" A. r }
4 v' I) a7 w# E) Z
* D3 G7 P" @6 {6 {' W. I9 f
2 _4 Z+ c" v1 k5 r3 ]6 o4 q那么在前面的代码为
# u9 f! X4 q+ r<!DOCTYPE html># M3 ~3 B% j3 I( u* E( u  [2 A
<html>
( r4 \6 x0 f6 {5 U9 f+ r% P3 x  <head>  C/ K' H3 F( ^4 U
<title>MyHtml.html</title>
" Q3 v) q9 n# E& t$ H: R4 j# G  </head> & g4 {7 I0 v9 k8 e5 T! C! u/ V- X* N
  <body>
" C- g/ r- X' m8 e9 k  <canvas id="mycanvas" width="600px" height="600px"></canvas>
; t& d' R' E) L& k& ~5 U% {1 _/ _* Y9 P" i2 V
  </body>3 r4 n! r" }0 I7 x( S4 a
  <script type="text/javascript">$ o# F0 A' ]  `+ Z2 G$ @' N
//自行添加上面代码
( W  ^) }9 [- N$ n% e+ |# W //    var mymap=new Array(36);' V2 h, k& n, f6 p9 f, W
//    for(var i=0;i<36;i++)
& i# i; T7 ~7 v+ O' m4 X //    {mymap=-1;}
( o8 _' L0 b! `+ i9 b! {. R+ N* U. D function getnei(a)//获得邻居号  random
: c& _$ o5 Q, v8 b {. k/ A+ _  n: s" u# L: X
      var x=parseInt(a/aa);//要精确成整数
! M& N( C- H8 k) V% @3 s, Z8 p       var y=a%aa;
* S9 P- P2 L( N$ H. j% p0 b       var mynei=new Array();//储存邻居
, A0 ~% W  M! ]8 E8 Z       if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点8 S" F/ f! _5 G
      if(x+1<14){mynei.push((x+1)*aa+y);}//下节点1 s% K$ ~, x5 }/ @8 G4 W
      if(y+1<14){mynei.push(x*aa+y+1);}//有节点: }) r6 e% t& w# U' X% z; ]+ p
      if(y-1>=0){mynei.push(x*aa+y-1);}//下节点
8 f7 J+ j, |# \5 w' q9 |       var ran=parseInt(Math.random() * mynei.length );
* E. u% ^7 m+ g       return mynei[ran];
# w0 i9 {  N  W  f  [6 j
! }% O9 A, i0 s9 T& _6 D5 M }5 B& x- `8 c6 f7 ^) l
function search(a)//找到根节点
4 f" k( Z1 v/ ^; W/ i) S {
3 b7 o( Z$ W8 e% B' e       if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
: t7 T# _7 m0 x# J  S. d  a; O       {: Y1 a. c) E- O& ^8 y9 \( l
         return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩
% J$ f) b: ?5 Y       }/ ^7 X' r. O- E; m
      else9 a- j' x# K+ W9 X3 L$ C( Y
         return a;  z9 F# n( _  U& t* U
}
: N4 g/ c+ P. y1 _$ B% ~ function value(a)//找到树的大小
9 r/ o2 E& q% S  r2 J8 V1 F: I {
3 j7 N3 s+ \; r! \       if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
' D3 _( d: T+ x2 S) W8 v       {! C# s& n. r2 W* }) _
         return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩# ^* y2 |5 o1 \( ~
      }
- [+ R8 p( i! o( c4 e; _2 u* C       else$ h: O! g' |+ t+ z, p. Q  u, M
         return -tree[parseInt(a/aa)][a%aa];5 }: z" d' O  r: t
}6 a% U1 t% h& F, m9 z5 X6 X
function union(a,b)//合并! _" j3 I. A1 D5 B
{% c5 W4 g5 h* X& X- l3 j+ s, S. |
      var a1=search(a);//a根
& I/ X3 }7 {! L" E* e       var b1=search(b);//b根
* y9 d8 E; O" Y. X       if(a1==b1){}
0 b$ c- W: A' z! D8 W& S/ X* F       else
  l1 _+ q/ e( j! Z. L       {: b2 n0 U5 r8 O( x6 q2 Z/ U4 Y
         if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数()，为了简单减少计算，不在调用value函数, \# F1 ~( M5 S( @( a4 V* P
         {  e+ b, ~- P% }5 R$ A4 `
            tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加  注意是负数相加7 m  b. X& X: ~& a6 M- m7 p  E
            tree[parseInt(b1/aa)][b1%aa]=a1;    //b树成为a树的子树，b的根b1直接指向a；
2 r: a% D8 ^4 _          }$ K) ~1 a5 S0 t
         else6 N) o  r/ b6 v( @1 ?5 {0 v: G
         {
8 N- B  L& W9 C* _             tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];
% G) D; s6 X0 e6 T- p/ h7 k5 L             tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树
7 T9 X3 N. K& @7 K- _* _          }4 s7 {( i: }$ h
      }' y8 U1 P+ a8 ]' `) |7 N
}
& w! T9 @0 }. u% W: x/ q% J3 d  B' k5 J& Y# }' r
function drawline(a,b)//划线，要判断是上下还是左右; s3 s  F! S# t, I8 G. e
{
4 X2 w  N$ f! @8 O6 j  f1 o2 i) m, g) D
      var x1=parseInt(a/aa);
: S/ j  q) u7 Q% \9 L  _       var y1=a%aa;) ~, J; [2 h/ ]. G
      var x2=parseInt(b/aa);6 z1 r) u; N" s, Z5 V8 e4 D1 X! [
      var y2=b%aa;
6 z3 J  P* m3 A! l8 r" B3 L       var x3=(x1+x2)/2;# H! }. d, d1 o3 E+ E* F: F
      var y3=(y1+y2)/2;
2 \9 A& C3 V" G" s4 Q/ F       if(x1-x2==1||x1-x2==-1)//左右方向的点  需要上下划线
6 Y; g1 p8 L- O9 G( D# P) c       {
4 b+ c3 H- z$ F; a          //alert(x1);
4 u2 Y% x* x0 b" l  M          //  context.beginPath();
, V5 ]0 |7 q* _          context.strokeStyle = 'white';' ?6 N$ r6 `1 S# S4 }
         // context.moveTo(30+x3*30,y3*30+15);//, |6 c: p5 y5 q* H. r" T
         // context.lineTo(30+x3*30,y3*30+45);
" Z3 O" t. U1 ~3 z: ~! h          context.clearRect(29+x3*30, y3*30+16,2,28);
+ u  z  k9 K' s& z          // context.stroke();
. v8 _  ]1 W$ I. c6 O+ f* B# O# l       }* ^3 K( V' @4 A" r1 X$ f
      else- }8 b* e" H) \4 G- D: v7 n
      {
. {' V0 \# w; X          // context.beginPath();
+ X; b1 M3 i& e          context.strokeStyle = 'white';
/ c* o$ v$ M; O; u5 r          //  context.moveTo(x3*30+15,30+y3*30);//
; S- E" s: s! B) Z& Z& O- [          // context.lineTo(45+x3*30,30+y3*30);8 k. d. z/ H7 U& K; k
         context.clearRect(x3*30+16, 29+y3*30,28,2);
, J. X7 r- X+ y: [) V          //    context.stroke();
0 y# G, `8 _0 j1 L* O4 |       }8 b8 a9 T/ M/ d. j
}
! u" u3 [- h" [; ]7 z
" T- r1 J: Z& Q% J- i+ e5 Y while(search(0)!=search(aa*aa-1))//主要思路! y3 i  J) r! x( S$ m- E
{
9 g& m. \- J0 U, E       var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数# N" S5 e# j! P- m; \8 l. q+ F( j8 S
      var neihbour=getnei(num);
1 S0 @1 n# E# Y9 }% U& C       if(search(num)==search(neihbour)){continue;}
/ ~" O$ x$ x* k& R. B1 d       else//不在一个上
! y4 Q2 a/ r: E4 O       {
6 |/ S3 ~5 j, T2 L# t          isling[num][neihbour]=1;isling[neihbour][num]=1;
/ L2 ~  Z! U: {- s" U          drawline(num,neihbour);//划线" G& J, `7 V& }1 C5 j/ b# q
         union(num,neihbour);! ^- `: ?$ ^$ u
. V; N' s' H! @" A$ B$ `3 I
      }
  p8 @+ }8 H9 A }5 ?3 ?- V* j6 n. z, N0 ]
  </script>0 J# v$ J% ~& c6 x
</html>& R* L1 i: m$ F" k3 a/ J! t

$ D0 k) ~8 B7 N" }% t' a
8 e. U: x5 @9 M' \6 _$ G实现效果：% v( Q8 g0 `, {. e7 J, A: h
3 e6 q/ B6 x. G8 b

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

7 s' [3 T- Y# F8 a0 c. ]5 \5 m7 i+ R! ^

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

* y& Q& _+ i- A% N* R; \5 Q) m
方块移动
9 {1 r7 O5 D7 F/ p% J, z+ M
这部分我采用的方法不是动态真的移动，而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉，在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除，可以根据像素大小精准擦除。
8 a6 }# q; k3 e7 l, X" e$ h8 a# t, e; K/ h* O: k* F/ b9 }$ Q
另外，再移动中要注意不能穿墙、越界。那么怎么判断呢？很好办，我们再前面会判断两个格子是否联通，如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组)& U8 U- b7 p2 U4 h# j7 U' N( A* A! f
( [8 `/ J+ [- q0 M# G. ~
另外，事件的监听上下左右查一查就可以得到，添加按钮对一些事件监听，这些不是最主要的。* L9 h8 y+ f$ R" v# C2 e

, w/ r) F  Q3 P' \& h为了丰富游戏可玩性，将方法封装，可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外，如果写成动态存库那就更好了。
. d: j, x/ Q: F+ N& d% o

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

' n8 ]6 y, U2 L' W; Y1 ~8 ^4 Z% f/ W
- @) @+ a  i2 h! k: O
. h- H7 G! ?2 Z, }6 j) ?8 Y————————————————
0 d6 I) n9 U& U4 d版权声明：本文为CSDN博主「Big sai」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
! C+ ]7 T$ A& A/ L4 ?' o4 y- P0 C原文链接：https://blog.csdn.net/qq_40693171/article/details/100716766+ M1 c* E# l" _

' U- M# n  Y& m! I' c& e% E3 t4 P4 ^2 z: ~3 y, `' T