- 在线时间
- 1630 小时
- 最后登录
- 2024-1-29
- 注册时间
- 2017-5-16
- 听众数
- 82
- 收听数
- 1
- 能力
- 120 分
- 体力
- 565547 点
- 威望
- 12 点
- 阅读权限
- 255
- 积分
- 174887
- 相册
- 1
- 日志
- 0
- 记录
- 0
- 帖子
- 5313
- 主题
- 5273
- 精华
- 3
- 分享
- 0
- 好友
- 163
TA的每日心情 | 开心
2021-8-11 17:59 |
|---|
签到天数: 17 天 [LV.4]偶尔看看III 网络挑战赛参赛者 网络挑战赛参赛者 - 自我介绍
- 本人女，毕业于内蒙古科技大学，担任文职专业，毕业专业英语。
 群组: 2018美赛大象算法课程 群组: 2018美赛护航培训课程 群组: 2019年 数学中国站长建 群组: 2019年数据分析师课程 群组: 2018年大象老师国赛优 |
- n) }4 j" {9 F( ^0 e z我花了一夜用数据结构给女朋友写个H5走迷宫游戏
+ G8 k% e3 r/ q1 u+ K文章目录5 w( q+ n) q% g* i$ o+ d* }
4 g6 z1 B( S! u; D( J! K ~
起因" r& e: a* K9 \8 S: x m
分析
# H& p# b& u7 H画线(棋盘)
2 c3 |5 g% M d* v3 b画迷宫
3 [9 J: e6 K9 {方块移动- o p7 P& ?) h# o
结语
' t8 C* C& s3 [! L5 @% j先看效果图(在线电脑尝试地址http://biggsai.com/maze.html)：' v$ p! J$ b" F
% x C3 h- u; B' k/ e3 e7 n/ F6 @, ?/ G7 }2 D& d$ S. H* S1 d: v4 l
起因
0 i) q4 G8 _! h. N+ }
3 m: j& O2 e Q' |' ~% {5 O
v5 M. H3 L/ ~又到深夜了，我按照以往在公众号写着数据结构！这占用了我大量的时间！我的超越妹妹严重缺乏陪伴而 怨气满满！3 P$ J$ G4 {! ]" r# |( E1 C
! v& o) e4 [0 S, }. x超越妹妹时常埋怨，认为数据结构这么抽象难懂的东西没啥作用，常会问道：天天写这玩意，有啥作用。而我答道：能干事情多了，比如写个小游戏啥的！
. N i8 [. ?* C: Q# J5 y% e
, B0 [/ {6 Q4 ?; d6 f5 e; d# `0 _: r当我码完字准备睡觉时：写不好别睡觉！
6 E( z0 C1 A% M5 l6 }) N4 I% J# d, P7 @4 J# L
) Y( @, y, W4 m6 p5 T2 W# S分析$ Q; a! Y' i) [2 N2 ^
' A9 F, R9 O* Q4 f1 q, _# R t) [: Q
如果用数据结构与算法造出东西来呢？
( m7 N# \* ?$ @4 M, I1 ~
7 u1 q& X s, v: p$ r什么东西简单容易呢？我百度一下，我靠，这个鸟游戏原来不好搞啊，得接触一堆不熟悉的东西，搞不来搞不来。
, F ]8 i6 c, T+ O" }8 ^3 N有了(灵光一闪)，写个猜数字游戏，问他加减乘除等于几。
5 ?8 R9 b# S9 O' O( g( D; ~5 r' d8 p N' |
超越妹妹又不是小孩子，糊弄不过去。
/ n% H4 o2 Z& M$ a& ?- l9 H3 r经过一番折腾，终于在半夜12点确定写迷宫小游戏了。大概弄清楚其中的几个步骤。' _9 Q( S( k$ o0 c5 i7 X3 A
, _7 D2 Q" ^9 ? k4 {1 C大概是：
, [, i3 T; W0 ^6 S% x
0 w+ h& i- }' k( d: U% k画线—>画迷宫(擦线)—>方块移动、移动约束(不出界不穿墙)—>完成游戏。& H# k- R- n/ A9 Z4 ~8 a x2 n. K
画线(棋盘)
- k" b) X) `! q- d1 U
& S) o% G7 u0 ?( M: I" ?6 s对于html+js(canvas)画的东西，之前学过javaswing应该有点映像。在html中有个canvas 的画布，可以在上面画一些东西和声明一些监听(键盘监听)。: t; z( R# c6 D# m3 F" i
* {! v/ z5 }$ S% k. c& L2 g
对于迷宫来说，那些线条是没有属性的，只有位置x,y，你操作这个画布时候，可能和我们习惯的面相对象思维不一样。所以，在你设计的线或者点的时候，记得那个点、线在什么位置，在后续划线还是擦线还是移动的时候根据这个位置进行操作。9 Q0 W, D' A. |% Z9 }; ~* h/ ]/ z
<!DOCTYPE html>/ P0 G* J& X/ J$ E) N/ [- c! r9 G
<html>. v# x: l N1 \; ?* t! `: j
<head>" {; M% z8 _+ r+ [
<title>MyHtml.html</title> ( a4 D( s3 Q* K
</head> 8 \8 X# ?$ w% U5 Z7 G+ ?
<body>- x7 ~; v9 b, |, `$ p
<canvas id="mycanvas" width="600px" height="600px"></canvas>$ e% u. x* s. l+ ]' H [
/ {1 K# g, k) `8 p6 G- w8 k) u. D5 d m* F
</body>; m1 j2 |1 a, Q& \
<script type="text/javascript">
7 Q* p" P) P8 M0 y* M! ]$ z6 y( r& h8 ^! j2 O
var aa=14;
I: O" o1 c: i8 r var chess = document.getElementById("mycanvas");
' h4 s9 O4 J" ]+ P1 t var context = chess.getContext('2d');
$ ~# p, P0 l* Y) z# b( y L" Q& z: w1 z5 d9 [0 R9 u
// var context2 = chess.getContext('2d');% J: r; r; m0 P: [5 i$ u
// context.strokeStyle = 'yellow';& \ S; {. p8 |# V) `7 A% b2 q
var tree = [];//存放是否联通" y( N2 ]. E$ W2 M5 U+ `0 `
var isling=[];//判断是否相连, `' T. c0 r7 P+ g
for(var i=0;i<aa;i++){
' Y% @% k/ n4 I8 r, E7 R1 m$ ] tree=[];) R# L8 w2 \. A2 E0 u5 H! w1 C1 U
for(var j=0;j<aa;j++){
* j: B/ x0 U" j2 E tree[j]=-1;//初始值为03 e7 r4 G" W, V
}
- j, J* r9 |& J } for(var i=0;i<aa*aa;i++){. k9 q' Y, x6 @) U% b
isling=[];
5 P5 u' c3 K3 f# o l for(var j=0;j<aa*aa;j++){: X7 r' y. ]0 [, `0 C0 L2 z2 s
isling[j]=-1;//初始值为0
0 k1 M( {* q4 e' \% S% M/ T }
3 M) s& N9 y& c7 ]4 Y/ V$ _ }7 P- H5 y$ ?4 F- v' g
) K# \8 W5 ?( j2 m! G function drawChessBoard(){//绘画/ e) p7 W4 y7 b& ?
for(var i=0;i<aa+1;i++){
1 K& o- T& d/ C- k2 L context.strokeStyle='gray';//可选区域
! _) P$ Y1 p) \1 a context.moveTo(15+i*30,15);//垂直方向画15根线，相距30px;
! H: J9 ^4 \* G+ H3 a% Y& H3 S context.lineTo(15+i*30,15+30*aa);& m; z H8 ` \7 _& ~; V
context.stroke();
7 M# `5 P1 t% w3 @" f: c# X; Y) S context.moveTo(15,15+i*30);//水平方向画15根线，相距30px;棋盘为14*14；
' k m8 i; K; [$ d, O context.lineTo(15+30*aa,15+i*30);$ }- |* F7 a0 G
context.stroke();
+ [) S& d$ i. g# h& F q6 v1 A- P }
# v: _: L1 a) p, ~1 Q9 y y }! `# z- F- G* i6 M- |
drawChessBoard();//绘制棋盘4 v2 m2 x+ W' F
7 A5 U6 D+ P( i3 @
// var mymap=new Array(36);
5 c2 G- i- R9 |0 N) W: W // for(var i=0;i<36;i++)1 v7 N! A- _+ L9 Q7 q3 q# g; y: z# X
// {mymap=-1;}8 A9 t3 n" X% J1 ]- D7 I7 y* |: s
& S$ a+ K+ P6 X+ b
1 t z9 q/ \$ R, l: W) F </script>
8 g1 @0 q+ A3 s0 H/ ^' ~</html>1 d d& S1 S0 ]9 ~3 N( W" f
3 T7 d4 @1 V+ M( i, M2 t) \
; N4 _% d) B. P9 c$ [3 `
实现效果, B" v% n4 ]4 s3 m' B3 c
$ |4 }2 y0 V3 X8 C1 A
3 [7 j" f2 E6 z# u6 ?, _$ B画迷宫
1 Z# H# a1 V/ p3 Q, R0 P2 J1 |9 c3 a" \/ L' P+ C s& w1 k
随机迷宫怎么生成？怎么搞？一脸懵逼。% B: i. E3 \( {. h v8 f* {: E/ R
' n6 j$ A J1 G( ~1 K+ Q* t( g" g因为我们想要迷宫，那么就需要这个迷宫出口和入口有连通路径，你可能压根不知道迷宫改怎么生成，用的什么算法。小声BB：用并查集(不相交集合)。
2 f7 @: l4 F5 J+ B' g迷宫和不相交集合有什么联系呢？(规则)
* L3 y1 o, `6 ]% N4 E6 R4 [- L! r, x! P) V k& }/ A3 B, y
之前笔者在前面数据结构与算法系列中曾经介绍过并查集(不相交集合)，它的主要功能是森林的合并，不联通的通过并查集能够快速将两个森林合并，并且能够快速查询两个节点是否在同一个森林中！
3 J; |7 z! x$ B而我们的随机迷宫：在每个方格都不联通的情况下，是一个棋盘方格，这也是它的初始状态。而这个节点可以跟邻居可能相连，也可能不相连。我们可以通过并查集实现。
7 x& w1 `+ h6 i0 w( ^4 b }
) l4 Z4 p2 N( _0 \5 z具体思路为：(主要理解并查集)
2 k- Q4 `+ m% k6 O8 E& w2 P- _. @
# ^5 U9 |+ Q- U( o1：定义好不想交集合的基本类和方法（search,union等）/ b }' v/ Z' o
2：数组初始化，每一个数组元素都是一个集合，值为-1
/ K6 J( @! C/ t3：随机查找一个格子（一维数据要转换成二维，有点麻烦），在随机找一面墙（也就是找这个格子的上下左右），还要判断找的格子出没出界。
5 l% T6 z& m" o, T: d具体在格子中找个随机数m——>随机数m在二维中的位置[m/长,m%长]——>这个二维的上下左右随机找一个位置p[m/长+1,m%长]或[m/长-1,m%长]或[m/长,m%长+1]或[m/长,m%长-1]——>判断是否越界: Y, @5 V- k7 e# Y9 x
4：判断两个格子(一维数组编号)是否在一个集合(并查集查找)。如果在，则重新找，如果不在，那么把墙挖去( U0 P; F! r8 z. U; X9 T
5：把墙挖去有点繁琐，需要考虑奇偶判断它那种墙(上下还是左右，还要考虑位置)，然后擦掉。（根据数组转换成真实距离）。具体为找一个节点，根据位置关系找到一维数组的号位用并查集判断是否在一个集合中。# |9 ^9 u: ] b0 Z) v6 \
6：最终得到一个完整的迷宫。直到第一个(1,1)和(n,n)联通停止。虽然采用随机数找墙，但是效果并不是特别差。其中要搞清一维二维数组的关系。一维是真实数据，并查集操作。二维是位置。要搞懂转化！3 `4 O% O3 z% A( w8 M
注意：避免混淆，搞清数组的地址和逻辑矩阵位置。数组从0开始的，逻辑上你自己判断。别搞混淆！
) N/ V" F" d8 y% x" M# G
& ?7 X6 E8 n: E- j2 U主要逻辑为：) u6 a, s& U. \) X
while(search(0)!=search(aa*aa-1))//主要思路
' b+ n; \- d7 D; N {! m2 g" D& ~; N8 ]' z
var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数' V$ T. Q% d1 H$ V O
var neihbour=getnei(num);: V3 S4 }/ s6 ~
if(search(num)==search(neihbour)){continue;}
# @: n1 V: U; a+ W- n+ X else//不在一个上. A- Y& c+ ^" W
{% ?' } b# v* K$ b" R
isling[num][neihbour]=1;isling[neihbour][num]=1;
' m" b) ~+ C0 q9 Y5 O- G5 b5 p drawline(num,neihbour);//划线( w5 O( s# R& t; B. p( M$ C5 `
union(num,neihbour);
$ p$ Q- |7 v1 M. ^9 ?5 F1 Y6 K R, T4 R7 L
}: U @4 v$ j" p2 Z/ y" ^
}
. @+ w2 j. ^- }$ X- G0 d
1 R- N, Q) _3 m! U1 a! }# S9 \: f6 i1 W4 T& R: Y$ m3 E
那么在前面的代码为
$ o* S* I3 b5 z: O1 Y$ w$ K<!DOCTYPE html>
+ [* ^# m W" f& [& T<html>+ w6 Y7 [& Z* }$ O* T6 q
<head>
! f' Z+ v; e. h4 `/ Y" i <title>MyHtml.html</title>
0 H) o, n3 j! M1 t3 V$ {- G- c0 z </head>
2 Q) s9 N6 b( N. x <body>) u* z* s2 l$ k t3 {* z
<canvas id="mycanvas" width="600px" height="600px"></canvas>
/ G5 Q- I0 ?. ?8 c6 e9 U5 x, i$ T& Z, h
</body>) {7 _, ~6 W" \' E
<script type="text/javascript">0 s# _& J: V$ A1 {, n( Y! h& [
//自行添加上面代码
1 x0 k6 c3 u& U6 z. D, `1 @ // var mymap=new Array(36);- P0 g6 z9 X( b; [( U3 V: E
// for(var i=0;i<36;i++)
6 |* {% G7 u( M/ ^ // {mymap=-1;}' Z# R" d, q& A q' S
function getnei(a)//获得邻居号 random
& B8 j o/ x) K0 X {+ \# Q/ J8 G6 P6 t5 o
var x=parseInt(a/aa);//要精确成整数2 n9 O/ i4 j3 O. h* j& v, G
var y=a%aa;
; a$ a2 I! ~) Y t3 h7 l! M# o var mynei=new Array();//储存邻居+ S4 ^8 m3 j' L
if(x-1>=0){mynei.push((x-1)*aa+y);}//上节点
! t+ t: a4 k. g* k0 h6 k if(x+1<14){mynei.push((x+1)*aa+y);}//下节点3 y0 ~& G. H5 M
if(y+1<14){mynei.push(x*aa+y+1);}//有节点
3 }3 t& s7 `9 ~: b% ~5 t( p if(y-1>=0){mynei.push(x*aa+y-1);}//下节点8 _2 S: A" q: k6 f4 ?
var ran=parseInt(Math.random() * mynei.length );
: s( _# z ?+ F0 X, B! L return mynei[ran];: g7 U1 d) s" D6 P5 I ]! r
5 p/ ?0 ^& {# r) z" m
}
. A+ i% N/ d' q9 i4 i9 U7 u function search(a)//找到根节点
( F/ u- c) r2 i- A2 K: d {3 e% r% |* {( h$ R2 h3 u& s$ x
if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点
$ g( [' j+ z2 |% W, u1 ^9 ^ {
/ {; S3 k3 U: X1 e# c return search(tree[parseInt(a/aa)][a%aa]);//不能压缩路径路径压缩
$ k2 O/ q+ W+ `- |! T: k2 g2 e }' M5 H0 Y# [$ Q* P* E2 a, f) R! v
else
9 j' J, E) w) E! L$ v/ E return a;. w) \+ R; s% R% X1 s
}
1 m; `; t) q2 c2 Z function value(a)//找到树的大小0 K6 S) c2 \& f# s9 v' {+ |% T$ `
{
# }3 d# Z& B# f. }. Q' j, K if(tree[parseInt(a/aa)][a%aa]>0)//说明是子节点- G, U$ @6 x. D* Z! x! B
{
2 z2 C4 q: S3 L3 D8 t+ G$ @ return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路径压缩, n! s9 Q( ?8 ?$ t" Y6 U
}
$ c; d( t: {. b) l else
' |1 x, r& g4 ]4 P return -tree[parseInt(a/aa)][a%aa];
^0 z2 J: h. x) e% O }
. P/ ~% S( k$ ]2 B) v2 E function union(a,b)//合并1 H6 `& _3 Y9 w* J8 k0 C
{7 e9 c) A8 y3 @3 |
var a1=search(a);//a根- ]& ~6 M* a* R! J) _
var b1=search(b);//b根: x0 v$ I7 z; ]* O( j
if(a1==b1){}4 M$ c3 G4 l' [4 @5 w! C' n. \8 d* }
else
+ J4 u/ [* w0 z- Y, x$ Y {4 y3 Z1 h6 i$ |
if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//这个是负数()，为了简单减少计算，不在调用value函数
8 s: U% B7 o& R8 U# S7 `$ L {
1 h _& O9 O. k6 j v0 P# Y1 g( T# q, n tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//个数相加 注意是负数相加
0 g# I: G4 i* z tree[parseInt(b1/aa)][b1%aa]=a1; //b树成为a树的子树，b的根b1直接指向a；
4 }' l' J# x- a1 C } `+ N; }6 b( m" w& ^% ~# g
else! ` ~; z9 c" R2 w p
{" [; k, b0 U& n) ]& H2 P
tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];) ?5 y3 G5 i) H1 S, u; `$ ?3 x
tree[parseInt(a1/aa)][a1%aa]=b1;//a所在树成为b所在树的子树
" ]$ y; Y- e* I/ H }5 L, W! O, B, d, E8 z6 x
}# U! C! `4 ~0 |: ?- m: r S8 Q0 B% E
}
# I% S* T! j* d9 c/ p) _1 @2 V2 A5 A" k) K5 o
function drawline(a,b)//划线，要判断是上下还是左右* J! {: I2 X1 c( Z
{
* i t, G; _5 Q8 `" K
3 `% }% r' Q7 v8 X$ ]' I% d var x1=parseInt(a/aa); M2 n$ n" m3 k" D, z/ |- E
var y1=a%aa;) J9 x" e, Y; z+ \
var x2=parseInt(b/aa);9 x% U, H. m) R. ~
var y2=b%aa;
# c% x- t8 y5 w var x3=(x1+x2)/2;. F1 F" V7 x9 s0 K6 w+ W
var y3=(y1+y2)/2;1 A6 X- L D+ h7 S! \" Z1 C
if(x1-x2==1||x1-x2==-1)//左右方向的点 需要上下划线
( G/ E) W$ Z( ~* R8 V# N7 ` {
: R, j6 p4 \% E2 I* s. k //alert(x1);
2 F; m0 @5 W- T; k9 c // context.beginPath();
9 K9 ]# i8 k: ]* k% N M context.strokeStyle = 'white';5 a# Y/ g0 v. i: g1 ~9 V
// context.moveTo(30+x3*30,y3*30+15);//
7 j( a+ j1 D4 h, U/ ~6 ]' Y; N // context.lineTo(30+x3*30,y3*30+45);
7 d9 Y9 {2 j5 \+ |/ n context.clearRect(29+x3*30, y3*30+16,2,28);! f3 z5 p( @2 X7 ]* B7 z
// context.stroke();9 q+ d& r5 }' Z
}% y0 a4 B3 p7 q7 s
else
% s: n+ l! O+ E0 g- p/ \% ]' | {
0 v) x8 k& O* n2 d3 y: W1 r // context.beginPath();
1 G# G9 J( x' B/ R' x9 o context.strokeStyle = 'white';/ p* h# C5 A5 E" A0 @$ H- ]9 p
// context.moveTo(x3*30+15,30+y3*30);//9 E# @( y. y' W2 R/ Y
// context.lineTo(45+x3*30,30+y3*30);
! a) `( T4 B3 ^4 {2 D- [ context.clearRect(x3*30+16, 29+y3*30,28,2);* h2 d1 G) _0 |
// context.stroke();
2 w9 I# t4 \; m* E9 V* H }2 b5 P% K) w+ h1 ^+ q* p
}3 T) t- b. O+ |0 j$ c5 {; f
/ A: P5 K2 A9 Z( {6 s8 [6 |: W5 d0 A
while(search(0)!=search(aa*aa-1))//主要思路6 z8 h* R2 O5 `7 [: v7 y
{
7 D" P, x* P' q+ B2 s( x var num = parseInt(Math.random() * aa*aa );//产生一个小于196的随机数
8 N0 K& s4 r" K4 Z T& q var neihbour=getnei(num);4 e5 d2 y8 Z# X& ~& F
if(search(num)==search(neihbour)){continue;}+ h+ c8 B0 U" i" l' Q0 _
else//不在一个上) d2 `" ?" ^: I
{
+ h8 q- M7 V% [% d isling[num][neihbour]=1;isling[neihbour][num]=1;2 Z3 m3 ~; P* B' `5 b, \# \
drawline(num,neihbour);//划线" _* }1 Z: }" {! {- \
union(num,neihbour);3 O6 ?: j1 S0 }+ n5 O, i
9 c5 O) V& `6 g; _
}/ Z/ W: w }, R9 Q7 T6 ~" V! k; l
}, n3 |& Y* G6 h' N7 Q* z
</script>
" U/ U- W" s, i0 W! X: f. C0 B3 Y</html>
6 W0 d% l0 W2 {& C# p/ n3 X
: t0 R7 k# v( O" A( D: s
# G }6 ?& ~/ o) }3 h实现效果：
6 V7 O6 f4 x3 }' A- V( k3 r2 o0 a. n; A. w, u1 w/ Z+ g) g- U% L
7 c5 g, L7 n1 P) f+ `0 m% ?
9 K+ q3 k; N& v/ _3 f1 e
) a6 K) l3 T+ i; T2 g' [方块移动3 [" D1 A' M& R( \
2 J* Z( Z" Y7 J6 p) }# V! I这部分我采用的方法不是动态真的移动，而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉，在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除，可以根据像素大小精准擦除。
( d2 U+ G, a# [* n" G* Q3 h# Z. i! M* @* I( ]
另外，再移动中要注意不能穿墙、越界。那么怎么判断呢？很好办，我们再前面会判断两个格子是否联通，如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组)' B h0 S8 y# l/ v' P" e S \
0 m1 o9 y' E# Z' {3 u另外，事件的监听上下左右查一查就可以得到，添加按钮对一些事件监听，这些不是最主要的。' K/ h+ V F8 S+ u" V
/ v; I$ H/ U8 c/ _, r/ f为了丰富游戏可玩性，将方法封装，可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外，如果写成动态存库那就更好了。: M! ~$ b+ @* D B- a9 c
) U0 [1 k1 F6 I8 i2 }
6 n. u: F7 v; x {5 ^$ [
! V* `) J! M" x
————————————————
) E2 k/ a w' ]% v* F5 J版权声明：本文为CSDN博主「Big sai」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
3 x; b8 D/ x7 T1 o$ s2 S4 e, N5 `原文链接：https://blog.csdn.net/qq_40693171/article/details/100716766
' U- z9 {4 c U! b" K, S/ y0 ?( s& N* l0 k: `
; o0 a! ]+ L1 W& \9 ] |
zan
|
IP卡
狗仔卡
发表于 2020-4-1 10:57
转播
淘帖
分享
收藏
支持
反对
微信
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
显身卡
