Steering Behaviors (Comportamentos de navegação)

Existem diversos algoritmos desenvolvidos para simular eventos da vida real em computadores. O comportamento da máquina de realizar tarefas humanas de forma autônoma é chamado de inteligência artificial. Dentro do campo de inteligência artificial, ainda existem outros campos, como a aprendizagem profunda que é um método que faz a máquina aprender imitando o funcionamento do cérebro humano. Todos esses métodos podem ser usados em diversas áreas, podendo ser adaptados do modo que aproveite as suas qualidades da melhor forma.

O campo da robótica e do desenvolvimento de jogos demandam vários tipos de métodos inteligentes para implementação de comportamentos. Conhecer e aplicar esses métodos no momento ideal pode poupar tempo e aumentar a qualidade do produto. Um conceito usado em larga escala em jogos é o Steering Behavior.

O que é steering behaviors?

Em português, pode ser chamado de “comportamentos de navegação”. São um conjunto de técnicas de inteligência artificial para simular agentes com movimentos realísticos. Esses agentes reagem ao ambiente e interagem com os objetos ao seu redor, podendo calcular uma ação e agir de forma autônoma.

A grande vantagem da técnica de steering behaviors é a sua simplicidade. Esse algoritmo funciona com base na informação local, realizando cálculos baseando-se nos vizinhos do agente. Mesmo com poucos recursos, consegue simular padrões de movimentos complexos e realistas, podendo ser implementado sem envolver muitas linhas de código complexo.

Os tipos de ações que podem ser efetuadas com os comportamentos de navegação são:

• Procurar (buscar)
• Fugir
• Chegar (encontrar)
• Vagar
• Perseguir
• Desviar
• Percorrer um caminho
• Alinhamento

Os cálculos são realizados usando vetores geométricos e podem ser combinados uns com outros para realizar múltiplos tipos de movimentos.

O que faz o steering behavior ser tão especial?

Steering behaviors são principalmente usados e valorizados em simulações de movimentos e comportamentos. Jogos podem implementar essas técnicas para tornar o jogo mais emocionante e desafiador. Por exemplo, para o deslocamento de um veículo ser satisfatório, ele deve realizar curvas parecidas com os carros da vida real. Simplesmente deslocar o veículo sem efeitos como derrapagem pode tornar o jogo bastante entediante.

Supondo que o veículo seja o triângulo, o deslocamento realizado não chega nem um pouco perto da realidade. Além disso, não é um movimento satisfatório, podendo deixar jogadores descontentes. Porém, ao utilizar técnicas de steering behaviors, o trajeto percorrido sofre uma variação e se torna mais realístico.

Percebe-se que ao fazer uma curva, o veículo sofreu uma força, cuja força apresentou uma certa resistência em relação a mudança do trajeto. Dependendo da velocidade, pode-se dizer que o carro derrapou para fazer a manobra acima.

Para simular tais movimentos não é necessariamente obrigatório usar steering behaviors. Aplicando conceitos de física como a cinemática (kinematics) é possível simular o mesmo efeito acima. Porém, esse método dificilmente será mais simples e prático do que os comportamentos de navegação. Steering behaviors é muito mais do que um simples movimento, ele é um conjunto de vários comportamentos que podem ser selecionados conforme a demanda do desenvolvedor. Sua importância está em todo seu conjunto de técnicas.

Como funciona o steering behavior?

Os vetores geométricos são constantemente usados no conceito de comportamentos de navegação. Os atributos (variáveis locais de cada agente) mais utilizados como base para os cálculos são posição, velocidade, aceleração e raio de visão. Outro atributo que é calculado a partir dos atributos existentes é a “velocidade desejada”.

A velocidade desejada é a direção onde o agente deseja se locomover, fazendo com que o agente mude a sua rota e chegue ao seu destino. Na imagem acima, o agente possuía uma velocidade que apontava para o sudeste. No meio do caminho, o destino foi modificado e o agente teve que mudar sua rota repentinamente. Porém, o agente não pode simplesmente cancelar a velocidade atual instantaneamente e se locomover para a direção da velocidade desejada. Consequentemente, o agente deve mudar sua rota em direção ao destino sofrendo influência de outras forças, saindo um pouco do eixo e eliminando aos poucos a velocidade anterior. Isso resultará em um movimento circular.

A fórmula para calcular a velocidade desejada é bastante simples:

• steering = desired_velocity - velocity

