0 收听	2 听众	108 主题

使用lua实现各种算法，先从A*（A-star）算法开始

IP属地：浙江省杭州市

发表于 2024-7-5 16:29:21 | 查看: 133| 回复: 1

接下来我们可以实现A（A-star）算法。A算法是一种用于图搜索的启发式算法，广泛应用于游戏中的路径规划。它结合了广度优先搜索和贪心搜索的优点，通过使用启发式函数来估计从当前节点到目标节点的最短路径。

以下是用 Lua 实现的A*算法：

-- 定义节点结构
Node = {}
Node.__index = Node

function Node:new(x, y, g, h, parent)
    local node = {
        x = x,
        y = y,
        g = g, -- 从起点到当前节点的代价
        h = h, -- 从当前节点到目标节点的估计代价
        f = g + h, -- 总代价
        parent = parent -- 父节点
    }
    setmetatable(node, Node)
    return node
end

-- 曼哈顿距离作为启发式函数
function manhattanDistance(x1, y1, x2, y2)
    return math.abs(x1 - x2) + math.abs(y2 - y1)
end

-- 检查节点是否在列表中
function isInList(list, node)
    for _, n in ipairs(list) do
        if n.x == node.x and n.y == node.y then
            return true
        end
    end
    return false
end

-- 获取节点在列表中的索引
function getNodeIndex(list, node)
    for i, n in ipairs(list) do
        if n.x == node.x and n.y == node.y then
            return i
        end
    end
    return -1
end

-- A*算法函数
function aStar(startX, startY, goalX, goalY, grid)
    local openList = {}
    local closedList = {}
    local startNode = Node:new(startX, startY, 0, manhattanDistance(startX, startY, goalX, goalY), nil)
    table.insert(openList, startNode)

    while #openList > 0 do
        -- 找到f值最小的节点
        table.sort(openList, function(a, b) return a.f < b.f end)
        local currentNode = table.remove(openList, 1)
        table.insert(closedList, currentNode)

        -- 如果到达目标节点
        if currentNode.x == goalX and currentNode.y == goalY then
            local path = {}
            local node = currentNode
            while node do
                table.insert(path, 1, {x = node.x, y = node.y})
                node = node.parent
            end
            return path
        end

        -- 获取邻居节点
        local neighbors = {
            {x = currentNode.x + 1, y = currentNode.y},
            {x = currentNode.x - 1, y = currentNode.y},
            {x = currentNode.x, y = currentNode.y + 1},
            {x = currentNode.x, y = currentNode.y - 1}
        }

        for _, neighbor in ipairs(neighbors) do
            if grid[neighbor.y] and grid[neighbor.y][neighbor.x] and grid[neighbor.y][neighbor.x] == 0 then
                local g = currentNode.g + 1
                local h = manhattanDistance(neighbor.x, neighbor.y, goalX, goalY)
                local neighborNode = Node:new(neighbor.x, neighbor.y, g, h, currentNode)

                if not isInList(closedList, neighborNode) then
                    local index = getNodeIndex(openList, neighborNode)
                    if index == -1 or g < openList[index].g then
                        if index ~= -1 then
                            table.remove(openList, index)
                        end
                        table.insert(openList, neighborNode)
                    end
                end
            end
        end
    end

    return nil -- 无法找到路径
end

-- 测试A*算法
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 = aStar(startX, startY, goalX, goalY, grid)

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

在这个实现中：

Node 结构表示图中的一个节点，包含坐标、代价和父节点等信息。
manhattanDistance 函数计算两个节点之间的曼哈顿距离，作为启发式函数。
isInList 和 getNodeIndex 函数用于检查节点是否在列表中以及获取节点在列表中的索引。
aStar 函数实现A*算法，接受起点坐标、目标坐标和网格（表示地图）作为输入，返回从起点到目标的路径。
在 aStar 函数中，使用 openList 和 closedList 分别表示待访问的节点和已访问的节点。通过不断扩展当前节点的邻居节点，直到找到目标节点或无法找到路径。
测试代码定义了一个简单的网格，并调用 aStar 函数进行路径规划，输出找到的路径。