lua写A星算法

以下是一个简单的 Lua 实现 A* 算法的示例代码：

-- 定义节点结构体
local Node = {
    x = 0, -- 节点的 x 坐标
    y = 0, -- 节点的 y 坐标
    g = 0, -- 从起点到当前节点的实际代价
    h = 0, -- 从当前节点到目标节点的估计代价
    f = 0, -- f = g + h
    parent = nil, -- 父节点
}

-- 计算曼哈顿距离
local function manhattanDistance(node, target)
    return math.abs(node.x - target.x) + math.abs(node.y - target.y)
end

-- A* 算法
local function aStar(start, target, map)
    -- 初始化 open 和 close 列表
    local open = {}
    local close = {}

    -- 将起点加入 open 列表
    table.insert(open, start)

    while #open > 0 do
        -- 选取 f 值最小的节点
        local current = open[1]
        for i = 2, #open do
            if open[i].f < current.f then
                current = open[i]
            end
        end

        -- 如果当前节点为目标节点，则返回路径
        if current.x == target.x and current.y == target.y then
            local path = {}
            while current.parent ~= nil do
                table.insert(path, 1, current)
                current = current.parent
            end
            table.insert(path, 1, start)
            return path
        end

        -- 将当前节点从 open 列表中移除，并加入 close 列表
        for i = #open, 1, -1 do
            if open[i].x == current.x and open[i].y == current.y then
                table.remove(open, i)
                break
            end
        end
        table.insert(close, current)

        -- 遍历当前节点的邻居节点
        local neighbors = {}
        if map[current.x - 1] and map[current.x - 1][current.y] then
            table.insert(neighbors, map[current.x - 1][current.y])
        end
        if map[current.x + 1] and map[current.x + 1][current.y] then
            table.insert(neighbors, map[current.x + 1][current.y])
        end
        if map[current.x][current.y - 1] then
            table.insert(neighbors, map[current.x][current.y - 1])
        end
        if map[current.x][current.y + 1] then
            table.insert(neighbors, map[current.x][current.y + 1])
        end

        for _, neighbor in ipairs(neighbors) do
            -- 如果邻居节点已经在 close 列表中，则忽略
            local isInClose = false
            for i = 1, #close do
                if close[i].x == neighbor.x and close[i].y == neighbor.y then
                    isInClose = true
                    break
                end
            end
            if isInClose then
                goto continue
            end

            -- 如果邻居节点不可通行，则忽略
            if not neighbor.walkable then
                goto continue
            end

            -- 计算邻居节点的实际代价
            local g = current.g + 1

            -- 如果邻居节点不在 open 列表中，则添加到 open 列表
            local isInOpen = false
            for i = 1, #open do
                if open[i].x == neighbor.x and open[i].y == neighbor.y then
                    isInOpen = true
                    break
                end
            end
            if not isInOpen then
                neighbor.parent = current
                neighbor.g = g
                neighbor.h = manhattanDistance(neighbor, target)
                neighbor.f = g + neighbor.h
                table.insert(open, neighbor)
            else
                -- 如果邻居节点已经在 open 列表中，则更新 f 值和父节点
                if g < neighbor.g then
                    neighbor.parent = current
                    neighbor.g = g
                    neighbor.f = g + neighbor.h
                end
            end

            ::continue::
        end
    end

    -- 没有找到路径，返回空表
    return {}
end

在使用该算法时，需要先定义地图和起点、目标点的位置。地图可以用一个二维数组来表示，每个元素表示一个节点，包含节点的 x、y 坐标和是否可通行等信息。下面是一个简单的示例：

local map = {
    { {x=1, y=1, walkable=true}, {x=1, y=2, walkable=true}, {x=1, y=3, walkable=true} },
    { {x=2, y=1, walkable=true}, {x=2, y=2, walkable=false}, {x=2, y=3, walkable=true} },
    { {x=3, y=1, walkable=true}, {x=3, y=2, walkable=true}, {x=3, y=3, walkable=true} },
}

local start = map[1][1]
local target = map[3][3]

local path = aStar(start, target, map)

该示例中，起点为地图左上角节点，目标点为地图右下角节点。节点的 `walkable` 属性表示是否可通行，其中 `false` 表示不可通行。算法返回的结果是一个包含路径节点的数组，按顺序表示从起点到目标点的路径。