搜索鼠标所在的六角网格上哪个元素的有效方法

Question

我正在制作一张由六边形网格组成的游戏地图。目前，我在生成每个元素的中心点时将其保存到列表中。我想让当前鼠标悬停的图块突出显示。我通过获取鼠标位置并使用距离公式来工作，并循环遍历每个元素以找到离鼠标最近的元素。

CENTER LIST 是每个六边形图块的中心点列表。

def get_distance(x1, y1, x2, y2):
    dist = sqrt((x2 - x1)**2 + (y2 - y1)**2)
    return dist

def find_nearest_hex(pos):
    index = 0
    min_val = 10000
    for i in range(len(CENTER_LIST)):
        x,y= CENTER_LIST[i]
        if get_distance(pos[0], pos[1], x, y) < min_val:
            min_val=get_distance(pos[0], pos[1], x, y)
            index = i
    return index

如果有人对如何更高效地执行此操作有任何想法，我很乐意听取他们的意见。

Answer 1

保留中心点列表可能不是表示六边形图块的最佳方式，使用六边形坐标系可能是解决问题的最合适方式（请参阅 post 下面的评论获取良好的入门资源）。

我们是否应该保留您的中心点列表方法，但是，加速这种计算的一个好方法通常是使用 numpy 库，它是为科学计算而构建的，并带有非常快速的内置函数：

import numpy as np

# We create a numpy array (basically a list of lists) of 5000 random coordinates
# You can convert a python list to a numpy array with my_array = np.array(my_list)
CENTER_LIST = np.random.random((5000,2))

def find_nearest_hex2(pos):
    dist = np.sum((CENTER_LIST - pos)**2, axis=1)
    return np.argmin(dist)

这个版本比你在我电脑上的代码快了大约 75，在 CENTER_LIST 中有 5000 个元素。

使用 KDTree 数据结构而不是 list/numpy 数组可以获得更高的加速（在我的测试中快 265），因为此结构是根据您的应用程序精确构建的（查询最近的点云）：

from scipy.spatial import KDTree

my_kdtree = KDTree(CENTER_LIST)

def find_nearest_hex(pos):
    dist, index = my_kdtree.query(pos)
    return index

搜索鼠标所在的六角网格上哪个元素的有效方法

Efficient way to search for which element on hex grid the mouse is in

python

pygame