引言

迷宫生成是计算机科学中一个经典的问题，常用于算法教学和游戏开发。本文将介绍如何使用 Go 语言和 Ebiten 游戏引擎实现一个基于深度优先搜索（DFS）的随机迷宫生成算法，并通过可视化的方式展示迷宫的生成过程。

技术栈

• Go 语言：一种高效、简洁的编程语言，适合实现算法和并发任务。
• Ebiten：一个轻量级的 2D 游戏引擎，适合快速开发简单的图形应用程序。
• 深度优先搜索（DFS）：一种经典的图遍历算法，用于生成随机迷宫。

算法原理

深度优先搜索（DFS）

DFS 是一种用于遍历或搜索树或图的算法。在迷宫生成中，我们可以将迷宫看作一个图，每个块是一个节点，墙是节点之间的边。DFS 通过随机选择邻居节点并打破墙来生成迷宫。

栈回溯

为了确保迷宫生成的完整性，我们使用栈来记录访问路径。当当前块没有未访问的邻居时，通过栈回溯到上一个未完全探索的块，继续生成迷宫。

代码实现

package mainimport ("image/color""math/rand""os""time""github.com/hajimehoshi/ebiten/v2""github.com/hajimehoshi/ebiten/v2/vector"
)const (N            int     = 20  // 迷宫的行数和列数BlockSize    int     = 50  // 每个迷宫块的大小（像素）WindowWidth  int     = N*BlockSize + 2*int(WW)  // 窗口宽度WindowHeight int     = N*BlockSize + 2*int(WW)  // 窗口高度WW           float32 = 2   // 墙的宽度（像素）BS           float32 = float32(BlockSize)  // 块大小的浮点数表示
)// Pos 结构体表示一个二维坐标
type Pos struct {X, Y int
}// Dirs 数组表示四个可能的移动方向（上、左、右、下）
var Dirs [4]Pos = [4]Pos{Pos{0, -1}, Pos{-1, 0}, Pos{1, 0}, Pos{0, 1}}// Game 结构体表示游戏的状态
type Game struct {T     int          // 当前已访问的块数P     Pos          // 当前的位置Walls [N][N][4]bool // 记录每个块的四面墙是否存在IsVis [N][N]bool   // 记录每个块是否被访问过Stack []Pos        // 栈，用于记录访问路径
}// Update 是 Ebiten 游戏循环中的更新函数，每一帧调用一次
func (g *Game) Update() error {SystemFunction()  // 处理系统功能（如退出）if g.T < N*N {    // 如果还有未访问的块g.Next()  // 生成下一个块}return nil
}// Draw 是 Ebiten 游戏循环中的绘制函数，每一帧调用一次
func (g *Game) Draw(screen *ebiten.Image) {g.DrawWalls(screen)  // 绘制迷宫的墙
}// Layout 设置游戏窗口的布局
func (g *Game) Layout(outsideWidth, outsideHeight int) (int, int) {return outsideWidth, outsideHeight
}func main() {ebiten.SetWindowTitle("maze")  // 设置窗口标题ebiten.SetWindowSize(WindowWidth, WindowHeight)  // 设置窗口大小game := &Game{P:     Pos{rand.Intn(N), rand.Intn(N)},  // 随机选择一个起始位置Stack: make([]Pos, 0),  // 初始化栈}if err := ebiten.RunGame(game); err != nil {  // 运行游戏panic(err)}
}// SystemFunction 处理系统功能，如退出游戏
func SystemFunction() {if ebiten.IsKeyPressed(ebiten.KeyEscape) {  // 如果按下 ESC 键os.Exit(0)  // 退出程序}
}// DrawWalls 绘制迷宫的墙
func (g *Game) DrawWalls(screen *ebiten.Image) {if g.T < N*N {  // 如果还有未访问的块// 绘制当前块的位置（红色方块）vector.DrawFilledRect(screen, float32(g.P.X)*BS, float32(g.P.Y)*BS, BS, BS, color.RGBA{255, 0, 0, 255}, true)}// 遍历所有块，绘制墙for i := 0; i < N; i++ {for j := 0; j < N; j++ {if !g.Walls[i][j][0] {  // 如果上墙存在vector.DrawFilledRect(screen, float32(i)*BS, float32(j)*BS, BS, WW, color.White, true)}if !g.Walls[i][j][1] {  // 如果左墙存在vector.DrawFilledRect(screen, float32(i)*BS, float32(j)*BS, WW, BS, color.White, true)}if !g.Walls[i][j][2] {  // 如果右墙存在vector.DrawFilledRect(screen, float32(i+1)*BS, float32(j)*BS, WW, BS, color.White, true)}if !g.Walls[i][j][3] {  // 如果下墙存在vector.DrawFilledRect(screen, float32(i)*BS, float32(j+1)*BS, BS, WW, color.White, true)}}}
}// Next 生成迷宫的下一个块
func (g *Game) Next() {// check 函数检查给定的坐标是否在迷宫范围内且未被访问过check := func(x, y int) bool {return x >= 0 && x < N && y >= 0 && y < N && !g.IsVis[x][y]}// 标记当前块为已访问if !g.IsVis[g.P.X][g.P.Y] {g.IsVis[g.P.X][g.P.Y] = trueg.T++}// 查找当前块的所有未访问邻居var neighbors []intfor i := 0; i < 4; i++ {if check(g.P.X+Dirs[i].X, g.P.Y+Dirs[i].Y) {neighbors = append(neighbors, i)}}if len(neighbors) > 0 {// 如果有未访问的邻居，随机选择一个方向d := neighbors[rand.Intn(len(neighbors))]g.Stack = append(g.Stack, g.P)  // 将当前位置压入栈g.Walls[g.P.X][g.P.Y][d] = true  // 打破当前块的墙g.P.X += Dirs[d].X  // 移动到邻居块g.P.Y += Dirs[d].Yg.Walls[g.P.X][g.P.Y][3-d] = true  // 打破邻居块的对应墙} else if len(g.Stack) > 0 {// 如果没有未访问的邻居，回溯到上一个块g.P = g.Stack[len(g.Stack)-1]  // 弹出栈顶元素g.Stack = g.Stack[:len(g.Stack)-1]}
}