实时战略游戏的快速欧几里得距离计算

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 循环组成，我测试了 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的哪些功能？赛通会更好吗？

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]