Разреженная (псевдо) структура данных с бесконечной сеткой для веб-игры

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

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

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

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

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

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

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

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

Дерево kd или дерево квадрантов — хорошая структура данных для решения вашей проблемы. Особенно последнее - это умный способ обратиться к сетке и уменьшить сложность 2d до сложности 1d. Quadtrees также используется во многих картографических приложениях, таких как карты bing и google. Вот хорошее начало: блог Ника Квадтри о пространственном индексе кривой Гильберта.