- 在线时间
- 1630 小时
- 最后登录
- 2024-1-29
- 注册时间
- 2017-5-16
- 听众数
- 82
- 收听数
- 1
- 能力
- 120 分
- 体力
- 564650 点
- 威望
- 12 点
- 阅读权限
- 255
- 积分
- 174618
- 相册
- 1
- 日志
- 0
- 记录
- 0
- 帖子
- 5313
- 主题
- 5273
- 精华
- 3
- 分享
- 0
- 好友
- 163
TA的每日心情 | 开心 2021-8-11 17:59 |
|---|
签到天数: 17 天 [LV.4]偶尔看看III 网络挑战赛参赛者 网络挑战赛参赛者 - 自我介绍
- 本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。
 群组: 2018美赛大象算法课程 群组: 2018美赛护航培训课程 群组: 2019年 数学中国站长建 群组: 2019年数据分析师课程 群组: 2018年大象老师国赛优 |
- x" m- d7 y& w7 D
我花了一夜用数据结构给女朋友写个H5走迷宫游戏6 k5 r- |4 S3 k8 r
文章目录4 B4 U3 r( z1 @
, h; V5 l% u4 R5 O! Y/ n+ }起因
! V. C* E+ v4 s, c p- W8 Y9 g- Y分析6 Y. c" @, u2 R) E- y" P- ?
画线(棋盘)
) v) l4 J( O+ Z4 L5 \% e0 G画迷宫
* K) H* U6 _7 |, R, l% o& Y方块移动- ~" s4 ~/ |# t3 h7 k) v- k! W
结语
! s- H8 T+ B6 I; i4 E a先看效果图(在线电脑尝试地址http://biggsai.com/maze.html):
6 w+ B0 J$ [/ J! f" u% k# k
0 I/ R# [3 r; l+ N3 i9 ~* ]
( i; @3 l7 ?2 O起因$ B( V) O% q, O! W! F) l! i
& z. x Q" ?- D7 k) W; d0 H6 \. F V+ k: M
又到深夜了,我按照以往在公众号写着数据结构!这占用了我大量的时间!我的超越妹妹严重缺乏陪伴而 怨气满满!3 Q5 U. r( G7 @2 s! g1 x4 j
; T7 D8 F/ _; V, r; O/ r, f8 m/ N- g超越妹妹时常埋怨,认为数据结构这么抽象难懂的东西没啥作用,常会问道:天天写这玩意,有啥作用。而我答道:能干事情多了,比如写个小游戏啥的!* t) h! I- L8 U
& Q9 z1 H& X0 d当我码完字准备睡觉时:写不好别睡觉!7 d3 k7 f( _) q. M- |
- c* x7 G n. x# @# O+ i. F
1 @1 |/ P8 D" `+ \6 b分析
' s+ M( e7 {( E1 g# [% B' O( U7 j, Z6 W3 j6 f" ?' z6 ]
如果用数据结构与算法造出东西来呢?
0 N8 D% R1 h* z( W1 P2 V ~
1 S# k+ s' w7 e6 Q8 d! d什么东西简单容易呢?我百度一下,我靠,这个鸟游戏原来不好搞啊,得接触一堆不熟悉的东西,搞不来搞不来。" A, L9 _' L' j' u; a; h! q
有了(灵光一闪),写个猜数字游戏,问他加减乘除等于几。
& S. h" ^* O" f# G) C( Y5 W
1 a# N& x/ P) [+ r0 I超越妹妹又不是小孩子,糊弄不过去。2 t$ d9 z: A7 W9 L8 h# K: R
经过一番折腾,终于在半夜12点确定写迷宫小游戏了。大概弄清楚其中的几个步骤。/ ^: a3 B: ]; l% a; r4 t
( Z2 H( S$ S0 j% X& P# [$ b0 W' T, R大概是:
; O- b, h" F; J8 X6 K7 y3 w/ h+ c! B4 c" m& i! @
画线—>画迷宫(擦线)—>方块移动、移动约束(不出界不穿墙)—>完成游戏。
0 O, r: x' d7 Y. |画线(棋盘)
, X$ f5 n @# s* ?' M+ y# \4 m$ f5 t* t" M) {& z# q2 K' d. s
对于html+js(canvas)画的东西,之前学过javaswing应该有点映像。在html中有个canvas 的画布,可以在上面画一些东西和声明一些监听(键盘监听)。
8 ~6 o/ b/ N4 Q& F V" d+ r7 ?" I6 A
对于迷宫来说,那些线条是没有属性的,只有位置x,y,你操作这个画布时候,可能和我们习惯的面相对象思维不一样。所以,在你设计的线或者点的时候,记得那个点、线在什么位置,在后续划线还是擦线还是移动的时候根据这个位置进行操作。
1 L% v2 W- L+ \% F+ j: I2 e! m) o( n <!DOCTYPE html>& i2 S. d9 y% N- ?& R$ G% w& N% Y! ?
<html>- e, R: P/ \" n9 S
<head>
: f, z! j5 J& v/ a$ I <title>MyHtml.html</title>
4 z3 `2 B+ a% c8 f' c2 S4 r% X </head> * Z+ j' b H, K
<body>
3 Y$ p6 L% S, v( X# T3 v <canvas id="mycanvas" width="600px" height="600px"></canvas>
& C6 {# Q) M/ b2 V' w# A5 c0 g J9 U, X% V8 f9 s
</body>
3 G# ? N: D3 c( c( M. x <script type="text/javascript">
% w* A: _' V. m: H2 s
5 K0 S9 ^) ^' e( s( hvar aa=14;
8 ]+ w8 e' h( B var chess = document.getElementById("mycanvas");. k+ W1 l8 s) {: y9 P
var context = chess.getContext('2d');
1 Q) Y8 g2 S3 W3 o( A) A6 u
9 v. `( x, g& s3 _; U1 s // var context2 = chess.getContext('2d');
; a' }9 R1 W1 \7 T9 |$ q // context.strokeStyle = 'yellow';
/ Q6 H6 m' _9 ] var tree = [];//存放是否联通
. o7 V, {$ ^/ b+ s2 [6 Z var isling=[];//判断是否相连
( a' `2 B, \( h for(var i=0;i<aa;i++){
, { H1 w1 m$ x0 D5 W4 E4 P. ]" e7 Q tree=[];
; Z, g2 v8 U ]1 d) Z/ n7 M for(var j=0;j<aa;j++){+ k, V0 y4 T2 q, O8 _! W
tree[j]=-1;//初始值为0
( P% O% Q z) J0 p+ `0 |8 R }
9 A" F3 a* J0 k( X# K9 L1 C' ~: h } for(var i=0;i<aa*aa;i++){3 T# ~. o" U+ u5 K6 G: M8 S
isling=[];
. p* p8 m( x, c7 r8 P* |. X9 A. ? for(var j=0;j<aa*aa;j++){
& } O9 c2 v% c% N+ Q isling[j]=-1;//初始值为0- o# @/ A* G. c: Y- C& T
}
) z/ R' Q4 ^0 w }4 F% B, s$ a/ o5 S$ a/ _
0 F9 Q: v- P0 B
function drawChessBoard(){//绘画2 W8 a, g% e1 Z
for(var i=0;i<aa+1;i++){
j2 L6 P, [$ N2 l context.strokeStyle='gray';//可选区域4 u. P6 }) D9 n; k# n
context.moveTo(15+i*30,15);//垂直方向画15根线,相距30px;+ S# C: W8 j) ~9 p
context.lineTo(15+i*30,15+30*aa);
0 r% L4 @1 u7 ?9 k. f/ b context.stroke();
6 v+ _% Z: G7 r0 I; f context.moveTo(15,15+i*30);//水平方向画15根线,相距30px;棋盘为14*14;
7 C2 Z' ]( V, j5 V5 ~4 K context.lineTo(15+30*aa,15+i*30);
7 d. B5 V* v6 G ~" B" ]! \ context.stroke();
# |0 g3 y0 z" Q* P5 D6 B3 h7 D }* c- A, L+ i) ]5 i) h0 K! v
}, }# R) M+ W; g' H
drawChessBoard();//绘制棋盘
+ N9 s& P F& }' W7 ?
' Y. Q5 L: k1 F6 w7 d& H g // var mymap=new Array(36);) J- N6 C, x8 t% s. c; V K+ B' ]
// for(var i=0;i<36;i++)1 z {' e3 x$ a& x" R& c V0 u* o+ N
// {mymap=-1;}. d6 Y+ B& @7 o: R' M. H9 \
$ \1 L; j1 [7 ?( F7 R/ v1 l8 P7 _ ?4 {3 V+ O" G" w6 Q% D
</script>0 f7 ?$ B+ ^( T A5 j! ]1 v% g
</html>9 C# T' I; |! t( B" z- n
. E" M$ I/ K: c8 {' \/ h
0 v; I( y% K5 o
实现效果
7 z6 B4 O* n8 r- n" G. p6 n1 q
# G9 D3 h0 f+ C+ Q
+ l B: J5 x! i$ H& N) ^画迷宫; [* j3 Q c& R. j- r
8 p; D3 h5 |9 d% B- e$ d) {
随机迷宫怎么生成?怎么搞?一脸懵逼。
, q0 Z/ b0 Z7 v( m9 U; R7 _; b+ N( R6 N7 a! u9 b
因为我们想要迷宫,那么就需要这个迷宫出口和入口有连通路径,你可能压根不知道迷宫改怎么生成,用的什么算法。小声BB:用并查集(不相交集合)。% I! Q& S! `: t, h( w
迷宫和不相交集合有什么联系呢?(规则)
- c4 e% a5 C K9 X" \0 B3 s* V1 R F
之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合),它的主要功能是森林的合并,不联通的通过并查集能够快速将两个森林合并,并且能够快速查询两个节点是否在同一个森林中!) z9 [; V9 S2 l$ W
而我们的随机迷宫:在每个方格都不联通的情况下,是一个棋盘方格,这也是它的初始状态。而这个节点可以跟邻居可能相连,也可能不相连。我们可以通过并查集实现。$ M! {) Q& ^; H, I* a
4 [9 }8 Z/ q# P1 X: a具体思路为:(主要理解并查集)
. a4 e! ]1 w, S4 V2 I1 h
5 M7 N* q( O; |1:定义好不想交集合的基本类和方法(search,union等)1 N2 S0 n# r7 ?' Z
2:数组初始化,每一个数组元素都是一个集合,值为-1
0 z6 V8 Z; W. Y" o' o& P. L3:随机查找一个格子(一维数据要转换成二维,有点麻烦),在随机找一面墙(也就是找这个格子的上下左右),还要判断找的格子出没出界。
7 ~5 H) j/ J4 F8 h具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界
3 P6 @& d/ T, p d4:判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在,则重新找,如果不在,那么把墙挖去% Q$ c8 `5 D8 V3 S h/ G& i
5:把墙挖去有点繁琐,需要考虑奇偶判断它那种墙(上下还是左右,还要考虑位置),然后擦掉。(根据数组转换成真实距离)。具体为找一个节点,根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。
+ I4 U3 Y9 d/ J7 C7 Q6:最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙,但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据,并查集操作。二维是位置。要搞懂转化!0 U* u7 T, E& h! f6 _) @ B. u
注意:避免混淆,搞清数组的地址和逻辑矩阵位置。数组从0开始的,逻辑上你自己判断。别搞混淆!9 x" d) }, F) M: ?- }, b! b8 U# O+ [
$ M, e* j1 f4 w主要逻辑为:/ x* t. x) r+ ^& U; M% L
while(search(0)!=search(aa*aa-1))//主要思路
0 s: n. M; x* X6 _% S, E; D+ k7 i {
# `8 {/ f9 ?3 E) |6 r var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数$ h& W; X7 B: x$ O& H$ G2 o& |
var neihbour=getnei(num);
3 P) L9 W3 j1 m, f# k$ l) c if(search(num)==search(neihbour)){continue;}
" R" y8 G+ N# L. @ else//不在一个上3 i% c$ K% r9 U
{ l# q) H6 E7 k. M4 o
isling[num][neihbour]=1;isling[neihbour][num]=1;; h$ Q/ ^' C+ G' s
drawline(num,neihbour);//划线3 Q2 ^7 }; i- m2 u% a
union(num,neihbour);# d. E @0 [+ @! i- ~" B0 j
: c5 `, T3 a: T* Q
}1 b8 m+ A$ W, a' R
}
H1 ?% o; w- g& o, s* D* R$ L$ Z
! U+ @9 Z3 y$ V; ~9 Z5 C" P* i; p _那么在前面的代码为
5 o/ C+ G- [$ v+ u5 L. L<!DOCTYPE html>
& N6 b' ?8 Q' R# ]. V6 w+ I<html>' `) Z( G5 l$ n9 A
<head>
) ?" q& h# Q' Y; B( z, s <title>MyHtml.html</title>
( D2 B' y3 [3 `3 a) \ </head>
4 a+ n# h, W2 S2 B j <body>2 I4 D/ c! v) G5 @; E+ t9 x
<canvas id="mycanvas" width="600px" height="600px"></canvas>' q6 Q q: n9 F& _1 l9 p
2 Z7 y# V7 o/ v0 @% K K
</body>
/ m- M2 X* R# N" R, H <script type="text/javascript">
' v$ o2 S0 S+ h//自行添加上面代码6 P# u6 ~/ i Q0 u+ |
// var mymap=new Array(36);2 K; k& u6 x+ s+ Z; O9 T& ^8 r6 b4 Q
// for(var i=0;i<36;i++)
2 j. A. P' ^2 x3 f% ` // {mymap=-1;}- v- o1 q0 ?! X4 s+ f! g
function getnei(a)//获得邻居号 random
z( |) G' V# Z7 }% ?- @$ f {+ k% u6 V8 q, g" A& `
var x=parseInt(a/aa);//要精确成整数
5 C' X0 s O0 O! A0 c; }1 ` var y=a%aa;
1 Z. F( S6 h4 W. B var mynei=new Array();//储存邻居/ ^* m5 l4 _8 W1 P# A
if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点& J9 f3 Z9 d: J% w
if(x+1<14){mynei.push((x+1)*aa+y);}//下节点
: K) G4 e+ w G7 i! m2 c* V if(y+1<14){mynei.push(x*aa+y+1);}//有节点6 U; N% w0 E. u
if(y-1>=0){mynei.push(x*aa+y-1);}//下节点
/ I4 H* C$ [4 w. ~; y5 z5 x. b var ran=parseInt(Math.random() * mynei.length );
! y+ k" t/ g* h; P3 K8 n1 B return mynei[ran];
4 \+ g, x* ?* l( m! B
) @# W% [! A1 k2 Y0 p. z9 M }
# t7 [8 q" x9 G function search(a)//找到根节点: @7 Z0 K H% S) q1 C, u0 P
{/ V( N# ~% r$ x" [
if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点- w7 L6 H' `! p( k) a
{5 C" q7 g4 c P" t) J! l
return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩
; A7 b% d, b: Z }
' k4 L3 U; X" I1 ` else+ U9 x# R8 @; I* I! @) u
return a;7 ?/ i- r! e; V: ~4 `8 H
}
9 Z; o2 ]4 ~; v" ~ function value(a)//找到树的大小: ?3 ~9 x) Q4 Q
{
* ]0 w( {$ c2 K5 f& I if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点' z7 Z* L, r$ q: u4 W
{
1 ]: D, I/ ^) V8 u/ K4 q return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩
0 C+ g) T! k3 g* n- P$ V }
0 h7 L k& w# Q else
4 R8 }: ?( G$ X% J return -tree[parseInt(a/aa)][a%aa];
, h6 F$ q5 I$ H0 H8 _0 H- u }
: ~/ y1 a) f5 B' h) f function union(a,b)//合并7 |5 W4 X% l4 E6 b7 d5 n9 e8 H
{9 f$ O: ^) H5 U
var a1=search(a);//a根
9 e1 Q- q$ |8 J) M. J var b1=search(b);//b根6 O' w8 \0 w" F
if(a1==b1){}. b& S4 g/ I! F2 d
else
) b1 a r9 `: s2 X; y {& K. l1 @# G1 T# U* k, W
if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数(),为了简单减少计算,不在调用value函数' t! N( W5 n. Y5 w: |, f5 T2 ]
{- k3 v! h( s& @# o
tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加 注意是负数相加
6 ]5 n/ o* C$ d/ _8 T; G- Z tree[parseInt(b1/aa)][b1%aa]=a1; //b树成为a树的子树,b的根b1直接指向a;) _# v/ A! p0 Q+ I* ^, H! Q) x' j
}
B h2 x$ R) l5 U1 N2 Q7 b+ f else
5 k! f% y! S3 i; m y# r {
* S2 v. S6 q1 w7 z n( k2 F tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];# ?! l8 t% z( E9 I
tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树
0 @/ ~5 B9 Z; h, q }7 V! F L$ e8 I6 Y: x4 a
}+ a! F7 G- G/ ]; ^
}* N4 R( C; w. [* K8 F8 ]+ c
1 U* k0 ^7 `- ?7 U" @0 k
function drawline(a,b)//划线,要判断是上下还是左右
2 |: `5 H+ s9 g& F, E3 T {
& l: y. k; U0 H* R k" O2 L2 [2 C
( c* b) a: T7 m" [6 p" i. U! C, S var x1=parseInt(a/aa);
4 o {: Q( t6 O) ^; t4 U var y1=a%aa;
" W* }6 k1 u. B( ]' |+ J4 ? var x2=parseInt(b/aa);
, m8 Z! e! B/ y) O6 W$ b var y2=b%aa;
4 R2 z/ g$ l8 { S- y! j var x3=(x1+x2)/2; G5 W/ t: J/ G; n6 J% ?- e2 l
var y3=(y1+y2)/2;+ P# Z; D7 V" w
if(x1-x2==1||x1-x2==-1)//左右方向的点 需要上下划线
& [, I5 B' D. X/ G5 a {
. I! [9 X* e. u- R. x( H //alert(x1); H4 u% v! P- j( G! a% t1 I! S
// context.beginPath(); G2 Y5 y- C% c& q" T% o
context.strokeStyle = 'white'; ^# l t' B; R- x4 P' Q W
// context.moveTo(30+x3*30,y3*30+15);//
# a: k: s% T6 r7 s7 A" v // context.lineTo(30+x3*30,y3*30+45);
0 B, L( b5 n# z+ b c) n, e0 _7 T8 W context.clearRect(29+x3*30, y3*30+16,2,28);) v! G/ V) ?2 a% C, x$ I
// context.stroke();1 N; r- k, K7 Q \
}
* B2 Z: k* Q4 x, l0 Y4 H else
4 d; R* ?+ d) Y% t) X% L6 o {
$ d! n) N' w0 ?7 m* B // context.beginPath();* ]/ T/ ^4 }* O! h- b, S l: R
context.strokeStyle = 'white';
$ V1 W/ K( I [ // context.moveTo(x3*30+15,30+y3*30);//
* N4 D2 |1 Z" O0 V8 d" w // context.lineTo(45+x3*30,30+y3*30);
% g1 Z) b5 P0 R" [% g" M context.clearRect(x3*30+16, 29+y3*30,28,2);
: ]: ~ W" l/ D( q7 V' y // context.stroke();' j/ _: r! o8 D3 M, R
}. y/ R1 w' L0 t: O3 P$ r/ Q" R" ]
}! d" N' O+ S3 W& o0 U0 A/ b
$ @1 f( z+ s0 L( [9 e4 d
while(search(0)!=search(aa*aa-1))//主要思路
7 L3 `+ u; @: ~9 @% E9 L P5 v) r {/ `; u& p) L- J& S2 |( L) c
var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
5 L& y+ Y- s) N5 t( K+ U var neihbour=getnei(num);
6 m T6 r6 n: J/ E- D if(search(num)==search(neihbour)){continue;}2 T H9 U! ^& |+ F1 C+ J" O
else//不在一个上* f! A* E4 b5 [# X! u
{. |5 G& a( D* f* q
isling[num][neihbour]=1;isling[neihbour][num]=1;
. P/ ]& y8 e, p G drawline(num,neihbour);//划线
' x- ~( h1 R, ~+ t% @6 k. }4 j union(num,neihbour);
) v& @# Y( {; E' \0 ~; ~) \1 Q( \! M. j7 Q! X; y& d
}
6 W* o0 A0 i8 z* e& C }
2 [+ k" Q& J8 g8 w+ m& s </script># ^2 |& X ?( ^) y
</html>) H0 j' D6 }+ s9 X! \2 ?
. s7 O+ Z8 p" F) j! x
% {* C7 P+ f& `+ S5 t9 u# o实现效果:
, `6 B; f+ P7 C+ K2 y$ P% ]7 R f3 g$ b0 r: J
9 v1 v. Z7 s5 k; i
- F7 E; l, Z0 ?4 L7 ]! @, o5 J
% J' i6 I& _7 d+ g& `$ w. k/ S方块移动7 C8 Q' J7 n9 G. W
4 y: d) v' q/ z% u1 Z这部分我采用的方法不是动态真的移动,而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉,在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除,可以根据像素大小精准擦除。6 B7 H* x8 m5 U6 i! h& r
' M' Y8 i" h' x* l' ?, c" R% I另外,再移动中要注意不能穿墙、越界。那么怎么判断呢?很好办,我们再前面会判断两个格子是否联通,如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组)/ t6 O5 \, c7 [9 {; ^0 s/ r
2 S5 o9 M- N( E! k6 T. }! T( K$ @另外,事件的监听上下左右查一查就可以得到,添加按钮对一些事件监听,这些不是最主要的。
% _4 f" J' N# S
( E2 `! y0 e3 f; V% \4 T, e' Q8 ?; `为了丰富游戏可玩性,将方法封装,可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外,如果写成动态存库那就更好了。5 E& J! z9 A) N6 D; B1 c
, Q* V# q7 e* \& W. I2 c
3 l* y C, e% W: o1 M( A5 D9 y3 X4 N
* Q* k- ~% I, D. Q————————————————
$ Z8 s" ~; F2 G4 c8 |! x( U2 H# m版权声明:本文为CSDN博主「Big sai」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
; g6 N+ `. j5 I) E0 i$ i( ~ Y原文链接:https://blog.csdn.net/qq_40693171/article/details/100716766
; t9 t3 O, r( Q0 C1 V5 x2 F. J
3 d0 `$ u+ s! [" H" ~1 g' b2 w. X E
|
zan
|