В настоящее время я пишу симуляцию 2D AI, но я не совсем уверен, как проверить, находится ли положение агента в поле зрения другого.
В настоящее время разделение моего мира - это простое разбиение пространства ячеек (сетка). Я хочу использовать треугольник для представления поля зрения, но как я могу вычислить ячейки, которые пересекаются с треугольником?
Похож на эту картину:
Красные области - это ячейки, которые я хочу вычислить, проверяя, пересекает ли треугольник эти ячейки.
Заранее спасибо.
РЕДАКТИРОВАТЬ:
Просто чтобы добавить к путанице (или, возможно, даже сделать это проще). Каждая ячейка имеет вектор min и max, где min - это нижний левый угол, а max - верхний правый угол.
collision-detection
intersection
Рэй Дей
источник
источник
Ответы:
Вычислите три угла вашего fov-треугольника, поверните их так, чтобы они были повернуты правильно, и затем выполните одно из следующих действий:
1) выполнить тест точка-треугольник для всех потенциальных целей
2) вычислите ограничивающий прямоугольник этого треугольника и выполните тест «точка-треугольник» для всех потенциальных целей в ячейках в этом ограничивающем прямоугольнике - это будет очень простой код для отладки
Аналогичный подход заключается в использовании квадродерева, а не сетки и пересечений. Если доступ к тайлу O (1) ускоряет вас, то просто тестирование всех ячеек в границах fov-треугольника для in-треугольника должно быть настолько быстрым, чтобы быть мгновенным. Поскольку вы смотрите на другие варианты, я предполагаю, что это не так, и что O (1) на самом деле берет на себя огромную стоимость промаха кэша, когда вы перебираете его. Вы, конечно, могли бы, возможно, взглянуть на инструкции по предварительной загрузке, чтобы аннотировать свой ограничивающий переход ...
3) «растеризовать» этот треугольник и проверить ячейки, которые он «рисует» - вероятно, самый эффективный код, но, возможно, лишь незначительно, так как я бы предположил, что в нем преобладает время пропуска кэша, и это зависит от того, насколько сложны ваши ячейки и насколько они заняты они есть.
Альтернативный подход состоит в том, чтобы визуализировать FOV в закадровом растровом изображении и затем прочитать значение пикселя для каждого из ваших объектов; Вы не можете «размешать краску», но с ограниченным количеством объектов и, тщательно выбирая свою краску, вы можете определить, кто видел кого. Этот подход аналогичен тому, как много игр отрабатывают то, на что нажимал пользователь - они рисуют сцену вне экрана, используя сплошные цвета для областей попадания. GPU очень быстро заполняют треугольник ...
источник
Я полагаю, что каноническое решение в программных средствах визуализации (которые должны выполнять этот точный алгоритм каждый раз, когда они растеризуют треугольник) состоит в том, чтобы сканировать треугольник по одной строке пикселей за раз. Левый и правый края каждого ряда рассчитываются путем спуска по сторонам треугольника с помощью Брезенхэма , а затем вы заполняете ряд между ними.
Я замалчиваю многие детали, но это основная идея. Если вы ищите «рендеринг программного обеспечения» и «растеризацию треугольника», вы, вероятно, найдете более подробную информацию. Это хорошо решенная проблема. Ваша видеокарта делает это миллионы раз за кадр.
Если вы хотите более специфичное для roguelike решение, вот как я реализовал FOV в своей. Кажется, работает довольно быстро. По сути, это простой заклинатель теней, работающий с октантом одновременно, сканирующий наружу от игрока.
источник
Я использую разновидность алгоритма сканирования, чтобы решить ту же проблему. Я начал с сортировки трех точек треугольника по их высоте. Затем я проверяю, находятся ли два ребра слева или справа. Для стороны с двумя ребрами, вы должны отметить их ряд, где вы изменяете, какое ребро разделяет ваши ряды. Для стороны с одним краем, вы всегда можете использовать это.
Итак, для каждой строки я знаю, какие два ребра ограничивают его, и я могу вычислить верхнюю и нижнюю границы в направлении x. Это звучит довольно сложно, но сокращается до нескольких строк кода. Убедитесь, что вы обрабатываете специальный случай, когда один край полностью горизонтален!
источник
Как насчет поддержания диапазона столбцов для каждой строки, которые находятся в треугольнике? Что вы можете сделать, это установить минимальный и максимальный столбец для каждой строки, где каждая точка находится, и где каждая треугольная линия пересекает горизонтальную линию разделителя строк.
Вывод:
источник
В сообществе roguelike, которое занимается FOV / LOS / освещением в мире на основе тайлов, есть некоторая работа с алгоритмами.
Возможно, на этой странице вы найдете что-то, что поможет решить вашу проблему: http://roguebasin.roguelikedevelopment.org/index.php?title=Field_of_Vision
В частности, «Permissive FOV» может быть наиболее подходящим для вашей ситуации.
источник