Introdução
O algoritmo de Boids é uma demonstração relativamente simples de comportamento emergente em um grupo. Ele tem três regras principais, conforme descrito por seu criador, Craig Reynolds:
O modelo básico de flocagem consiste em três comportamentos simples de direção que descrevem como um indivíduo faz manobras baseadas nas posições e velocidades de seus companheiros próximos:
- Separação : orientar para evitar aglomerar companheiros de rebanho locais.
- Alinhamento : direcione para a direção média dos companheiros de bando locais.
- Coesão : siga para a posição média dos companheiros de bando locais.
Cada boid tem acesso direto à descrição geométrica de toda a cena, mas o rebanho exige que ele reaja apenas aos companheiros de rebanho dentro de um determinado bairro pequeno ao seu redor. A vizinhança é caracterizada por uma distância (medida a partir do centro do boid) e um ângulo , medido a partir da direção de vôo do boid. Companheiros de rebanho fora deste bairro local são ignorados. O bairro poderia ser considerado um modelo de percepção limitada (como em peixes em águas escuras), mas provavelmente é mais correto pensar nele como definindo a região na qual os companheiros de rebanho influenciam a direção.
Eu não sou perfeito ao explicar as coisas, por isso recomendo verificar a fonte . Ele também tem algumas fotos super informativas em seu site.
Desafio
Dado o número de boids (entidades simuladas) e o número de quadros, produz uma animação da simulação.
- Os boids devem ser renderizados como um círculo vermelho, com uma linha dentro do círculo mostrando seu cabeçalho, que é a direção em que o boid está apontando:
- O ângulo de cada boid (como descrito por Reynolds) deve ser de 300 graus. (não 360)
- O cabeçalho inicial e a posição de cada boid devem ser uniformemente aleatórios (mas semeados, para que a saída ainda seja determinada), bem como a posição.
- Se o raio do boid for 1, o raio da vizinhança deve ser 3.
- O número de boids estará entre 2-20.
- O número de quadros será de 1-5000
- A animação deve ser reproduzida com no mínimo 10 milissegundos por quadro e no máximo 1 segundo vezes o número de boids. (2 boids = 2 segundos por quadro no máximo, 3 boids = 3 segundos por quadro no máximo, etc.)
- A animação de saída deve ter pelo menos 5 raios-x por 5 raios-x, vezes a metade do número de boids. Portanto, o tamanho mínimo para 2 boids seria 10 boid-raio por 10 boid-raio, o mínimo para 3 boids seria 15 boid-raio por 15 boid-raio, etc.
- O raio de cada boid deve ter no mínimo 5 pixels e no máximo 50 pixels.
- A velocidade de cada boid precisa ser limitada para que não mova mais de 1/5 do seu raio em um quadro.
- A saída precisa ser determinada, para que a mesma entrada produza a mesma saída se for executada várias vezes.
- Se um boid atingir uma borda, ele deve voltar para o outro lado. Da mesma forma, a vizinhança em torno de cada boid também deve envolver as fronteiras.
Regras para o algoritmo
Nesse caso, cada boid possui um setor em torno de 300 graus, centrado no cabeçalho do boid. Quaisquer outros boids nesse "bairro" são considerados "vizinhos" ou (para usar o termo de Reynolds) "companheiros de rebanho".
Cada boid deve ajustar seu rumo para evitar colisões e manter uma distância confortável de um raio de boid com seus vizinhos. (Esse é o aspecto "Separação" do algoritmo. O raio de boid pode ser ignorado, mas deve ser como um elástico, voltando ao lugar.)
Cada boid também deve ajustar seu cabeçalho para ficar mais próximo do cabeçalho médio dos outros boids em sua vizinhança, desde que não interfira na primeira regra. (Este é o aspecto "Alinhamento" do algoritmo)
Cada boid deve virar-se para a posição média de seus companheiros de rebanho, desde que isso não cause colisão ou interfira significativamente na segunda regra.
Em seu artigo sobre o assunto , ele explica o seguinte:
Para construir um rebanho simulado, começamos com um modelo boid que suporta vôo geométrico. Acrescentamos comportamentos que correspondem às forças opostas da prevenção de colisões e ao desejo de se juntar ao rebanho. Apresentados resumidamente como regras e em ordem decrescente de precedência, os comportamentos que levam ao flocagem simulada são:
- Prevenção de Colisão: evite colisões com companheiros de rebanho próximos
- Correspondência de velocidade: tente combinar a velocidade com companheiros de bando próximos
- Centragem no rebanho: tente ficar perto de companheiros de rebanho próximos
Descrição mais detalhada do movimento:
- A implementação padrão do algoritmo Boids geralmente faz um cálculo para cada uma das regras e as mescla.
- Para a primeira regra, o boid percorre a lista de boids vizinhos em sua vizinhança e, se a distância entre ele e o vizinho for menor que um determinado valor, um vetor que empurra o boid para longe de seu vizinho é aplicado ao cabeçalho do boid.
- Para a segunda regra, o boid calcula o cabeçalho médio de seus vizinhos e adiciona uma pequena porção (usaremos 1/10 neste desafio) da diferença entre o cabeçalho atual e o cabeçalho médio no cabeçalho atual.
- Para a terceira e última regra, o boid calcula a média das posições de seus vizinhos e calcula um vetor que aponta para esse local. Esse vetor é multiplicado por um número ainda menor do que o usado na regra 2 (para esse desafio, 1/50 será usado) e aplicado ao cabeçalho.
- O boid é então movido na direção de seu cabeçalho
Aqui está uma implementação útil de pseudocódigo do algoritmo Boids.
Exemplo de entrada e saída
Entrada:Resultado:5, 190 (5 boids, 190 quadros)
Critério de vitória
Isso é código-golfe , então a menor solução em bytes vence.
fonte
Respostas:
Processando 3.3.6 (Java) ,
932931940928957917904 bytes-1 byte de Jonathan Frech
+11 bytes para corresponder melhor à especificação
-2 bytes de Kevin Cruijssen
-12 bytes para alterar args para t ()
+29 bytes porque eu estava fazendo fantasmas incorretos; veja a versão comentada abaixo de
-40 bytes para usar para loops em vez de chamadas separadas para cada fantasma
-13 bytes para usar o frameRate padrão, 30
Bem, é um começo, para alguém que não pratica golfe em Java. :)
Como não conheço nenhuma maneira razoável de inserir dados no processamento, as duas primeiras variáveis são as entradas (e eu não contei seus valores (5 bytes) na contagem de bytes). Se isso for um problema, posso tentar outras coisas.
Também não conheço uma boa maneira de permitir a tentativa on-line (o projeto Processing.js não pode lidar com esse estilo de código) sem hospedar coisas; e isso é algo que não estou ansioso para tentar. Deixe-me saber se há algo inteligente que eu possa fazer.
Código formatado, com comentários
Saída de amostra
n = 15, quadros = 400:
Ou a mesma animação, mas mostrando a vizinhança de cada boid.
fonte
2*PI
é possívelTAU
salvar um byte?,i,
para,i=0,
remover oi=0
interior do loop for. (-1 byte);frameCount%f==0
paraframeCount%f<1
(1 byte);&&
para&
na final if2*d>=p.dist(m)&q.angleBetween(v,q.sub(m,p))<=5*PI/6
(-1 byte). Novamente, não tenho certeza se isso é possível, mas como o processamento parece bastante semelhante ao Java, acho que é. Além disso, você pode tentar criar um gif no screentogif.com .JavaScript (ES6) + HTML5, 1200 bytes
Aqui está minha solução atual usando a API do Canvas. O
eval()
retorna uma função de avaliar num cuja primeira entrada é aBoid
população, e o segundo é o número de quadros de animação. Você pode usarInfinity
para animação contínua.São
eval(...)
1187 bytes e<canvas id=c>
13 bytes, perfazendo um total de 1200. O CSS é desnecessário, mas, por conveniência, permite ver as bordas da tela.Editar
Conforme solicitado, outro snippet com uma entrada para a população Boid:
fonte
t.a+v+l/10+f/50
, se você mudar parat.a+v/3+l/10+f/50
, produz um comportamento um pouco mais interessante, mas o programa atual é menor e ainda precisa ser especificado.