查看: 2587|回复: 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=[];8 f5 D6 _, t) k: Y' h/ m" x$ a
      for(var j=0;j<aa;j++){9 Q" M% ]1 ^7 Z1 X. j) o
         tree[j]=-1;//初始值为0
, P& O8 g- w7 E       }: f& S4 ]; i! X: Y9 `/ C
}  for(var i=0;i<aa*aa;i++){" {$ k0 Z# C  ~  a
      isling=[];, y& w) n7 j# [, x9 F8 f/ T
      for(var j=0;j<aa*aa;j++){
; Z) T5 }* T7 c% S. [+ a          isling[j]=-1;//初始值为0" F3 Y; A& d9 V
      }
' k  q' o( H, ]8 i. u }
: E# c  l1 l+ c; W6 `% L/ z. d. h; D5 q" V* ~/ J! W
function drawChessBoard(){//绘画
% T' }3 v. o5 s- K       for(var i=0;i<aa+1;i++){
9 y3 |. v8 d) N1 y* C          context.strokeStyle='gray';//可选区域
  l6 S0 I2 m( z          context.moveTo(15+i*30,15);//垂直方向画15根线，相距30px;
, l0 y7 G4 F3 F8 Z          context.lineTo(15+i*30,15+30*aa);2 v, [8 ?0 R9 z7 @4 q
         context.stroke();1 p6 A+ p& u! T% g4 Q2 @6 T) X
         context.moveTo(15,15+i*30);//水平方向画15根线，相距30px;棋盘为14*14；' p/ T/ }5 E9 m
         context.lineTo(15+30*aa,15+i*30);; P. E! J$ n  |1 f
         context.stroke();* _& i9 J# v. H' ^8 ~
      }
: T% H- c) F  s$ q" b! y }
/ p" o) b$ U3 ~/ H# f( X drawChessBoard();//绘制棋盘* p* |; V( R3 g5 {
+ g3 ~2 R: J' p5 A) ]
//    var mymap=new Array(36);2 P' r$ J! ]  t( W. I$ \
//    for(var i=0;i<36;i++), [0 {9 l( u% K( m6 F6 `
//    {mymap=-1;}
5 j) G# R( P9 l! c# a" g" i. c: M8 O) u+ x7 Q7 J
* L& H1 w  J" k# t
  </script>
- I* V) s/ r. _, E% E</html>- l6 ]4 M& }  b' I& m
9 ^9 Q  f8 W& S/ w6 q
6 @( \" a0 Z, d! v3 ]( {" G
实现效果8 ]! c. k$ Z3 k" z9 \" F. {+ e

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

