查看: 2589|回复: 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* J( W9 h" Z4 N! O5 J
      for(var j=0;j<aa;j++){8 s+ L, g# T: [; m2 [. n
         tree[j]=-1;//初始值为0) `) C7 U2 x8 b
      }
5 I1 N, ^# M1 ~* C8 Q* S) T }  for(var i=0;i<aa*aa;i++){) `/ G& g$ n  D6 v( C; N$ R$ F
      isling=[];
6 ^$ w& ]  ~- x2 ]1 u; ~4 e1 K       for(var j=0;j<aa*aa;j++){
, k0 m6 c2 x9 ]2 e; ?( H          isling[j]=-1;//初始值为0
5 u: {: V) g1 d: y4 R! }       }
- A4 u" b9 ~" C }
) ~7 Q0 w( I! k9 B$ q# [/ K2 w7 C/ V, M. V. H
function drawChessBoard(){//绘画# Y/ h" w0 y7 T/ ~  \2 _
      for(var i=0;i<aa+1;i++){3 B2 |/ [: Z, o) ~# |
         context.strokeStyle='gray';//可选区域$ s+ c  e8 R5 D0 Y. t& U
         context.moveTo(15+i*30,15);//垂直方向画15根线，相距30px;
  o6 e0 N( {1 ~7 n( z$ _          context.lineTo(15+i*30,15+30*aa);7 H% H% G1 D' T1 y; l
         context.stroke();
2 o5 q# s! ]( Q; y- i          context.moveTo(15,15+i*30);//水平方向画15根线，相距30px;棋盘为14*14；, T# ~+ I, E. h3 O
         context.lineTo(15+30*aa,15+i*30);4 e2 W, K. e+ q
         context.stroke();
: u" a9 B* V9 p& a& r' ^7 p       }( q, F. A  W( p
}) a6 [- A1 k" [6 U
drawChessBoard();//绘制棋盘
( {5 _4 q% Q0 J/ L9 }1 o/ x: _$ M
//    var mymap=new Array(36);
5 y$ T  `0 T9 y8 C+ e3 T" }7 y! j //    for(var i=0;i<36;i++)) \( {" ^1 w' y+ `$ ~4 u. j6 d; G
//    {mymap=-1;}
" j. t; `( D; c0 f" U9 z- y) Y9 w/ k9 \% n8 ?5 C' f! S
" x; F0 K6 J; b1 V" i  c1 m( i
  </script>0 O, N- a! c& n  Q( @4 G3 f+ ^; }
</html>
1 [: R( p8 f/ l2 C* S) A: t7 T3 _* [) }. D/ J' \
* F) f! c1 a" e+ _) F1 g
实现效果% t% m* u& O4 D8 A. _

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

3 W9 y0 i& ?3 V0 {3 v

  _- A) B* g: q' X8 Q8 s* Z画迷宫7 h4 ~* y1 U: r' L* @4 ]3 t/ P
* b3 \& o+ l0 w; _' |
随机迷宫怎么生成？怎么搞？一脸懵逼。( V* X9 J2 ^, x" H
$ j: K+ a6 w/ D7 {  [7 d5 v
因为我们想要迷宫，那么就需要这个迷宫出口和入口有连通路径，你可能压根不知道迷宫改怎么生成，用的什么算法。小声BB：用并查集(不相交集合)。) Q5 ]/ X" I- f2 e
迷宫和不相交集合有什么联系呢？(规则)
5 Q/ o; f) n, `3 H$ |+ a8 b
$ b2 D- b9 J0 S" Z) q2 b7 x之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合)，它的主要功能是森林的合并，不联通的通过并查集能够快速将两个森林合并，并且能够快速查询两个节点是否在同一个森林中！9 _. [) u0 y* I# W: Q
而我们的随机迷宫：在每个方格都不联通的情况下，是一个棋盘方格，这也是它的初始状态。而这个节点可以跟邻居可能相连，也可能不相连。我们可以通过并查集实现。
. f+ }( J& j* Z8 c1 G! {- s0 e9 e  N' x
具体思路为：(主要理解并查集)
7 s9 [0 e; S6 ?
6 I: t& ~4 J" Z6 e3 |+ }1：定义好不想交集合的基本类和方法（search,union等）
6 m, E0 b% w$ ]2 X2：数组初始化，每一个数组元素都是一个集合，值为-1" i% n& B+ l6 p* Y
3：随机查找一个格子（一维数据要转换成二维，有点麻烦），在随机找一面墙（也就是找这个格子的上下左右），还要判断找的格子出没出界。3 E0 p% i5 G4 |
具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界
2 ~" ~7 d( |% R) m0 T: [4：判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在，则重新找，如果不在，那么把墙挖去! _) V7 a# i# W+ ]
5：把墙挖去有点繁琐，需要考虑奇偶判断它那种墙(上下还是左右，还要考虑位置)，然后擦掉。（根据数组转换成真实距离）。具体为找一个节点，根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。+ y3 m5 v# i7 h. V$ L" R  N
6：最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙，但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据，并查集操作。二维是位置。要搞懂转化！. [; I5 A' j# x7 f" T: b
注意：避免混淆，搞清数组的地址和逻辑矩阵位置。数组从0开始的，逻辑上你自己判断。别搞混淆！
6 u% I# {$ S* \5 s0 Q2 e

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

5 a; k% D4 D) `2 f
主要逻辑为：
( K& I4 M$ G; s4 ]0 {while(search(0)!=search(aa*aa-1))//主要思路  V$ o7 k, y( [# X6 Y3 J( E
{
9 W4 M, D/ s% p% T0 D       var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
9 x2 T/ p/ `0 _, b3 [+ D9 v       var neihbour=getnei(num);
% B/ F5 Y9 c' L       if(search(num)==search(neihbour)){continue;}; v' w3 D6 w6 Q7 L" u1 A. p
      else//不在一个上
8 Y2 I  w4 a8 w8 W7 k! D       {
/ y- m' p  t$ v/ E/ O5 [" h+ g# Q2 E          isling[num][neihbour]=1;isling[neihbour][num]=1;
: C6 O) N1 X( G0 j# q7 k; G          drawline(num,neihbour);//划线
. x/ {" S4 V+ s5 v1 ]& E, J7 v          union(num,neihbour);4 h1 Q1 w# K; B
, K$ j) K9 [' H9 ?7 N
      }0 x- g0 @+ G5 x  \
}
/ M# J7 a1 g1 v
. H! Q0 c  V+ z: j/ o
那么在前面的代码为
; B9 n: L2 A- m* y( g<!DOCTYPE html>
8 E* j9 J9 O: X3 I  y% L<html>
' @0 }, T/ Z3 w& @  <head>
6 j; {  g( q( {/ P7 L: `: I <title>MyHtml.html</title> ! `4 u# {" o8 K5 w3 R
  </head>
! w' a0 G3 x  ~' ^% l% r* s2 r. V8 D  <body>
5 X' H- {! ]9 r* U1 K# I  <canvas id="mycanvas" width="600px" height="600px"></canvas>5 [9 t$ y$ y6 ~( f$ _
& I' `6 W4 B5 H, r0 O5 o
  </body>4 H5 u- }) Z) d% M9 K+ n/ P
  <script type="text/javascript">
' k& Z+ d; j& v5 P% U0 v- u//自行添加上面代码" \5 S' X* W) T  ^/ r
//    var mymap=new Array(36);
3 Q! x; D! g+ z- e //    for(var i=0;i<36;i++)
" v1 {8 \' ^) o, I7 Z- b5 K% U( c+ X //    {mymap=-1;}! j7 H3 t! J6 O8 F! i) X" P/ i
function getnei(a)//获得邻居号  random2 Y3 O- I  o; o9 M& k$ e; R; j
{
$ U  w" P: h  _6 ^0 @       var x=parseInt(a/aa);//要精确成整数
7 S5 m- h9 p0 s. H3 ^% z       var y=a%aa;4 c3 W/ R; K( N  s4 g' ]) j! n- x
      var mynei=new Array();//储存邻居6 G8 ^+ ~. E7 w* N: Q, G! n) U
      if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点
8 P+ L+ f: W: T       if(x+1<14){mynei.push((x+1)*aa+y);}//下节点
: ?$ q/ `2 @  w5 M* _       if(y+1<14){mynei.push(x*aa+y+1);}//有节点# x# g$ @% F( Y
      if(y-1>=0){mynei.push(x*aa+y-1);}//下节点7 d& v$ ]: q  s1 U
      var ran=parseInt(Math.random() * mynei.length );* D6 t8 n# o( `- c/ `: j
      return mynei[ran];
# M% k8 h' |; w1 S) K$ V' E+ h& ]1 l& X# p( W/ h3 N
}/ \1 {! g+ T- ]  {4 h, y
function search(a)//找到根节点; U$ a/ T0 A4 I4 ^, I. B
{, G8 e; Y) L! _5 C- Y. |, z
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点5 I+ e& Z4 d" o# X
      {, k2 W2 k2 n" P) @
         return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩
) E6 P* _/ z. w       }
. k$ @+ W4 }: M. f" J3 y1 c! c       else
# ?- k( a- k4 _' A          return a;
% l  X5 s% Q& B2 o1 J }
1 l- k; S- m" u0 V# n/ ?) V- N function value(a)//找到树的大小
& I" h7 Z/ P: f" }" o& V7 K8 y; B {
2 a5 A' h4 s6 l7 }8 k" A! F       if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点8 I- j1 {( X$ U! |/ x! ?
      {
( Y7 y% K* E1 l4 j2 d' \2 `          return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩" L7 l& {/ Y2 s! \4 Q4 g7 D; c
      }$ D- o$ r2 `* L6 r. O  k
      else8 Y# j; l  y; J. {8 ]4 s! b) ?, i& I
         return -tree[parseInt(a/aa)][a%aa];
& v9 c# u  l( m6 E, ?4 n( | }' Z' t2 ]' u% b! {1 v) W
function union(a,b)//合并
3 k/ D% H2 M! _  h- s {# Q( d# ]- R- `( u0 \9 l/ K/ j
      var a1=search(a);//a根+ ?  q8 W3 z4 Q) l6 K( h
      var b1=search(b);//b根2 d  \/ n& e0 j: y7 G- B0 s
      if(a1==b1){}
. A' ?: G. R* R6 {       else
. x/ Z) d6 C3 o, @+ X9 ~8 z- t7 C: D       {
* Q& ]) q3 S1 r- c8 c          if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数()，为了简单减少计算，不在调用value函数
. x7 P! y$ m6 p6 k& g          {
# H  Z% R" t5 r( d$ o3 }( C             tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加  注意是负数相加
- S9 ?$ p$ \. p+ E9 d. M             tree[parseInt(b1/aa)][b1%aa]=a1;    //b树成为a树的子树，b的根b1直接指向a；
. M1 X+ f1 P# S          }
0 l! ]+ K& L( u1 J) t- F  M* d          else5 j( o0 M3 R+ [. a& {8 L
         {0 i! q# ?/ y9 ?4 v6 Q0 N  C/ b
            tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];
* K8 s- y, p) ~) v             tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树7 }0 t2 N5 `# `3 Y* Y
         }
* X8 x' B& o- _6 T  i       }
5 U: _8 g" c+ { }
/ J3 o! `' |4 q! d' U) O# ~, g: Z
% Q/ A7 N5 y4 Q. i function drawline(a,b)//划线，要判断是上下还是左右
, s) n& d0 h  x2 o, X {
) h% @' B1 @6 [  K4 B( s% r
& k3 D* R: h9 ~! i1 K% z9 E: G       var x1=parseInt(a/aa);5 F& x5 J; k% s+ _. c; @4 [
      var y1=a%aa;+ ?" n( ~+ V( Q; q6 m
      var x2=parseInt(b/aa);, O8 u, I* K+ d! a" I3 u( I, e0 ^
      var y2=b%aa;
/ H  |! d6 S* `, W" m# i5 W       var x3=(x1+x2)/2;: J! E3 ^8 [! F6 N! v9 R
      var y3=(y1+y2)/2;
$ E4 g% w& n1 }/ S: y6 B- m       if(x1-x2==1||x1-x2==-1)//左右方向的点  需要上下划线
: B2 o+ J% ^6 a  l( \; T       {
- @! w6 T* m2 j- r3 ~          //alert(x1);) @2 b  A! z* X# z* O' h
         //  context.beginPath();
9 }8 f9 a: u$ z! ^5 U) \/ L          context.strokeStyle = 'white';
' K( B1 o0 Z5 @' v7 q, ^' q          // context.moveTo(30+x3*30,y3*30+15);//
" _* W7 q; ]2 f          // context.lineTo(30+x3*30,y3*30+45);
6 ]- E, U* i+ K) J) m$ {          context.clearRect(29+x3*30, y3*30+16,2,28);* u" ~" N6 h( c: F3 S6 D2 v
         // context.stroke();: a4 o' J3 q6 B2 I
      }% ?  L4 P5 k# a
      else
. a4 K$ X( A+ Y* n9 u8 b       {! f, P& G$ |7 G' d4 a- e
         // context.beginPath();
4 J; X$ f4 K1 h) @          context.strokeStyle = 'white';, s' _4 x) `; r2 U, N2 x/ T, U4 K
         //  context.moveTo(x3*30+15,30+y3*30);//1 W/ n( I( w0 h" g# K; x" I
         // context.lineTo(45+x3*30,30+y3*30);$ K6 A& n2 Y) C. t
         context.clearRect(x3*30+16, 29+y3*30,28,2);
: x2 C# b' r% I( U9 D+ I5 k, }          //    context.stroke();! Z3 o; ~( K3 d" {6 V5 N, E/ p2 e
      }( H/ z  m5 w: Z$ N! |
}6 m: A; ?9 L0 J6 K4 J
6 @9 {; g& G7 G- ?5 G# e
while(search(0)!=search(aa*aa-1))//主要思路% i% O3 M& C6 |5 w9 R
{
6 Y$ A, j* @+ h3 Q+ w       var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数- W* L! @# l# B
      var neihbour=getnei(num);  _) U7 ]- B- n, n
      if(search(num)==search(neihbour)){continue;}  {- k2 ]% r9 m* e* F5 _
      else//不在一个上
' U4 |# h" n' J! ?3 @% l& i       {
7 p8 S# M4 n1 v6 Y7 |4 h# T          isling[num][neihbour]=1;isling[neihbour][num]=1;3 w/ \7 [3 M: e" |& F  Y: p
         drawline(num,neihbour);//划线
& [# [1 y1 V# a; e9 i% `          union(num,neihbour);* x2 H! r: }0 i# {# u

( t4 I4 F8 |4 f9 I! A; x       }
: p. V! ~% X, \- h }$ \4 @2 E3 A( b* }( [; M6 [0 d6 c
  </script>7 g2 D% c" t8 s% z" F
</html>4 t5 O9 ]9 E) I

9 \' b, D8 {% }, j  N% ^: u  M& G/ t1 v, j) l& Y- P$ G7 y, H
实现效果：* G) A: W+ W  T5 l/ z

' ]" @+ ~7 l* v  Z; v- _% ]

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

4 ~' ?  a1 I# i& a/ ]  ~* T2 L) W6 ~* n' q! `0 M

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

: x# x6 A1 m7 f& B: z7 ]
方块移动
% \8 H& |5 ~, r4 [! }* t7 J8 ^
* J) J6 z5 A/ h7 G- A这部分我采用的方法不是动态真的移动，而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉，在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除，可以根据像素大小精准擦除。3 y+ ?+ Q, P) G! P+ R

2 C! M8 l* b* O) C5 s2 @另外，再移动中要注意不能穿墙、越界。那么怎么判断呢？很好办，我们再前面会判断两个格子是否联通，如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组)6 h0 O# i8 o+ M1 t

" R; `- [! J$ _0 t另外，事件的监听上下左右查一查就可以得到，添加按钮对一些事件监听，这些不是最主要的。; x; p4 x1 T' b( P% p

* E% s$ O' C* P为了丰富游戏可玩性，将方法封装，可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外，如果写成动态存库那就更好了。
/ q( G: I/ F7 `1 n/ ~* {

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

4 n0 w6 O1 V2 n4 E
4 ~  r9 e; d: l2 `. L6 i/ y: H
( g& L0 g/ T, R; E) D————————————————, f6 Y  U% J, D: T
版权声明：本文为CSDN博主「Big sai」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。: q1 I8 H6 \1 X; V% b( b: [# t
原文链接：https://blog.csdn.net/qq_40693171/article/details/100716766. A: G+ d3 h; ?4 X  t5 p
* `. R7 G+ g9 F# E# G# X7 d4 Z: ^7 g
% T9 n0 `  _, j4 ~4 o6 Z% M