Python 自动寻路入门

1.pathfinding

在地图的任意一点寻找离目标最近的路线涉及很多，相当复杂的数学算法，现在在python中有一个专门用于自动寻路的模块”pathfinding“，它捆绑了如下模块：

A*
Dijkstra
Best-First
Bi-directional A*
Breadth First Search (BFS)
Iterative Deeping A* (IDA*)
Minimum Spanning Tree (MSP)

假设我们有一个由点组成的地图网格，有些格子可以通过，有些格子不能通过,例如下图，其中“1”代表可通过的点，“0“代表不可通过的点。

我们定义了开始的点和结束的点，打算找到最短的移动路径

弄清这条路线有不同的数学方法，当下实现此方法的最为出名数学模型的就是A star。我们先安装pathfinding，它包含了A star

pip install pathfinding

安装完成后我们按照官方例子来创建一个最简单的寻路项目

from pathfinding.core.grid import Grid
from pathfinding.finder.a_star import AStarFinder
matrix = [[1, 1, 1, 1, 1, 1],
          [1, 0, 1, 1, 1, 1],
          [1, 1, 1, 1, 1, 1]]

# 1.创建一个网格，导入矩阵
grid = Grid(matrix=matrix)

# 2.创建开始和结束的点
start = grid.node(0, 0)
end = grid.node(5, 2)

# 3.创建移动方法
finder = AStarFinder()

# 4.使用finder查找路径
path, runs = finder.find_path(start, end, grid)
print(path)  # 移动路线
print(runs)  # 计算次数

运行后的结果

[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (5, 1), (5, 2)]
17

在遍历了17次后，现在需要移动了8个点，到达目的地，不过现在它只能“上下左右”移动，并不能对角线移动，所以移动的路线并不是最短的。

添加对角线移动类和方法

from pathfinding.core.diagonal_movement import DiagonalMovement
finder = AStarFinder(diagonal_movement=DiagonalMovement.always)

再次运行得到结果

[(0, 0), (1, 0), (2, 0), (3, 0), (4, 1), (5, 2)]
9

在遍历了9次矩阵后，移动6次即可到达目标。有了这些后，我们可以尝试在自己的项目中实现他。

2.实践

我们先截取一张游戏的地图，并用PS处理图片为黑白，截取时要注意，尽可能的从游戏中的0.0坐标开始，方便下一步绑定。

这时，我们可以把此图生成矩阵，但图片尺寸过大392*366像素。此时尽可能的缩小图片，保持最窄的白色区域有2个左右像素即可，下图缩小了4倍。

使用CV2来生成二值化矩阵

import cv2

# 读取图片
img = cv2.imread("7.jpg")
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

# 将图片转换为二值图
ret, thresh = cv2.threshold(gray, 127, 255, 0)

# 获取图片的高度和宽度
height, width = thresh.shape

# 定义一个矩阵，用于存储图片中每个像素点的信息
matrix = []

# 遍历图片的每一个像素
for i in range(height):
    row = []
    for j in range(width):
        # 获取像素的值
        pixel = thresh[i, j]
        # 判断像素值是否为 0，如果为 0，表示该像素为障碍物，否则为路径
        if pixel == 0:
            row.append(0)  # 0 表示障碍物
        else:
            row.append(1)  # 1 表示路径
    matrix.append(row)
    print(row)

输出结果如下，可以看到白色可通过区域都是1，其它区域0。

使用之前的寻路程序引入这个矩阵，定义开始和结束的点，已经可以正确的找出最短路线。

可视化

# 可视化显示

import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation

fig, ax = plt.subplots()
im = ax.imshow(img)


def update(i):
    x, y = path[i]
    im.set_data(img)
    ax.scatter(x, y, c='r')
    ax.scatter([point[0] for point in path[:i]], [point[1] for point in path[:i]], c='r')


ani = FuncAnimation(fig, update, frames=range(len(path)), repeat=False)
plt.show()