0 A4 E: n6 `, ?9 t1 [  ~
% P9 [3 n0 g4 t! w  _, k* ]画迷宫
, T0 s& J0 o) Z2 D. Z! X& w* H. z
随机迷宫怎么生成？怎么搞？一脸懵逼。7 b" t( c* U9 p: x, F, |% O

) c9 [2 Q' Z: H5 @因为我们想要迷宫，那么就需要这个迷宫出口和入口有连通路径，你可能压根不知道迷宫改怎么生成，用的什么算法。小声BB：用并查集(不相交集合)。
$ D! s- ^3 T+ J5 ?; x) I迷宫和不相交集合有什么联系呢？(规则); ^0 k: Q8 y/ ~; f) u/ S

$ E* a& k. D4 _之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合)，它的主要功能是森林的合并，不联通的通过并查集能够快速将两个森林合并，并且能够快速查询两个节点是否在同一个森林中！
" v( L/ p/ g8 l3 i9 O. s  S% }1 e而我们的随机迷宫：在每个方格都不联通的情况下，是一个棋盘方格，这也是它的初始状态。而这个节点可以跟邻居可能相连，也可能不相连。我们可以通过并查集实现。
& w) o9 A" \6 X$ @9 u; A
  e# _" X" b6 m4 ]6 G. P/ r具体思路为：(主要理解并查集)
0 @0 @' ^% K$ G$ f1 U0 b& R. R' @. S. s5 w; Q
1：定义好不想交集合的基本类和方法（search,union等）( W$ H# ^, `$ w. `8 |) g
2：数组初始化，每一个数组元素都是一个集合，值为-1- `% j# t6 ?# R2 M) q& e. L" O
3：随机查找一个格子（一维数据要转换成二维，有点麻烦），在随机找一面墙（也就是找这个格子的上下左右），还要判断找的格子出没出界。, j! j7 D! @8 w9 e
具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界
5 P" l$ C# R# k5 j. K9 D0 I4：判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在，则重新找，如果不在，那么把墙挖去* s$ \3 Z! O+ Z" ?* C4 A
5：把墙挖去有点繁琐，需要考虑奇偶判断它那种墙(上下还是左右，还要考虑位置)，然后擦掉。（根据数组转换成真实距离）。具体为找一个节点，根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。& p+ u3 F" ?6 [6 G
6：最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙，但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据，并查集操作。二维是位置。要搞懂转化！: E" Y0 q9 {5 m# O9 j0 Y
注意：避免混淆，搞清数组的地址和逻辑矩阵位置。数组从0开始的，逻辑上你自己判断。别搞混淆！- y0 p2 c/ K' v* }6 a' ^' K

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

) k& I4 J7 B: p& n主要逻辑为：
0 e4 B1 D* G! ?8 u+ Swhile(search(0)!=search(aa*aa-1))//主要思路
, V( i' u# k; P& k0 j {2 b8 B. U4 |. \7 `. Y3 U0 Q
      var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数. a* d" e) b: H
      var neihbour=getnei(num);
; r. i# G  ?. }4 e" L       if(search(num)==search(neihbour)){continue;}
7 E# \" m  l% |6 L       else//不在一个上
9 c/ k9 \. `1 {' }" X7 R       {9 ^- j( _5 x- A( h
         isling[num][neihbour]=1;isling[neihbour][num]=1;' A& o! v0 i4 `: W/ ?. {& p
         drawline(num,neihbour);//划线* d4 H! Y7 K1 ^
         union(num,neihbour);
$ z3 z/ G& s5 I2 ]% o/ q1 z+ X6 k! k  u1 [4 C7 V4 k
      }
- I* S: B: y3 K$ i4 s2 i5 } }3 A# `) v  q7 [. e
( r, Q6 {) T9 X/ s4 f
- f3 u& }4 ~: \
那么在前面的代码为, c2 o% E) k0 S# ?9 c( o4 c7 u
<!DOCTYPE html>
- ~, G$ M! p% Z<html>" y: L. m2 y) }6 W4 W% I3 t8 }0 d: l' ?
  <head>
: \3 L& q& n1 N <title>MyHtml.html</title>
; ]3 X2 k) P" D$ q1 L# L  </head> ; [! O. C* x; c  q
  <body>
! l3 t# R: x% W( f1 P: Z5 f  <canvas id="mycanvas" width="600px" height="600px"></canvas>* A3 I4 r1 R, P' P: X" N
) c( |9 i: K% ]2 K
  </body>( q' k. @9 i# h- e+ W
  <script type="text/javascript">
( z; C6 g6 C/ s- Q/ K/ o//自行添加上面代码
! N% r  C; ]. ]  X& b3 u //    var mymap=new Array(36);
% ?) i3 r' d% d2 u //    for(var i=0;i<36;i++)
" l  |' K* o3 ?. Y2 W //    {mymap=-1;}
4 ^, f1 m# w/ h$ d7 Q* { function getnei(a)//获得邻居号  random
9 H8 f6 ]# F! y7 G) q3 p( i5 ^ {' C* A) R4 H5 h
      var x=parseInt(a/aa);//要精确成整数
4 w3 l8 k' r' p       var y=a%aa;0 C: v, c+ k  I4 r
      var mynei=new Array();//储存邻居/ I6 c$ t3 E$ A2 L2 a! ^1 D% S
      if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点, I9 A) r+ O* I+ u- U2 \
      if(x+1<14){mynei.push((x+1)*aa+y);}//下节点
