- 在线时间
- 1630 小时
- 最后登录
- 2024-1-29
- 注册时间
- 2017-5-16
- 听众数
- 82
- 收听数
- 1
- 能力
- 120 分
- 体力
- 565553 点
- 威望
- 12 点
- 阅读权限
- 255
- 积分
- 174889
- 相册
- 1
- 日志
- 0
- 记录
- 0
- 帖子
- 5313
- 主题
- 5273
- 精华
- 3
- 分享
- 0
- 好友
- 163
TA的每日心情 | 开心 2021-8-11 17:59 |
|---|
签到天数: 17 天 [LV.4]偶尔看看III 网络挑战赛参赛者 网络挑战赛参赛者 - 自我介绍
- 本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。
 群组: 2018美赛大象算法课程 群组: 2018美赛护航培训课程 群组: 2019年 数学中国站长建 群组: 2019年数据分析师课程 群组: 2018年大象老师国赛优 |
6 I/ R5 A: n) x9 a我花了一夜用数据结构给女朋友写个H5走迷宫游戏
" D- i' o A. ]5 l" L3 }8 w6 ~文章目录
/ e, I0 f; A( y
% [ I- ~! [# L4 O' F+ \# w* V起因
- {, o3 v$ i) M6 J3 `0 Q3 D分析
( R3 c, W: y4 c/ R4 N* E! @画线(棋盘)* x1 B% n) `3 L" j- p
画迷宫
* Z3 y9 ?' [9 o& ^/ Y! p) o3 N6 v方块移动* L1 k" G9 u8 F/ [5 f- |
结语
0 T/ V* F H6 t) M先看效果图(在线电脑尝试地址http://biggsai.com/maze.html):' L a; p: W1 B/ h' q. G
( c& b. W" b: F( z# V( z
9 Q* L1 y, e4 t/ y3 J9 Y; H起因
& V( k& B( f5 X" E; _' d
5 R+ k1 R2 k% O1 Q
: v* x/ B5 k: o! e又到深夜了,我按照以往在公众号写着数据结构!这占用了我大量的时间!我的超越妹妹严重缺乏陪伴而 怨气满满!
, n! e7 b; ~" a) w" j
0 X( y* d/ t2 `# Z: H超越妹妹时常埋怨,认为数据结构这么抽象难懂的东西没啥作用,常会问道:天天写这玩意,有啥作用。而我答道:能干事情多了,比如写个小游戏啥的!2 _+ m2 Y. i, k3 m+ t) V
# {2 ~5 j. X, I( h* C
当我码完字准备睡觉时:写不好别睡觉!+ u, t( G7 Z8 }8 M- s; {
- Z8 K, z& L! j2 t
, f' |& O9 b% k& Q, |分析6 F9 Y5 Z( p# A
- Z7 t: ^: }0 @- |
如果用数据结构与算法造出东西来呢?5 d' k' l4 E4 K: ~# N" q
5 `9 j4 S" [8 s1 u* f什么东西简单容易呢?我百度一下,我靠,这个鸟游戏原来不好搞啊,得接触一堆不熟悉的东西,搞不来搞不来。7 i4 l1 U; ~' w3 W
有了(灵光一闪),写个猜数字游戏,问他加减乘除等于几。7 |; [% K1 |( P6 r
* [2 y$ E" o+ L) e超越妹妹又不是小孩子,糊弄不过去。% m( I$ m( M. v% C$ A4 R( h: ~
经过一番折腾,终于在半夜12点确定写迷宫小游戏了。大概弄清楚其中的几个步骤。. v/ Z$ g$ B/ l) X5 h
( s" y3 q" |. R4 y3 @
大概是:8 T# v& V* L/ t! U y
$ E! b6 n+ E: N" G9 J画线—>画迷宫(擦线)—>方块移动、移动约束(不出界不穿墙)—>完成游戏。* n. e0 d# ~) F( R- d( `
画线(棋盘)
6 R4 ^7 u- E1 i! O5 h
/ v" V, e3 k" K( u, h6 m6 p6 X对于html+js(canvas)画的东西,之前学过javaswing应该有点映像。在html中有个canvas 的画布,可以在上面画一些东西和声明一些监听(键盘监听)。
) F7 W, C- J7 \4 w; _
5 z- v! Y( a" u: b对于迷宫来说,那些线条是没有属性的,只有位置x,y,你操作这个画布时候,可能和我们习惯的面相对象思维不一样。所以,在你设计的线或者点的时候,记得那个点、线在什么位置,在后续划线还是擦线还是移动的时候根据这个位置进行操作。8 s2 c, [. |' a5 O' T* Z1 {
<!DOCTYPE html>
! I0 m O2 p6 {7 n& c<html>, `- K4 v1 f c+ D, h4 ~
<head>$ Q: O6 S8 C0 ?) P5 }6 U/ v
<title>MyHtml.html</title>
, B! {; ]+ z- z# v* v7 T7 j </head>
, [7 p3 p: D, A/ [7 f% Y; r <body>
% B+ @4 ^/ F. ]- ] <canvas id="mycanvas" width="600px" height="600px"></canvas>
0 ~# E3 r6 O$ f+ y8 ]) b7 C- A# ~9 }6 r' b: Y* D
</body>
/ Y0 m% i& D' F9 m; g <script type="text/javascript">
7 N: U/ B8 M& s3 J9 ~9 M2 P
) R" r. b( K- kvar aa=14;
0 D- H# P# |/ _! S9 d. n var chess = document.getElementById("mycanvas");. \& R; W, Z9 P5 t
var context = chess.getContext('2d');) E( O# a/ \- ] Q3 J, h+ U4 v9 s
& r; x/ r. C. R* X- g/ W8 [+ U
// var context2 = chess.getContext('2d');
( c0 f, v* s! w7 I: B1 w // context.strokeStyle = 'yellow';- I+ N9 O2 q' H ]3 l
var tree = [];//存放是否联通 }- C7 r, a$ ^) _6 a9 m5 i
var isling=[];//判断是否相连
) j' f+ x d4 ~) n R for(var i=0;i<aa;i++){9 b# }0 _( I L* m: ]' q
tree=[];( `# [1 ~, X, D. T" y, B7 @$ }% L
for(var j=0;j<aa;j++){
# }4 c3 N8 e; ?- |! I0 t tree[j]=-1;//初始值为02 g- W9 E! v8 o4 T
}( b# ^2 ^( r1 ^! c8 n
} for(var i=0;i<aa*aa;i++){
& W/ Y1 T0 s( U) x+ x isling=[];
- h* C. y6 O; ?) d2 P for(var j=0;j<aa*aa;j++){ d# l+ i1 W! A: t" g
isling[j]=-1;//初始值为0
6 M5 ?7 z, Q% q/ z, n1 K }7 T. W: o @6 L
}, [2 p8 s: E2 w( F" X7 C
6 }# l# I0 V% P7 b9 {+ F
function drawChessBoard(){//绘画3 Y/ g. H8 e: N D
for(var i=0;i<aa+1;i++){; c6 E5 z) z( P& r8 [# X/ \9 d
context.strokeStyle='gray';//可选区域! P3 C- Z3 D5 ^1 H, Q$ @
context.moveTo(15+i*30,15);//垂直方向画15根线,相距30px;
$ C1 k- y+ f3 f) t" } context.lineTo(15+i*30,15+30*aa);
" K& V6 J ]( ~! V6 v+ [ context.stroke();9 \7 k/ X$ E: M( k* ]5 K
context.moveTo(15,15+i*30);//水平方向画15根线,相距30px;棋盘为14*14;
0 P$ a& U0 ?" G( j4 F0 Y context.lineTo(15+30*aa,15+i*30);
; Y$ F7 G6 y3 M! Q% T$ V* y context.stroke();
2 I: V2 Z0 G8 F! T }' v6 K+ P7 ]; S7 j! [8 L) ~8 ^
}
, U) d( n. n" F( \ J" b: L+ n drawChessBoard();//绘制棋盘5 V( V( b0 z0 U
2 Q6 l$ ~3 Y+ u: f. V) Z- q% `3 w' o
// var mymap=new Array(36);! T* [& a9 p7 z
// for(var i=0;i<36;i++)
6 V: R+ h; W1 B0 [0 R: J6 Z( T // {mymap=-1;}! N5 u# A4 }/ a
% M; r7 g# n; J# x1 f6 i6 O
% P. Y$ K" f2 B) z9 O L7 z </script>& x i9 s9 B7 m/ f) m% s( b/ R
</html>
7 F v% {# U8 {! q \
8 a7 p, F: M- u) N4 w" L, @
, I: r3 W2 a/ P实现效果
! ]( g+ t0 Z& I
8 G$ V9 d" P& L, Z8 y
5 x% V8 K4 H7 @) S画迷宫8 m: w9 \# `1 u. r; X! f$ @
8 b2 x) b, Y: p! @随机迷宫怎么生成?怎么搞?一脸懵逼。5 y; D: h) f2 l+ j
/ ?! F! r* Z( Y5 t, M
因为我们想要迷宫,那么就需要这个迷宫出口和入口有连通路径,你可能压根不知道迷宫改怎么生成,用的什么算法。小声BB:用并查集(不相交集合)。
0 U1 i0 d1 ^, @6 L8 x3 y迷宫和不相交集合有什么联系呢?(规则)
5 ~. u9 @0 g4 U3 }; m$ i: X9 S
* \" p( q, W6 p0 H* v* c之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合),它的主要功能是森林的合并,不联通的通过并查集能够快速将两个森林合并,并且能够快速查询两个节点是否在同一个森林中!& I! Y5 B6 I$ W2 h
而我们的随机迷宫:在每个方格都不联通的情况下,是一个棋盘方格,这也是它的初始状态。而这个节点可以跟邻居可能相连,也可能不相连。我们可以通过并查集实现。
7 b; ~) f. H1 ^- ^6 [* H8 B; l: j% [/ O4 p9 ^" T
具体思路为:(主要理解并查集)
* l7 h6 c$ D: W) K) j' `- {% \& q7 g K: C6 ^5 }7 b G! n
1:定义好不想交集合的基本类和方法(search,union等)
3 I8 C: N3 A- Z X2:数组初始化,每一个数组元素都是一个集合,值为-16 y' D# n; [9 a6 [9 M5 n5 A: `
3:随机查找一个格子(一维数据要转换成二维,有点麻烦),在随机找一面墙(也就是找这个格子的上下左右),还要判断找的格子出没出界。* ~" _6 a% r. }2 u1 z
具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界0 @! t& D, r+ L% B$ G
4:判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在,则重新找,如果不在,那么把墙挖去4 U& s" Q6 O1 {) V- h
5:把墙挖去有点繁琐,需要考虑奇偶判断它那种墙(上下还是左右,还要考虑位置),然后擦掉。(根据数组转换成真实距离)。具体为找一个节点,根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。: K% `4 j7 v& `& k6 [ L
6:最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙,但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据,并查集操作。二维是位置。要搞懂转化!1 l# r( _3 W3 e( ]. Y0 H8 \
注意:避免混淆,搞清数组的地址和逻辑矩阵位置。数组从0开始的,逻辑上你自己判断。别搞混淆!/ e! y, f8 p* ]
1 m5 \/ E9 t- k% y4 _
主要逻辑为:
! ?2 L, K. q! Q6 h( w( Q2 w& Z4 Qwhile(search(0)!=search(aa*aa-1))//主要思路
# m+ M* f7 { D' Z {
: w- r/ R$ {* G D0 u) X6 e var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数8 o3 l1 H) D7 R6 M) X4 H% R: P5 U
var neihbour=getnei(num);6 f) F/ Q" u: z8 ~2 }
if(search(num)==search(neihbour)){continue;}
, d3 d4 q* |5 Z else//不在一个上& m/ s7 |. o1 `8 c
{
% b* A2 J- C( ^& x isling[num][neihbour]=1;isling[neihbour][num]=1;
, ^$ W( w/ `( r J1 n drawline(num,neihbour);//划线
, j2 P* Q5 Y4 z. L) L union(num,neihbour);
; ]% j- q* S9 g, B |' k# k/ K6 v- l9 o; g! Z- U6 t! [
}
8 h! s9 [+ i- u4 p) ` }6 @# a/ [% V( C9 q- a, X& ]
) f8 L4 A2 i: Y) N! ]4 S7 E5 x+ r, e* J" D
那么在前面的代码为
! _% A+ [. Z4 |<!DOCTYPE html>; g ?& D( w$ Q% K% O. R
<html>' W4 v0 z c/ Q* i* H: k
<head>
. z4 r T' ?0 ?) w <title>MyHtml.html</title>
6 k% |) M7 k, J: I </head> 7 }, ~) g/ c9 w& o; Z* B
<body>- x$ \2 v3 V8 ?& q
<canvas id="mycanvas" width="600px" height="600px"></canvas>1 g2 \" Q% P( A
1 u6 S& G. p$ s: r: W9 q, w </body>
) U$ c! F% t$ q% T6 ]* e <script type="text/javascript">7 I0 }0 i* U+ k4 B
//自行添加上面代码
% J, O" r! z, A F' m7 ^ // var mymap=new Array(36);6 D3 K0 ^: y6 n; e! i) J3 G
// for(var i=0;i<36;i++)% a& L( N' y m5 f; @; [ P7 |& e
// {mymap=-1;}; f5 {, i* N \) p8 z( }
function getnei(a)//获得邻居号 random
* A& n1 _4 F" i7 K& a& e" I {
8 X3 W! y. M' b% {2 s) ` var x=parseInt(a/aa);//要精确成整数
0 P# H4 c- ]3 ~: D2 E N var y=a%aa;4 W& R6 q" o S& ^9 L2 N4 e5 j
var mynei=new Array();//储存邻居
, H1 n' N; l/ z# Q( [8 p if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点
+ y" U, E c. }( c; k( t if(x+1<14){mynei.push((x+1)*aa+y);}//下节点
9 F) \9 [- L" `$ C! i0 T4 u+ y# U0 | if(y+1<14){mynei.push(x*aa+y+1);}//有节点
3 I; t* P8 P# O( ^- S if(y-1>=0){mynei.push(x*aa+y-1);}//下节点1 @3 E; G7 K6 Y( y, \( O P+ L1 v
var ran=parseInt(Math.random() * mynei.length );
u$ d/ ^8 y; y return mynei[ran];" E. I6 e6 Z' }) @1 ~0 e# }' ^* z: T
8 Y* S3 T2 O- Q8 h+ u% A1 J2 B, Y
}
8 ~+ w6 m8 l0 t* o+ ] function search(a)//找到根节点4 s* z: v5 i. A1 f4 `9 P$ ~: B. S
{% r0 ?5 [) @' W# H4 @
if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
3 @6 {6 ~# q% g, _. v; O {. U b0 d0 }+ A( g
return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩
6 @8 w' |0 v* l# Q, T& k n# ] }
: ^9 U6 E' S/ l0 \ else
! e3 c0 `, a# R- x% Z return a;
' z3 \' z8 n* L- t5 _: T' i& } }
* f/ U9 [+ X* l1 O/ a& `9 L! B function value(a)//找到树的大小
) o2 p$ Y* s! s$ T' u2 z {
+ f6 ~" k. w- }% s4 ^# K9 r if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
' G2 Y/ {) o( \( a4 } {9 [& S; B3 R4 L* G8 ^
return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩
5 r% n" h9 |8 e" a7 h3 m& n8 \& g }8 R0 a0 n9 E. n# X# d7 K; K
else
* e- s' B( Y2 l, S. Q) v4 | return -tree[parseInt(a/aa)][a%aa];( K8 D2 G, b- X8 Z
}) O7 N5 \/ ]$ ^" |9 h
function union(a,b)//合并 _* }# \6 C. a4 ~/ i* _) B: x
{
" @3 n* P/ S; q/ e. e. u var a1=search(a);//a根8 c# ~/ k6 j3 P2 ~" I- r$ K
var b1=search(b);//b根. ?# ?% p" y) f1 R( ~) J" v
if(a1==b1){}
. |9 ^2 P2 g& g) P else
* Q1 v+ \! J+ E {
7 O7 [. o8 A8 ^ if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数(),为了简单减少计算,不在调用value函数
& J q, c! x! g3 L {
, W* t: \# Z7 l1 d+ p tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加 注意是负数相加
/ N H# w' [7 p, j2 |* t: Y tree[parseInt(b1/aa)][b1%aa]=a1; //b树成为a树的子树,b的根b1直接指向a;! r3 F1 y' A* Y, f
}
7 B# G. B' Q; ]' Z+ E else
* y3 \7 M4 _5 t2 T {
( `7 u. G: _; T# ~4 |; V/ Z' h tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];
, s' V1 }7 m/ u9 n1 B" R tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树( a M0 r0 A* g4 \+ X @; N( r
}5 b$ O$ @9 c' l! \( K& f0 e8 O5 V
}
3 g3 R+ H& }3 z }% N/ m1 @: X5 _: Q* S; W N
/ s# L+ a G/ F. |: c. }% n3 x7 ` function drawline(a,b)//划线,要判断是上下还是左右/ ]" Q" [+ N( P' A
{
% j0 O8 W9 J' `" o; N5 z+ W0 l4 G! f
var x1=parseInt(a/aa);
0 R7 |3 @1 K+ O1 E1 b% n var y1=a%aa;4 }, F4 C+ n, [# a. d5 B5 B
var x2=parseInt(b/aa);/ \0 V& F: A1 J$ Z4 r7 A* x7 [# g
var y2=b%aa; / c: g, T. q4 n+ O
var x3=(x1+x2)/2;% b2 u) ~ J: m" G8 k9 ?8 ]
var y3=(y1+y2)/2;
+ i) _7 V& H! @8 Z if(x1-x2==1||x1-x2==-1)//左右方向的点 需要上下划线# { X. o; g9 v r$ w8 J
{; D0 Y$ ?* h7 T/ j- s* o( a
//alert(x1);
3 w! N: V) g) w5 {# u // context.beginPath();
3 R% f, e% m( ?* G8 W! j6 Z context.strokeStyle = 'white';
- V; E+ a& J7 z) i9 z: s% [ // context.moveTo(30+x3*30,y3*30+15);//
+ p A$ i: i) G. Y# Z, ] // context.lineTo(30+x3*30,y3*30+45);4 J5 ^" r3 O. c2 N6 P3 j5 _
context.clearRect(29+x3*30, y3*30+16,2,28);
O% o Q' n% V: i/ G1 ~ // context.stroke();
& x! n/ @" n$ Q+ X6 t& I }/ l& ]8 n! f, f. {5 W
else3 B& d# m" e, J: y0 c# E' z9 C* o
{
) U' I/ |7 _+ @: S% u- z // context.beginPath();6 \0 Q- j2 w2 }3 l
context.strokeStyle = 'white';
' o& D c2 }6 } // context.moveTo(x3*30+15,30+y3*30);//
" x# Y8 k6 R3 h0 Y% U // context.lineTo(45+x3*30,30+y3*30);
) t6 w5 ?9 m1 T7 ` context.clearRect(x3*30+16, 29+y3*30,28,2);
" W; n6 o5 p& {' [# [: ~ // context.stroke();
$ E) T6 d3 o7 s) v1 Y }! I8 w( n% N9 H1 i1 e7 |- V
}) G3 k2 _7 B3 Q* f6 k. z
! Y# U2 p6 y/ X1 e
while(search(0)!=search(aa*aa-1))//主要思路
( n2 @7 v, i+ v# Y2 T0 O0 N {
* b5 C5 q- w: ?/ N& M2 M, y, R var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
9 e% z# }& X# [+ d var neihbour=getnei(num);
7 @$ n4 _9 N4 q$ ~ if(search(num)==search(neihbour)){continue;}$ Q" M: [+ j A J t
else//不在一个上
" X5 q7 J: V& ?0 k& Y$ M- _+ y# ~/ J { h3 J, ?, K2 e1 I P" e
isling[num][neihbour]=1;isling[neihbour][num]=1;
' T4 ~, f* t2 T- L/ E/ `. ^ drawline(num,neihbour);//划线
; S( d' ^: E1 z. v4 ` union(num,neihbour);
1 \; f# y5 x8 {' i) O, j4 b2 v; a, f: y
} i2 h1 l% I$ v6 b: d* E
}- u* w3 H$ q4 R5 ~( G
</script>. E% G- U: p5 r1 I# R% @( n
</html> D0 }* R: P& f C, M- ?, x. y
* a3 e. [% p+ b _( V: _+ _8 V2 G
( l9 f r d# F实现效果:
4 F* R* `4 t: z" c3 @# `3 i
- s/ M9 r1 {) m. E
# H( q/ H* q' T0 ~' N2 l D2 H6 E% X
* p- a+ `6 u+ J- g: M3 F0 ?
1 b! i! t; E r方块移动
: g/ ^& E ]0 f3 y; x7 X$ k* S; v
$ f# e& }) Q( r6 n6 W这部分我采用的方法不是动态真的移动,而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉,在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除,可以根据像素大小精准擦除。( u. R4 w' i& |2 }9 W9 Q f
3 f u5 p X8 A8 m另外,再移动中要注意不能穿墙、越界。那么怎么判断呢?很好办,我们再前面会判断两个格子是否联通,如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组)
1 }& D, ^5 t$ K; @; V7 I* ?9 X& ?% U5 s+ v, P
另外,事件的监听上下左右查一查就可以得到,添加按钮对一些事件监听,这些不是最主要的。' H A A: f' Y) h1 H, M
; D! p0 K, `2 Y3 n* V
为了丰富游戏可玩性,将方法封装,可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外,如果写成动态存库那就更好了。
; S* ?# ^% h# b+ z" w9 _
5 U- R& [% H) |0 I
! d7 y \$ Y+ [$ F2 T% n4 M: d- a3 g
1 Q# _( L. ?& o0 Y: i) q6 I————————————————
9 i( R) g$ d: |" b版权声明:本文为CSDN博主「Big sai」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。% B, q. }" G! t) j2 x1 ^
原文链接:https://blog.csdn.net/qq_40693171/article/details/100716766
6 O/ ~" ]+ j/ I6 u# S) I9 C4 d
6 j1 m9 G a0 j" ~$ i0 x
+ U W9 ~/ T- S/ Q" E |
zan
|