查看: 2549|回复: 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" Y7 h: y6 Z$ b
      for(var j=0;j<aa;j++){) I$ o4 ^/ n3 e& @; `
         tree[j]=-1;//初始值为0
5 I. v$ L: i7 p, {       }6 b: L6 Z- P4 B' H
}  for(var i=0;i<aa*aa;i++){% X$ R/ q- w. x7 v9 j5 a# J& @
      isling=[];
% q: A" q# z$ @- H' e( ~5 {       for(var j=0;j<aa*aa;j++){# S5 Z6 V5 b: Y& a' a
         isling[j]=-1;//初始值为0
: \" D$ c% e" c4 @- ^       }5 M' y& }9 ?/ x
}
& o3 m5 z' D: G8 R. U. E$ g
7 Z: d5 Z" U* p2 Y& q9 y function drawChessBoard(){//绘画
: {. N8 h3 W0 o( i$ p       for(var i=0;i<aa+1;i++){4 X5 Z" P$ R) X! h# r& P2 ]
         context.strokeStyle='gray';//可选区域
$ J' W) w  |8 F* w# q! h( d# S          context.moveTo(15+i*30,15);//垂直方向画15根线，相距30px;9 X1 }  |1 D# t' p5 d
         context.lineTo(15+i*30,15+30*aa);5 y2 z2 R# `$ u2 c
         context.stroke();7 }! ]* |( K( j+ W; d
         context.moveTo(15,15+i*30);//水平方向画15根线，相距30px;棋盘为14*14；( G4 n9 l" g5 J3 [0 i
         context.lineTo(15+30*aa,15+i*30);
$ C; |5 Z, I! ]( \% C          context.stroke();1 h7 b- K  Y! K$ z; _$ N3 _
      }7 d) l: o: a: s% ~  e* h( o- [
}
3 c5 ]" U" u" e- N4 e* I drawChessBoard();//绘制棋盘
* Z& v7 A/ i6 r# H. _9 {
5 J- P1 @+ v) B! D //    var mymap=new Array(36);
9 _0 Q( u) z9 { //    for(var i=0;i<36;i++)
4 o7 L' L5 J' n$ x* Z //    {mymap=-1;}
, P0 h( d, l3 a+ \8 B* }
, D0 q6 [9 y1 L5 @6 I* ^+ m2 a( C) @, Z$ a$ [4 s! u
  </script>
' \, Y9 E4 c* g3 e; d; z</html>
/ p  E$ ^# W/ U' A2 n; h# w( B; U2 ?3 M
6 y& r! e; `; g4 Y- u% c
实现效果
; `, R. T6 b" e+ ^: E. N! `3 T+ |- F6 J

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

2 k5 V8 F3 _# L8 L3 x# ~/ L  G& L0 n4 y0 f) `4 _
画迷宫# ?: n3 D. o  x! \) k7 ~
; {1 x+ [  F4 D
随机迷宫怎么生成？怎么搞？一脸懵逼。8 k  y: K$ W5 p, M8 A# M

$ a6 n! `+ @$ `因为我们想要迷宫，那么就需要这个迷宫出口和入口有连通路径，你可能压根不知道迷宫改怎么生成，用的什么算法。小声BB：用并查集(不相交集合)。
! T. ~; T* A; F  a迷宫和不相交集合有什么联系呢？(规则)
0 s) x6 x. i1 T: ^" l; S9 T
" m7 k7 R6 ]" e" B4 _8 Y& [! J6 _之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合)，它的主要功能是森林的合并，不联通的通过并查集能够快速将两个森林合并，并且能够快速查询两个节点是否在同一个森林中！$ m' x! t3 {/ {/ v3 |6 _- P. G% X4 a
而我们的随机迷宫：在每个方格都不联通的情况下，是一个棋盘方格，这也是它的初始状态。而这个节点可以跟邻居可能相连，也可能不相连。我们可以通过并查集实现。
& p% C' L+ o- z! f' ?7 g/ R* B0 {1 b8 u$ ~5 |; d$ {% z; w
具体思路为：(主要理解并查集)
. n0 R) ?+ E3 ]/ Z2 a
; i; O# [- H$ [1：定义好不想交集合的基本类和方法（search,union等）3 a' I/ h7 R) o9 w( ?1 E7 c: c& a
2：数组初始化，每一个数组元素都是一个集合，值为-1
, o9 ?1 W0 _( t" Q1 r1 ~# H3：随机查找一个格子（一维数据要转换成二维，有点麻烦），在随机找一面墙（也就是找这个格子的上下左右），还要判断找的格子出没出界。
) f7 ?% Y0 v6 @- M5 h" t具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界' j" x2 t" G  o3 b% n
4：判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在，则重新找，如果不在，那么把墙挖去
$ v  \- c/ \) G" w5：把墙挖去有点繁琐，需要考虑奇偶判断它那种墙(上下还是左右，还要考虑位置)，然后擦掉。（根据数组转换成真实距离）。具体为找一个节点，根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。2 B' |0 q: i3 S- Q- U
6：最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙，但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据，并查集操作。二维是位置。要搞懂转化！( P, V! W1 k  w- N" j: ~! q5 V
注意：避免混淆，搞清数组的地址和逻辑矩阵位置。数组从0开始的，逻辑上你自己判断。别搞混淆！
, G* b' A5 H* }* U

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

$ c0 V* V. k/ [0 J( d4 M主要逻辑为：
while(search(0)!=search(aa*aa-1))//主要思路
" l) G6 |$ X& r {% p5 u$ _0 Z; l& b
      var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
$ l# R* x1 O, J* l2 \       var neihbour=getnei(num);. W/ V: @- i4 k% V" L# A/ e
      if(search(num)==search(neihbour)){continue;}5 c& Z1 z( ^9 j
      else//不在一个上
' ~+ c3 `! A2 O: H9 s( [       {! F. Q% Z! l# l0 ^1 v% @
         isling[num][neihbour]=1;isling[neihbour][num]=1;1 a. `/ l: A0 s4 e- A
         drawline(num,neihbour);//划线9 g+ B4 Y9 b' p7 I( E  A
         union(num,neihbour);
* D# v; g, h3 P$ j) k
8 c* s6 |. O; N& t" n1 i       }
2 ^3 ?) M8 k6 e9 h9 ^ }- `+ x7 E2 r5 v) |1 w( F# H

* {4 O2 M/ v! n( v) v9 b8 P8 _( p1 y( P& [' J+ W1 i5 f
那么在前面的代码为- B% D* g" P9 }+ s8 a
<!DOCTYPE html>
9 a' l, l0 ]# y- N<html>
; }; [$ ]* G. \& e5 u5 j  <head>) x4 T, T* ^+ d# U8 I
<title>MyHtml.html</title> 0 h- e1 t4 z" y- R) V* _. t
  </head>   F, G4 }" Z, [& `( ]  M, l
  <body>% n' B8 t1 x* q, a# N
  <canvas id="mycanvas" width="600px" height="600px"></canvas>  [/ O8 `; x; Z4 `! Z

- v; @) v0 {5 s. v( {% E  </body>
/ o- b8 i* h/ w4 l1 \4 e6 G' k: F* y  <script type="text/javascript">% y% m( a3 k" f9 g$ V0 p& B% B4 U
//自行添加上面代码( W) U! o% \' {3 r  B
//    var mymap=new Array(36);  Y9 |9 ]' C$ w( o' d
//    for(var i=0;i<36;i++)
, F" V# T2 S) T5 X" D //    {mymap=-1;}
0 n" \* R" M' F) M! {! x function getnei(a)//获得邻居号  random+ c: @" ?; c- n2 @4 {) }! K5 @4 I# J. V
{3 R) Q% P* [' T* @* u. r7 J, y
      var x=parseInt(a/aa);//要精确成整数# _7 N! h) i4 P1 T) h6 d
      var y=a%aa;0 x+ B7 a1 b  e; T' }; c) m
      var mynei=new Array();//储存邻居+ C* N4 {$ @9 W" q, r2 V9 @
      if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点
# a: ?3 j( K+ U7 n5 G; e1 a3 W       if(x+1<14){mynei.push((x+1)*aa+y);}//下节点
+ A: d4 m" Y/ G6 p7 C! R       if(y+1<14){mynei.push(x*aa+y+1);}//有节点
# G- N. r% w8 A! }4 t       if(y-1>=0){mynei.push(x*aa+y-1);}//下节点8 Z4 x* u+ d* D% |, K
      var ran=parseInt(Math.random() * mynei.length );
7 ^- e5 F5 _' r$ L  {- K! O% Y       return mynei[ran];
9 O9 c7 k; J+ ?( h" y' \* ]+ G; P% \
}
" o5 j0 b; @5 |* K function search(a)//找到根节点  \  G2 y- O: E* `
{2 r1 p5 K7 f) B% b/ Y' S, V
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
+ J; n! e: Q% D       {
+ j6 Y( ?% m% K) d          return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩$ v# r% I( J* d$ y
      }5 x$ x: _% u' K8 m) Q
      else
: t" E3 k6 [6 t          return a;3 V( i9 S/ p2 I' S( o. s
}
; t  v2 u: e7 U4 a function value(a)//找到树的大小' q6 e9 k5 k4 ^; m3 G0 s
{3 @8 T: L$ M) j# E7 P3 W: L
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点7 K1 G; F/ U$ |. l
      {% g4 J" Y  E' L0 a
         return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩
/ V5 E1 W5 q4 A. p! s" z) O       }8 F9 R, U+ D' W% r6 L! H
      else
. M; b, r' c3 v# a          return -tree[parseInt(a/aa)][a%aa];: G, y7 r/ d. X; x0 f2 E- V
}
" k, W9 e' ^/ ]" } function union(a,b)//合并; s1 \2 o8 n1 [. P8 ]1 T1 {
{* S3 C! A/ c9 [2 O; m- N8 R& C
      var a1=search(a);//a根/ l/ ~1 ]; B  ?1 q& _5 G# u/ i
      var b1=search(b);//b根
0 A: j% |# Y# e6 a3 G: X+ k6 x1 x! t- P       if(a1==b1){}; _7 W" e9 Z' Y
      else) o# H  k. ?; T
      {
% Y4 w9 ]% A4 U& L3 ]          if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数()，为了简单减少计算，不在调用value函数" Y; {* Z4 u" _
         {* E5 ]( G: ]; g' b: F
            tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加  注意是负数相加% _( {) \" Z1 q3 e  l
            tree[parseInt(b1/aa)][b1%aa]=a1;    //b树成为a树的子树，b的根b1直接指向a；$ U. C6 b, l, \, _6 ?4 f% Q* U
         }( P( q4 t3 c% K; y7 S$ R: D
         else
4 U1 Z. y$ d5 l  S6 p          {' ^& I0 T% b% A, T
            tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];
: D' S) e; y4 G" z             tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树
, \, d/ O. f( Y  m+ T  U          }9 u( M+ }2 ?! T  D
      }1 z& d; X' H! N0 a
}
6 {2 }* Y* r& n; O
8 Y2 T. N, h4 A! h9 @/ _- z function drawline(a,b)//划线，要判断是上下还是左右
& i1 l. F: f+ H' _# v" E+ h {# F7 T/ k6 D8 ^* p* E

' j7 l9 I  Q7 i2 ]$ a5 f' y       var x1=parseInt(a/aa);
7 R* }/ E& n/ R8 c       var y1=a%aa;+ v3 k- }2 T$ `0 a( `* q" O- ?
      var x2=parseInt(b/aa);) l7 ?, i/ v! e' E
      var y2=b%aa;
+ [0 R& a% w3 N- g" D: w9 {       var x3=(x1+x2)/2;- k! r& E' w7 x# ]* i
      var y3=(y1+y2)/2;! f. [# [/ u# U! l
      if(x1-x2==1||x1-x2==-1)//左右方向的点  需要上下划线  t( I! W9 {  n: D. b
      {
. Y( s" n, x; G6 f& h          //alert(x1);
# |3 E. \; ]2 l7 O          //  context.beginPath();
* u7 a0 w0 R9 i  g+ l* ]4 J7 e          context.strokeStyle = 'white';
0 G: W+ g; j# [: i. L" b; R          // context.moveTo(30+x3*30,y3*30+15);//& h; t& J: r. Z+ t" l
         // context.lineTo(30+x3*30,y3*30+45);8 p+ c, s6 I- l$ w
         context.clearRect(29+x3*30, y3*30+16,2,28);  v9 ^/ M/ Q% R& _
         // context.stroke();
1 a  b' d9 [0 n5 n) `4 q       }
5 }/ U$ ^1 |" F5 g+ A       else
/ I5 A, ~1 Q3 i( B5 S% g       {* O$ X3 e/ u4 O; e$ X5 u; @
         // context.beginPath();
( f. _$ c" X+ b$ F3 B          context.strokeStyle = 'white';: p% t5 \- I0 H- z7 ^
         //  context.moveTo(x3*30+15,30+y3*30);//
* R: B) B8 D" @9 K          // context.lineTo(45+x3*30,30+y3*30);
7 R) E3 B0 S2 _" t5 d7 \/ c. B          context.clearRect(x3*30+16, 29+y3*30,28,2);
, d; ]! H3 h6 `9 h          //    context.stroke();7 M( f/ N% e2 H$ b. F( v
      }
. F5 A9 L8 K$ K }1 }! [" ^( J! a+ `) _
# ~: @3 F  s; m7 G1 K0 b
while(search(0)!=search(aa*aa-1))//主要思路9 P1 M& y. }5 j% m' B( J2 w
{
) J/ K) R- T- n+ V4 f       var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
$ v0 C& L. I! a2 Y' M3 r" E       var neihbour=getnei(num);. @" v) ~! w4 h  h8 U: p7 V+ o5 \
      if(search(num)==search(neihbour)){continue;}! N& x$ O! J1 @3 `
      else//不在一个上) {3 {' G: ?+ |! w& G! v
      {
5 @8 n- X: o) b( P' b) x+ L          isling[num][neihbour]=1;isling[neihbour][num]=1;
! s& j& @  |8 Z6 K- H! F* i          drawline(num,neihbour);//划线
' B! J# e% v" t. v* `8 Q& ^          union(num,neihbour);
5 s4 t0 S: f2 {. H3 M" y  H0 Z# F
      }
/ d) X/ i0 r% l0 d$ e }. {# H% Q+ y) O. l- B7 f& ^; `% C
  </script>% @: H; _% x+ H- o2 ?0 H
</html>* F+ ~$ P( @: U% T

8 Z9 ?4 o7 I& L& W/ @* S8 R6 \4 \  r1 P
实现效果：
, h: ?+ i9 u! B6 E
9 Z  a* F- t! v+ d0 [

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

/ K2 K8 M) X' p0 E# y6 u
$ f7 [6 y5 X. M) p' r- s

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

4 n4 \# Y3 p' F: X, E" ]方块移动! h/ N( L5 c# M; r5 l
7 K5 G+ |: Z0 C' a! |. E6 ?7 A
这部分我采用的方法不是动态真的移动，而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉，在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除，可以根据像素大小精准擦除。
, i# Y) o( y- z! w" V8 s2 B+ u$ E! p) W; n/ ?) I
另外，再移动中要注意不能穿墙、越界。那么怎么判断呢？很好办，我们再前面会判断两个格子是否联通，如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组)
- ^1 b- D$ K0 D4 C( s" G; c& g& Z/ V0 E
另外，事件的监听上下左右查一查就可以得到，添加按钮对一些事件监听，这些不是最主要的。( w$ L: d, E4 I9 n) L; \  r+ v9 l' t
3 S, U4 J9 F; u& R
为了丰富游戏可玩性，将方法封装，可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外，如果写成动态存库那就更好了。
$ O; g3 \/ \6 j

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

4 V# Q! m$ f( Z6 A, x
9 g& B- ]6 X! S& \
' m4 A' l6 s" p9 l7 ~  n
————————————————2 j1 A1 j4 |1 R$ b
版权声明：本文为CSDN博主「Big sai」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。7 P, w8 w6 @2 x+ P$ s
原文链接：https://blog.csdn.net/qq_40693171/article/details/100716766$ P, w* O4 n, C0 B* Y

* `/ s7 J+ H: p% d0 A
/ Q6 u2 e8 ^- p0 Q! J1 W; ?