Steering behaviors и библиотека OpenSteer

В стратегиях, да и не только в них, часто возникает необходимость реализации следования некоторому пути. Например, пускай нужно для героя проложить путь из замка A в замок B. Рассчитали его по какому-нибудь path finding алгоритму, идем. И тут оказывается, что еще кто-то бредет из замка C в замок D и пересекает нам дорогу. По пути копошатся крестьяне и бродят коровы, их надо бы обойти. И что теперь? Постоянно перестраивать путь? Слишком накладно. Можно слегка изменить направление уже по ходу движения, чтобы избежать столкновения. С крестьянами можно вообще не церемониться, герой в доспехах может их всех просто распихать.
Виды изменения направления по ходу движения и есть steering behaviors. В русском языке адекватный перевод найти оказалось сложно, я встречала термин "стиринг", а также глагол "стирить".
Самый известный ресурс по steering behaviors - это Steering Behaviors For Autonomous Characters Крейга Рейнольдса (Craig Reynolds). Для его понимания достаточно школьного курса математики, той части, что относится к векторам. Кроме уже описанного уклонения от столкновений, там есть довольно много интересных стирингов таких как "преследование" (pursue), "шатание без дела" (wander), "следование пути" (path following) и еще много всяких разных. Если полководец войско ведет, то можно реализовать стиринг "следование за лидером" (leader following), чтобы для каждого юнита не строить свой путь и чтобы они друг другу не мешались.
На открытых пространствах они будут толпой идти, в узком ущелье в колбасу вытянутся.

Стиринги используются не только в играх, в робототехнике, например, роботы могут препятствия огибать с помощью стиринга.

OpenSteer - это open source библиотека стирингов, описанных на Steering Behaviors For Autonomous Characters. Реализованы не все, но многие. Библиотекой ее можно назвать с натяжкой. Вообще это демка, написанная с использованием OpenGL, где код стиринга и код демки намертво спаяны в единое целое. Что будет легче - выдрать оттуда код стиринга и использовать его в своем проекте или написать свой код, посматривая в эту реализацию, сказать сложно. Я пока выбрала второй путь.

OpenSteer: реализация преследования и уклонения

OpenSteer: следование пути, плюс огибание препятствий на этом пути встречающихся.

OpenSteer: игра в футбол с использованием стиринга

Ссылки по теме:
Steering Behaviors For Autonomous Characters
Graphics and Artificial Life - исследования по моделированию поведения пешеходов
dtf.dev.ai "хождение (movement and pathfinding)"

Technorati tag: game development