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

user_17044623 0
Viewed 189

I am working on a game map, that is made up of a hex grid. Currently I am saving the center points of each element to a list when they are generated. I want to have the tile the current mouse is over, to be highlighted. I have it working by taking the mouse position, and using the distance formula, and loop through each element to find the closest element to the mouse.

CENTER LIST is a list of centerpoints for each hex tile.

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

If anyone has ideas on how to do this more in a more efficient way I would love to hear them.

pygame python
1 Answers

Keeping a list of central points probably isn't the best way to represent hex tiles, and using a hex coordinate system is probably the most appropriate way of solving the problem (see the comments below your post for good resources to get started).

Should we keep to your list of center points approach, however, a good way to speed up this kind of computation is usually to use the numpy library, which was built with scientific computing in mind and comes with extremely quick built-in functions:

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)

This version is about 75 faster than your code on my computer, with 5000 elements in CENTER_LIST .

Using a KDTreedata structure instead of a list/numpy array can get you an even higher speedup (265 faster in my tests), as this structure is built precisely with your application in mind (querying a point cloud for the closest one):

from scipy.spatial import KDTree

my_kdtree = KDTree(CENTER_LIST)

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