Steering (navegação) é a velocidade resultante da subtração da velocidade desejada pela velocidade atual. Essa força (steering) será adicionada à aceleração do agente e em seguida a aceleração será adicionada à velocidade atual. No final, a velocidade resultante será adicionada à posição do agente que finalmente irá se locomover.

function moveAgent(target) {
    ...
    let steering = desired_velocity - velocity;
    acceleration += steering;
    // Outros fatores como massa do agente podem ser calculados aqui
    velocity += acceleration;
    position += velocity;
    acceleration *= 0;
}

O cálculo da “desired_velocity” irá depender do tipo de comportamento que buscamos, podendo ser comportamentos como busca ou fuga de um alvo que são elementos contrários.

Como surgiu o steering behavior?

O conceito de comportamentos de navegação foi criado pelo cientista de computação gráfica chamado Craig Reynolds. Ele criou uma simulação de vida artificial em 1987, chamada de “Boids”. Essa simulação imita a revoada dos pássaros e passou a ser chamada de “algoritmo de Boids”. O nome Boid é a abreviação de “bird-oid object” que em português pode ser traduzido para objeto parecido com pássaro.

O algoritmo de Boids imita o comportamento de animais que se locomovem coletivamente, como os pássaros e alguns peixes, como o cardume. A revoada de pássaros é um comportamento que mostra perfeita sincronia entre os pássaros, uma vez que os pássaros podem evitar colisões com os seus vizinhos dentro da revoada e ajustar a própria direção e velocidade em relação aos seus vizinhos de forma sincronizada. Isso cria um efeito cascata, onde a ação de cada agente afeta os seus vizinhos, como resultado, afetando todo o grupo. Não há a presença de um líder definido para coordenar os movimentos, os pássaros seguem regras simples de modo natural e isso acaba originando uma emergência de padrões complexos. No algoritmo de Boids, cada agente segue 3 regras:

1. Evitar colisões: evita colisões com os vizinhos próximos
2. Ajustamento de velocidade: ajusta a velocidade com os vizinhos próximos
3. Aproximação com o rebanho: indivíduos sem grupo se juntam com bandos próximos

Como Craig Reynolds descreve a revoada de pássaros, bando de mamíferos e cardume de peixe?

Em sua documentação “Flocks, Herds, and Schools: A Distributed Behavioral Model” documentada em 1987, Craig Reynolds explica detalhadamente como simulou a revoada de pássaros e outros comportamentos coletivos usando técnicas de computação.

Craig Reynolds diz que “boid flocks” (simulação da revoada de pássaros) é bastante relativo com o sistema de partículas, porém possui algumas diferenças. Os boids deixam de ser apenas um ponto (partícula) e passam a ter uma forma geométrica mais complexa, passando também a ter orientação (direção para a frente). Além disso, o comportamento dos boids é mais complexo do que as partículas, pois cada agente precisa interagir com o ambiente e os agentes ao seu redor.

A expressão “informação local” se refere ao campo que o agente pode enxergar, dando a entender que o agente faz conclusões em base no que ele pode ver. Isso quer dizer que as medidas serão relativas a posição e a orientação do boid. A informação local pode ser convertida para informação global pelo processo de “globalize”, assim como a informação global pode ser convertida para informação local pelo processo de “localize”. Essa conversão é útil para biólogos obter dados estatísticos de simulações de comportamentos de cardumes de peixes e revoada de pássaros em relação a todo o ambiente (body length).

Ambiente computacional de Craig Reynolds em 1987

A complexidade do algoritmo boid é basicamente $O(n^2)$, pois conforme o quadrado (square) da população de agentes presentes em uma revoada aumenta, mais o algoritmo terá que processar informação. Ao adicionar dois agentes, o tempo tomado para o processamento é quadruplicado.

O código e a animação de Boids foram produzidos em um Symbolics 3600 Lisp Machine, cuja máquina teve uma boa performance nos anos 80. A linguagem de programação utilizada para o desenvolvimento do software foi Flavors, cuja linguagem já se tornou obsoleta.

O código aberto contendo técnicas de steering behaviors foi disponibilizado pelo autor Craig Reynolds e se encontra disponível até hoje para o público, com o nome de OpenSteer.

Conclusão

Os comportamentos de navegação são um conjunto de técnicas de algoritmo que simulam comportamentos realísticos de agentes. Essas simulações podem ser úteis para campos que estudam os comportamentos de seres vivos e para o campo de desenvolvimento de jogos. Ainda é amplamente usada para diversas finalidades.