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()

3.绑定游戏坐标

8

评论1

  1. 能完善最后的游戏坐标绑定吗,并再游戏中根据坐标自动寻路吗
    达到 2023-07-21 0 回复
显示验证码