Блог

Я рассматриваю возможность создания игры, действие которой разворачивается на практически бесконечной сетке.

• Сетка очень разреженная. Определенные небольшие области с относительно высокой плотностью. Относительно немного изолированных непустых ячеек.
• Объем используемой сетки слишком велик для наивной реализации, но, вероятно, маловат по стандартам «больших данных» (я не пытаюсь отобразить Интернет или что-то в этом роде)
• Это должно быть легко сохранить.

Вот операции, которые я, возможно, захочу выполнить (достаточно эффективно) с этой сеткой:

• Запросите некоторую небольшую прямоугольную область ячеек и все их содержимое (текущее местоположение игрока)
• Устанавливайте отдельные ячейки или выделяйте небольшие области (игрок делает ход)
• Запросите приблизительную форму или контур / силуэт некоторых более крупных прямоугольных областей (карта мира или предварительный просмотр региона)
• Найдите несколько областей с приблизительно заданной плотностью (место появления игрока)
• Приблизительный кратчайший путь через промежутки, состоящие не более чем из нескольких небольших постоянных пустых пространств за переход (часто можно быть плохим приближением, но не нормально продолжать поиск в неправильном направлении)
• Приблизительная выпуклая оболочка для области

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

Ребята, какой совет вы можете мне дать по реальной реализации этого? Как бы вы это сделали, если бы не было ограничений веб-приложения? Как бы вы изменили это, если бы они были?

Всем большое спасибо!

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

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

• Регион с приблизительно заданной плотностью: если плотность, которую вы ищете, высока, тогда я бы поддерживал отдельный индекс всех объектов на вашей карте. Возьмите случайный объект и проверьте плотность вокруг этого объекта в quadtree. Большинство объектов будут находиться вблизи областей с высокой плотностью, просто потому, что в областях с высокой плотностью много объектов. Если плотность вблизи выбранного вами объекта не та, которую вы искали, выберите другой.

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

• Приблизительный кратчайший путь: если это не слишком частая операция, то создайте приблизительный график области «между» начальной точкой A и конечной точкой B, для некоторого подходящего определения between (возможно, квадрат, содержащий круг с серединой AB в качестве центра и диаметром 1,5 * AB в качестве, за исключением случаев, когда этот диаметр меньше определенного минимума, в этом случае … поэкспериментируйте). Создайте сетку того же типа, которую вы использовали бы для приблизительной формы / контура, затем создайте (скажем) триангуляцию черных точек по Делоне. Создайте кратчайший путь на этом графике, затем наложите его на реальную карту и уточните путь до того, который имеет смысл, учитывая реальную карту. Возможно, вам придется переделать это на нескольких разных уровнях уточнения — начните с очень приблизительного графика, затем «увеличьте», взяв две точки, которые вы получили с более высокого уровня, в качестве начальной и конечной точек, и повторите.

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

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

Я не уверен, что это было бы легко поместить в реляционную базу данных; хранилище на основе файлов могло бы работать, но было бы непрактично, чтобы операция записи была одновременной с чем-либо еще, что вы, вероятно, захотите, если хотите, чтобы это число увеличилось до разумного числа игроков (на мир / карту, если существует несколько миров / карт). Я думаю, что в этом случае вам, вероятно, лучше всего поддерживать отдельный процесс … и даже тогда заставить его должным образом учитывать многопоточность будет головной болью.

kd-дерево или quadtree — хорошая структура данных для решения вашей проблемы. Особенно последнее, это умный способ обратиться к сетке и уменьшить сложность 2d до сложности 1d. Quadtrees также используется во многих приложениях maps, таких как bing и Google Maps. Вот хорошее начало: Блог Nick quadtree spatial index hilbert curve.