- 在线时间
- 1630 小时
- 最后登录
- 2024-1-29
- 注册时间
- 2017-5-16
- 听众数
- 81
- 收听数
- 1
- 能力
- 120 分
- 体力
- 539958 点
- 威望
- 12 点
- 阅读权限
- 255
- 积分
- 167366
- 相册
- 1
- 日志
- 0
- 记录
- 0
- 帖子
- 5324
- 主题
- 5250
- 精华
- 18
- 分享
- 0
- 好友
- 163
TA的每日心情 | 开心 2021-8-11 17:59 |
---|
签到天数: 17 天 [LV.4]偶尔看看III 网络挑战赛参赛者 网络挑战赛参赛者 - 自我介绍
- 本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。
群组: 2018美赛大象算法课程 群组: 2018美赛护航培训课程 群组: 2019年 数学中国站长建 群组: 2019年数据分析师课程 群组: 2018年大象老师国赛优 |
! z8 H* O- a+ m/ f( \我花了一夜用数据结构给女朋友写个H5走迷宫游戏# N: ?$ D7 j& p C- f
文章目录% [! L" b3 r4 `8 w
5 G7 V& Z K( g6 i3 I. D- A起因
\) \! N1 Q2 ?5 K, F& ^( N分析
# l5 e$ m9 h6 n; n& V# \/ v3 v画线(棋盘)% e7 ~$ E& r) P% S
画迷宫
* m0 W% R5 s2 R) |& Y方块移动6 h( S4 E$ u: p; J5 J/ W
结语& g4 B: v8 G9 Y$ `5 G
先看效果图(在线电脑尝试地址http://biggsai.com/maze.html):
6 P& }3 H. t3 d( E$ D+ ~/ {% b$ N
! }% B/ h1 c" d% B4 y
, }2 N: K$ b* y, c; D2 i. k
起因
% V$ U8 k& n/ s/ k: E2 q5 G
! B4 L2 O, H' R2 H7 g
# ~: N0 w; U8 g9 F) C又到深夜了,我按照以往在公众号写着数据结构!这占用了我大量的时间!我的超越妹妹严重缺乏陪伴而 怨气满满!( `. i% X S+ T' t: V% O5 r
) Q( c% |5 m# L1 E
超越妹妹时常埋怨,认为数据结构这么抽象难懂的东西没啥作用,常会问道:天天写这玩意,有啥作用。而我答道:能干事情多了,比如写个小游戏啥的!
# c" u5 b3 p1 {- s( f* m
1 e0 ^, S- B+ m* J: G
当我码完字准备睡觉时:写不好别睡觉!# c+ y3 D: y- b
8 @' Y1 g/ v5 u) L
9 j/ p# o9 Q) c% N- o分析
0 p5 B1 o% x5 @, }: m) p; X( M1 m" p- V V6 q+ h# v# }
如果用数据结构与算法造出东西来呢?' d% O4 f. F7 Q0 o
: ^5 I) Y) i! B* P/ q/ j
什么东西简单容易呢?我百度一下,我靠,这个鸟游戏原来不好搞啊,得接触一堆不熟悉的东西,搞不来搞不来。
; S5 ~& O: D' b% f2 U* `有了(灵光一闪),写个猜数字游戏,问他加减乘除等于几。( b0 m. U1 ~$ q8 g. j2 Q0 B
* e2 l4 [ b0 z' y9 c3 s2 x! Q3 |
超越妹妹又不是小孩子,糊弄不过去。
2 D8 C O+ S3 V) z经过一番折腾,终于在半夜12点确定写迷宫小游戏了。大概弄清楚其中的几个步骤。0 \* J2 b* a' I5 X0 o/ q. O
* x6 t7 ^! H5 ~( t( T大概是:' C" K* p5 r$ H1 B, E0 y% I
1 s) f, a! S' u; P8 I画线—>画迷宫(擦线)—>方块移动、移动约束(不出界不穿墙)—>完成游戏。# H+ f' h. ~1 ?0 Q9 K- A7 E( u# s
画线(棋盘)$ s/ p! c6 J8 E/ J
% z8 G B9 }5 ^: v( _/ L) ^对于html+js(canvas)画的东西,之前学过javaswing应该有点映像。在html中有个canvas 的画布,可以在上面画一些东西和声明一些监听(键盘监听)。; r4 | g8 \( A! ^
" E$ y; q0 c4 C2 O对于迷宫来说,那些线条是没有属性的,只有位置x,y,你操作这个画布时候,可能和我们习惯的面相对象思维不一样。所以,在你设计的线或者点的时候,记得那个点、线在什么位置,在后续划线还是擦线还是移动的时候根据这个位置进行操作。
7 x2 r& b" f9 ?" [- q <!DOCTYPE html>; t, X/ w# k! r7 S
<html>0 B* E+ }2 o" w# w: q7 X# W
<head>
1 v/ n& l$ Y' p/ h4 b v" R) O, p <title>MyHtml.html</title> 1 U6 \: Y$ R! ~
</head>
* ^5 ]0 v0 O p5 I1 T! X# R0 N+ d <body>6 l5 z+ R: ?1 \0 O5 S$ t, K3 d! r1 O
<canvas id="mycanvas" width="600px" height="600px"></canvas>2 J3 \1 T3 f* @9 Q0 X2 b0 i) E
% @4 G: q& s) J
</body> C0 {" q: U: o
<script type="text/javascript">; ?% o) s; Z4 ]/ W% V
4 O" M& W4 X# P. t$ f9 {. ~var aa=14;! ]' \& K$ |" ~: @
var chess = document.getElementById("mycanvas");. o- u$ K0 O, y8 a9 @$ `; H7 l
var context = chess.getContext('2d');7 D6 n- D. ?& i* z' X% {* y
3 R2 [1 G( O$ P! K% U3 q/ s1 m // var context2 = chess.getContext('2d');
0 M5 F. d# t1 X/ O7 j1 V0 m // context.strokeStyle = 'yellow';
+ q q6 K; u3 B b; d& e var tree = [];//存放是否联通
" v* i( @/ |+ q3 J6 Z var isling=[];//判断是否相连
/ D( a- D- Y+ ~! } for(var i=0;i<aa;i++){
6 x; h0 o$ r* @* p5 Y8 p tree=[];
1 D: \- p2 S) S: I6 P. K for(var j=0;j<aa;j++){. i9 K& O3 i2 g' K% x
tree[j]=-1;//初始值为0 m1 h+ S- |5 N/ V$ u6 G& ~5 I f! |( }
}
, b2 D& Q5 v; f# W% X4 O } for(var i=0;i<aa*aa;i++){# O/ k' R6 ? q- h K3 ~
isling=[];
& m! _- k$ n1 r& {) c( e for(var j=0;j<aa*aa;j++){0 l9 A4 l, @5 t* v* `: v, l& e8 e3 ^
isling[j]=-1;//初始值为0
, ~) N1 C, w6 @1 o+ F1 b8 _# n }
! B- z7 h3 g. c; M3 z! h! S: y6 A }) E# Q$ b3 q9 ?: t( y3 w
( ~5 ?' M }6 k+ Z6 {- E* p1 S
function drawChessBoard(){//绘画/ l4 [9 u4 u" u- p" ]- d' F( y
for(var i=0;i<aa+1;i++){
9 r5 [ c' [5 b1 E% Y context.strokeStyle='gray';//可选区域3 L' X" U5 Q; {
context.moveTo(15+i*30,15);//垂直方向画15根线,相距30px;
e$ k( Z: t; r6 [! j6 Q$ k context.lineTo(15+i*30,15+30*aa);1 Q) |8 ?: |' r. B
context.stroke();
8 g$ P% _% }( ? context.moveTo(15,15+i*30);//水平方向画15根线,相距30px;棋盘为14*14;0 G$ I% S. T' J, I9 R2 b
context.lineTo(15+30*aa,15+i*30);
; P. {" y8 J, M context.stroke();- I7 w0 @. O6 a) {$ r" N
}1 i6 f: ~/ ^& _# i, g* ~% L2 K6 O! i- ~
}- f- N9 z1 A* f* Z8 Z
drawChessBoard();//绘制棋盘4 O2 ?( Y1 @- T& |+ H
. B. H! Y0 Q- B* O; P z! ?- o+ [
// var mymap=new Array(36);
$ W1 P' P- U& N // for(var i=0;i<36;i++)
7 J3 I" l% B& I: i) E // {mymap=-1;}# N4 y8 i# |9 e/ E J x
: I5 K( i7 z8 y1 j
* g8 p6 _* d) }2 Y# f </script>
! k. ~& O0 O$ w</html>/ e3 C# O5 B0 h* R( Q
* }1 O7 G9 c$ a% v% @
8 i: c5 J' u0 x. n. \* F
实现效果2 j+ }+ i. B% E j: l$ c- N5 J
) x. s! L+ i& d% Y. C
* y9 ^# ^' g0 v9 S7 P画迷宫8 u }5 H$ z4 s9 W
# U, d0 h( A* f% r0 A# j
随机迷宫怎么生成?怎么搞?一脸懵逼。
/ x: g6 K9 ^0 a) ]5 f1 ^0 |% I h3 s8 [ F
* h( i3 u# }7 `8 J* T9 Q+ y因为我们想要迷宫,那么就需要这个迷宫出口和入口有连通路径,你可能压根不知道迷宫改怎么生成,用的什么算法。小声BB:用并查集(不相交集合)。5 h. \7 `3 R: k; Y6 H
迷宫和不相交集合有什么联系呢?(规则)
1 N! ]; V$ V A( R4 v$ N, }- ]( i/ }, h/ S) R/ c2 R2 i
之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合),它的主要功能是森林的合并,不联通的通过并查集能够快速将两个森林合并,并且能够快速查询两个节点是否在同一个森林中!
0 m2 i2 R3 \: D% G4 U3 `而我们的随机迷宫:在每个方格都不联通的情况下,是一个棋盘方格,这也是它的初始状态。而这个节点可以跟邻居可能相连,也可能不相连。我们可以通过并查集实现。' Y0 [8 o) o$ n7 G7 L! A0 y [
" L3 J0 a, \( p
具体思路为:(主要理解并查集)/ u5 @* s/ j! F, i6 O/ t
! T c& r4 Y; Q6 U) B a/ \1:定义好不想交集合的基本类和方法(search,union等)( n0 q! M% b! d7 a
2:数组初始化,每一个数组元素都是一个集合,值为-1
3 Z( V9 Q: K% S$ L3 i9 z3:随机查找一个格子(一维数据要转换成二维,有点麻烦),在随机找一面墙(也就是找这个格子的上下左右),还要判断找的格子出没出界。& b1 G' Z1 ? p
具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界
* G2 a7 }" o" V) }9 j4:判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在,则重新找,如果不在,那么把墙挖去" F% {$ k5 ~- k* b" r
5:把墙挖去有点繁琐,需要考虑奇偶判断它那种墙(上下还是左右,还要考虑位置),然后擦掉。(根据数组转换成真实距离)。具体为找一个节点,根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。% Q0 |7 i% P! `" U9 M
6:最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙,但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据,并查集操作。二维是位置。要搞懂转化!
# d1 K/ H; o0 Z a: ?# o注意:避免混淆,搞清数组的地址和逻辑矩阵位置。数组从0开始的,逻辑上你自己判断。别搞混淆!" M; c% B" e% n8 c
( z% @! A5 n6 o3 p: D* J: I) Z主要逻辑为:( k; w5 N& m9 ^) Q
while(search(0)!=search(aa*aa-1))//主要思路0 B9 T6 F5 a: e1 J! }$ W% F) G
{% w' d7 D4 q1 W9 K
var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
# E$ n6 h6 `1 x( j* o var neihbour=getnei(num);$ }* o; ^: |: P; i1 w# P- U! G
if(search(num)==search(neihbour)){continue;}& K8 o% v9 s6 o6 x2 A2 J4 P6 p( C
else//不在一个上
8 X a: Y4 u+ f6 F+ }% N7 q {; w1 s" }, H. _7 b
isling[num][neihbour]=1;isling[neihbour][num]=1;
9 F, ~ V3 c$ [8 ~( h( r L drawline(num,neihbour);//划线- F! [, @4 l1 p. i( ]" J; S5 d
union(num,neihbour);6 K; O- U; b/ g- W, ?* W7 X1 x3 Y
8 s4 V7 Q5 h8 [- e" y$ L
}
& {! I$ T/ O* i$ m- F9 J }
* A! s; g7 P, e) y5 B( r3 z, D/ |0 l! w; Z
+ H6 k- X, j5 }& ~
那么在前面的代码为
, @# D& `& ?, G) M6 A4 h& z<!DOCTYPE html> l- A6 _/ m$ F- {) ] t9 s
<html>+ v8 j8 \1 r9 P! C/ x
<head>- f7 t. a6 ?( o, S" |9 L5 R
<title>MyHtml.html</title> % W/ z6 }0 V, B
</head>
7 f+ V+ b' \! m( T1 \ f$ D <body>$ p6 l% Q7 A/ H. i+ N [
<canvas id="mycanvas" width="600px" height="600px"></canvas>
! T5 H7 X: D6 O8 F( a
7 J& B. t0 ^# ]8 ` </body>
" h6 R8 Q# V8 ?0 V F" I8 K <script type="text/javascript">
/ H# p4 F( V S- W//自行添加上面代码
3 e( k. O) ~+ i7 I; l8 @9 y5 ?, X/ E // var mymap=new Array(36);
d5 l: a! h+ ?! w, O- l6 n // for(var i=0;i<36;i++)
$ s. y- [+ S. N& ^8 l // {mymap=-1;}2 o$ O2 m' a7 |* F# n
function getnei(a)//获得邻居号 random
) k E1 e; s. G2 y- Z {5 Z* Q( W# {: y( `( b( F
var x=parseInt(a/aa);//要精确成整数
) M1 B* a" U" r0 S5 t+ T var y=a%aa;
" `7 {9 b0 _6 r' i var mynei=new Array();//储存邻居
% ~: B. K, Y8 H, }* _: ~ if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点1 w1 ]* ?6 V& d% ^' d* M
if(x+1<14){mynei.push((x+1)*aa+y);}//下节点) C% G! e0 Q6 [% l/ d9 ?9 h
if(y+1<14){mynei.push(x*aa+y+1);}//有节点- I- n7 o' z) e1 S* w7 k
if(y-1>=0){mynei.push(x*aa+y-1);}//下节点
5 C" Q1 w' `$ e, f var ran=parseInt(Math.random() * mynei.length ); \6 R% w+ G: F) s6 E7 Q
return mynei[ran];
- s V+ `3 z3 \3 t* e' K. o6 |4 [* r5 n
}! ?% o. Y8 h7 @, P8 A
function search(a)//找到根节点% { s6 f) ~$ O% _' f/ b/ p
{3 W) j f5 m+ L( ]" e5 C& `
if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
) d8 J, b2 g+ p {
) s7 R. `' @( v# u" c return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩
# q1 @' `# L" W6 [# ?8 H* m# K; } }
! y, D3 ~3 y/ ~* f else
3 _$ s8 C' J/ }0 _* r return a;
/ `2 _2 f5 A' v2 }" \# {/ V }
& x7 n! y* m O& V5 c; Y1 z6 ?! Q function value(a)//找到树的大小
) I* I+ Y3 t& F4 m$ Q3 e5 a/ N {
5 p, T6 q6 U9 t: e5 W) y if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点# L& a2 P( U) |
{6 }& c2 Z) p* e; X k& J: `
return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩" j* O1 c, D4 t, u% ]( ^7 B
}
6 D! Q9 E* N' O+ m! z else
7 B% P0 H- @5 D. i) L' F2 \ return -tree[parseInt(a/aa)][a%aa];
|9 _! }9 U9 o' w4 B( U. |7 [+ { }
0 n3 x' q2 V/ f function union(a,b)//合并
' o# _) _7 @) I1 ` L7 p. O% ] {
9 U b, \4 V2 l1 v0 R9 S! B) B var a1=search(a);//a根
8 ?# ~1 {. ^3 r6 y, W# j/ ^" Z var b1=search(b);//b根# d5 z( ~9 s# L1 R( c1 f
if(a1==b1){}
1 s8 x: }# X0 w0 Y else$ Z: }+ \' R" G6 p0 f. o
{
8 g, E) C9 P9 w! N+ m8 B if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数(),为了简单减少计算,不在调用value函数' Z* u; ^; ^7 v1 ]0 b! y
{
' b2 K9 X+ v( Q. v5 Y0 X: J tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加 注意是负数相加
4 k/ P2 R7 w) _9 S tree[parseInt(b1/aa)][b1%aa]=a1; //b树成为a树的子树,b的根b1直接指向a;0 W- ]/ g& ?0 L" m
}
6 X! T% Q2 y3 ]' s8 a else2 Q" e. b0 z# e9 v! n* F
{" \0 ]8 ?$ ^: g6 u& R5 O
tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];* N9 u# K& S6 B6 q
tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树
* T, [# r! s+ l0 D2 s }# S7 V& n5 F$ z B6 {5 v. q
}
6 k3 O3 Z, _3 P }, z- e6 q$ r% C5 g l5 `) t
$ G- Z6 S0 W: M0 U1 l5 o function drawline(a,b)//划线,要判断是上下还是左右" o% [/ ~$ A+ k& \( ^1 ^
{% }) U6 j& e: }! ~
3 w: l7 `% i( \6 r+ ~ r5 y var x1=parseInt(a/aa);
5 D# T3 }9 O) y( t- ^! i4 K var y1=a%aa;
2 `, a+ s( {: S' M, a" v var x2=parseInt(b/aa);; D' @. G) a# L: I0 ]: b
var y2=b%aa; + b& t- R" H/ `/ R" Q1 i
var x3=(x1+x2)/2;+ a+ G: A8 n& [
var y3=(y1+y2)/2;2 W. [3 _: V4 J' C: q
if(x1-x2==1||x1-x2==-1)//左右方向的点 需要上下划线
0 U: m& {1 ^' { U# w) ` {2 W" b7 \% m& [8 d j
//alert(x1);+ |6 p; [* S4 k5 X: G
// context.beginPath();
% `+ [" A. I6 ^' x+ v; ^6 q% _ context.strokeStyle = 'white';
9 w. J/ ?0 o2 `& e // context.moveTo(30+x3*30,y3*30+15);//
# P& l& E0 m$ Z // context.lineTo(30+x3*30,y3*30+45);5 b# o) Z% O6 F' p
context.clearRect(29+x3*30, y3*30+16,2,28);
, n) q, c$ ?: ~* d& G // context.stroke(); z4 n" b/ ^3 @- m3 Y5 `+ B
}& D- c, D; \" U7 d4 _) o
else
I+ `1 R) F) U {0 j. L! ^" G1 X& Z3 q* b- a: i$ M
// context.beginPath();
- C8 u5 n J+ P0 _1 U# F context.strokeStyle = 'white';& Z; C/ l: w2 A" C* u# H9 [
// context.moveTo(x3*30+15,30+y3*30);//
2 o; s" O8 H! W! s // context.lineTo(45+x3*30,30+y3*30);2 ^" ]+ G' g# i+ z- R8 W5 ?
context.clearRect(x3*30+16, 29+y3*30,28,2);
: \; { ~2 G/ f% d, X) ? // context.stroke();" H$ t& U6 j% h, d8 G! }; c; b
}
7 s! i3 d9 R# t( X# n# H }
9 {. M/ Z; a( w* b8 t3 \( y! F
2 U; v+ M2 l$ H0 d4 w while(search(0)!=search(aa*aa-1))//主要思路
$ x2 _7 |7 I: ^$ v& ]6 E- T+ ?/ w {1 c+ s8 g4 c- l! G' W6 C
var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
4 j0 s5 I$ \$ f/ \ var neihbour=getnei(num);
9 s9 A( G$ G, m+ D* S if(search(num)==search(neihbour)){continue;}: C9 x& W5 k1 C! j
else//不在一个上
% ^$ V- ]$ f9 k& U {
- g9 g+ D9 H2 H9 s isling[num][neihbour]=1;isling[neihbour][num]=1;
' w/ {; x% L+ ~ drawline(num,neihbour);//划线
1 p) Q$ H6 D) J: _- J union(num,neihbour);1 r: Z' p# m: _% U% a4 U' a6 U
: ~# k: B2 d4 {3 ?0 D
}
5 m, G+ i1 D m5 z5 h }+ e3 K' N9 G0 O3 M" ~: ~6 X
</script>
) O+ r7 U8 @! {* s2 @/ [</html>
0 q0 I- z9 R/ }/ h5 K) `) ?5 w& h @ j( y* g* i
, }4 w5 o- p( r6 p6 B. D* O% t
实现效果: }6 ]/ d: D/ t- c, K, ^
, x" m1 X; B# q) ~, W
2 Y9 Q# I' \* k# a' Q. d) q8 `1 T- l2 t7 [% p% ~' i: W+ _
$ h0 U* ^/ G7 m1 v
方块移动
/ L% r; K- h, X( Q n' M4 j! P; q, L' H$ N' g
这部分我采用的方法不是动态真的移动,而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉,在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除,可以根据像素大小精准擦除。9 x6 @2 Q2 \8 t$ I* U
7 |$ Z9 f3 [$ x# r5 w; J$ `0 c
另外,再移动中要注意不能穿墙、越界。那么怎么判断呢?很好办,我们再前面会判断两个格子是否联通,如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组), j. p% k8 n6 Z7 S3 y: M$ o
0 z( e% i. m* m: H! X6 _# z另外,事件的监听上下左右查一查就可以得到,添加按钮对一些事件监听,这些不是最主要的。
, L! U- |' |- g7 t/ R; L$ l0 W: Z, U' Y. k* d* Z
为了丰富游戏可玩性,将方法封装,可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外,如果写成动态存库那就更好了。
# G1 ?" Q" q J) h! |9 Q/ m
) ^4 c& j* {+ T' e5 Q) {1 G3 ~1 ?- i5 r9 p$ c$ A
: G' J" a b) H
————————————————4 N6 s/ q$ P, \7 @8 e' g
版权声明:本文为CSDN博主「Big sai」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。2 c. W" R5 k2 q& V6 `! R {
原文链接:https://blog.csdn.net/qq_40693171/article/details/100716766
* V# o# q7 {8 X8 \& Y. @. ~8 M
0 V" N I7 ], M7 h, F" I3 ^5 q
! X9 P Z: Y0 b" e Z |
zan
|