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

Visualizações: 114

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

Implementando um algoritmo de pathfinding

Implementando um programa que encontra a menor distância entre dois pontos dentro de um labirinto usando o algoritmo A* (a-estrela).

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

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 artes de texto usando imagens

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

Veja também

Um algoritmo não pode ser composto por instruções ambíguas, isso pode trazer resultados inesperados

Os algoritmos na ciência da computação são o principal meio para o desenvolvedor poder escrever instruções para o computador, operando a sua maneira

O endereçamento de dispositivos na internet é automatizado graças ao DHCP

Antigamente o endereçamento de dispositivos era feito manualmente, porém isso traz muitas dificuldades em questão de administração. O DHCP resolve esses problemas

Perseguir (pursuit) e desviar (evade)

Dois tipos de comportamentos que preveem o trajeto do alvo. Em outras palavras, esses dois algoritmos tomam decisões se baseando em informações do futuro.

Vagar (Wander)

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

Diversidade nas empresas

Política e filosofia que tem como objetivo aceitar pessoas de diferentes etnias, comportamentos e características como funcionário.

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.