用Lua实现了一个简单的方块A*寻路。

A*寻路的原理是会计算路径，产生一个估值f值，这个估值是由起点到走过的路径g值和当前的位置到终点的估值h组成的。取这个估值的最小值来进行寻路，所以A*寻路的效率是由估值函数的效率决定的。
代码分析：

  • 创建一个节点，该节点保存位置和估值信息，并保留父节点，相当于整个路径是由链式节点组成。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    local node = {}
    node.__index = node
    function (pos, h, p)
        local n = {}
        n.pos = {x = pos.x, y = pos.y}
        n.h = h
        n.parent = p
        n.g = 0
        if p ~= nil then
            n.g = p.g + 1
        end
        n.f = n.g + n.h
        return setmetatable(n, node)
    end
    function node:get_pos()
        return self.pos
    end
    function node:get_g()
        return self.g
    end
    function node:get_f()
        return self.f
    end

  • 开始寻路的时候，会把当前节点的四周节点加入开放列表中（寻找路径只会在开放列表中），把障碍物或者已经走过的路径放入关闭列表中（防止重复行走）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    local astar = {}
    astar.close = {}
    astar.open = {}
    local function estimate_hvalue(srcPos, dstPos)
        return math.abs(srcPos.x - dstPos.x) + math.abs(srcPos.y - dstPos.y);
    end
    --f值排序
    local function nodeSort(l, r)
        if l:get_f() == r:get_f() then
            return l:get_g() > r:get_g()
        end
        return l:get_f() < r:get_f()
    end
    local function contain(t, pos)
        for _, v in ipairs(t) do
            if v:get_pos().x == pos.x and v:get_pos().y == pos.y then
                return v
            end
        end
    end
    function astar:fitNode(pos)
        if self.map[pos.x] ~= nil and self.map[pos.x][pos.y] == 0 then
            return true
        end
        return false
    end
    --把周围4个节点不是墙或者没走过的节点加入开放列表中，开放列表中按f值从少到多排序
    function astar:addOtherNode(curNode)
        if curNode == nil then return end
        local d = {
            {x = 0, y = 1},
            {x = 0, y = -1},
            {x = -1, y =  0},
            {x = 1, y = 0}
        }
        table.insert(self.close, curNode)
        local newPos, h = {x = 0, y = 0}, 0
        for _, v in ipairs(d) do
            newPos.x = curNode:get_pos().x + v.x
            newPos.y = curNode:get_pos().y + v.y
            h = estimate_hvalue(newPos, self.dstPos)
            if contain(self.close, newPos) == nil and self:fitNode(newPos) then
                table.insert(self.open, node.new(newPos, h, curNode))
            end
        end
        table.sort(self.open, nodeSort)
    end
    --重复从开放列表中取f值低的节点，直到终点，然后把终点的节点和一连串的父节点组成路径
    function astar:makePath()
        self.close = {}
        self.open = {}
        local path = {}
        local h = estimate_hvalue(self.srcPos, self.dstPos)
        if h == 0 then return end
        local n = node.new(self.srcPos, h, nil)
        table.insert(self.open, n)
        local last = nil
        while #self.open ~= 0 and last == nil do
            n = table.remove(self.open, 1)
            self:addOtherNode(n)
            last = contain(self.open, self.dstPos)
        end
        while last ~= nil do
            table.insert(path, 1, last)
            last = last.parent
        end
        return path
    end

  • 加载地图等资源进行寻路

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    local astar = require "astar"
    local map = {
    	{0, 0, 0, 0, 0, 0},
    	{0, 0, 1, 1, 1, 0},
    	{0, 0, 1, 0, 1, 0},
    	{0, 1, 1, 0, 1, 0},
    	{0, 1, 0, 0, 1, 0},
    	{0, 0, 0, 0, 0, 0}
    }
    function printMap()
        for i=1, #map do
            local s = ""
            for j=1, #map[i] do
                s = s..string.format("%d ", map[i][j])
            end
            print(s)
        end
    end
    function main()
        local path = astar:getPath({x = 1, y = 1}, {x = 3, y = 4}, map)
        if path ~= nil then
            print("before")
            printMap()
            
            local n = nil
            for i=1, #path do
                n = path[i]
                map[n:get_pos().x][n:get_pos().y] = 2
            end
            print("after")
            printMap()
        end
    end
    main()


0是空地，1是墙壁，2是行走的路径

A*寻路的优化

  • 当地图比较大的时候，使用A*寻路的效率就会变低，这时候不用再一次函数计算中得到结果，可以在游戏帧中分几帧来计算。
  • 像魔兽或者帝国中，一大堆兵团进行寻路时候，可以使用队列中间的一个来进行计算，其他兵种靠偏移量来确定位置。