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.

Categoria de Programação

Postado em 31 maio 2023

Atualizado em 31 maio 2023

Palavras-chave: steering,behavior,perseguir,desviar,prever,futuro,comportamento,trajeto,busca,navegacao

Visualizações: 418



Os comportamentos de navegação (steering behaviors) foram introduzidos pela primeira vez em 1987. Desde então, eles passaram a ser usados em vários tipos de simulação. A primeira aparição dessa técnica de algoritmo foi em uma simulação de revoada de pássaros e um cardume de peixes.

Um conjunto de vários comportamentos possibilitam a simulação de agentes que se comportam como pássaros em uma revoada. Dentro desses comportamentos, já foram publicados os seguintes comportamentos:

Uma das vantagens de utilizar os comportamentos de navegação é a compatibilidade entre os comportamentos. É possível estender alguns comportamentos para que eles se tornem ainda mais realísticos. Os comportamentos de perseguição (pursuit) e esquiva (evade) são exemplos disso.

O que são os comportamentos de perseguição e esquiva?

Os comportamentos de perseguição e esquiva são uma extensão dos comportamentos de busca (seek) e fuga (flee). Os comportamentos de busca e fuga simulam um agente com um desejo de ir em uma determinada direção. O desejo do agente é definido com base no alvo de referência. Em outras palavras, se o agente estiver buscando pelo alvo, a direção desejada será calculada através de uma subtração da distância entre os dois agentes. Essa direção será normalizada e em seguida multiplicada pelo velocidade máxima do agente. O resultado é uma pequena aproximação do agente em relação ao alvo de referência em cada frame. O comportamento de fuga é praticamente idêntico ao comportamento de busca, a única diferença é que a direção desejada será convertida para um valor negativo. O resultado disso é um distanciamento em relação ao alvo de diferença.

Assim como os comportamentos de busca e fuga, os comportamentos de perseguição e esquiva possuem os mesmos valores com um sinal oposto. Se o valor da perseguição é positivo, o valor da esquiva será negativa. A relação entre esses 4 comportamentos pode ser representada da seguinte maneira:

# Original Extensão
1 Busca Perseguição
2 Fuga Esquiva

O comportamento de perseguição estende o comportamento de busca e o comportamento de esquiva estende o comportamento de fuga. A perseguição e a esquiva preveem a trajetória que o alvo irá fazer no futuro, assim antecipando o movimento e tornando a simulação mais realista.

A perseguição pode ser usada para simular agentes que querem alcançar um determinado alvo. Além de ser simples de implementar traz resultados satisfatórios. A esquiva simula um agente tentanto evitar ser capturado, prevendo o movimento do perseguidor e esquivando de uma provável investida.

Resultado antes de usar o algoritmo de perseguição

Antes de começar a usar os algoritmos de perseguição e evasão, vamos conferir como é uma perseguição usando o algoritmo de busca (seek).

Veja que o nosso agente fica logo atrás do alvo mas não pode capturá-lo. Com essa velocidade, poderíamos ter alcançado o alvo, mas o trajeto que o nosso agente percorre não aparenta ser muito eficiente.

Desenvolvendo o algoritmo de perseguição

A perseguição é uma extensão do comportamento de busca. Após obter o valor da força do movimento de busca, modificamos esse valor para prever a trajetório do alvo.

pursue(target) {
    // Posição do alvo para calcular a distância entre os agentes
	let targetPosition = target.position.clone();
	
	// Velocidade do alvo para prever o trajeto do alvo
	let targetVelocity = target.velocity.clone();

	// Distância entre o nosso agente e o alvo
	let distanceBetween = this.position - targetPosition;

	// Calcula a escala da previsão do futuro
	// Perceba que quanto mais os agentes se aproximam, menor é a escala
	let differenceAhead = distanceBetween.magnitude / target.maxSpeed;
	
	// Multipla o valor da velocidade do alvo para prever o trajeto
	targetVelocity *= differenceAhead;

	// Adiciona na coordenada atual a velocidade multiplicada pela escala
	targetPosition += targetVelocity;

	// Passa ao algoritmo de busca uma posição no futuro
	return this.seek(targetPosition);
}

Primeiro, copiamos os vetores de coordenada e velocidade atual do alvo. Em seguida, calculamos a diferença da distância entre os dois agentes. Agora, veja a variável differenceAhead.

escala perseguição steering behaviors pursuit

Veja que conforme a distância entre os agentes fica menor, a escala de previsibilidade do trajeto também diminui. Isso quer dizer que quando o agente 1 chegar o mais perto possível do agente 2, a escala de previsibilidade será provavelmente 1.

Ao multiplicar a escala de previsibilidade ao valor de posição atual do agente 2, apenas estamos adiantando esse valor.

previsão de trajetp steering behaviors pursuit

A coordenada atual do “agente 2 no futuro” será o valor a ser passado como parâmetro para a função buscar.

Em resumo, o agente 1 estima qual será a posição do alvo no futuro. Essa estimativa é baseada na velocidade e na direção do alvo.

Na demonstração acima, note que há um ponto branco se locomovendo junto. Esse ponto branco representa a posição que o nosso agente está perseguindo.

Desenvolvendo o algoritmo de evasão

A evasão é o mesmo valor da perseguição, mas com um sinal negativo. Mas lembre-se que o comportamento de fuga também possui o mesmo valor do comportamento de busca com um sinal negativo. Logo, podemos simplesmente copiar e colar o código do comportamento de perseguição e mudar apenas a função para “this.flee”.

evade(target) {
	let targetPosition = target.position.clone();
	let targetVelocity = target.velocity.clone();
	let distanceBetween = this.position - targetPosition;
	let differenceAhead = distanceBetween.magnitude / target.maxSpeed;
	targetVelocity *= differenceAhead;
	targetPosition += targetVelocity;
	return this.flee(targetPosition);
}

Agora, ao invés de perseguir, o agente irá tentar fugir do nosso agente estimando o trajeto no futuro.

Nessa demonstração diminuímos a velocidade do alvo para podermos acompanhá-lo.

Conclusão

Os comportamentos de perseguição e esquiva preveem o trajeto do alvo para tomarem decisões. Esse algoritmo pode ser eficiente em casos de simulação de captura e fuga de agentes.

Projetos práticos

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

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

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.

Caixa eletrônico usando arquitetura limpa

Usando JavaFX e arquitetura limpa para criar um aplicativo de caixa eletrônico extremamente simples.

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.

Veja também

Os bancos estão sendo substituídos pelos robôs em transações online

As criptomoedas mudaram totalmente o modo das pessoas pensarem. Usar robôs para autentificar transações online, custa muito menos comparado com os bancos em relação às taxas...

A internet é uma terra sem lei. O que vai proteger a nossa rede interna da internet é o firewall

Uma rede interna sem um firewall é como se fosse uma casa com a porta destrancada. Um indivíduo com más intenções pode se aproveitar para a invadir quando menos esperamos.

Busca linear

A busca linear é um algoritmo de força bruta não muito eficiente, mas com grande simplicidade, sendo utilizada regularmente por programadores.

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.

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.

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.