0 u; X" @  v8 W" T9 I       if(y+1<14){mynei.push(x*aa+y+1);}//有节点  q4 G! p/ `! H7 h
      if(y-1>=0){mynei.push(x*aa+y-1);}//下节点& @% c# D0 f. ^7 L# y7 ?
      var ran=parseInt(Math.random() * mynei.length );- V& X/ Y7 [9 ^: g" M) f
      return mynei[ran];/ c0 c# g0 I- e5 ]
! P9 r; K, @0 e; h# F, a0 L
}$ d  d, V& F6 j# K% y
function search(a)//找到根节点* n! T; `3 u) i, I! p
{( w8 f0 W) F6 J& W+ i/ U
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点7 ^. H# t" L+ C0 y7 B
      {7 Z% }: v- L) G5 N) o6 S+ C
         return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩) z. }; o* R6 ]
      }
2 b: @2 }0 X% j# d/ K) ]) O       else
- P$ b; Y3 q- Z! h0 T          return a;
! \' X, }# g% V* s, J* ^ }
; l+ t: z3 n" J function value(a)//找到树的大小
1 T& C( Z! ^1 ?# [ {
. I7 \* U: x) J! Q7 d       if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点; f8 E7 y" E8 m3 |5 I" [
      {
0 J4 D" `" I$ }  _( l4 y4 [0 T          return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩/ H# A) z( }/ w& ?2 R
      }
0 _; m4 v+ Z; R) [/ d/ `       else
5 Z3 o% j2 R! T* F+ o! K          return -tree[parseInt(a/aa)][a%aa];
/ v/ t& d2 \# z# b }
, L' e, t) W+ w7 s5 L! H; |9 J function union(a,b)//合并
' N$ R; {7 f* q: g9 C! | {
" D  j9 L* t  n3 m! q1 U       var a1=search(a);//a根
2 T- {% V9 ^# p4 W1 [+ R+ q, y2 }       var b1=search(b);//b根
* v6 e0 _0 n* s7 s( ^; @* \       if(a1==b1){}
4 J- d$ J) G3 A1 p$ G% W/ v: w       else* P4 a% G3 k' O: Y- x
      {
# s8 p2 [2 R3 \0 I: d          if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数()，为了简单减少计算，不在调用value函数8 k# R2 `* Y* u
         {( ~7 z4 U" F* C$ x
            tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加  注意是负数相加* _8 b8 c: p  r' s
            tree[parseInt(b1/aa)][b1%aa]=a1;    //b树成为a树的子树，b的根b1直接指向a；5 b" J( p7 H) p- f$ c% X: P; J
         }
: }, r3 Q! n7 b. {9 L0 m          else
; ?8 U( h' x5 x" t          {* z+ F* e% r6 i+ i9 n  h" ?0 e
            tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];
- a* Z$ |6 X8 N7 N+ Q3 Y             tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树
* H7 O! O. [# j: I- S; {# s3 t          }
5 M  d" w  O# U9 `$ f  q* u( @       }( A, t. `: T% L
}8 c# q/ V# t* X5 _# e4 W
% B$ m4 d1 T, e+ P- g$ q* p
function drawline(a,b)//划线，要判断是上下还是左右( u" `/ ^2 C0 {- D
{
+ W2 }$ `7 _" \) |% `! Z/ H7 Y5 `) ^% x  @& q/ L! G* n; K
      var x1=parseInt(a/aa);: c! W( a# ^) {# D1 K* l9 E. `
      var y1=a%aa;4 ]9 K* C' \+ V* K1 T. }( `* e
      var x2=parseInt(b/aa);; T8 S/ G; i& K( d. r  Y* j
      var y2=b%aa;       % i; y3 u3 ?6 \3 Y% J! i6 i
      var x3=(x1+x2)/2;
' X, @6 {1 V$ _       var y3=(y1+y2)/2;) q* o, J6 }2 E8 D2 ^
      if(x1-x2==1||x1-x2==-1)//左右方向的点  需要上下划线
7 p9 a1 |& i( T2 |' x0 m+ n! n) a$ b       {
6 {4 B. R$ k+ s0 n          //alert(x1);
3 C& w( l, \7 v& |  V# J+ V          //  context.beginPath();
& L( Q9 Y; ^; c0 B0 j  R          context.strokeStyle = 'white';
* S3 x7 d! C' M8 C* @          // context.moveTo(30+x3*30,y3*30+15);//
/ f. b6 I  W& y1 R) [1 x9 q          // context.lineTo(30+x3*30,y3*30+45);4 d! K4 f! A# I
         context.clearRect(29+x3*30, y3*30+16,2,28);
% `7 Z7 U! R* x; L( K0 q% V          // context.stroke();$ v8 F  w+ X" k, m" h. L/ C
      }
  N, x! X( S* r: u* y       else! E' Y( W: D& `* C" a9 X- x+ a! T. `
      {
1 X& m7 @5 E: z          // context.beginPath();
         context.strokeStyle = 'white';! m+ B" g2 l, Q& D& V
         //  context.moveTo(x3*30+15,30+y3*30);//7 B1 B- L% T0 c, J8 J
         // context.lineTo(45+x3*30,30+y3*30);
' A, F6 o2 ?3 |: I( g) f          context.clearRect(x3*30+16, 29+y3*30,28,2);8 D& L1 ^: |: O: @) L6 c# ^! o
         //    context.stroke();
  d$ B% G/ C1 L       }8 a. g) J2 [5 Z8 f3 ~
}  q6 F& T6 r4 m; h
  h$ u) z: ^2 W8 D3 I0 Y% R
while(search(0)!=search(aa*aa-1))//主要思路
3 H4 a9 ^4 N9 F! s" p  h: M  A {: X! M3 K7 q0 r8 e! {6 h) e& x
      var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数0 z7 C8 H# _8 g
      var neihbour=getnei(num);3 @' T1 l' F& F- i4 g
      if(search(num)==search(neihbour)){continue;}* b7 a  u4 u7 W2 a
      else//不在一个上6 f1 v- W3 q1 D
      {. F& G, P9 `+ Y* p' }0 p
         isling[num][neihbour]=1;isling[neihbour][num]=1;
. A3 c6 z5 u7 \+ ~, N          drawline(num,neihbour);//划线% d8 [4 Y1 |! x! c! V6 _
         union(num,neihbour);
) R% ?6 B$ f; Q' d$ V* c+ J; f" s& N  B* g# \9 ]
      }; K' X0 I8 e& |$ |* m# K% f) f$ I
}
& W4 e: z0 {6 z! y3 A; i) w* s  </script>7 t7 a0 ]6 ]7 r& ^% E, V4 O+ m+ W8 S
</html>) j* d# E2 u% A$ Q$ V. u, @0 F

- Z4 {8 s0 ]* F: a5 q+ V0 B' m9 M2 [1 B
实现效果：6 `9 K1 o% p# ~0 r# W

, S) q, J( x2 b2 X- b

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

9 q9 i  f- x7 p4 @7 y, R# B3 \0 x7 i( [

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

$ h! ~3 C9 W8 s6 R% r1 c1 y
方块移动
* J: r! E/ q; j8 c, E" O' s5 H6 h* e6 b. R2 f# _
这部分我采用的方法不是动态真的移动，而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉，在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除，可以根据像素大小精准擦除。
3 ]- ~) W/ D$ P  _2 K1 D/ E9 P9 s8 j! j$ Q6 \( t& [
另外，再移动中要注意不能穿墙、越界。那么怎么判断呢？很好办，我们再前面会判断两个格子是否联通，如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组)4 @* o5 I6 B, Q
. `( r+ r8 F5 h  [8 O
另外，事件的监听上下左右查一查就可以得到，添加按钮对一些事件监听，这些不是最主要的。
) e3 P, R# ]9 d# c
: e6 }6 z- q+ ?! X1 K3 ^为了丰富游戏可玩性，将方法封装，可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外，如果写成动态存库那就更好了。9 {7 k' M- {; M* h0 z  W

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

1 p* s5 a; j8 I( d# K6 a! Q

5 t* C- S3 n/ l
! ~$ [+ A/ y) `+ B————————————————
5 `0 Y" p7 z3 e5 W版权声明：本文为CSDN博主「Big sai」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。: u# d4 r6 o7 d# O  @5 z" x, x: w
原文链接：https://blog.csdn.net/qq_40693171/article/details/100716766
8 X/ j2 B, n7 Q! N) q# i  P
3 R0 o/ @6 j' T9 H3 ?: S' B+ }
. @2 K5 s0 l! W* o2 [. B) W6 e) H