python - 即时战略游戏的快速欧氏距离计算

Question

实现快速距离计算的最佳方法是什么？

我正在为星际争霸 2 编写一个机器人，其中每帧都必须计算许多距离。

这是正在使用的库的一部分，我想改进: https://github.com/Dentosal/python-sc2/blob/develop/sc2/position.py

我记录了一个 10 分钟游戏的计算，平均每帧有这么多调用:

distance_to 10
distance_to_point2 965
_distance_squared 1775
closest 42

注意 closest 由一个 for loop 组成，我测试了 n 有多大，并得到了这个游戏分布:

0 < n <= 5 : 21389
5 < n <= 10 :  16426
10 < n <=20 :  28202
20 < n <=605 : 13620
60 < n :  34
len n of 'closest' call: 79671
average n of 'closest' call: 13.815654378632125
min n of 'closest' call: 2
max n of 'closest' call: 128

我的想法是使用 numpy 并为“最近”函数使用向量解决方案来一次计算所有距离。

我还想实现另一个功能，即计算一个列表的所有成员到另一个列表的所有成员的最近距离。

numpy 是正确的想法吗？我使用 numpy 的哪些功能？ Cython 会更好吗？

Answer 1

numpy 和 scipy 在 C 中完成所有这些类型的计算。不需要自己做 cython。

%%timeit
from scipy.spatial.distance import euclidean
import numpy as np
matrices = []
for i in range(10):
    matrices.append(np.random.randint(10,size=(1,5)))
[[euclidean(matrices[i],matrix) for i, j in enumerate(matrices)] for matrix in matrices]