space2pacman
@space2pacman
Просто царь.

Как узнать, входит ли игрок1 (x,y,z) в поле игрок2 (x,y,z)?

Онлайн игра. 1000 игроков.

Как сделать, чтобы обмен пакетами был между ближайшими игроками?
Игрок может как сам ходить и подходить к другим игрокам, так и игроки сами могут подойти к стоящему игроку.

6613c3a183a98905399444.png
  • Вопрос задан
  • 206 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Я правильно понял, что идет обмен между двумя игроками, если их окружности пересекаются?

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

Но это медленно. Для усокрения, надо хранить всех игроков в какой-то трехмерной структуре данных. Например, квадро-дерево. Там для ускорения поиска в каждой вершине храните сколько там игроков есть, и при рекурсивном спуске не идите в те вершины, для которых обрамляющий прямоугольник не пересекается с окружностью для игрока, относительно которого вы соседий ищите. Когда дошли до листа с игроками, каждого из них проверьте - досаточно ли они близки для добавления в ответ. Для упрощения, вы вместо окружности пересекайте с обрамляющим прямоугольником квадрат описанный вокруг окружности. Сильно упрощает код, хоть и даст немного лишних проверок.
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
@WitFed
Программист
Это что-то из олимпиадного ? Разовые сдвиги между "кадрами" не очень большие ? Резко прыгать никто не будет между соседними моментами времени ?
Как видно из рисунка, зелёным помечены круги игроков, расстояние между которыми до 2R, где R -- радиус взаимодействия, одинаковый для всех.
Расстояния будут попарно считаться как суммы квадратов разностей dx*dx + dy*dy.
Можно для начала рассматривать для каждого игрока только товарищей, у которых дельты по осям обе не больше 4хR.
Их тогда в среднем будет сильно меньше 1000.
Были на 4хR, за "секунду" сблизились каждый на R, и уже "на связи" ! ;)
Хранить и пересчитывать ближайших с надо запасом, чтобы при небольших сдвигах одного не сравнивать его расстояния со всеми остальными, а только если он сдвинется на R и более.
Надо иметь массив А[1000,999] с парами {№ соседа, расстояние}, максимальным (вдруг они таки "столпятся" и захотят "пообщаться", и тогда пойдут тормоза, выбрать ближайших будет сильно дольше).
Ещё массив Л[1000] с текущим количеством "соседей" для каждого А[i].
И, конечно, позиции Х/У для всех О[1000], где был последний полный пересчёт А[i].
В первый раз пересчитать все расстояния, каждому в А[i] писать только "недалёких", до 16хRхR.
Потом -- сортировка всего А[i], и первые ближайшие до 4хRхR окажутся достойными для общения.
После каждого сдвига игрока И[i] его список пересчитывается целиком, если дельта с О[i] больше RхR (и О[i] обновляется).
В обратном случае -- просто пересчёт дистанций/сортировка внутри прежнего списка А[i] на длину Л[i].
Новый список с дистанциями до 4хRхR надо сравнить со старым, и если кто-то там новый появился, то его пометить для перестройки позже.
И кто "пропал с дистанции" -- тоже требует перестройки.
Полной или не очень, просто добавить/удалить себя к нему -- надо ещё додумать.
Инкрементальные действия между "степами" будут пропорциональны количеству немного шевельнувшихся между "степами" игроков И[i], и в основном на длину списков их "соседей", этого достаточно ?
Ответ написан
Комментировать
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
8 класс средней школы. Декартова система координат.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы