Таранес
Логово Снежного Волка

Работа в Paradox Interactive

Добавлен , опубликован
Тема
Всем привет. Давненько, а может и не очень, не виделись. Решил поделится с вами некоторой информацией, надеюсь кому-то пригодится.
"Достаточно ли ты 1337?
Хотел бы ты работать в Paradox Interactive, самом дружелюбном к утконосам работодателе на свете? Ты умеешь кодить? Отлично, выполни тестовое задание и возможно именно ты станешь частью нашей команды!"
Таков дословный перевод баннера с заглавной страницы парадоксплазы. Ребята из PI ищут талантливого программиста к себе в команду. Возраст, опыт, образование не имеют значения! Главное - талант, способность найти необычное решение проблемы.
Преамбулу к тестовому заданию можно прочитать тут:
career.paradoxplaza.com/jobs/5763-are-your-pro..
Задание может быть выполнено на C, C#, C++, Go, Haskell, Java, JavaScript, Objective-C, PHP, Python 2 или Python 3. Нужно создать алгоритм поиска пути (path-finding algorithm) который позволяет проложить путь и вернуться обратно самым коротким путем между 2 точками на двухмерной плоскости. Лимит времени - 4 секунды. Лимит памяти - 1024 МБ.
Подробнее само тестовое задание можно почитать тут:
https://paradox.kattis.com/problems/paradoxpath
Если кто решиться его сделать - уважуха и респект. Расскажите потом как все прошло. Удачи.
Послесловие
Paradox Interactive - шведская компания, расположенная в Стокгольме, занимающаяся разработкой компьютерных игр, преимущественно глобальных исторических стратегий. Из наиболее известных игр - серии Europa Universalis, Hearts of Iron, Victoria и Crusader Kings.
6 окт 2015
20 249
`
ОЖИДАНИЕ РЕКЛАМЫ...

Показан только небольшой набор комментариев вокруг указанного. Перейти к актуальным.
0
Показать
24
0
Показать
Mihahail, сомневаюсь что кто-то надеется на таком задании получить уникальный алгоритм, который еще не был ни кем придуман, суть задания в другом. Во-первых оценивается сам факт знания алгоритмов поиска пути помимо дийкстры и A*, во-вторых оценивается качество отправленного кода с точки зрения стандартов качества кода и архитектуры (и то и другое уже в ручном режиме после первичного отбора роботом, который отфильтрует все не работающие и слишком медленные алгоритмы). Все выше сказанное - мое личное мнение, основанное на опыте, так что оно вполне может быть ошибочным и не соответствовать действительности.
0
Показать
30
0
Показать
wave algorithm
/thread
0
Показать
14
0
Показать
Praytic,
Как можно решить такую фигню "необычным способом"?
Предобработкой карты. В реальных играх никто не рубит в лоб A* или чем-там ещё сколько бы не был он оптимизирован. Если у тебя большая карта и много юнитов, то ты просто заранее считаешь популярные пути, делишь карту на сектора с известными путями между ними и прочая - вот там полёт фантазии не ограничен ничем. Может быть 4 секунды тут дают именно на демонстрацию такого подхода.
А вообще явно задание на общее нахождение в теме и организацию архитектуры решения, оформление кода, как ты оптимизацию используешь и всё такое.
2
Показать
24
2
Показать
Кстати, обратите внимание на один хитрый нюанс, в задании есть оговорка, что путь должен быть кратчайшим. Некоторые быстрые "аналитические" алгоритмы поиска пути находят далеко не кратчайший путь, а просто "хороший" путь к цели, такие с большой долей вероятности засыпятся на заковыристых заданиях со сложной картой.
Еще есть оговорка, что это путь туда и обратно. На сетке с одинаковой проходимостью это условие кажется лишним, так что либо авторы вопроса просто "старались", либо есть какая-то заковырка, суть которой мне не ясна.
Еще из интересного есть решение задачи выбора при наличии нескольких путей одинаковой сложности - тут можно проявить массу креатива (желательно так, чтобы автоматический тест алгоритм все-же проходил, а красивости были доступны уже в ручном режиме, если до него в принципе дойдет дело и алгоритм не будет отфильтрован раньше по формальным признакам).
Kozinaka:
Предобработкой карты. В реальных играх никто не рубит в лоб A* или чем-там ещё сколько бы не был он оптимизирован. Если у тебя большая карта и много юнитов, то ты просто заранее считаешь популярные пути, делишь карту на сектора с известными путями между ними и прочая - вот там полёт фантазии не ограничен ничем. Может быть 4 секунды тут дают именно на демонстрацию такого подхода.
Сильно сомневаюсь, что в этом дело. Во-первых давать завышенный фиксированный лимит времени это стандартная практика при использовании автоматической проверки решений. Во-вторых с таким подходом просто не где развернуться в этом задании - на каждой итерации используется новая копия твоей программы и, скорее всего, другая карта, а запрос на поиск маршрута только один за итерацию - буферизировать и оптимизировать банально не чего. Думаю, если бы ожидалось решение такого типа, то и условия проверки были бы соответствующие.
2
Показать
30
2
Показать
Kozinaka:
Если у тебя большая карта и много юнитов, то ты просто заранее считаешь популярные пути, делишь карту на сектора с известными путями между ними и прочая
Авторитетно заявляю, что если игра - стратегия, то такое не делается по куче причин.
Если игра - РПГ, например, то все вейпоинты мобов лежат на плечах дизайнера уровней.
Если игра - шутер, то пишется скрипт, которые автоматически считает роуты и хайдспоты по пути для ботов.
\о/
prog:
либо есть какая-то заковырка, суть которой мне не ясна.
Возможно, путь может изменяться.
0
Показать
24
0
Показать
Clamp:
Авторитетно заявляю
Чем подкреплен авторитет, если не секрет?
0
Показать
30
0
Показать
darkowlom, тремя с половиной годами на должностях гейм-дизайнера/дизайнера уровней в паре крупных компаний.
0
Показать
14
0
Показать
Clamp:
Авторитетно заявляю, что если игра - стратегия, то такое не делается по куче причин.
Обоснуй пожалуйста! Я как автор одной-единственной, но стратегии (клона первого Starcraft'а) имею противоположный опыт. Я вообще использовал примитивный поиск в ширину, т.к. он никогда не искал в большой зоне, он был нужен только для поиска внутри мелких квадратов карты и для обхода динамических препятствий. Большие пути собирались из заранее рассчитанных. Только так я мог считать пути сразу для большого количества юнитов вне зависимости от расстояние на которое им нужно было переместиться. Проблемой может быть только динамически изменяющийся ландшафт карты, которого в моём случае не было.
0
Показать
30
0
Показать
Kozinaka:
Обоснуй пожалуйста!
Если руками прописывать роуты и вейпоинты каждой карте, то необходимые для нормального функционирования новых карт действия начнут выходить из компетенции дизайнера уровней, что приведёт к очень сильному повышению затрат на разработку игры в целом. Кроме того, такой подход полностью лишит игру расширяемости за счёт пользовательского контента.
Разумеется, я говорю о более-менее крупных проектах, которые делает команда и которые имеют бюджет в целом.
0
Показать
14
0
Показать
Clamp, никаких роутов и вейпоинтов. Делишь большую карту на крупные квадраты и рассчитываешь кратчайшие пути между центрами этих квадратов. Пути от каждого квадрата к каждому. Теперь когда тебе нужно найти путь из точки А в точку Б, то ты узнаешь в каком квадрате А, в каком квадрате Б. Путь между этими квадратами у тебя уже рассчитан заранее. Осталось просчитать коротенькие пути до центров этих квадратов и сгладить полученный конгломерат, чтобы естественно смотрелось. Дёшево и сердито. Зависимость времени расчета от длины пути - константа! Пофигу куда искать - в соседний тайл или в противоположный конец карты. Астар, не астар, любой честный проход по сетке не может иметь константную сложность.
0
Показать
30
0
Показать
Kozinaka, беру и по результатам плейтестов удаляю какой-нибудь проход, ставлю туда стену, для баланса, например. В результате тебе приходится пересчитывать всю карту и задавать новые значения, а в нормальных играх (давай не будем далеко ходить за примером: SC2 или WC3, или вообще любая игра с редактором) этого делать не надо, только автоматически генерится новая карта проходимости.
Показан только небольшой набор комментариев вокруг указанного. Перейти к актуальным.
Чтобы оставить комментарий, пожалуйста, войдите на сайт.