algorithm - 寻找范围内的东西

Question

我正在构建我的第一个在线多人游戏，并试图找出找到特定玩家范围内所有玩家的最佳方法。

我环顾四周；所有其他解决方案均基于内置测距功能的游戏引擎 API。

每个玩家都有一对原始的 x,y 坐标。

我首先想到的是:遍历服务器上的每个用户并过滤掉范围内的用户 - 只需使用毕达哥拉斯定理 - 但我知道必须有更好的方法来做到这一点。

我想到的最好的办法是将 map 分成大约 100 (10 x 10) 个部分，然后将用户相应地放入部分。然后我可以获得用户所在的部分，而不是遍历服务器上的每个用户，而是遍历 9 个方 block (3x3，用户部分和它周围的所有其他部分)内的每个用户。

我敢肯定这比简单地每秒循环遍历整个服务器 1000 次要好，但是是否有标准的方法可以做到这一点，或者它是如何完成的？

我想在客户端和服务器端都保持精简。

Answer 1

是的，您的想法是渐近最优的，因为每个玩家的操作次数是恒定的，除非他们都聚集在同一个象限中。为了避免为数组分配大量内存，您可以使用 (hashset/table/dictionary) 和将 x, y 映射到 x/distance, y/distance 的哈希函数，这样您就可以检查字典是否有周围条目，然后检查相关玩家距离内玩家的条目。

This video谈论一个几乎同构的问题:用一堆圆圈命中检测。虽然在视频中，你不能在同一个地方有一堆圆圈。

如果您正在寻找更简单的优化，您可以先检查其他玩家的 x 和 y 是否都在相关玩家的 x 和 y 范围内，然后再检查 x 和 y 的差异的平方和y 小于您要检查的距离的平方。

一些伪代码是:

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