go-maze/maze/maze.go

package maze

import (
	"errors"
	"math/rand/v2"
)

// Grid represents a maze as a matrix of cells.
// A value of 0 is a wall and 1 is a walkable path.
type Grid [][]int

const GOLDEN_RATION_BIT_MIXER = 0x9e3779b97f4a7c15

var (
	// ErrInvalidDimensions is returned when width or height are not positive.
	ErrInvalidDimensions = errors.New("maze dimensions must be greater than zero")
	// ErrInvalidGrid is returned when a maze grid is empty or malformed.
	ErrInvalidGrid = errors.New("maze grid must be non-empty and rectangular")
	// ErrNoEntranceExit is returned when the maze has no valid top entrance or bottom exit.
	ErrNoEntranceExit = errors.New("maze grid must contain a top entrance and bottom exit")
	// ErrNoPath is returned when no path exists between entrance and exit.
	ErrNoPath = errors.New("no path exists between maze entrance and exit")
)

// Generate creates a maze grid with the given width and height.
//
// The returned grid uses 0 for walls and 1 for open cells.
// The algorithm is randomized depth-first carving with one entrance on the top border
// and one exit on the bottom border.
func Generate(width, height int) (Grid, error) {
	return generate(width, height, rand.IntN)
}

// GenerateWithSeed creates a maze grid with deterministic randomness.
//
// The same width, height, and seed always produce the same maze.
func GenerateWithSeed(width, height int, seed uint64) (Grid, error) {
	rng := rand.New(rand.NewPCG(seed, seed^GOLDEN_RATION_BIT_MIXER))
	return generate(width, height, rng.IntN)
}

func generate(width, height int, intN func(int) int) (Grid, error) {
	if width <= 0 || height <= 0 {
		return nil, ErrInvalidDimensions
	}

	cells := make([]int, width*height)
	grid := make(Grid, height)
	for y := 0; y < height; y++ {
		rowStart := y * width
		grid[y] = cells[rowStart : rowStart+width]
	}

	if width < 3 || height < 3 {
		return grid, nil
	}

	startX, startY := 1, 1
	grid[startY][startX] = 1

	stackX := make([]int, 1, width*height/2)
	stackY := make([]int, 1, width*height/2)
	stackX[0], stackY[0] = startX, startY

	// Depth-first backtracking carve:
	// grow the maze from the current cell into a random unvisited neighbor,
	// and backtrack when no further expansion is possible.
	for len(stackX) > 0 {
		last := len(stackX) - 1
		x, y := stackX[last], stackY[last]
		dirs := shuffledDirections(intN)

		carved := false
		for _, d := range dirs {
			dx, dy := directionDelta(d)
			nx, ny := x+dx, y+dy
			if nx <= 0 || nx >= width-1 || ny <= 0 || ny >= height-1 {
				continue
			}
			if grid[ny][nx] == 1 {
				continue
			}

			grid[y+dy/2][x+dx/2] = 1
			grid[ny][nx] = 1
			stackX = append(stackX, nx)
			stackY = append(stackY, ny)
			carved = true
			break
		}

		if !carved {
			stackX = stackX[:last]
			stackY = stackY[:last]
		}
	}

	// Choose a top-border entrance that connects to an already carved cell.
	topChoices := make([]int, 0, width/2)
	for x := 1; x < width-1; x++ {
		if grid[1][x] == 1 {
			topChoices = append(topChoices, x)
		}
	}
	if len(topChoices) > 0 {
		entranceX := topChoices[intN(len(topChoices))]
		grid[0][entranceX] = 1
	}

	// Choose a bottom-border exit that connects to an already carved cell.
	bottomChoices := make([]int, 0, width/2)
	for x := 1; x < width-1; x++ {
		if grid[height-2][x] == 1 {
			bottomChoices = append(bottomChoices, x)
		}
	}
	if len(bottomChoices) > 0 {
		exitX := bottomChoices[intN(len(bottomChoices))]
		grid[height-1][exitX] = 1
	}

	return grid, nil
}

// Solve finds a path from the top entrance to the bottom exit in a maze.
//
// It returns a matrix with the same dimensions as the input grid, where true
// marks cells that belong to the computed path.
func Solve(grid Grid) ([][]bool, error) {
	width, height, err := validateGrid(grid)
	if err != nil {
		return nil, err
	}

	startX := -1
	endX := -1
	for x := 0; x < width; x++ {
		if grid[0][x] == 1 {
			startX = x
			break
		}
	}
	for x := 0; x < width; x++ {
		if grid[height-1][x] == 1 {
			endX = x
			break
		}
	}
	if startX == -1 || endX == -1 {
		return nil, ErrNoEntranceExit
	}

	start := startX
	end := (height-1)*width + endX
	parent := make([]int, width*height)
	for i := range parent {
		parent[i] = -1
	}

	visited := make([]bool, width*height)
	queue := make([]int, 1, width*height)
	queue[0] = start
	visited[start] = true

	dx := [4]int{0, 1, 0, -1}
	dy := [4]int{-1, 0, 1, 0}

	// Breadth-first search from entrance to exit while recording parent links
	// so the shortest path can be reconstructed afterward.
	found := false
	for head := 0; head < len(queue); head++ {
		idx := queue[head]
		if idx == end {
			found = true
			break
		}

		x := idx % width
		y := idx / width
		for i := 0; i < 4; i++ {
			nx := x + dx[i]
			ny := y + dy[i]
			if nx < 0 || nx >= width || ny < 0 || ny >= height {
				continue
			}
			if grid[ny][nx] == 0 {
				continue
			}

			nIdx := ny*width + nx
			if visited[nIdx] {
				continue
			}
			visited[nIdx] = true
			parent[nIdx] = idx
			queue = append(queue, nIdx)
		}
	}

	if !found {
		return nil, ErrNoPath
	}

	// Reconstruct the path by following parent pointers backward from exit to entrance.
	pathCells := make([]bool, width*height)
	for idx := end; idx != -1; idx = parent[idx] {
		pathCells[idx] = true
		if idx == start {
			break
		}
	}

	// Expose the flat path buffer as a 2D matrix aligned with the maze grid.
	path := make([][]bool, height)
	for y := 0; y < height; y++ {
		rowStart := y * width
		path[y] = pathCells[rowStart : rowStart+width]
	}

	return path, nil
}

func validateGrid(grid Grid) (width, height int, err error) {
	height = len(grid)
	if height == 0 {
		return 0, 0, ErrInvalidGrid
	}
	width = len(grid[0])
	if width == 0 {
		return 0, 0, ErrInvalidGrid
	}
	for _, row := range grid {
		if len(row) != width {
			return 0, 0, ErrInvalidGrid
		}
	}
	return width, height, nil
}

func directionDelta(direction uint8) (dx, dy int) {
	switch direction {
	case 0:
		return 0, -2
	case 1:
		return 2, 0
	case 2:
		return 0, 2
	default:
		return -2, 0
	}
}

func shuffledDirections(intN func(int) int) [4]uint8 {
	dirs := [4]uint8{0, 1, 2, 3}
	for i := 3; i > 0; i-- {
		j := intN(i + 1)
		dirs[i], dirs[j] = dirs[j], dirs[i]
	}
	return dirs
}