/
maze.go
182 lines (139 loc) · 5.44 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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
package maze
// visitedCells represents the cells whose numbers are mapped to their respective addresses.
// It is used in creating and navigating through the maze.
var visitedCells = map[int]cellAddress{}
// Dimensions defines the actual number of cells that make up the maze along the vertical and
// the horizontal edges. Length represents the number of the cells along the horizontal
// edge while Width represents the number of the cells along the vertical edge.
type Dimensions struct {
Length int
Width int
StartPosition []int
FinalPosition []int
}
// generateMaze converts the created grid view playing field into a series on paths and walls.
// The Maze is created such that only a single path can exists between the starting point and
// and the goal.
func (config *Dimensions) generateMaze(intensity int) ([][]string, error) {
var neighbors []int
startPos := config.getStartPosition()
finalPos, cellsPath, currentPos := []int{1, startPos}, []int{startPos}, startPos
maze, err := config.createPlayingField(intensity)
if err != nil {
return [][]string{}, err
}
config.StartPosition = config.getCellAddress(startPos).MiddleCenter
visitedCells[currentPos] = config.getCellAddress(currentPos)
cellsPath = append(cellsPath, currentPos)
for len(visitedCells) < (config.Length * config.Width) {
for {
neighbors = config.getPresentNeighbors(currentPos)
if len(neighbors) > 0 {
break
}
cellsPath, currentPos = cellsPath[:len(cellsPath)-1], cellsPath[len(cellsPath)-1]
}
startPos = neighbors[getRandomNo(len(neighbors))]
if _, ok := visitedCells[startPos]; !ok {
visitedCells[startPos] = config.getCellAddress(startPos)
config.createPath(maze[:], currentPos, startPos)
cellsPath = append(cellsPath, startPos)
if len(cellsPath) > finalPos[0] {
finalPos[:][1], finalPos[:][0] = startPos, len(cellsPath)
}
currentPos = startPos
}
}
config.FinalPosition = config.getCellAddress(finalPos[1]).MiddleCenter
return maze[:], config.optimizeMaze(intensity, maze[:])
}
// createPath creates a path on the common wall between the current and the new cell.
// A path is created by replacing the wall characters with the respective number of blank spaces.
// Wall characters are defined by the intensity value used while creating the grid view.
func (config *Dimensions) createPath(maze [][]string, currentCellNo, newCellNo int) {
addr := config.getCellAddress(currentCellNo)
neighbors := config.getCellNeighbors(currentCellNo)
switch newCellNo {
case neighbors.Bottom:
maze[addr.BottomCenter[0]][addr.BottomCenter[1]] = " "
case neighbors.Left:
maze[addr.MiddleLeft[0]][addr.MiddleLeft[1]] = " "
case neighbors.Right:
maze[addr.MiddleRight[0]][addr.MiddleRight[1]] = " "
case neighbors.Top:
maze[addr.TopCenter[0]][addr.TopCenter[1]] = " "
}
}
// getPresentNeighbors returns a slice of the neigboring cells associated with the cell number provided.
// Only neighboring cells with no common paths to others cells that are returned. i.e. Non-Visited Cells.
func (config *Dimensions) getPresentNeighbors(cellNo int) []int {
var (
ok bool
presentCells []int
neighbors = config.getCellNeighbors(cellNo)
)
for _, neighbor := range []int{neighbors.Bottom, neighbors.Left, neighbors.Right, neighbors.Top} {
if _, ok = visitedCells[neighbor]; !ok && neighbor != 0 {
presentCells = append(presentCells, neighbor)
}
}
return presentCells
}
// getStartPosition returns the cell which becomes the maze traversal starting position.
// The starting position can only be a cell along the maze edges i.e. has less than four
// neighbors. When getStartPosition is called, all cells are have no common paths to other cells.
func (config *Dimensions) getStartPosition() int {
var (
neighbors []int
randCellNo int
)
for {
randCellNo = getRandomNo((config.Length * config.Width) + 1)
neighbors = config.getPresentNeighbors(randCellNo)
if len(neighbors) < 4 && randCellNo != 0 {
return randCellNo
}
}
}
// optimizeMaze replaces some wall characters so as the maze can
// be more clear and sharp when printed on the terminal.
func (config *Dimensions) optimizeMaze(intensity int, maze [][]string) error {
var (
addr cellAddress
chars []string
err error
)
// This error will never be caught
if chars, err = getWallCharacters(intensity); err != nil {
panic(err)
}
for cell := 1; cell <= (config.Length * config.Width); cell++ {
addr = config.getCellAddress(cell)
config.replaceChar(addr.BottomRight, chars[2], maze)
config.replaceChar(addr.TopRight, chars[2], maze)
}
return nil
}
// replaceChar switches left and right wall character with a top and bottom wall character.
func (config *Dimensions) replaceChar(point []int, replChar string, maze [][]string) {
elemTop, elemBottom := "", ""
lenTop, lenBottom := false, false
// checks if the top point in relation to the given point can be calculated
if (point[0] - 1) > 0 {
elemTop = maze[point[0]-1][point[1]]
lenTop = true
}
// checks if the bottom point in relation to the given point can be calculated
if (point[0] + 1) <= (config.Width * 2) {
elemBottom = maze[point[0]+1][point[1]]
lenBottom = true
}
switch {
case !lenTop && lenBottom && isSpaceFound(elemBottom):
maze[point[0]][point[1]] = replChar
case lenTop && !lenBottom && isSpaceFound(elemTop):
maze[point[0]][point[1]] = replChar
case lenTop && lenBottom && isSpaceFound(elemBottom) && isSpaceFound(elemTop):
maze[point[0]][point[1]] = replChar
}
}