如何以非O(N²)复杂度实现多人游戏的玩家范围检测

我正在开发一款多人游戏，希望服务器仅向玩家发送其屏幕内显示的玩家数据，避免传输冗余信息。

现有数据与判断逻辑 #

玩家数据结构示例 #

var players = [
{ x: 100, y: 100, range: 50, id: 1},
{ x: 150, y: 100, range: 100, id: 2},
{ x: 250, y: 150, range: 50, id: 3},
....
]

注：数据存储形式不局限于数组，可采用任何高效结构

范围判断逻辑 #

通过计算两位玩家的距离，若距离小于当前玩家的range值，则判定目标玩家在范围内：

const distance = (x1, y1, x2, y2) => Math.hypot(x2 - x1, y2 - y1); 

function isPlayerInRange(player, checkPlayer) {
  return distance(player.x, player.y, checkPlayer.x, checkPlayer.y) < player.range
}

目标与性能瓶颈 #

预期输出 #

得到每个玩家对应的范围内玩家ID列表，示例如下：

[
{id: 1, inRange: [3,4]},
{id: 2, inRange: []},
{id: 3, inRange: [1]}
]

其中inRange为范围内玩家的ID集合，且每位玩家的range值因游戏成长机制各不相同。

性能问题 #

初始实现采用嵌套循环，时间复杂度为O(N²)，玩家数量增多时计算量暴涨（比如100位玩家需要10000次计算），无法支撑数百位玩家的服务器需求。现寻求复杂度为O(N)、O(2N)甚至O(logN)的实现方案，并给出伪代码。

要降低时间复杂度，核心思路是用空间换时间，通过空间索引结构减少需要检查的玩家数量，避免全量遍历。以下是两种常用的高效方案：

1. 网格划分（Grid Partitioning） #

原理 #

将游戏地图划分为固定大小的网格单元格，每个玩家根据坐标归属到对应的网格中。当需要查询某玩家的范围内玩家时，只需检查该玩家所在网格及其相邻的若干网格（具体数量由玩家的range决定），无需遍历所有玩家。

伪代码实现 #

// 1. 初始化网格结构，键为网格坐标（如"x,y"），值为该网格内的玩家列表
grid = {}
cellSize = 最大玩家range值 // 或根据游戏地图调整为合理大小

// 2. 将所有玩家分配到对应网格
for each player in players:
    gridX = floor(player.x / cellSize)
    gridY = floor(player.y / cellSize)
    gridKey = `${gridX},${gridY}`
    if gridKey not in grid:
        grid[gridKey] = []
    grid[gridKey].push(player)

// 3. 为每个玩家查询范围内的玩家
result = []
for each player in players:
    inRangeIds = []
    // 计算需要检查的网格范围
    startGridX = floor((player.x - player.range) / cellSize)
    endGridX = floor((player.x + player.range) / cellSize)
    startGridY = floor((player.y - player.range) / cellSize)
    endGridY = floor((player.y + player.range) / cellSize)
    
    // 遍历目标网格范围内的所有玩家
    for gridX from startGridX to endGridX:
        for gridY from startGridY to endGridY:
            gridKey = `${gridX},${gridY}`
            if gridKey not in grid:
                continue
            for each checkPlayer in grid[gridKey]:
                if player.id == checkPlayer.id:
                    continue
                if distance(player.x, player.y, checkPlayer.x, checkPlayer.y) < player.range:
                    inRangeIds.push(checkPlayer.id)
    result.push({id: player.id, inRange: inRangeIds})

return result

复杂度分析 #

• 初始化网格：O(N)
• 查询阶段：平均情况下为O(N)（每个玩家仅检查少量网格内的玩家），最坏情况仍为O(N²)（所有玩家集中在同一个网格），但实际游戏中玩家分布相对分散，性能提升明显。

2. 四叉树（Quadtree） #

原理 #

四叉树是一种二维空间划分树结构，将空间递归划分为四个象限，适合处理动态分布的玩家。当玩家移动时，更新其在四叉树中的位置；查询时，递归遍历可能包含目标范围内玩家的节点，减少无效检查。

伪代码实现 #

// 定义四叉树节点
class QuadtreeNode:
    constructor(boundary, capacity):
        this.boundary = {x, y, width, height} // 节点覆盖的矩形区域
        this.capacity = capacity // 节点最多容纳的玩家数
        this.players = []
        this.children = [] // 四个子节点：左上、右上、左下、右下

    // 插入玩家到节点
    insert(player):
        if player不在当前节点的boundary内:
            return false
        if 当前节点未分裂且players数量 < capacity:
            this.players.push(player)
            return true
        // 节点已满，分裂为四个子节点
        if 当前节点未分裂:
            this.split()
        // 尝试插入到子节点
        for child in this.children:
            if child.insert(player):
                return true
        return false

    // 分裂节点为四个子节点
    split():
        halfWidth = this.boundary.width / 2
        halfHeight = this.boundary.height / 2
        x = this.boundary.x
        y = this.boundary.y
        // 创建四个子节点
        this.children.push(new QuadtreeNode({x, y, halfWidth, halfHeight}, this.capacity)) // 左上
        this.children.push(new QuadtreeNode({x+halfWidth, y, halfWidth, halfHeight}, this.capacity)) // 右上
        this.children.push(new QuadtreeNode({x, y+halfHeight, halfWidth, halfHeight}, this.capacity)) // 左下
        this.children.push(new QuadtreeNode({x+halfWidth, y+halfHeight, halfWidth, halfHeight}, this.capacity)) // 右下
        // 将当前节点的玩家转移到子节点
        for player in this.players:
            for child in this.children:
                if child.insert(player):
                    break
        this.players = []

    // 查询范围内的玩家
    query(rangeCircle, foundPlayers):
        if 当前节点的boundary与rangeCircle无交集:
            return
        // 检查当前节点内的玩家
        for player in this.players:
            if distance(rangeCircle.x, rangeCircle.y, player.x, player.y) < rangeCircle.radius:
                foundPlayers.push(player)
        // 递归查询子节点
        for child in this.children:
            child.query(rangeCircle, foundPlayers)
        return foundPlayers

// 1. 初始化四叉树（边界设为游戏地图的最大范围，容量设为合理值，比如4）
quadtree = new QuadtreeNode({x: 0, y: 0, width: 地图宽度, height: 地图高度}, 4)

// 2. 插入所有玩家到四叉树
for each player in players:
    quadtree.insert(player)

// 3. 为每个玩家查询范围内的玩家
result = []
for each player in players:
    foundPlayers = []
    // 定义查询范围：以玩家为中心，半径为player.range的圆
    queryRange = {x: player.x, y: player.y, radius: player.range}
    quadtree.query(queryRange, foundPlayers)
    // 过滤掉自身，收集ID
    inRangeIds = [p.id for p in foundPlayers if p.id != player.id]
    result.push({id: player.id, inRange: inRangeIds})

return result

复杂度分析 #

• 插入与查询的平均时间复杂度为O(logN)，适合玩家分布动态变化的场景。当玩家移动时，只需从四叉树中移除并重新插入即可，维护成本较低。

• 若玩家的range值差异极大，可以结合两种方案：为不同range区间的玩家划分不同粒度的网格，或在四叉树中根据玩家range调整查询深度。
• 实际实现中，可根据游戏地图大小、玩家数量、移动频率选择最适合的方案，网格划分实现简单，四叉树更适合动态场景。

内容的提问来源于stack exchange，提问作者Coder Gautam YT