使用lua实现各种算法，先从广度优先搜索开始

萧山财神

接下来我们可以实现一种在2D游戏中常用的算法：广度优先搜索（Breadth-First Search, BFS）。BFS是一种用于图遍历的算法，常用于寻找最短路径、迷宫求解等场景。

以下是用 Lua 实现的广度优先搜索算法：

-- 定义队列结构
Queue = {}
Queue.__index = Queue

function Queue:new()
    local queue = {first = 0, last = -1, items = {}}
    setmetatable(queue, Queue)
    return queue
end

function Queue:enqueue(item)
    self.last = self.last + 1
    self.items[self.last] = item
end

function Queue:dequeue()
    if self.first > self.last then return nil end
    local item = self.items[self.first]
    self.items[self.first] = nil
    self.first = self.first + 1
    return item
end

function Queue:isEmpty()
    return self.first > self.last
end

-- 广度优先搜索算法
function bfs(startX, startY, goalX, goalY, grid)
    local directions = {
        {x = 1, y = 0},
        {x = -1, y = 0},
        {x = 0, y = 1},
        {x = 0, y = -1}
    }

    local queue = Queue:new()
    queue:enqueue({x = startX, y = startY, path = {{x = startX, y = startY}}})
    local visited = {}
    visited[startY] = {}
    visited[startY][startX] = true

    while not queue:isEmpty() do
        local current = queue:dequeue()

        if current.x == goalX and current.y == goalY then
            return current.path
        end

        for _, direction in ipairs(directions) do
            local newX = current.x + direction.x
            local newY = current.y + direction.y

            if grid[newY] and grid[newY][newX] == 0 and (not visited[newY] or not visited[newY][newX]) then
                visited[newY] = visited[newY] or {}
                visited[newY][newX] = true
                local newPath = {table.unpack(current.path)}
                table.insert(newPath, {x = newX, y = newY})
                queue:enqueue({x = newX, y = newY, path = newPath})
            end
        end
    end

    return nil -- 无法找到路径
end

-- 测试广度优先搜索算法
local grid = {
    {0, 1, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 1, 0},
    {0, 1, 0, 0, 0},
    {0, 0, 0, 1, 0}
}

local startX, startY = 1, 1
local goalX, goalY = 5, 5
local path = bfs(startX, startY, goalX, goalY, grid)

if path then
    print("找到路径:")
    for _, node in ipairs(path) do
        print("(", node.x, ",", node.y, ")")
    end
else
    print("无法找到路径")
end

在这个实现中：

1. Queue 结构表示一个队列，包含 enqueue 和 dequeue 方法，用于实现广度优先搜索中的节点管理。
2. bfs 函数实现广度优先搜索算法，接受起点坐标、目标坐标和网格（表示地图）作为输入，返回从起点到目标的路径。
3. 在 bfs 函数中，使用 queue 来存储待访问的节点，并使用 visited 表来记录已访问的节点。通过不断扩展当前节点的邻居节点，直到找到目标节点或无法找到路径。
4. 测试代码定义了一个简单的网格，并调用 bfs 函数进行路径规划，输出找到的路径。

广度优先搜索算法在2D游戏中的迷宫求解、最短路径查找等方面有广泛应用。它能够保证找到最短路径（如果存在），适用于无权图的路径规划。