Вступление
Boids алгоритм является относительно простой демонстрацией поведения эмерджентного в группе. У него есть три основных правила, описанных его создателем Крейгом Рейнольдсом:
Базовая модель флокирования состоит из трех простых режимов рулевого управления, которые описывают, как маневрирует отдельное судно в зависимости от местоположения и скорости движения его ближайших обитателей:
- Разделение : бычок , чтобы избежать скученности местных flockmates.
- Выравнивание : держитесь в сторону среднего курса местных флокматов.
- Сплоченность : держитесь, чтобы двигаться к среднему положению местных флокматов.
Каждый бид имеет прямой доступ к геометрическому описанию всей сцены, но стая требует, чтобы он реагировал только на флокматов в пределах некоторого небольшого соседства вокруг себя. Соседство характеризуется расстоянием (измеренным от центра стрелы) и углом , измеренным от направления полета стрелы. Flockmates за пределами этого местного соседства игнорируются. Соседство можно было бы считать моделью ограниченного восприятия (как у рыб в мутной воде), но, вероятно, правильнее было бы думать о том, что оно определяет регион, в котором флокмашины влияют на рулевое управление.
Я не идеален при объяснении вещей, поэтому я настоятельно рекомендую проверить источник . У него также есть несколько супер информативных фотографий на своем сайте.
Вызов
Учитывая количество boids (моделируемых объектов) и количество кадров, выведите анимацию моделирования.
- Боиды должны отображаться в виде красного круга с линией внутри круга, показывающей его направление, то есть направление, на которое указывает боид:
- Угол каждого рычага (как описано Рейнольдсом) должен составлять 300 градусов. (не 360)
- Начальный заголовок и позиция каждого штанги должны быть равномерно случайными (но затравленными, чтобы выходные данные по-прежнему определялись), а также позиция.
- Если радиус боида равен 1, то радиус окрестности должен быть равен 3.
- Количество боидов будет где-то 2-20.
- Количество кадров будет где-то 1-5000
- Анимация должна воспроизводиться с минимальным 10 миллисекундами на кадр и максимальным количеством секунд, которое увеличивается в 1 секунду. (2 boids = 2 секунды на кадр максимум, 3 boids = 3 секунды на кадр максимум и так далее)
- Выходная анимация должна быть не менее 5 радиусов boid на 5 радиусов boid, умноженной на половину числа boid-радиусов. Таким образом, минимальный размер для 2 boids был бы 10 boid-радиусами на 10 boid-радиусов, минимальный размер для 3 boids был бы 15 boid-радиусами на 15 boid-радиусов, и так далее.
- Радиус каждой области должен быть не менее 5 пикселей и не более 50 пикселей.
- Скорость каждого бида должна быть ограничена, чтобы он не перемещался более чем на 1/5 своего радиуса в одном кадре.
- Выходные данные должны быть детерминированными, чтобы один и тот же вход давал один и тот же результат, если он запускался несколько раз.
- Если boid достигает границы, он должен вернуться на другую сторону. Точно так же окрестности вокруг каждого бида должны также обернуться вокруг границ.
Правила для алгоритма
В этом случае каждое поле имеет сектор вокруг него, охватывающий 300 градусов, с центром в направлении заголовка. Любые другие boids в этом «соседстве» считаются «соседями», или (если использовать термин Рейнольдса) «flockmates».
Каждый бид должен отрегулировать свой курс, чтобы избежать столкновений и поддерживать удобное расстояние одного радиуса бида со своими соседями. (Это аспект «разделения» алгоритма. Один радиус радиуса действия может быть обойден, но он должен быть как резиновая лента, возвращающаяся на место.)
Каждый бид должен дополнительно отрегулировать свой курс так, чтобы он был ближе к среднему курсу других бидов в его окрестности, если он не мешает первому правилу. (Это аспект «выравнивания» алгоритма)
Каждый бид должен поворачиваться к среднему положению своих флок-товарищей, если это не вызывает столкновения или существенно мешает второму правилу.
В своей статье на эту тему он объясняет это следующим образом:
Чтобы построить имитированное стадо, мы начнем с модели boid, которая поддерживает геометрический полет. Мы добавляем поведение, которое соответствует противоположным силам предотвращения столкновений и побуждению присоединиться к стаду. Кратко изложенные как правила, и в порядке уменьшения приоритета, поведения, которые приводят к моделируемому скоплению:
- Предотвращение столкновений: избегайте столкновений с ближайшими соседями
- Velocity Matching: попытка сопоставить скорость с ближайшими соседями
- Сосредоточение стада: попытка остаться рядом с соседними стаями
Более подробное описание движения:
- Стандартная реализация алгоритма Boids обычно выполняет вычисления для каждого из правил и объединяет их вместе.
- По первому правилу boid проходит список соседних boids в его окрестности, и, если расстояние между ним и соседом меньше определенного значения, вектор, отталкивающий boid от is соседа, применяется к заголовку boid.
- Для второго правила boid вычисляет средний курс своих соседей и добавляет небольшую часть (мы будем использовать 1/10 в этой задаче) разницы между его текущим и средним курсом к его текущему курсу.
- По третьему и последнему правилу boid усредняет позиции своих соседей, вычисляет вектор, который указывает на это местоположение. Этот вектор умножается на еще меньшее число, чем то, которое использовалось для правила 2 (для этой задачи будет использоваться 1/50) и применяется к заголовку.
- Затем груз перемещается в направлении своего направления.
Вот полезная реализация псевдокода алгоритма Boids.
Пример ввода и вывода
Входные данные:Выход:5, 190 (5 боидов, 190 кадров)
Критерий победы
Это код-гольф , поэтому выигрывает самое маленькое решение в байтах.
источник
Ответы:
Обработка 3.3.6 (Java) ,
+932+931940928+957917904 байта-1 байт от Джонатана Фрека
+11 байт, чтобы лучше соответствовать спецификации
-2 байта от Кевина Круйссена
-12 байт для изменения аргументов на t ()
+29 байт, потому что я делал неправильное двоение, см. Закомментированную версию ниже
-40 байт для использования для циклы вместо отдельных вызовов для каждого ghost
-13 байтов для использования по умолчанию frameRate, 30
Ну, это начало для тех, кто не занимается Java-гольфом. :)
Я не знаю какого-либо разумного способа сделать ввод в Processing, поэтому первые две переменные - это входные данные (и я не посчитал их значения (5 байт) в счетчик байтов). Если это проблема, я могу попробовать другие вещи.
Я также не знаю хорошего способа разрешить попробовать его в Интернете (проект Processing.js не может справиться с этим стилем кода) без размещения вещей самостоятельно; и это то, что я не хочу пытаться. Дайте мне знать, если есть что-нибудь умное, что я могу сделать.
Отформатированный код с комментариями
Образец вывода
n = 15, кадры = 400:
Или та же анимация, но показывающая соседство каждого бида.
источник
2*PI
стать,TAU
чтобы сохранить байт?,i,
в ,,i=0,
а затем удалитьi=0
внутри для петли. (-1 байт);frameCount%f==0
доframeCount%f<1
(1 байт);&&
чтобы&
в финале , если2*d>=p.dist(m)&q.angleBetween(v,q.sub(m,p))<=5*PI/6
(-1 байт). Опять же, не уверен, что это возможно, но поскольку обработка кажется довольно похожей на Java, я думаю, что это так. Кроме того, вы можете попробовать создать GIF с screentogif.com .JavaScript (ES6) + HTML5, 1200 байт
Вот мое текущее решение с использованием Canvas API.
eval()
Возвращает каррированной функцию, первый вход являетсяBoid
популяция, а во- вторых это количество кадров анимации. Вы можете использоватьInfinity
для непрерывной анимации.Это
eval(...)
1187 байт и<canvas id=c>
13 байт, что в сумме составляет 1200. CSS не является необходимым, но для удобства он позволяет видеть края холста.редактировать
В соответствии с просьбой, еще один фрагмент с входными данными для населения Boid:
источник
t.a+v+l/10+f/50
, если вы измените это наt.a+v/3+l/10+f/50
, то это приведет к несколько более интересному поведению, но текущая программа меньше и все еще требует спецификаций.