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()
评论0