Как я могу процедурно найти стену, которая разделяет две или более точек на карте на основе сетки?

8

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

введите описание изображения здесь

  1. Синий отделен от красного.
  2. Синий отделен от красного и желтого.
  3. Синий отделен от Красного с помощью плитки.
  4. Несколько Blue отделены от нескольких Red.

Есть идеи как это сделать?

IanLarson
источник
1
Это слишком широко ... хотите ли вы минимизировать площадь синего, или, возможно, вы хотите равную площадь, или, возможно, область не имеет значения, но вы хотите минимизировать длину стены, или, возможно, все, что не имеет значения и что действительно важно, так это быстро найти решение ... и т. д.
Theraot
1
Чтобы дать вам, или другим, одно из возможных направлений, это звучит в зависимости от варианта «Манхэттенское расстояние вороной» в зависимости от вида, который вы ищите, или просто от обычного вороноя.
Сирисян
Согласившись с обоими другими комментариями, моей первой мыслью было «существует бесконечное количество решений». Где «бесконечность» не может быть бесконечной, сколь угодно большой. Нет никаких ограничений на то, что позволяет это, а не это .
Draco18s больше не доверяет SE
Извините, что не стал более конкретным. Действительно, единственное строгое требование состояло в том, чтобы стена разделяла данные точки, что, как я понимаю, имеет почти бесконечные решения. Изображения, которые я предоставил, на самом деле не были чем-то большим, чем общее представление о том, что я пытался сделать, так что ваше редактирование, Драко, было бы совершенно приемлемым результатом для моих целей. Я просто искал методы, которые бы давали такие результаты, даже если результатов было огромное количество.
Ян Ларсон

Ответы:

8

Я представлю общую концепцию и три решения, использующие эту концепцию.

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

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

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

Решение 1 :

Чтобы найти способ обернуть синий, найдите разницу между расстоянием до синего и любой другой вещи, для каждой точки. Приложение : Область, где разность положительна, является областью влияния для синего цвета. Если вы берете области влияния для каждой цветовой точки, вы можете построить диаграмму Вороного . Спасибо Сирисяну за упоминание о них .

Мы можем утверждать, что для точки, близкой к синему, разница будет положительной, а для точки, близкой к другой цветовой точке, разница будет отрицательной. Учитывая, что расстояние является непрерывной функцией, по теореме о промежуточном значении мы можем утверждать, что по крайней мере одна точка в середине разность будет приближаться к нулю. Решением было бы отследить стену, которая минимизирует расстояние между всеми плитками, где разница приближается к нулю.

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

Примечание: это решение приближается к равной области для синего и остальных в плоском сценарии.

Решение 2 :

Абстрактно, вы можете найти точки дросселирования между областью влияния синего и других, а затем разместить там стены. Делая это, вы разместите стены в местах, где влияние не находится в равновесии (стены ближе к одной стороне), но минимизирует длину стен.

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

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

Решение 3 :

Первое решение имеет проблему, которая может привести к слишком длинной стене. Второе решение имеет проблему, которая может привести к стенам, которые слишком далеко от синего цвета.

Обратите внимание, что работа с пикселями, мозаикой или работа с сетью, концепция карты влияния, как представление расстояния до цветовых точек, является действительной и полезной. Таким образом, решение 1 можно применить к сети выпуклых узлов.

Мое третье решение состоит в том, чтобы объединить вышеупомянутые подходы. Как только вы работаете по сети, вы можете рассматривать длину стены и разницу во влиянии - и любую другую метрику, которую вы хотите - как метрику «стоимости» одного индикатора, которую вы можете оптимизировать.

Theraot
источник
1
Это супер полезно. Использование карты влияния звучит именно так, как мне нужно. Спасибо за ссылки и подробный ответ.
Ян Ларсон