Я думаю, что вы можете делать все, используя квадри, как предлагали другие, и, возможно, несколько дополнительных структур данных. Вот немного подробнее:
- Запрос содержимого ячейки, настройка содержимого ячейки: это основные операции с квадродеревом.
- Грубая форма / контур: Учитывая прямоугольник, пройдите на достаточное количество шагов в пределах дерева квадрантов, чтобы большинство ячеек были пустыми, и сделайте непустые субэлементы на этом уровне черными, остальные - белыми.
Регион с приблизительно данной плотностью: если плотность, которую вы ищете, высока, то я бы поддерживал отдельный индекс всех объектов на вашей карте. Возьмите случайный объект и проверьте плотность вокруг этого объекта в квадри. Большинство объектов будут находиться вблизи областей с высокой плотностью просто потому, что в областях с высокой плотностью имеется много объектов. Если плотность около выбранного вами объекта не та, которую вы искали, выберите другой.
Если вы ищете низкую плотность, просто выберите случайные местоположения на карте - учитывая, что это редкая карта, которая обычно должна давать вам пятна низкой плотности. Опять же, если это не сработает, попробуйте еще раз.
Приблизительный кратчайший путь: если это не слишком частая операция, то создайте приблизительный график области «между» начальной точкой A и конечной точкой B для некоторого подходящего определения между (может быть, квадрат, содержащий круг с серединой AB в качестве центра и 1,5 * AB в качестве диаметра, за исключением случаев, когда этот диаметр меньше определенного минимума, в этом случае ... эксперимент). Создайте сетку того же типа, что и для грубой формы / контура, а затем создайте (скажем) триангуляцию Делоне для черных точек. Сделайте кратчайший путь на этом графике, затем наложите его на реальную карту и уточните путь до того, который имеет смысл, учитывая реальную карту. Возможно, вам придется повторить это на нескольких различных уровнях уточнения - начните с очень грубого графика, затем «увеличьте», взяв две точки, полученные с более высокого уровня в качестве начальной и конечной точки, и выполните итерацию.
Если вам нужно делать это очень часто, вы захотите сохранить этот тип графика для всей карты вместо того, чтобы каждый раз восстанавливать его. Это может быть дорого, хотя.
Приблизительно выпуклый корпус: снова начните с чего-то вроде грубой формы, затем возьмите выпуклый корпус из черных точек в этом.
Я не уверен, будет ли это легко поместить в реляционную базу данных; хранилище на основе файлов могло бы работать, но было бы нецелесообразно, чтобы операция записи была параллельной с чем-либо еще, что вы, вероятно, захотите, если вы хотите, чтобы это число росло до разумного числа игроков (на мир / карту, если несколько миров / карт). Я думаю, что в этом случае вам, вероятно, лучше всего поддерживать отдельный процесс в действии ... и даже тогда, если вы соблюдаете это должное уважение, многопоточность будет головной болью.