Как позволить серверу эффективно информировать игровых клиентов о других близлежащих видимых игроках?

Question

Я работаю над многопользовательской флеш игрой. Сервер сообщает каждому клиенту, какие другие игроки находятся рядом с игроком. Для этого сервер должен постоянно проверять, какие клиенты находятся рядом. Вот что я сейчас использую как временное решение:

private function checkVisibilities()
{
    foreach ($this->socketClients as $socketClient1)
    { //loop every socket client
        if (($socketClient1->loggedIn()) && ($socketClient1->inWorld()))
        { //if this client is logged in and in the world
            foreach ($this->socketClients as $cid2 => $socketClient2)
            { //loop every client for this client to see if they are near
                if ($socketClient1 != $socketClient2)
                { //if it is not the same client
                    if (($socketClient2->loggedIn()) && ($socketClient2->inWorld())
                    { //if this client is also logged in and also in the world
                        if ((abs($socketClient1->getCharX() - $socketClient2->getCharX()) + abs($socketClient1->getCharY() - $socketClient2->getCharY())) < Settings::$visibilities_range)
                        { //the clients are near each other
                            if (!$socketClient1->isVisible($cid2))
             { //not yet visible -> add
                                 $socketClient1->addVisible($cid2);
                            }
                        }
                        else
                        { //the clients are not near each other
                            if ($socketClient1->isVisible($cid2))
                            { //still visible -> remove
                                $socketClient1->removeVisible($cid2);
                            }
                        }
                    }
                    else
                    { //the client is not logged in
                        if ($socketClient1->isVisible($cid2))
                        { //still visible -> remove
                            $socketClient1->removeVisible($cid2);
                        }
                    }       
               }
         }
     }
}

Работает нормально. Однако до сих пор я играл только с двумя игроками одновременно. Эта функция зацикливает каждого клиента для каждого клиента. Таким образом, при 100 игроках это будет 100 * 100 = 10.000 циклов при каждом запуске функции. Это не лучший и не самый эффективный способ сделать это.

Теперь мне интересно, что вы, ребята, думаете о моей текущей настройке и есть ли у вас какие-либо предложения о том, как лучше обрабатывать эти видимости.

Обновление: я забыл упомянуть, что мир бесконечен. Это на самом деле "вселенная". Там нет карт. Кроме того, это двумерная (2D) игра.

Заранее спасибо.

Answer 1

Первое, что я бы сказал, это то, что ваш код выглядит наизнанку. Почему у вас есть логическая функция высокого уровня, которая должна выполнять основную работу по проверке того, какие клиенты вошли в систему и во всем мире? Все эти сетевые вещи должны быть удалены из игровой логики, чтобы это было сделано на более высоком уровне, и внутриигровая логика должна обрабатывать только игроков, которые в настоящее время играют и в мире. Это оставляет вас с простым вопросом: достаточно ли близки эти два игрока друг к другу? Здесь достаточно простой проверки расстояния, как у вас уже есть.

Следующая вещь - уменьшить количество циклов, которые вы делаете. Расстояние, как правило, является коммутативным свойством, поэтому вам не нужно проверять расстояние между A и B, а также между B и A. Чтобы сделать это, в то время как ваш первый цикл проходит через всех клиентов, второй цикл должен только перебирать все клиенты, которые приходят после первого. Это вдвое уменьшает количество итераций, которые вам нужно сделать.

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

Если это все еще недостаточно для вас, то какая-то система пространственного хеширования, описанная ianh, является хорошим способом уменьшения количества запросов, которые вы делаете. Сетка является самой простой, но какая-то древовидная структура (в идеале самобалансирующаяся) является еще одним вариантом.

Answer 2

Самое простое решение - разделить мир на единую сетку, например:

_|____|____|____|_
 |    |    |    |
_|____|____|____|_
 |    |    |    |
_|____|____|____|_
 |    |    |    |
_|____|____|____|_
 |    |    |    |

Затем вставьте ваши объекты в любой фрагмент сетки, который они пересекают:

_|____|____|____|_
 | @  |    |    |
_|____|____|____|_
 |    |d d |    |
_|____|____|____|_
 |    | d  |  d |
_|____|____|____|_
 |    |    |    |

Теперь, чтобы выполнить запрос для близлежащих объектов, вам нужно только посмотреть на соседние ячейки. Например, чтобы увидеть, кто в пределах одного тайла от игрока (@), вам нужно всего лишь отметить 9 тайлов, а не всю карту:

/|////|////|____|_
/|/@//|////|    |
/|////|////|____|_
/|////|d/d/|    |
/|////|////|____|_
 |    | d  |  d |
_|____|____|____|_
 |    |    |    |

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

Answer 3

Попробуйте использовать квад-дерево для представления местоположений игроков.
Вики-статья для этого здесь .
То, что он делает, это хранит объекты, которые вы ему даете, в пространстве (пользователи) в дереве, которое делит пространство (плоскость) на столько, сколько необходимо. Что касается проблемы бесконечности - ничто в программировании не является действительно бесконечным, поэтому определите границу, которая не может быть пройдена пользователями (даже для очень большого числа для координаты, что займет у пользователя около 100 лет) .