查看: 2610|回复: 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=[];
: n/ i$ `5 W/ {  l; v       for(var j=0;j<aa;j++){
" y8 ^2 L1 w" B$ ]5 I0 J; @! N          tree[j]=-1;//初始值为0$ _1 z. c$ E9 a7 P: H5 V! @
      }' ]3 Q$ |1 S- J
}  for(var i=0;i<aa*aa;i++){8 y- I4 U+ c, O; I
      isling=[];
( [3 z7 n! a- q& \9 R4 }       for(var j=0;j<aa*aa;j++){6 X. D6 W# f" b2 k' |$ c7 j
         isling[j]=-1;//初始值为0
/ y5 o! f* _& w7 k& m1 Q7 g       }9 `  l! h; F+ S; l
}' A6 k4 f( O$ t2 q

/ H4 h1 z6 I0 O3 U" ~" z2 L function drawChessBoard(){//绘画
. V7 N, @% L& B! {; }% ^4 e       for(var i=0;i<aa+1;i++){
6 t" k6 K5 S, l          context.strokeStyle='gray';//可选区域
+ L# V# N6 E! C          context.moveTo(15+i*30,15);//垂直方向画15根线，相距30px;
$ D! _5 N, ]9 Y( Y          context.lineTo(15+i*30,15+30*aa);
0 |+ |, b7 a- g% D2 L; r  I          context.stroke();8 z% \8 o# A7 `2 b. a
         context.moveTo(15,15+i*30);//水平方向画15根线，相距30px;棋盘为14*14；4 V& V& o. T8 |7 ]% B! ]
         context.lineTo(15+30*aa,15+i*30);
8 N- u  m- K! ^5 N: n# O0 O/ H          context.stroke();
. q3 D& x# f1 L2 P, o% \1 S  J       }7 t% j  L9 R" |# {
}! @4 N  W  s3 Y4 d0 E0 A* F
drawChessBoard();//绘制棋盘
$ s1 |8 r. v/ l# v. i' l" P$ U1 }5 _* e) Y. ^- O
//    var mymap=new Array(36);
0 X, m6 E0 U( k% t //    for(var i=0;i<36;i++)1 ?' r0 h6 Q3 A3 E# ~& {" Z( O
//    {mymap=-1;}
4 X1 m! f3 C+ V4 W& h3 ^5 P( K; p
- j7 }; s, ~& X7 f1 |! z) t2 q2 g0 R
  </script>
% c( ]' m' N. q2 n7 B5 b</html>
0 P# W# Y6 m% v% ^/ H* j6 T! U7 W; m6 \. h! R- Q
3 V2 _) A' k9 a; U% m, j+ V
实现效果$ A3 q- l2 Z' r0 n

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

& K  X- I( T8 I9 j6 J8 G

6 J- q; |$ \) _, \5 t+ @+ `( ^画迷宫
9 X1 e" J& @3 ^4 |! N* V$ ^4 X4 {$ M, p+ _$ i
随机迷宫怎么生成？怎么搞？一脸懵逼。, v* [% {# N, m4 R% `- U
# K; v. m/ s9 C8 {$ D( e0 ~. g
因为我们想要迷宫，那么就需要这个迷宫出口和入口有连通路径，你可能压根不知道迷宫改怎么生成，用的什么算法。小声BB：用并查集(不相交集合)。3 q% O( y  r2 R9 f6 G
迷宫和不相交集合有什么联系呢？(规则): K) x% _8 {+ ]  f+ l. R* x

