时间戳

首页 > 解决方案 > 搜索鼠标所在十六进制网格上哪个元素的有效方法

python - 搜索鼠标所在十六进制网格上哪个元素的有效方法

问题描述

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

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

如果有人对如何以更有效的方式更有效地做到这一点有想法，我很想听听他们的意见。

标签： pythonpygame

解决方案

保留中心点列表可能不是表示十六进制图块的最佳方式，而使用十六进制坐标系可能是解决问题的最合适方式（请参阅帖子下方的评论以获取入门资源）。

但是，如果我们保留您的中心点方法列表，加速这种计算的一个好方法通常是使用该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数据结构而不是列表/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

推荐阅读