Эффективное определение границ множества

Я пишу ИИ для игры RTS, используя API, который предлагает игра. Одна вещь, которую я хочу сделать, это определить набор линейных сегментов, ограничивающих вражескую нацию, однако, игра предлагает только функцию, которая говорит мне teamID одной 2D точки территории.

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

Как я могу эффективно определить набор ограничивающих линий вокруг невыпуклой области пространства, используя минимальное число запросов?

Nb: бонусные баллы за ответ, написанный на Lua, но псевдокод тоже хорош.

3 3
language-agnostic computer-science geometry

3 ответа:

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

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

Каждый луч представлен углом тета и имеет начало Z. вместо одной длины каждый луч имеет две связанные длины, внутреннюю и внешнюю, которые мы попытаемся свести. Начальное значение Inside устанавливается равным 0, а outside - равным значению, превышающему радиус любой возможной территории ("горизонт"); мы будем сжиматься вовне, пока она не окажется внутри территории, и расти вовнутрь, пока она не окажется совсем вне территории, используя двоичный поиск (log2 N в диаметре ваше игровое пространство). Мы также собираемся увеличить количество лучей, поскольку конечные точки распространяются, чтобы получить детализацию границ территории. Предполагается, что конечным результатом будет набор лучей, устанавливающих границу вокруг территории, конечные точки которой не более чем "расстояние" друг от друга. Вы можете начать с одного луча (тета=Север (0), внутри=0, снаружи=Горизонт). Назовем множество лучей R. будем считать, что множество лучей R Отсортировано по тэта, и если у нас есть луч r от R, то следующий (r) - это следующий Рэй в сортированном наборе, с next (r) для последнего луча в R, являющегося первым лучом в наборе. С вы знаете расположение городов, вы можете засеять набор лучами, имеющими города в качестве внутренних точек. Это должно сработать в любом случае.

Дополнительный параметр "порог" дает вам степень точности вашего ответа.

R = empty
add_to_R(0,0,Horizon)
repeat until done
    done = true
     for each ray r in R
      guess = average(Inside(r),Outside(r))
      if guess>threshold
         then done = false
      if interritory(Z+(Theta(r),guess))
        then Inside(r)=guess
        else Outside(r)=guess
     for each ray r in R
       if (distance(Inside(r),Inside(next(r)))> spacing
          then add_to_R(average(Theta(r),Theta(next(r)),
                        min(Inside(r),Inside(next(r)),
                        max(Outside(r),Outside(next(r))
end

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

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

2

Возможно, вы ищете выпуклую оболочку вокруг набора точек, см.: http://en.wikipedia.org/wiki/Convex_hull

Это проблема O(N log n) - не слишком плохая вычислительно. Некоторые псевдокоды см.: http://en.wikipedia.org/wiki/Graham_scan

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

Подробнее EDIT : если у вас действительно есть функция для запроса только одной точки, то ваша проблема такая же, как векторизация растрового изображения. Каждая точка - это "пиксель", а вражеская область-это (приблизительная) векторизация"пикселей".

3

Я предлагаю вам подойти к нему с помощью методов Монте-Карло

Http://en.wikipedia.org/wiki/Monte_Carlo_method

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

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

Редактировать:

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

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

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

2