% b3 F0 p. I! [# |之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合)，它的主要功能是森林的合并，不联通的通过并查集能够快速将两个森林合并，并且能够快速查询两个节点是否在同一个森林中！3 u0 m+ z+ d: Q' Z1 t6 L" y
而我们的随机迷宫：在每个方格都不联通的情况下，是一个棋盘方格，这也是它的初始状态。而这个节点可以跟邻居可能相连，也可能不相连。我们可以通过并查集实现。9 n: c, _% k( u: i
. x5 R) @" }) ^$ U: K0 e
具体思路为：(主要理解并查集)
, k' c9 i# A, k1 F; T
! ?. ~$ n6 K+ C, T1：定义好不想交集合的基本类和方法（search,union等）7 l2 U- H4 P" r- h% v) J
2：数组初始化，每一个数组元素都是一个集合，值为-13 U( N$ m) d! ]* o3 p& V% d$ s3 ]) Y
3：随机查找一个格子（一维数据要转换成二维，有点麻烦），在随机找一面墙（也就是找这个格子的上下左右），还要判断找的格子出没出界。
+ n! x. Z, q& E( M具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界
& X1 k3 w, |* B4：判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在，则重新找，如果不在，那么把墙挖去
2 B1 \8 \3 [0 L1 ~4 l/ D' B5：把墙挖去有点繁琐，需要考虑奇偶判断它那种墙(上下还是左右，还要考虑位置)，然后擦掉。（根据数组转换成真实距离）。具体为找一个节点，根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。
; K' q1 x2 Q$ s6：最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙，但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据，并查集操作。二维是位置。要搞懂转化！) r3 G& ?1 ^* u  J6 z# i5 C
注意：避免混淆，搞清数组的地址和逻辑矩阵位置。数组从0开始的，逻辑上你自己判断。别搞混淆！
/ r4 e) p2 r$ h$ m

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

" ]/ |" W, g( s* u8 x" v( v
主要逻辑为：
* k; P; f$ r, _; u5 dwhile(search(0)!=search(aa*aa-1))//主要思路
( ?7 d" u/ A. _. D {
' [! q; F# d# `       var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
2 j# F/ U! ~1 }4 ^# i       var neihbour=getnei(num);
8 L# U3 y  O5 Q( R1 h       if(search(num)==search(neihbour)){continue;}/ Y( I$ S# K7 t5 n% ~
      else//不在一个上6 N" \3 j7 A5 m+ S6 O! l
      {$ h# l, |' W1 t9 o6 ]& p
         isling[num][neihbour]=1;isling[neihbour][num]=1;+ k. i9 k( E4 a' I# z* u0 A
         drawline(num,neihbour);//划线
- s5 M. W* p. T* C, b          union(num,neihbour);0 R0 K; k9 `0 Y. t+ `
( n- k: e7 a- }
      }
0 y: C2 R+ i) {# l }
: j+ E% w1 O# L' w4 s& `, q# \; C( I6 f: _- a

* y# }/ L/ c; ]0 |6 K* G那么在前面的代码为" j2 O% K- v/ z8 e! ~6 Z6 E( c
<!DOCTYPE html>: \/ N$ m( }* k
<html>+ b. p0 D; @6 H  a" h
  <head>
' i- H7 p8 w9 w( F/ s' s( a2 a <title>MyHtml.html</title> # {: [1 J5 b2 }2 ~* W
  </head> ! E$ O7 ~# v7 V' N" z7 P+ v
  <body>
: n7 y1 p2 c' ?  <canvas id="mycanvas" width="600px" height="600px"></canvas>* p! l: j, q( Z) i9 s3 H& a

! F+ D) f2 V$ s1 l3 B8 B9 P  </body>
9 O. X( E0 b3 ^! t7 }  <script type="text/javascript">
0 R  C" {3 ]" e. V, ^" d//自行添加上面代码- z. T0 }6 N* N. e$ X8 [
//    var mymap=new Array(36);& t9 j( v: C/ e- Z8 o" F# o2 @5 L
//    for(var i=0;i<36;i++)
. ?4 Z8 J* ~7 y$ u+ ?1 g //    {mymap=-1;}
3 I! {; L! n# m4 U; A, z$ o+ J function getnei(a)//获得邻居号  random
7 T6 T4 L8 z3 h/ E/ A' _& C1 ~ {; S# ^* H' e  l9 p
      var x=parseInt(a/aa);//要精确成整数  a& ]7 y; H( ~6 L2 j, `
      var y=a%aa;
, s1 E* S. l9 c% o/ a       var mynei=new Array();//储存邻居& R4 x/ K( c, R
      if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点
; }1 t+ A' G" g$ L  W3 v- Q4 d' O       if(x+1<14){mynei.push((x+1)*aa+y);}//下节点% _! Q( T+ ?; c4 f3 X6 N
      if(y+1<14){mynei.push(x*aa+y+1);}//有节点
3 _* E2 Z2 E8 y' z, ~& V       if(y-1>=0){mynei.push(x*aa+y-1);}//下节点
# ?4 M$ G$ x3 @. P       var ran=parseInt(Math.random() * mynei.length );: z* s' F$ {9 L* j2 |2 @. [5 {
      return mynei[ran];
0 r: y$ C3 e' T( V4 V/ F9 N' T3 A4 |4 U+ U
}
# T. ~( X& C8 s9 Z+ Q function search(a)//找到根节点# P# s; V( o- T+ Q. W( d
{9 K& f1 I( K; J& p; _+ u) \
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点, N8 |" l; M, K" a1 m# |7 F8 w
      {) g# t, s7 H2 y. H( k0 D' r
         return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩6 u+ t: R" U  r6 s, J
      }2 `* _6 [) ?* S1 d) S
      else
- n8 d/ a/ B; q) Q/ j* D+ _6 Q7 ?          return a;
! o6 f. ]  e2 @' r% V) i( C }
/ a, i  S/ F! r8 M, G function value(a)//找到树的大小
" U5 y4 R& G9 P" v& j {5 M5 D, c' J" r7 D! C
      if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点& ?. W% ?6 X- H7 K6 |% T: x- W* D
      {6 h) m. [4 }, z( }" c* m3 L
         return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩
" O/ u9 y; j$ p3 Q       }
7 _5 S6 _  b% f4 e3 W! ?       else: i  ?8 @5 T! g/ M5 j' y$ |
         return -tree[parseInt(a/aa)][a%aa];1 x) T! F% x" B' S! x
}: d" q5 p8 v( O- L/ @
function union(a,b)//合并
- r& f0 @% @' C  F {' ~5 ]  E+ U7 g5 K- i/ ?( n7 C4 t
      var a1=search(a);//a根
" \% O; ]: r8 V: m$ s       var b1=search(b);//b根6 O; A) j5 T* i
      if(a1==b1){}3 \# B+ I4 w# Z/ D
      else
- ?6 a8 H& U# _: N. w0 ~       {; L. f1 A7 M& S# R
         if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数()，为了简单减少计算，不在调用value函数
; ]5 s4 y+ \, Y, T; s* t          {( n$ E; n+ S6 o, z/ n5 X# y# v/ q/ ]1 a! W
            tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加  注意是负数相加
- o$ n5 C/ H( k             tree[parseInt(b1/aa)][b1%aa]=a1;    //b树成为a树的子树，b的根b1直接指向a；
4 C4 O& H; X0 n0 k          }5 x. y; G6 ^1 j$ w, |3 d0 P
         else4 G. }6 a! w9 r8 N7 ?% g3 l
         {; }# |: e* ?4 F
            tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];
6 W8 [  q1 G) X  {, k2 A             tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树. l) `. ]+ J3 c, B
         }
- y5 e/ P8 K) }7 ?& _+ X9 `       }* A- B- [4 T8 }, i
}
, F- q& K& Q! J  ~1 B
8 J9 a0 t, e1 `) m function drawline(a,b)//划线，要判断是上下还是左右
' M) N2 U. Z9 Z5 d1 i( E. H {
+ Z) S) K& P, g; G
* b8 r) u+ ]2 R       var x1=parseInt(a/aa);
' N( S( Y3 b6 g1 {       var y1=a%aa;7 f, F  ?. ~& W" h$ e1 i
      var x2=parseInt(b/aa);* @. I: s  a; ^3 l! r+ e- z
      var y2=b%aa;       , Z- ?% H0 i2 {7 T0 l$ H/ m) u# i
      var x3=(x1+x2)/2;
