Как определить видимость в 2D

Question

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

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

альтернативный текст http://img231.imageshack.us/img231/2972/shadows.png

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

Какие-нибудь классные идеи?

Answer 1

Это не самый быстрый алгоритм, но он создает многоугольник, который может быть полезен для дальнейшего анализа вашим AI:

1. Для каждого отрезка линии рассчитайте угол между объектом и двумя конечными точками.
2. Сортировка точек по углу.
3. «развертка» около 360 °, отслеживая, какие отрезки линии пересекаются с линией развертки. Когда вы пересекаете точку начала сегмента, вы добавляете этот сегмент в набор; когда вы пересекаете точку конца сегмента, вы удаляете этот сегмент из набора.
4. Ближайшие отрезки образуют многоугольник того, что видно. Многоугольник - это объединение треугольников.

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

Answer 2

Если вы используете простые формы, чтобы заблокировать вид объекта, есть простой способ сделать это, который я реализовал:

Создайте VisionWave объект, который может двигаться как горизонтально, так и вертикально. Вы можете определить VisionWave, используя исходную координату, две линии, которые пересекают эту точку, и расстояние от исходной точки.

У вас должно быть 4 волны: одна идет вверх, одна вниз, одна влево и одна справа, а линии, которые их определяют, должны иметь наклон 1 и -1 (то есть X). Мой грубый рисунок ниже показывает одну волну (направо), представленную символом >.

  \     /
   \   />
    \ / >
     @  >
    / \ >
   /   \>
  /     \

Создайте петлю, которая распространяет каждую волну по одному пикселю за раз. Когда вы распространяете волну, вы хотите сделать следующее:

1. Отметьте каждый пиксель, к которому соприкасается волна, как видимый.
2. Если какой-либо из пикселей, которым волна касается, блокирует свет, то вы хотите разделить волну на два и рекурсивно распространить каждый из них.

Я внедрил подобную систему в моем Roguelike, и она очень быстрая. Обязательно профилируйте свой код для узких мест.

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

Answer 3

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

См. теневые объемы для 3D-эквивалента.