algorithm - 在范围内寻找事物

我正在建立我的第一个在线多人游戏，并试图找出最好的方式找到所有球员范围内的具体之一。
我环顾四周，所有其他的解决方案都是基于游戏引擎api的，它们内置了测距功能。
每个玩家都有一对原始坐标。
我想到的第一件事是：遍历服务器上的每个用户并过滤出范围内的用户——简单地使用毕达哥拉斯定理——但是我知道必须有更好的方法来做到这一点。
我想到的最好的办法是把地图分成大约100个部分（10 x 10），并相应地把用户分成几个部分然后我可以得到用户所在的部分，而不是在服务器上的每个用户之间循环，而是在9个方格内循环（3x3，用户部分和围绕它的所有其他部分）。
我确信这比简单地每秒在整个服务器上循环1000次要好，但是有没有一种标准的方法可以做到这一点，或者说是这样做的？
我希望在客户端和服务器端都保持简洁。

最佳答案

是的，你所想的是渐近最优的，因为每个玩家的操作数是恒定的，除非它们都在同一个象限中相互靠近。为了避免为数组分配大量内存，可以使用一个（hashset/table/dictionary）和一个将x、y映射到x/distance、y/distance的散列函数，这样就可以检查字典是否包含周围的条目，然后检查该条目的播放器距离内的播放器。
This video讨论了一个几乎同构的问题：用一堆圆进行命中检测。尽管在视频中，你不能在同一个位置有一堆圆圈。
如果你在寻找更简单的优化，你可以先检查其他玩家的x和y是否都在相关玩家的x和y范围内，然后再检查x和y的差平方和是否小于你要检查的距离的平方。
其中的一些psudocode是：

distance = 100
sections = {}

# initial setup
for player in players:
    section_x = player.x / distance
    section_y = player.y / distance
    index = [section_x, section_y]
    if !sections.get(index):
        sections[index] = []
    sections[index].push(player)

def players_near(player):
    nearby_players = []
    section_x = player.x / distance
    section_y = player.y / distance
    for section_dx in -1..1:
        for section_dy in -1..1:
            index = [section_x + section_dx, section_y + section_dy]
            players = sections[index]
            if players:
                nearby_players.extend(players)

    result = []
    for nearby_player in nearby_players:
        dx = abs(player.x - nearby_player.x)
        dy = abs(player.y - nearby_player.y)
        if dx <= distance and dy <= distance and sqr(dx) + sqr(dy) < sqr(distance):
            result.push(nearby_player)

    return result

关于algorithm - 在范围内寻找事物，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/39187048/