原理

AStar又叫启发式搜索算法，在静态网格中求取最短路径的一种算法，这里有个通用公式F=G+H，我们根据这个公式来衍生我们的代码。

image-20220610155728638

下面我们会根据这张图来实现代码和验证逻辑，利用Excel来验证Astar我觉得是非常直观的，当然这个只是最简单的AStar。

  • G：表示从起点到终点移动直接消耗，能够直接算出来，就是直接走了几个格子
  • H：从指定的格子移动到终点的预计消耗

实现

创建格子

根据上图，我们需要创建一个10*10的格子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
local length = 10
local height = 10
local Grid = {}
for i = 1, length do
    Grid[i] = {}
    for k = 1, height do
        local t = {}
        t.x = i
        t.y = k
        t.f = 0
        t.g = 0
        t.h = 0
        t.print = string.format("[%s, %s]", i, k)
        t.__tostring = function()
            print("[%s, %s]", i, k)
        end
        Grid[i][k] = t
    end
end
  • x，y是坐标
  • f，g，h是每个给子对应我们F=G+H

添加障碍

1
2
3
4
5
6
7
8
--添加障碍
local Obstacles = {}
for i = 2, 3 do
    Obstacles[i] = {}
    for k = 2, 7 do
        Obstacles[i][k] = Grid[i][k]
    end
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
---GetAreaPoint
---@param x number 当前点的x
---@param y number 当前点的y
---@param endPoint table 目标点
---@param length number
---@param height number
local function GetAreaPoint(x, y, endPoint, length, height)
    local x1 = x
    local y1 = y
    local start = Grid[x][y]
    local openList = {}

    --region 检查边界
    if y1 - 1 >= 1 then
        openList[#openList + 1] = Grid[x1][y1 - 1]
    end

    if y1 + 1 <= height then
        openList[#openList + 1] = Grid[x1][y1 + 1]
    end

    if x1 - 1 >= 1 then
        openList[#openList + 1] = Grid[x1 - 1][y1]
    end

    if x1 + 1 <= length then
        openList[#openList + 1] = Grid[x1 + 1][y1]
    end

    if x1 - 1 >= 1 and y1 - 1 >= 1 then
        openList[#openList + 1] = Grid[x1 - 1][y1 - 1]
    end

    if x1 + 1 <= length and y1 - 1 >= 1 then
        openList[#openList + 1] = Grid[x1 + 1][y1 - 1]
    end

    if x1 - 1 >= 1 and y1 + 1 <= height then
        openList[#openList + 1] = Grid[x1 - 1][y1 + 1]
    end

    if x1 + 1 <= length and y1 + 1 <= height then
        openList[#openList + 1] = Grid[x1 + 1][y1 + 1]
    end

    --endregion

    --region 检查障碍
    for i, v in pairs(openList) do
        if Obstacles[v.x] and Obstacles[v.x][v.y] then
            openList[i] = nil
        end
    end
    --endregion

    --核心逻辑
    for _, v in pairs(openList) do
        if v.x ~= start.x or v.y ~= start.y then
            v.g = math.sqrt(math.pow(math.abs(v.x - start.x), 2) + math.pow(math.abs(v.y - start.y), 2))
            v.g = math.floor(v.g * 10) / 10
        else
            v.g = math.abs(v.x - start.x) + math.abs(v.y - start.y)
        end

        v.h = math.abs(v.x - endPoint.x) + math.abs(v.y - endPoint.y)
        v.f = v.g + v.h
    end
    print("--------------------------------")
    for _, v in pairs(openList) do
        print("周围点", v.print, v.f, v.g, v.h)
    end
    print("--------------------------------")
    --找到最合适的点
    local perfect
    for _, v in pairs(openList) do
        if not perfect then
            perfect = v
        else
            if perfect.f > v.f then
                perfect = v
            end
        end
    end
    return perfect
end

这个核心算法就是找到自己周围的点，然后算出下一步走哪里，至于怎么算就就是根据我们的F=G+H，下一步走我们的最优点，一直执行下去直到终点，可以根据下面的图来理解。

image-20220610153928958

image-20220610154032862

上图中我用的数值1,2,3就第几步的预测走法，我这里是吧障碍和编辑也标记进去了，下面就从代码来分析是怎么计算了，从第二个图中，正常情况的情况下每个点都附近都有八个点，从第一个图中，需要把我周围的八个点加入到openList，再过滤掉不能走的点，比如障碍，边界（正常情况下不会有），然后再从我们的得到的OpenList中计算出最优点。

1
2
3
4
5
6
7
8
9
10
11
for _, v in pairs(openList) do
    if v.x ~= start.x or v.y ~= start.y then
        v.g = math.sqrt(math.pow(math.abs(v.x - start.x), 2) + math.pow(math.abs(v.y - start.y), 2))
        v.g = math.floor(v.g * 10) / 10
    else
        v.g = math.abs(v.x - start.x) + math.abs(v.y - start.y)
    end

    v.h = math.abs(v.x - endPoint.x) + math.abs(v.y - endPoint.y)
    v.f = v.g + v.h
end

这段代码很简单，走斜线，计算路径，给每个点赋值上，f，g，h。

1
2
3
4
5
6
7
8
9
10
11
12
--找到最合适的点
local perfect
for _, v in pairs(openList) do
    if not perfect then
        perfect = v
    else
        if perfect.f > v.f then
            perfect = v
        end
    end
end
return perfect

拿到最优的点。

调试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
----------------------------------main----------------------------------------------------------------------------------
local startPoint = Grid[1][1]
local endPoint = Grid[9][10]
local perfect = startPoint
local x1 = os.clock()
local path = {}
while perfect.x ~= endPoint.x and perfect.y ~= endPoint.y do
    perfect = GetAreaPoint(perfect.x, perfect.y, endPoint, length, height)
    print("最优点", perfect.print)
    path[#path + 1] = perfect
end
print("------------------------------")
path[#path + 1] = endPoint
for _, v in pairs(path) do
    print(v.print)
end
local x2 = os.clock()

print(string.format("结束耗時%s秒", x2 - x1 ))

这段代码核心就是循环查找结束点，知道结束，然后取点的集合，就拿到了路径线。

Git链接

完整代码