Всем привет. Давненько, а может и не очень, не виделись. Решил поделится с вами некоторой информацией, надеюсь кому-то пригодится.
"Достаточно ли ты 1337?
Хотел бы ты работать в Paradox Interactive, самом дружелюбном к утконосам работодателе на свете? Ты умеешь кодить? Отлично, выполни тестовое задание и возможно…
Если у тебя большая карта и много юнитов, то ты просто заранее считаешь популярные пути, делишь карту на сектора с известными путями между ними и прочая
Авторитетно заявляю, что если игра - стратегия, то такое не делается по куче причин.
Если игра - РПГ, например, то все вейпоинты мобов лежат на плечах дизайнера уровней.
Если игра - шутер, то пишется скрипт, которые автоматически считает роуты и хайдспоты по пути для ботов.
Кстати, обратите внимание на один хитрый нюанс, в задании есть оговорка, что путь должен быть кратчайшим. Некоторые быстрые "аналитические" алгоритмы поиска пути находят далеко не кратчайший путь, а просто "хороший" путь к цели, такие с большой долей вероятности засыпятся на заковыристых заданиях со сложной картой.
Еще есть оговорка, что это путь туда и обратно. На сетке с одинаковой проходимостью это условие кажется лишним, так что либо авторы вопроса просто "старались", либо есть какая-то заковырка, суть которой мне не ясна.
Еще из интересного есть решение задачи выбора при наличии нескольких путей одинаковой сложности - тут можно проявить массу креатива (желательно так, чтобы автоматический тест алгоритм все-же проходил, а красивости были доступны уже в ручном режиме, если до него в принципе дойдет дело и алгоритм не будет отфильтрован раньше по формальным признакам).
Предобработкой карты. В реальных играх никто не рубит в лоб A* или чем-там ещё сколько бы не был он оптимизирован. Если у тебя большая карта и много юнитов, то ты просто заранее считаешь популярные пути, делишь карту на сектора с известными путями между ними и прочая - вот там полёт фантазии не ограничен ничем. Может быть 4 секунды тут дают именно на демонстрацию такого подхода.
Сильно сомневаюсь, что в этом дело. Во-первых давать завышенный фиксированный лимит времени это стандартная практика при использовании автоматической проверки решений. Во-вторых с таким подходом просто не где развернуться в этом задании - на каждой итерации используется новая копия твоей программы и, скорее всего, другая карта, а запрос на поиск маршрута только один за итерацию - буферизировать и оптимизировать банально не чего. Думаю, если бы ожидалось решение такого типа, то и условия проверки были бы соответствующие.
Как можно решить такую фигню "необычным способом"?
Предобработкой карты. В реальных играх никто не рубит в лоб A* или чем-там ещё сколько бы не был он оптимизирован. Если у тебя большая карта и много юнитов, то ты просто заранее считаешь популярные пути, делишь карту на сектора с известными путями между ними и прочая - вот там полёт фантазии не ограничен ничем. Может быть 4 секунды тут дают именно на демонстрацию такого подхода.
А вообще явно задание на общее нахождение в теме и организацию архитектуры решения, оформление кода, как ты оптимизацию используешь и всё такое.
BLOG-TARANES
Комментарии проекта Логово Снежного Волка
Работа в Paradox Interactive
Хотел бы ты работать в Paradox Interactive, самом дружелюбном к утконосам работодателе на свете? Ты умеешь кодить? Отлично, выполни тестовое задание и возможно…
Если игра - РПГ, например, то все вейпоинты мобов лежат на плечах дизайнера уровней.
Если игра - шутер, то пишется скрипт, которые автоматически считает роуты и хайдспоты по пути для ботов.
prog:
Ред. prog
/thread