понедельник, 4 февраля 2019 г.

Про boid

Boid - это алгоритм симуляции стайного поведения (flocking behavior).

Каждый бойдик в стае придерживается трех основных принципов: 

  1. Стая должна оставаться единым целым, для этого каждый участник движется в направлении к центру относительно ближайших соседей;
  2. Бойды стараются не сталкиваться - движутся от соседа, если расстояние стало слишком маленьким;
  3. Бойды стараются сделать свою скорость близкой к скоростям соседей.
Подробнее можно прочитать в разделе Flocking замечательной книги AI for Game Developers (полностью выложена в онлайн). 


В сети можно найти массу готовых симуляций. Вот, например, стая буковок носится по тетрадному листочку. 

Добавление новых правил в алгоритм бойдов может сделать их поведение более интересным. Как научить их избегать стен - рассказано в теме Wall avoidance steering на stackexchange.

А как распараллелить симуляцию? На том же stackexchange есть тема How could you parallelise a 2D boids simulation , где все объясняется с красивыми картинками. Было подмечено, что алгоритм  бойдов очень близок к задаче n тел (которую решают, например, в астрономии и молекулярной динамике). А про параллелизацию этой задачи рассказано здесь (мехмат ЮФУ, по адресу http://edu.mmcs.sfedu.ru еще много чего интересного) и здесь (веселый научный блог, увы заброшенный; в посте - про векторизацию алгоритма с использованием SSE)


Комментариев нет: