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