Steering Behaviors (Comportamentos de navegação)

Conjunto de técnicas de algoritmo que simulam comportamentos realísticos. Usado em jogos e em pesquisas biológicas para o estudo de comportamentos.

Categoria de Programação

Postado em 28 abril 2023

Atualizado em 28 abril 2023

Palavras-chave: steering,behavior,comportamento,algoritmo,navegacao,conjunto,jogos,pesquisa

Visualizações: 788



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.

movimento sem usar steering behaviors

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.

movimento usando steering behaviors

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”.

comportamento de navegação com vetores geométricos

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.

comportamento de navegação com vetores geométricos

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(n2)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.

Projetos práticos

Criando o esqueleto de um jogo de tiro 2D visto de cima usando P5.js

Usando lógicas matemáticas como trigonometria para criar e calcular o esqueleto de um jogo de tiro 2D em javascript

Integrando o PHP com Elasticsearch no desenvolvimento de um sistema de busca

Projeto de criação de um sistema de busca usando o framework Symfony e Elasticsearch. A integração com Kibana também é feito de modo remoto com um raspberrypi.

Criando um jogo de pacman usando javascript e pixi.js (parte 1)

Desenvolvimento dos conceitos mais básicos do clássico pacman, como: mapa, animação, deslocamento e detector de colisões.

Desenvolvendo um jogo de quebra blocos em javascript

Programando um jogo clássico de arcade usando javascript e p5.js. O usuário deve quebrar os blocos utilizando uma bola ao mesmo tempo que evita que a bola saia pela parte inferior da tela

Criando artes de texto usando imagens

Convertendo imagens para ascii art usando o valor da intensidade das cores cinzentas.

Veja também

Os computadores usam a numeração binária para a manipulação de dados em circuitos elétricos

A ausência e a presença de energia são dois estados que podem ser usados como valores. Esses valores são respectivamente zero e um.

Nunca se sabe quando tem alguém nos espionando no nosso computador

Um computador conectado à internet está exposto a diversos perigos. O spyware é um deles e é esse malware responsável por roubar contas de redes sociais.

Prevenção de colisões (collision avoidance)

Comportamento usado em steering behaviors para evitar que o agente se choque contra obstáculos durante o percurso do seu trajeto.

Algoritmo

O algoritmo é um conjunto de instruções escritas por um programador com intuito de solucionar um problema ou obter um resultado previsto.

Algoritmo A* (A-estrela)

Algoritmo que busca o caminho com o menor custo entre dois pontos. É usado em jogos e aplicativos de navegação para calcular a menor distância possível.

Direitos autorais

Os direitos autorais são garantidos para qualquer obra intelectual originadas do estado de espírito do autor ainda mesmo no período de desenvolvimento.