A*算法 | Lua版本

#! /usr/local/bin/lua
--参考： https://blog.csdn.net/u012234115/article/details/47152137
local kCost1=10; --直移一格消耗
local kCost2=14; --移一格消耗
local openList = {}
local closeList = {}

--初始化地图，用二维矩阵代表地图，1表示障碍物，0表示可通
local maze = {
    {1,1,1,1,1,1,1,1,1,1,1,1},
    {1,0,0,1,1,0,1,0,0,0,0,1},
    {1,0,0,1,1,0,0,0,0,0,0,1},
    {1,0,0,0,0,0,1,0,0,1,1,1},
    {1,1,1,0,0,0,0,0,1,1,0,1},
    {1,1,0,1,0,0,0,0,0,0,0,1},
    {1,0,1,0,0,0,0,1,0,0,0,1},
    {1,1,1,1,1,1,1,1,1,1,1,1}
}
--  F=G+H
--G 表示从起点 A 移动到网格上指定方格的移动耗费 (可沿斜方向移动).
--H 表示从指定的方格移动到终点 B 的预计耗费 (H 有很多计算方法, 本文代码使用简单的欧几里得距离计算方法).
local function calcG(startP, point)
    local extraG = math.abs(point.x-startP.x)+math.abs(point.y-startP.y)==1 and kCost1 or kCost2
    local parentG = (next(point.parent or {})) and point.parent.G or 0
    return parentG + extraG
end

local function calcH(point, endP)
    --用简单的欧几里得距离计算H，这个H的计算是关键，还有很多算法
    return math.sqrt((endP.x-point.x)^2 + (endP.y-point.y)^2)
end

local function calcF(point)
    return point.G + point.H
end

local function getPointString(point)
    return "<"..point.x.. ","..point.y..">"
end

local function isInList(tbl, target)
    for _,v in ipairs(tbl) do
        if target.x == v.x and target.y == v.y then
            return v
        end
    end
    return nil
end

--判断某点是否可以用于下一步判断
local function isCanreach(point, target, ignore)
    --如果目标点超出地图、与当前节点重合、是障碍物、或者在关闭列表中，返回false
    if target.x<1 or target.x>#maze
    or target.y<1 or target.y>#maze[1]
    or maze[target.x][target.y]==1
    or (target.x==point.x and target.y==point.y) then return false end
    if isInList(closeList, target) then
        --print("target in closeList: ".. getPointString(target))
        return false
    end
    --非斜角可以
    if math.abs(point.x-target.x) + math.abs(point.y-target.y) == 1 then return true end

    --斜对角要判断是否绊住
    if maze[point.x][target.y] == 0 and maze[target.x][point.y] == 0 then return true end
    return ignore
end

--获取节点周围的节点
local function getSurroundP(point, ignore)
    local surroundP = {}
    for i=point.x-1, point.x+1 do
        for j=point.y-1, point.y+1 do
            local tmp = {x=i,y=j, G=0, H=0, F=0}
            if isCanreach(point, tmp, ignore)then
                table.insert(surroundP, tmp)
            else
                --print("not search: point:" .. getPointString(point) .. "; target: ".. getPointString(tmp))
            end
        end
    end
    return surroundP
end

local function getLeastFPoint()
    local cur = 1
    local curP = openList[1]
    if not curP then return end
    for i, v in ipairs(openList) do
        if v.F < curP.F then
            curP = v
            cur = i
        end
    end
    return cur,curP
end

local function findPath(startP, endP, ignore)
    table.insert(openList, startP) --置入起点
    while next(openList) do
        local cur, curP = getLeastFPoint()--找到最小的F
        table.remove(openList, cur) --从开启列表中删除
        table.insert(closeList, curP) --放到关闭列表

        --1.找到当前周围八个格中可以通过的格子
        local surroundP = getSurroundP(curP, ignore)
        --print("curP: " .. getPointString(curP).." ####surroundP: "..#surroundP)
        for _, target in ipairs(surroundP) do
            --2,对某一个格子，如果它不在开启列表中，加入到开启列表，设置当前格为其父节点，计算F G H
            if not isInList(openList, target) then
                target.parent = curP
                target.G = calcG(curP, target)
                target.H = calcH(target, endP)
                target.F = calcF(target)

                table.insert(openList, target)
            else
                --3，对某一个格子，它在开启列表中，计算G值, 如果比原来的大, 就什么都不做, 否则设置它的父节点为当前点,并更新G和F
                local tempG = calcG(curP, target)
                if tempG < target.G then
                    target.parent =  curP

                    target.G = tempG
                    target.F = calcF(target)
                end
            end

            for i, v in ipairs(openList) do
                --print("openList: " .. getPointString(v))
            end

            local resP = isInList(openList, endP)
            if resP then
                return resP
            end
        end

    end
    return nil
end

local function GetPath(startP, endP, ignore)
    local result = findPath(startP, endP, ignore)
    local path = {}
    while result do
        table.insert(path, 1, result)
        result = result.parent
    end

    openList = {}
    closeList = {}
    return path
end

print("start findPath.....")
local startP = {x=2, y=2, G=0,H=0,F=0}
local endP = {x=7, y=11, G=0,H=0,F=0}
local path = GetPath(startP, endP, false)
for _, v in ipairs(path) do
    print(getPointString(v))
end
print("end.....")

$ lua astart.lua

start .....
<2,2>
<3,2>
<4,3>
<4,4>
<4,5>
<5,6>
<5,7>
<6,8>
<6,9>
<6,10>
<7,11>
end.....