Как проверить видимость из точки в точку? #533319

Есть поле 1000х1000 единиц, поделенное на клетки 10х10, итого получается сетка 100х100. Есть робот высотой 20 единиц, который может перемещаться по этому клеточному полю из клетки в клетку. У него строго в центре тела есть сенсор, высота которого произвольная( 0-20 ед). Поле заставлено прямоугольными блоками одного размера - 2х2 единицы в основании, 5 ед. высотой. Задача - _быстро_ проверить, может ли робот из клетки A,B (высота сенсора C) видеть точку X1,Y1,Z1. Как это сделать? Предпочтительны быстрые алгоритмы.

Лазерный метр присобачь. Если расстояние геометрической и реальное совпадают - значит видит

Это задача на программирование, если чо. Алгоритмическая.

Сейчас работает алгоритм "полета пули" - создается точка, и протаскивается по всей траектории от начала до конца с шагом 1 ед. На каждом шаге вычисляется пересечение со всеми блоками... Это очень медленно, нужен быстрый алгоритм. Интересно, тут BSP случаем не применим?

"Поле заставлено прямоугольными блоками одного размера - 2х2 единицы в основании, 5 ед. высотой. " Смотря как заставлено.

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

Жуть

На торце стоят. Вертикально. т.е. основание 2х2 всегда внизу. Стоят причем так, что ВСЕГДА можно наставить туда еще этих блоков так, их получилось ровно 25(5х5) на уровень. Т.е. для них клетка как бы еще порезана на 5х5 подклеточек-гнезд. Ну, bsp - быстрый алгоритм.

если "в лоб", то строишь по двум точкам (A,B,C) и (X1,Y1,Z1) уравнение прямой и проверяешь удовлетворяют ли ему координаты блоков. Если вектора подтянуть, то вполне элегантно может получиться.

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

сначала реши в проекции на само поле - основание - пересечение с проекциями блоков потом уже в плоскости полета - перпендикулярной основанию

А как узнать, какие блоки проверять? Вообще все блоки? Сейчас модель такая - блоки привязаны к клеткам в виде списков. При "протаскивании" точки клетка известна, список блоков к проверке - ограничен...

и?

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

попробовать с тем же алгоритмом, но ограничить сначала на плоскости кол-во блоков. для этого: 1. выбрать блоки которые входят либо пересекаются на пути т.е. на квадрат с диагональю А,В X1,Y1; 2. найти блоки, пересекающиеся с отрезком А,В  X1,Y1(наверное, проще всего на пересечение с диагоналями)

а то что проверив проекцию на основание - ты будешь знать - какие блоки проверять уже в перпендикулярной плоскости

Смысл? В чем будет отличие?

на плоскости вообще всё можно было перевести в полярные координаты, где за 0й вектор взять {(A,B),(X1,Y1)}. дальше всё просто

Я так и не понял, как "заставлено", но, думаю уравнение прямой (геометрия 7й класс) должно помочь...

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

Пардон, а что такое "проверяешь удовлетворяют ли ему координаты блоков"? Блок - не точка, между прочим. А объемная фигура. Пространство у нас только на плоскости порезано, оно ж на самом деле не дискретно. ЧТо в уравнение-то подставлять?

я думаю, автору сюда

а уравнение, может, и должно помочь... но не помогает.

Это я в курсе. Вот буду своё писать - обязательно воспользуюсь. ) Тут же всё-таки уже готовая модель, и надо придумать быстрый способ без её изменения.

Хотя да, kd-tree выглядит почти тем, чем надо... Спасибо за наводку...

есть минус... Блоки могут быть разной прозрачности...

охренеть! ты там новый движок для квейка пишешь?

Не. Такова игровая модель всего лишь древнего как гно мамонта Jagged Alliance 2. Без решения сабжевого вопроса не удается ничего сделать для модификации AI....