70 lines
2.1 KiB
Go
70 lines
2.1 KiB
Go
package main
|
|
|
|
import (
|
|
"log"
|
|
"math/rand"
|
|
)
|
|
|
|
// The code for generating mazes was copied and adapted from the following page:
|
|
// https://stackoverflow.com/questions/75563271/stuck-on-recursive-division-maze
|
|
|
|
func fillMazeRow(grid [][]bool, row, left, right int) {
|
|
for left <= right {
|
|
grid[row][left] = true
|
|
left++
|
|
}
|
|
}
|
|
|
|
func fillMazeCol(grid [][]bool, col, top, bottom int) {
|
|
for top <= bottom {
|
|
grid[top][col] = true
|
|
top++
|
|
}
|
|
}
|
|
|
|
func divideMaze(grid [][]bool, top, bottom, left, right int) {
|
|
// Check base case: if just one corridor, then there's nothing to divide
|
|
if bottom-top <= 2 || right-left <= 2 {
|
|
return
|
|
}
|
|
// Make the probability equal for all possible dividing-wall positions
|
|
// irrespective of their direction.
|
|
// A wall is always at an even index, not 0
|
|
choice := rand.Intn((bottom-top+right-left)/2-2)*2 + 2
|
|
if choice >= bottom-top { // The wall will be vertical
|
|
splitCol := choice - (bottom - top) + left + 2
|
|
fillMazeCol(grid, splitCol, top, bottom)
|
|
// Create a hole (always at an odd index):
|
|
grid[rand.Intn((bottom-top)/2)*2+1+top][splitCol] = false
|
|
// Recur on the two created areas
|
|
divideMaze(grid, top, bottom, left, splitCol)
|
|
divideMaze(grid, top, bottom, splitCol, right)
|
|
} else { // The wall will be horizontal
|
|
splitRow := choice + top
|
|
fillMazeRow(grid, splitRow, left, right)
|
|
// Create a hole (always at an odd index):
|
|
grid[splitRow][rand.Intn((right-left)/2)*2+1+left] = false
|
|
// Recur on the two created areas
|
|
divideMaze(grid, top, splitRow, left, right)
|
|
divideMaze(grid, splitRow, bottom, left, right)
|
|
}
|
|
}
|
|
|
|
func newMaze(width, height int) [][]bool {
|
|
if (height-2)%2 != 1 || (width-2)%2 != 1 {
|
|
log.Fatal("Grid dimensions should be odd and greater than 1")
|
|
}
|
|
// Create grid with no walls
|
|
grid := make([][]bool, height)
|
|
for y := range grid {
|
|
grid[y] = make([]bool, width)
|
|
}
|
|
// Build surrounding walls
|
|
fillMazeRow(grid, 0, 0, width-1)
|
|
fillMazeRow(grid, height-1, 0, width-1)
|
|
fillMazeCol(grid, 0, 0, height-1)
|
|
fillMazeCol(grid, width-1, 0, height-1)
|
|
// Main algorithm
|
|
divideMaze(grid, 0, height-1, 0, width-1)
|
|
return grid
|
|
}
|