И снова всем привет. Недавно наткнулся на прелюбопытнейший срач между администрацией и населением сайта из далекого 2012 года. Как и полагается, с многочисленными банами и увольнениями. Прошу очевидцев того события поведать мне о нем, подробненько, с предысторией и ходом событий. Буду благодарен.
Всем привет. Давненько, а может и не очень, не виделись. Решил поделится с вами некоторой информацией, надеюсь кому-то пригодится.
"Достаточно ли ты 1337?
Хотел бы ты работать в Paradox Interactive, самом дружелюбном к утконосам работодателе на свете? Ты умеешь кодить? Отлично, выполни тестовое задание и возможно…
Такой алгоритм на C++ писали на первом курсе - поиск в глубину, менее, чем за 4 секунды(с нормального размера входными).
Ошибся, это был не поиск в глубину, там у путей были стоимости и все углублялось в зависимости от стоимости очередного отрезка пути. Естественно, при сколь-нибудь серьезных данных здесь поиск в глубину бы за 4 сек не управился.
Итак. Мой вариант поиска на RTS:
Между точками юзаем лучевой эвристический поиск пути. Он быстро, очень быстро находит все пути. Алгоритм дает разветвление на препятствиях. По оптимистичному сценарию, как вы помните, мы просто берем короткую "руку" и сохраняем.
Но нам нужен кратчайший путь. Мы сохраняем оба результата. Понятно, что на стадии сглаживания, создавая всего по 4 вариации (сгладить левый и правый рукав со следующим левым и правым) пути мы так или иначе найдем, какой рукав короче. Таким образом мы найдем и кратчайший путь. В результате мы получаем относительно быстрый алгоритм без необходимости запекания (немного жертвуем скоростью, но все равно опережаем астар). И это еще без оптимизаций.
Говорю про лучевой алгоритм не с потолка, это самое частое решение для RTS. И есть несколько способов сделать из него "кратчайший" поиск.
Clamp, именно увидев это в ск2 я и решил попробовать реализовать такой вариант поиска пути на практике, а не ограничиваться теорией. Но мне на данный момент не нравится ни их ни моя реализация - очень криво обрабатываются некоторые ситуации.
Последнее что я обдумывал в этой сфере было посвящено тому, не выйдет ли такие ситуации разрулить с помощью алгоритмов симуляции жидкостей.
Вот это прикольно, кстати! В толпе неизбежно нужно толкаться, а не пути искать, я тоже делал толчки у себя. А тут некоторая надежда организовать этот хаос именно на уровне столкновения пачек. Оффтоп: ретро про жидкости :)
BLOG-TARANES
Комментарии проекта Логово Снежного Волка
Как админчики власть делили или [1000 vs Скорп]
Работа в Paradox Interactive
Хотел бы ты работать в Paradox Interactive, самом дружелюбном к утконосам работодателе на свете? Ты умеешь кодить? Отлично, выполни тестовое задание и возможно…
Ред. AsagiriGen
Между точками юзаем лучевой эвристический поиск пути. Он быстро, очень быстро находит все пути. Алгоритм дает разветвление на препятствиях. По оптимистичному сценарию, как вы помните, мы просто берем короткую "руку" и сохраняем.
Но нам нужен кратчайший путь. Мы сохраняем оба результата. Понятно, что на стадии сглаживания, создавая всего по 4 вариации (сгладить левый и правый рукав со следующим левым и правым) пути мы так или иначе найдем, какой рукав короче. Таким образом мы найдем и кратчайший путь. В результате мы получаем относительно быстрый алгоритм без необходимости запекания (немного жертвуем скоростью, но все равно опережаем астар). И это еще без оптимизаций.
Говорю про лучевой алгоритм не с потолка, это самое частое решение для RTS. И есть несколько способов сделать из него "кратчайший" поиск.
Ред. Kozinaka