-
Notifications
You must be signed in to change notification settings - Fork 4
/
maze.go
108 lines (94 loc) · 1.72 KB
/
maze.go
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
// generates a maze based on the dfs algorithm
package main
import (
"flag"
"fmt"
"math/rand"
"os"
"strconv"
"time"
)
func main() {
flag.Parse()
if flag.NArg() != 2 {
usage()
}
w, h := atoi(flag.Arg(0)), atoi(flag.Arg(1))
rand.Seed(time.Now().UnixNano())
g := gendfs(w, h)
output(g, w, h)
}
func atoi(s string) int {
v, err := strconv.Atoi(s)
if err != nil {
fmt.Fprintln(os.Stderr, err)
os.Exit(1)
}
return v
}
func usage() {
fmt.Fprintf(os.Stderr, "usage: w h\n")
os.Exit(1)
}
func output(g [][]uint8, w, h int) {
fmt.Print(" ")
for i := 0; i < 2*w-1; i++ {
fmt.Print("_")
}
fmt.Print("\n")
for y := 0; y < h; y++ {
fmt.Print("|")
for x := 0; x < w; x++ {
if g[y][x]&S != 0 {
fmt.Print(" ")
} else {
fmt.Print("_")
}
if g[y][x]&E != 0 {
if (g[y][x]|g[y][x+1])&S != 0 {
fmt.Print(" ")
} else {
fmt.Print("_")
}
} else {
fmt.Print("|")
}
}
fmt.Print("\n")
}
}
const (
N = 1 << iota
S
E
W
)
var (
DX = []int{E: 1, W: -1, N: 0, S: 0}
DY = []int{E: 0, W: 0, N: -1, S: 1}
OPPOSITE = []uint8{E: W, W: E, N: S, S: N}
)
func gendfs(w, h int) [][]uint8 {
p := make([]uint8, w*h)
g := make([][]uint8, h)
for i := range g {
g[i] = p[i*w : (i+1)*w]
}
dfs(g, 0, 0)
return g
}
func dfs(g [][]uint8, cx, cy int) {
dir := [4]uint8{N, S, E, W}
p := rand.Perm(4)
for i := range p {
dir[i], dir[p[i]] = dir[p[i]], dir[i]
}
for _, d := range dir {
nx, ny := cx+DX[d], cy+DY[d]
if 0 <= ny && ny < len(g) && 0 <= nx && nx < len(g[ny]) && g[ny][nx] == 0 {
g[cy][cx] |= d
g[ny][nx] |= OPPOSITE[d]
dfs(g, nx, ny)
}
}
}