Busca (seek), fuga (flee) e chegada (arrival)

Três tipos de comportamentos usados em steering behaviors para simular comportamentos de seres vivos de forma realística.

Categoria de Programação

Postado em 29 abril 2023

Atualizado em 29 abril 2023

Palavras-chave: steering,behavior,busca,fuga,chegada,seek,flee,arrival,navegacao,comportamento

Visualizações: 447

Steering behaviors (comportamentos de navegação) são um conjunto de técnicas de algoritmo para simular o comportamentos realísticos de animais. Foi apresentado pela primeira vez por Craig Reynolds em 1987, em seu algoritmo Boids, cujo algoritmo simula a revoada de pássaros.

Dentro desse conjunto de técnicas, existem diversos comportamentos que podem ser implementados em jogos, estudos e na robótica. Os comportamentos de busca (seek), fuga (flee) e chegada (arrival) são fáceis de serem implementados e apresentam excelentes resultados.

Desenvolvimento do código básico

Para a utilização de steering behaviors, recomenda-se usar vetores geométricos para calcular as coordenadas com mais facilidade.

A classe do agente é chamada de “vehicle”. A classe Vehicle possui 2 atributos (variáveis locais) essenciais definidos como vetor:

  • Posição
  • Velocidade

A aceleração também pode ser adicionada, porém não será necessário nesse momento. Outras duas variáveis serão adicionadas e influenciarão diretamente o valor da posição e velocidade do agente:

  • Velocidade máxima
  • Força máxima

A velocidade máxima é o limite que a velocidade do agente pode chegar. A força máxima é o limite que o steering (força de navegação) pode chegar.

class Vehicle {
    constructor() {
	    this.position = createVector(width / 2, height / 2);
	    this.velocity = createVector(0, 0);
	    this.maxSpeed = 4;
	    this.maxForce = 0.2;
    }
}

A posição inicial do agente será no centro da tela. Sua velocidade inicial será zero, por isso, não se moverá no início. O objetivo nesse tutorial é fazer o agente (Vehicle) perseguir algum objeto. Esse objeto será instanciado com o clique do mouse.

var target = null;
...
function mousePressed(event) {
	let mousePos = createVector(event.x, event.y);
	target = new Target(mousePos);
}

Em seguida, o algoritmo responsável por fazer o agente perseguir o objeto é implementado (implementação sem steering behaviors):

class Vehicle {
    ...
    function seek() {
	    if (target != null) {
		    // Distância entre o alvo e o agente
		    let destination = this.position - target.position;
		    let direction = destination.normalize();
		    let desiredVelocity = direction * this.maxSpeed;
		    this.position += desiredVelocity;
	    }
    }
}

A função “seek” será executada a cada frame e deslocará o agente aos poucos. A implementação de aproximação entre dois pontos pode ser realizada como mostra acima. O código irá funcionar e o agente irá perseguir o destino. Porém, a prática acima será um simples deslocamento de um objeto com a velocidade constante:

O deslocamento acima deixa muito a desejar quando falamos sobre jogos ou simulação de comportamentos de animais. Para tornar o movimento acima mais realístico usamos a técnica de steering behaviors.

Implementação do comportamento de busca (seek)

O comportamento de busca é melhorado aplicando uma nova força, o “steering”. O “steering” é o resultado da subtração da velocidade deseja pela velocidade atual. Esse resultado será adicionado na velocidade do agente.

comportamento de busca steering behaviors seek

O resultado do movimento acima é um movimento circular do agente para a direita. A velocidade atual que estava apontada para o noroeste foi diminuindo aos poucos e perdendo a sua influência sobre o agente. A velocidade desejada passa a influenciar a posição do agente, fazendo-o com que chegue ao seu destino.

class Vehicle {
    ...
    function seek() {
	    if (target != null) {
		    // Distância entre o alvo e o agente
		    let destination = this.position - target.position;
		    let direction = destination.normalize();
		    let desiredVelocity = direction * this.maxSpeed;
		    
		    let steering = desiredVelocity - this.velocity;
		    steering = steering.limit(this.maxForce);
		    
		    this.velocity += steering;
		    this.velocity = this.velocity.limit(this.maxSpeed);
		    
		    this.position += this.velocity;
	    }
    }
}

A variável “steering” será a força que resistirá à velocidade desejada. A função “limit” limita o valor máximo da variável, fazendo com que os valores não fiquem muito altos.

Diferente do primeiro exemplo, o agente mostra uma certa resistência ao modificar o seu trajeto. Esse efeito é bastante parecido com a inércia, fenômeno que acontece na vida real, pois não é possível anular uma força instantaneamente após aplicar outra.

Implementação do comportamento de fuga (flee)

A lógica do comportamento de fuga é totalmente igual ao comportamento de busca, a única diferença é que o agente irá fugir do alvo. Ao invés da sua velocidade desejada apontar para a direção do alvo, ela irá aponta para a direção contrária do alvo.

comportamento de fuga steering behaviors flee

O agente irá repetir o mesmo movimento circular do comportamento de busca, alternando para a direção mais longe possível do alvo.

