Поиск вещей с диапазоном

Question

Я строю свою первую многопользовательскую онлайн-игру и пытаюсь найти лучший способ найти всех игроков в пределах определенного диапазона.

Я огляделся; все остальные решения основаны на API-интерфейсе игрового движка, в котором встроен дальномер.

У каждого игрока есть пара координат x,y.

Первое, о чем я думал, было: перебирать всех пользователей на сервере и фильтровать их в пределах диапазона - просто используя теорему Пифагора - однако я знал, что должен быть лучший способ сделать это.

Лучшие вещи, о которых я думал, - это разбиение карты на разделы размером около 100 (10 x 10) и размещение пользователей в соответствующих разделах. Затем я мог бы получить раздел, в котором находится пользователь, и вместо того, чтобы перебирать каждого пользователя на сервере, прокручивайте каждого пользователя в пределах 9 квадратов (3x3, раздел пользователей и все остальные, окружающие его).

Я уверен, что это лучше, чем просто цикл через весь сервер 1000 раз в секунду, но есть ли стандартный способ сделать это, или это так, как это делается?

Я хочу держать вещи как на стороне клиента, так и на стороне сервера.

Answer 1

Да, вы считаете, что вы асимптотически оптимальны, поскольку это постоянное количество операций на одного игрока, если они не сгруппированы близко друг к другу в тех же квадрантах. Чтобы избежать выделения большого количества памяти для массива, вы можете использовать (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