среда, марта 03, 2010

Вопросы с собеседования: стиринги

Это третья часть вопросов. Все вопросы можно найти здесь.

Это вопросы по steering behaviors, в просторечье "стиринги". Я видела перевод "стайное поведение", но он мне не очень нравится.

(3a)Как работают системы, эмулирующие стаю? Каковы компоненты такой системы и как они объединены? Когда поведение стаи не работает или дает нежелательный результат? Есть ли в стандартной стайной модели Крэйга Рейнольдса (Craig Reynolds) проблемы с производительностью? Если да, то как с ними справиться?

Модель Крейга Рейнольдса тут.


(3b)Что такое аттракторы и репульсоры? (в оригинале "attractors and repulsors", хороший перевод не придумала) Какое отношение они имеют к стиринг-системе. Когда они полезны, каковы их ограничения? Когда они могут быть использованы для огибания препятствий, а когда их недостаточно?

Можно задать притяжение (это attractors) или отталкивание (repulsor) между объектами. Их можно использовать в дополнении к существующему поиску пути, в дополнении к стирингам. Притяжение и отталкивание не обязательно должны быть линейными. Можно нарисовать всякие интересные кривые. Можно кривые менять во времени. Например, зайцы убегают от волка. Но если у волка мало здоровья, то они убегают вяленько.
Страдают от проблемы локального минимума.
Не нашла ничего в открытом доступе, поэтому отсылаю вас к Game Programming Gems 4, Глава 4.6, Attractors and repulsors.


(3c)Вы начинаете работать над игрой, и один из ваших коллег предлагает полностью отказаться от поиска пути и использовать потенциальные поля для поиска пути и навигации. Он предлагает покрыть весь мир двумерной сеткой, в каждой ячейке которой записано расстояние для ближайшего препятствия. Хорошая ли это идея? Почему "да" или почему "нет"? Когда с этим решением возможны проблемы? Вне зависимости от ответа на этот вопрос, где еще может быть использована такая система?
Идея не хорошая, потому что у потенциальных полей много проблем, они любят застревать в локальных минимумах. Можно их использовать на тайловых малодетализированных уровнях. Подробнее: Motion Planning Using Potential Fields и Using Potential Fields in a Real-time Strategy Game Scenario (Tutorial)


(3d)Вы разрабатываете средневековую стратегию, в которой пехотинцы с пиками всегда должны идти перед лучниками, а катапульты всегда должны быть за лучниками. Расскажите как вы будете реализовывать систему передвижения, в которой пехотинцы будут спереди, а катапульты в тылу, насколько это возможно. Объясните как будет зависеть ваш ответ от того, надо ли просто войску выстроиться на месте назначения в таком порядке, или надо при передвижении сохранять такой порядок.

Краткий ответ. Если надо просто выстроиться в месте назначения - заранее определяем кто где будет стоять и направляем юнитов туда, это просто. Если надо сохранять порядок при передвижении - разделяем юниты по скорости. Обсуждение это вопроса есть тут.
Подробнее смотрите статьи: Movement Issues Facing Game Developers и Implementing Coordinated Movement.


(3e)Вам поручено реализовать толпу людей, прогуливающихся по улицам города. Расскажите о нескольких способах, которыми можно это реализовать быстро и эффективно. Как вы сделаете так, чтобы люди в толпе не дотрагивались друг до друга во время движения? Как они будут уступать друг другу дорогу и не застревать при этом, пытаясь обойти друг друга?

(3f)Дополнение к предыдущему вопросу. Толпа должна разбегаться, когда начинается драка. Как вы реализуете такое разбегание? Как вы сделаете так, чтобы толпа не возвращалась тут же обратно? Как вы сделаете так, чтобы толпа с течением времени "забывала" об этом инциденте и возвращалась обратно?

Repulsor, который с течением времени затухает.


(3g)У вас в игре есть машина на воздушной подушке и дизайнеры хотят, чтобы она двигалась линейно по определенным точкам. Она должна доходить до точки, останавливаться, стрелять в игрока несколько секунд, а затем случайно двигаться к следующей или к предыдущей точке из последовательности. Путь до новой точки должен занимать 4-5 секунд. Как вы реализуете движение такой машины, чтобы оно выглядело как можно более убедительно? Нужно ли здесь использовать физику, если да, то почему?

Я бы сгладила путь сплайнами, ну и всё. Без физики. Если бы это было не воздушная подушка, а грузовик на колесах, пришлось бы делать реалистичный разворот, учитывать радиус разворота.
Подробнее об этом рассказывается в AI game programming wisdom, глава Realistic Turning between Waypoints.

11 коммент.:

Mamon комментирует...

А почему на воздушной подушке
вместе вертолёта?

Alena комментирует...

2Mamon:

А почему на воздушной подушке
вместе вертолёта?


В оригинале hovercraft.

bialix комментирует...

С моим пониманием английского что-то не так. Причем здесь "стая" к steering?

ufonaut комментирует...

Классическая реализация ("boids")подразумевала моделирование поведения стай животных, наподобие рыбных косяков.

mkevac комментирует...

Откуда это? Можно ссылку?

Alena комментирует...

2mkevac:

Откуда это? Можно ссылку?

Ссылка будет в выходные.

mdegtiarev комментирует...

Это вопросы по steering behaviors, в просторечье "стиринги". Я видела перевод "стайное поведение", но он мне не очень нравится.

Мне кажется, "стадный инстинкт" звучало бы лучше ;)

golergka комментирует...

3d

Как пользователь, так и AI должен отдавать приказы не юнитам, а отрядам (пользователь может выбирать отряды, как захочет, а AI должен всё-таки держать какие-то постоянные отряды, причём включать в них разные тактические еденицы). Например, выбрал мышкой 5 юнитов - всё, отряд.

Отряд, в свою очередь, передаёт приказы юнитам. Собственно, именно на этой точке и должно происхить формирование боевого порядка.

Например, клик на позиции x приводит к тому, что пехоте назначаются позции вокруг x+n (где n - вектор направления движения, т.е. пехота оказывается в авангарде), катапультам - наоборот.

Плюс AI каждого конкретного юнита, очень простой: если выбранный враг дальше оптимальной дистанции, подойти, если ближе - отойти.

Не идеально, но по соотношению цена/качество оптимально, ИМХО.

golergka комментирует...

3e

Не застревать - отталкивание а-ля гравитация наоборот. Радиус действия отталкивания, естественно, шире, чем радиус коллизии.

Хождение по улицам: сделать несколько вершин графа (перекрёстков), по достижению любого из них выбирается рандомный сосед.

golergka комментирует...

3f - событие "нанесение урона" создаёт ещё один источник такого же отталкивания. Чтобы добавить анимацию и крики "убивают", сделать простой триггер - если человек находится в радиусе действия такого источника отталкивания, паниковать.

Источник отталкивания, созданный событием "нанесение урона", со временем тухнет (сила отталкивания и радуис). При событии "нанесение урона" проводится проверка; если рядом (совсем рядом! драка может двигаться постепенно) такой источник отталкивания ещё есть, то вместо создания нового этот источник возвращается в исходную силу.

После этого уже можно делать плейтест (в редакторе war3 сделать такую механику, вместе с пешеходами - дело 20 минут). Дальше твики по результатам теста.

sheich комментирует...

Блин, интересно это все!:)