A função “flee” pode copiar a função “seek”. A única diferença é que a velocidade desejada irá ser negativa.

 class Vehicle {
    ...
    function flee() {
	    if (target != null) {
		    // Distância entre o alvo e o agente
		    let destination = this.position - target.position;
		    let direction = destination.normalize();
		    let desiredVelocity = direction * this.maxSpeed;
			
			// Multiplica por -1 e torna o valor negativo
			let flee = desiredVelocity * -1;
		    
		    let steering = flee - this.velocity;
		    steering = steering.limit(this.maxForce);
		    
		    this.velocity += steering;
		    this.velocity = this.velocity.limit(this.maxSpeed);
		    
		    this.position += this.velocity;
	    }
    }
}

Ao modificar o sinal do valor da velocidade desejada para negativo, o trajeto que o agente irá percorrer será contrário ao que era antes.

Implementação do comportamento de chegada (arrival)

O comportamento de chegada será combinado com o comportamento de busca. Ao agente chegar no seu destino ele deve parar. A lógica do comportamento de chegada é desacelerar o agente aos poucos até ele entrar na fase de repouso encima do destino. A área de desaceleração da velocidade do agente é definida por um círculo ao redor do alvo. Quanto mais o agente penetra no círculo mais ele perde velocidade. Quando o agente chegar no centro do círculo (encima do alvo) a velocidade dele será zerada, entrando em repouso.

comportamento de chegada steering behaviors arrival arrive

Para saber se estamos dentro do círculo de chegada, usaremos a magnitude do vetor da distância entre o agente e o alvo. Caso a magnitude da distância entre o alvo e o agente seja menor do que o raio do círculo de chegada, o processo de desaceleração é iniciado. O processo de desaceleração é feito diminuindo a magnitude da velocidade desejada conforme o agente se aproxima do centro do círculo.

class Vehicle {
    ...
    function seek() {
	    if (target != null) {
		    // Distância entre o alvo e o agente
		    let destination = this.position - target.position;
		    let magnitude = destination.magnitude();
		    
		    let desiredVelocity = destination.normalize() * this.maxSpeed;
		    if (magnitude < target.radius) {
			    let newMagnitude = map(magnitude, 0, target.radius, 0, this.maxSpeed)
		        desiredVelocity = desiredVelocity.setMagnitude(newMagnitude)
		    }
		    
		    let steering = desiredVelocity - this.velocity;
		    steering = steering.limit(this.maxForce);
		    
		    this.velocity += steering;
		    this.velocity = this.velocity.limit(this.maxSpeed);
		    
		    this.position += this.velocity;
	    }
    }
}

function map(number, inMin, inMax, outMin, outMax) {
    return (number - inMin) * (outMax - outMin) / (inMax - inMin) + outMin;
}

A função “map” vai ajustar o valor da magnitude da velocidade desejada e manter o valor entre 0 e 4 (this.maxSpeed). Conforme a distância entre o agente e o alvo vai se aproximando, menor vai ficando a magnitude da velocidade desejada, até chegar no zero.

Conclusão

Os comportamentos de busca, fuga e chegada são uma porção do conjunto de comportamentos que steering behaviors (comportamentos de navegação) proporciona. Esses movimentos podem ser usados em vários tipos de aplicativos conforme as demandas dos desenvolvedores. A sua grande vantagem é a facilidade na sua implementação, não precisando de cálculos muito complexos e necessitando poucas linhas de código.

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

Desenvolvendo o campo de visão de um personagem em um plano 2D

Detectando objetos que entram dentro do campo de visão do personagem. Útil para servir de "gatilho" para eventos em um jogo.

Criando um sistema de mini garagem automatizada integrada com um sistema de monitoramento independente

Desenvolvimento de um sistema de monitoramento que exibi todos os eventos que acontecem na garagem automatizada, como abertura de portões ou ocupação de vagas.

Criando um sistema de integração contínua (CI/CD)

Fazendo a integração contínua de Jenkins, Sonatype Nexus, Sonatype, JUnit e Gradle para automatizar processos repetitivos. Prática bastante usada em tecnologias de DevOps.

Criando um jogo de guerra nas estrelas em javascript usando a biblioteca p5.js

Jogo simples de guerra espacial desenvolvido em javascript. Esse jogo usa cálculos de física para simular efeitos de atrito e inércia.

Veja também

Qual é o papel das grandes empresas além de fornecer seu serviços?

Poluição do ar, solo e água ainda é um grande problema para ser resolvido ainda em vários países. Há estudos que comprovam que os países mais poluentes podem causar câncer...

Afinal, vale a pena gastar tempo com web marketing?

Expressões como gastar tempo e investir tempo andam lado a lado. Quando algo investido não tem o retorno esperado isso se torna uma perde de tempo...

Seguir caminho (path following)

Um dos comportamentos de navegação (steering behaviors). Faz com que um agente siga um caminho pré-determinado pelo desenvolvedor.

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.

Vagar (Wander)

Técnica de algoritmo que faz o agente vagar pelo ambiente virtual sem um destino definido. Esse comportamento pertence ao steering behaviors.

Busca binária

A busca binária usa o método de divisão de conquista que visa em dividir os problemas em pequenos problemas até que eles se resolvam sozinhos.