* U9 O( Y, B. g, O       var y3=(y1+y2)/2;/ u% {9 P- F2 a, k3 |0 {' T
      if(x1-x2==1||x1-x2==-1)//左右方向的点  需要上下划线
! W) J( `( B( k. Y! ~* @       {
. }- v8 z; T# o$ K  u+ y          //alert(x1);
" G* A: r  X$ _6 c$ Z9 j: O1 u          //  context.beginPath();8 F2 F1 \+ A) b7 Z  f
         context.strokeStyle = 'white';
" s0 M: H7 n* O# f* `2 J          // context.moveTo(30+x3*30,y3*30+15);//7 j' ?! V* L2 _& [( z* I. Y- D
         // context.lineTo(30+x3*30,y3*30+45);
1 o5 e  S  j! V& }- j+ ?          context.clearRect(29+x3*30, y3*30+16,2,28);
9 G1 s" q2 w: U  \          // context.stroke();- o9 w0 W5 l( _5 N8 d
      }
$ s$ R3 J9 y5 R: d5 t( D6 v       else, W8 z* C1 l2 c0 B
      {
; k. V6 {- N# T* j: I% O          // context.beginPath();
8 d; F' |/ y* ]) ]: P, z6 C          context.strokeStyle = 'white';  K/ s" ?. |  m& g. @
         //  context.moveTo(x3*30+15,30+y3*30);//
; c- O) [* w( t( @* ]          // context.lineTo(45+x3*30,30+y3*30);
( o0 H# ~* s; j, [          context.clearRect(x3*30+16, 29+y3*30,28,2);# ^8 w. H1 P9 ~+ W
         //    context.stroke();7 y6 v# Y2 ]% P% u$ X5 m6 A
      }
3 V: Y8 F/ u; R4 ~; _ }( t, c1 u5 M$ T
/ H6 H! p) `: Y6 K
while(search(0)!=search(aa*aa-1))//主要思路. M# |; ^6 n/ Y5 d; _* D
{0 S  |/ _3 q" t/ c9 D3 e$ w" D
      var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数! ?9 Q) Q3 j* Q3 N' C, g8 _5 y3 k( b
      var neihbour=getnei(num);$ ~1 {, ^$ X+ Z' D; Z
      if(search(num)==search(neihbour)){continue;}8 t% i  d3 l; u8 U1 J9 N) X
      else//不在一个上
2 q, ~( k8 j) |- c& E4 b' Z       {
) |/ [5 f) e& H          isling[num][neihbour]=1;isling[neihbour][num]=1;3 s& ]$ N# N" v% C
         drawline(num,neihbour);//划线
' n9 {( J# [1 x$ L          union(num,neihbour);
: |, F9 {7 v& A
& p" B3 x, Q3 I3 t       }
8 {( Q& d$ i; c( W' k& J }2 l% g3 m$ W' f  Q' C( H2 _
  </script>
" L8 I6 H# e1 R2 _( z</html>+ L) c( \5 x& d6 E

' o0 r0 m6 s# q# w4 w# @- J# j/ Y5 Z# u. G+ I0 S
实现效果：' ]! b3 ?! g- X. G) `

6 y7 v) L, s1 C" ~

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

4 S0 @2 `: \$ X
% f9 Y8 h) L  t; F' h3 P0 O9 Z

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

+ H- Z, N" R3 I9 e; y
方块移动) z% j2 r& b# n! w6 V: Y
+ y$ I- L6 }( r& h/ F& g( G
这部分我采用的方法不是动态真的移动，而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉，在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除，可以根据像素大小精准擦除。
8 g9 H8 v2 y! Y4 e$ F7 [/ g1 \, ?' h: ?/ t+ p% {
另外，再移动中要注意不能穿墙、越界。那么怎么判断呢？很好办，我们再前面会判断两个格子是否联通，如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组): a  J9 m: Q+ H6 C- b' s

: K8 Z; H1 \7 `: G另外，事件的监听上下左右查一查就可以得到，添加按钮对一些事件监听，这些不是最主要的。
& E- A6 U: n" z
1 Q& j2 {- I' e2 a3 c+ s' ~为了丰富游戏可玩性，将方法封装，可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外，如果写成动态存库那就更好了。6 f( g2 B0 d1 M: o; g

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

. b5 {; Y; l  q" C5 Y+ L3 U
3 ]: h0 R: m1 m$ e
# ^* f1 L( V+ x) p. V9 U/ M
————————————————
. z3 ^6 D- e6 _$ [& b0 S$ \8 o8 l版权声明：本文为CSDN博主「Big sai」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
8 @0 x' F* R. E+ n1 ^+ T9 |原文链接：https://blog.csdn.net/qq_40693171/article/details/1007167662 x1 d2 R2 I- S0 `2 X
- J. k  u! H" R: x. Y
3 [% z& c- c3 V. A