@wlastas

Как замостить ориентированный по осям Rectangle блоками максимального размера, обходя препятствия?

Доброго дня.
Задача поиска пути и возможности атаковать (отсутствие препятствий в заданном направлении на нужном расстоянии) - нужна оптимизация построения условного Navigation mesh .
Есть большая готовая сетка проходимости(бывают до 1000х1000), разбитая на "квадраты 8x8" с непроходимыми секторами (красные на картинках).
Комбинируя проходимые сектора(1х1) внутри "квадратов 8x8" я строю грани navmesh, центры которых использую в качестве узлов графа.
Простое решение, которое работает сейчас, это разбиение "квадрата 8x8" на полоски 1хN,
60a65083afae1353376357.jpeg
но это немного медленно - хотелось бы ускорить в 2-4 раза.

Скорее всего будет отлично работать вариант как тут:
60a64e69a0b4e502902912.jpeg
Подскажите алгоритм ( может есть какая-то готовая математическая реализация), который можно использовать, чтобы получить проходимые сектора максимального размера
  • Вопрос задан
  • 59 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Во-первых, не очень понятно, зачем вам вообще это. Агрегируя квадратики в прямоугольники вы будете находить не самые короткие пути в этом графе. Каким алгоритмом вы дальше в графе работаете? Какой-нибудь Jump point search на неаггрегированных клетках может быть быстрее чего-бы то нибыло по аггрегированным.

Далее, если вам так хочется, то ваша задача аггрегирования - NP и кроме полного перебора вы не найдете оптимальное решение. Но вам, похоже, подойдет какое-нибудь достаточно хорошее решение, а не только оптимальное. Тогда будут работать всякие жадности и эвристики. Можно, например, брать самую левую-верхнюю непокрытую клетку и жадно растить вокруг нее максимальный по площади прямоугольник, который не пересекает ни одну покрытую или запрещенную клетку (допустим, перебирая нижнюю и верхнюю границу и жадно раздувая левую и правую до максимума). На примере из вопроса этот алгоритм построит 7 прямоугольников.
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
hint000
@hint000
у админа три руки
Простое решение, которое работает сейчас, это разбиение "квадрата 8x8" на полоски 1хN,
Предложу легко реализуемое улучшение, хотя и НЕ гарантирующее оптимальности.
Берёте ваши готовые полоски 1хN. Если снизу или сверху к этой полоске примыкает полоска с такими же координатами начала и конца, то объединяете эти полоски. Продолжаете проверку, если к полученному блоку примыкает ещё такая же полоска, то и её присоединяем к блоку, и т.д.
Плюс в простоте.

На вашем примере это даст 8 блоков вместо 12 полосок.
Ответ написан
@wlastas Автор вопроса
На вашем примере это даст 8 блоков вместо 12 полосок.

Да, спс, так получится 7 полосок и 2 блока. 
Еще есть вариант дополнительно нагенерить к этому же "квадрату 8х8" по такой же схеме, но на вертикальных полосах, и выбрать лучший. 
Насколько будет прирост от такой оптимизации - надо проверять.
Квадраты без препятствий внутри у меня и так не режутся на полосы и берутся как 8х8
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы