-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathturtle-maze.html
109 lines (104 loc) · 3.35 KB
/
turtle-maze.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<title>Turtle</title>
</head>
<body>
<script type="text/javascript" src="./js/1px-fix.js"></script>
<script type="text/javascript" src="./js/turtle.js"></script>
<script type="text/javascript" src="./js/demo.js"></script>
<script type="text/javascript">
//meeko中的函数抽出来
const uniformRandInt = (a, b) => {
let num
if (a > b) {
;[a, b] = [b, a]
}
const maxEx = b + 5
do {
num = Math.floor(Math.random() * (maxEx - a) + a)
num -= 4
} while (num < a || num > b)
return num
}
const W = [] // edge
const U = {} // 未分配
const V = {} // 已分配
const [m, n, modVal] = [20, 20, 100]
let count = 0
for (let i = 0; i < m; i++) {
W[i] = []
for (let j = 0; j < n; j++) {
W[i][j] = 1
count++
}
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
//所有距离都是1,可以链接的其他node
U[i * modVal + j + ''] = {
name: i * modVal + j + '',
link: [
(W[i - 1] || [])[j] ? (i - 1) * modVal + j + '' : 0,
W[i][j + 1] ? i * modVal + (j + 1) + '' : 0,
(W[i + 1] || [])[j] ? (i + 1) * modVal + j + '' : 0,
W[i][j - 1] ? i * modVal + (j - 1) + '' : 0
],
pre: [0, 0, 0, 0], //链出开始为空
next: [0, 0, 0, 0], //链入开始为空
connect: []
}
}
}
// 以上初始化结束
V['0'] = U['0']
V['0'].pre[3] = 1 //左入
delete U['0']
for (let i = 0; i < m * n - 1; i++) {
let uArr = Object.keys(U)
let vArr = Object.keys(V)
vArr = vArr.filter(x => {
return V[x].link.some(x => uArr.includes(x)) // 这里可以进行极大优化
})
let r = vArr[uniformRandInt(0, vArr.length - 1)] //vArr.pick()
let r1 = V[r].link[uniformRandInt(0, V[r].link.length - 1)] //V[r].link.pick()
while (r1 === 0 || V[r1]) {
r1 = V[r].link[uniformRandInt(0, V[r].link.length - 1)] // V[r].link.pick()
}
V[r].connect.push(r1)
V[r].next[V[r].link.findIndex(x => x === r1)] = 1
V[r1] = U[r1]
V[r1].pre[V[r1].link.findIndex(x => x === r)] = 1
delete U[r1]
}
V[(m - 1) * modVal + (n - 1) + ''].next[1] = 1 // 最后一个右边出口
let result = {}
Object.keys(V).forEach(x => {
result[V[x].name] = [
V[x].next[0] | V[x].pre[0],
V[x].next[1] | V[x].pre[1],
V[x].next[2] | V[x].pre[2],
V[x].next[3] | V[x].pre[3]
].join(',')
})
let maze = result
let t = new Turtle({ debug: false, animate: 10 }) //关闭debug打印
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
t.setxy(j * 20 - 210, i * 20 - 210)
let dir = maze[i * modVal + j + ''].split(',')
dir[3] === '1' ? t.pu() : t.pd()
t.fd(2).rt(90)
dir[2] === '1' ? t.pu() : t.pd()
t.fd(2).rt(90)
dir[1] === '1' ? t.pu() : t.pd()
t.fd(2).rt(90)
dir[0] === '1' ? t.pu() : t.pd()
t.fd(2).rt(90)
}
}
t.go()
</script>
</body>
</html>