Seguir caminho (path following)

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

Categoria de Programação

Postado em 29 junho 2023

Atualizado em 29 junho 2023

Palavras-chave: steering,behavior,busca,seek,path,following,seguir,caminho

Visualizações: 901



O deslocamento de agentes em um ambiente virtual pode ser efetuado de diversas formas. Dependendo do objetivo do agente dentro desse ambiente, o método de deslocamento utilizado pode ser um método existente. Um método existente, é um algoritmo já criado e publicado por outros programadores. Integrando algoritmos de outros desenvolvedores pode poupar tempo no desenvolvimento de comportamentos de agentes, em ambientes como jogos ou simulações.

Os comportamentos de navegação são um bom exemplo de algoritmos existentes que podem ser utilizados em determinados ambientes de simulação. Os comportamentos de navegação (steering behaviors) foram desenvolvidos por Craig Reynolds em 1897 e ainda apresentam grande eficiência quando adotados. O comportamento “path following” é um grande exemplo de método eficiente para fazer agentes seguirem um caminho pré-determinado.

O que é o comportamento “path following”?

Em português, “seguir caminho” é um comportamento que pertence aos comportamentos de navegação. Esse comportamento faz com que o agente siga um caminho pré-determinado em um plano virtual. Uma grande característica do comportamento “path following” é que o agente não segue o caminho perfeitamente. Em outras palavras, o agente pode desviar um pouco do caminho pré-determinado em curvas dependendo da sua velocidade atual.

Essa “imperfeição” é proposital, pois isso torna o deslocamento do agente mais realístico. Quando a curva é muito acentuada, o agente não pode simplesmente cancelar a sua velocidade atual e mudar de direção. Nesse caso, o agente irá sair um pouco do eixo principal na curva.

comportamentos de navegação seguir caminho

Se o agente diminuir a velocidade, provavelmente ele poderá virar a curva sem sair do caminho. Outros fatores como força máxima também influenciam no trajeto, pois é a força que determina a resistência em uma mudança de direção do agente.

O comportamento “seguir caminho” utiliza o comportamento de busca (seek), que também é um comportamento que pertence ao steering behaviors. Como o trajeto é ligado através de pontos, o agente irá procurar os pontos na ordem em que eles foram armazenados em uma lista. Na imagem acima, o caminho é ligado através de três pontos, tendo três caminhos e três curvas. Usando o método de busca, o agente “busca” por um ponto na tela. Quando a distância entre o agente e o ponto está próxima, o agente busca pelo próximo ponto na lista de pontos. Esse comportamento se repete infinitamente até que algo interrompa esse ciclo.

Desenvolvendo o algoritmo de “path following”

Antes de tudo é necessário implementar o básico. Ao todo são três classes:

  • Agente
  • Caminho
  • Principal

O agente tem o formato triangular na tela e também é chamado de BOID ou veículo. O caminho é uma classe com uma lista de todos os pontos que compõem o caminho. A classe principal simplesmente instancia e usa essas classes.

Desenvolvendo o agente

O agente possui cinco atributos importantes:

  • Posição
  • Velocidade
  • Aceleração
  • Velocidade máxima
  • Força máxima

A posição, velocidade e a aceleração são vetores geométricos que são atualizados constantemente. A velocidade máxima e a força máxima são valores fixos. Esses cinco valores são usados no deslocamento do agente.

Além dos cinco atributos acima, existem mais dois atributos:

  • Caminho (para armazenar a instância do caminho)
  • Número do ponto atual (ponto que liga os caminhos)

Os atributos são definidos no construtor da classe do agente.

class Agent {
    constructor(x, y) {
        this.position = createVector(x, y)
        this.size = 20
        this.maxSpeed = 5
        this.maxForce = 0.25
        this.velocity = createVector(0, 0)
        this.acceleration = createVector(0, 0)
        this.followingNodeIndex = null
    }

    setPath(path) {
        this.path = path
        this.followingNodeIndex = 0
    }
}

Além das funções acima, a classe agente possui outras 4 funções:

  • draw (exibir na tela)
  • seek (busca)
  • follow path (seguir caminho)
  • move (deslocamento)

A função draw e seek não serão documentadas aqui. A implementação da função draw está documentada no comportamento “vagar”.

move() {
    this.velocity += this.acceleration
    this.velocity.limit(this.maxSpeed)
    this.position += this.velocity
    this.acceleration *= 0
}

followPath() { // TODO }

A função “followPath” é a função principal e será implementada mais adiante. “Move” é responsável pelo deslocamento do agente. Em cada frame, o valor da aceleração é adicionada na velocidade até que o valor acumulado chegue no valor da velocidade máxima. Em seguida, esse valor acumulado é adicionada no valor de posição do agente. No final, a aceleração é zerada.

Desenvolvendo o caminho

O caminho é uma classe simples com duas simples funções:

  • draw
  • add node (adiciona um ponto)

A classe caminho possui apenas uma variável local: a lista de pontos.

class Path {
    constructor() {
        this.nodes = []
    }
}

Ainda dentro da classe “Path”, implementamos a classe de exibição do caminho e de adição de pontos:

draw() {
    for (let i = 0; i < this.nodes.length; i++) {
        if (i > 0) {
            line(this.nodes[i - 1].x, this.nodes[i - 1].y, this.nodes[i].x, this.nodes[i].y)
        }
        
        if (i == this.nodes.length - 1) {
            line(this.nodes[i].x, this.nodes[i].y, this.nodes[0].x, this.nodes[0].y)
        }

        circle(this.nodes[i].x, this.nodes[i].y, 20)
    }
}

addNode(node) {
    this.nodes.push(node)
}

Na função “draw” simplesmente fazemos um loop para exibir todos os pontos na tela. Além dos pontos, também exibimos as linhas que conectam cada ponto. Na função “addNode” adicionamos um ponto na lista. Isso é o suficiente para a classe “Path”.

Desenvolvendo a classe principal

A classe principal é responsável por instanciar as outras classes e invocar as funções necessárias. Ela tem o mesmo papel da classe “main” em java.

let agent;
let path;

function setup() {
    createCanvas(500, 400);
    agent = new Agent(width / 2, height / 2)
    path = new Path();
    path.addNode(createVector(50, 50))
    path.addNode(createVector(width - 50, 50))
    path.addNode(createVector(width - 150, 150))
    path.addNode(createVector(width - 50, 200))
    path.addNode(createVector(width - 150, height - 50))
    path.addNode(createVector(50, height - 50))
    path.addNode(createVector(width / 2, height / 2))
    path.addNode(createVector(60, 250))
    agent.setPath(path)
}

function draw() {
    background(220)
    path.draw()
    agent.followPath()
    agent.draw()
}

A posição inicial do agente é no centro da tela. Oito pontos são adicionados ao caminho. Esse será o contexto que o comportamento “path following” será implementado.

Implementando o comportamento de “seguir caminho”

Existem várias formas de implementar o comportamento de seguir um caminho. Dois exemplos são:

  1. Simplesmente buscar um ponto por vez
  2. Encontrar o ponto normal entre dois pontos e continuar avançando

O primeiro método é o mais simples. O segundo método é uma extensão do primeiro método.

Buscar um ponto de cada vez

Simplesmente armazenamos o nó (ponto) destino do agente dentro da variável “followingNodeIndex”. Uma vez que o agente chegar nesse nó destino, a variável aumenta e o nó destino muda.

Dentro da função “followPath” implementamos o conteúdo responsável por deslocar o agente ponto por ponto.

followPath() {
    // Número do nó destino atual
    let currentNodeIndex = this.followingNodeIndex;
    // Nó destino
    let destinationNode = this.path.nodes[currentNodeIndex]

	// Posição do agente no futuro
    let futurePos = this.position.copy().add(this.velocity)
    // Tamanho do campo necessário pro agente atingir o seu destino
    let range = 60

    if (futurePos.distance(destinationNode) < range) {
		// Se atingir o destino, o número do nó destino atual é aumentado
        if (currentNodeIndex + 1 >= this.path.nodes.length) {
            this.followingNodeIndex = 0
        } else {
            this.followingNodeIndex += 1
        }
    }

	// Busca pelo nó destino
    this.seek(destinationNode)
    this.move()
}

No exemplo acima, o agente chega em cada nó destino sem problemas. Na maioria dos casos, a implementação acima é o suficiente para alguns ambientes de simulação. Porém, o método acima pode possuir alguns problemas, pois na realidade, o agente não está muito preocupado em andar dentro do trajeto. Por mais que o agente aparente estar percorrendo sobre o trajeto, ele está apenas buscando pelo nó destino.

comportamentos de navegação seguir caminho exemplo de falha

O valor do tamanho do campo necessário (range) para o agente reconhecer que chegou ao destino é de 60. Quando o trajeto possui variações em uma curta distância, o agente parece ignorar o nó. Mas naverdade, o agente reconhece que chegou ao destino. Também é possível diminuir o valor do “range” para 30. Essa diminuição parece resolver o problema, porém faz com que o agente reconheça que chegou ao destino atrasado. Consequentemente, o agente sai mais do trajeto principal do que antes.

Para resolver esse problema, o agente deve voltar ao trajeto e buscar o nó destino. No exemplo acima, o agente está apenas buscando pelo nó destino.

Encontrar o ponto normal entre dois pontos e continuar avançando

Esse método é uma extensão do método anterior. Após a sua aplicação, o agente deve ser capaz de se manter dentro do trajeto com mais efetividade.

A grande diferença é que agora precisamos de um ponto de início e um ponto final para encontrar o ponto normal. O ponto normal é o produto escalar entre dois vetores. O produto escalar será responsável por guiar o agente para dentro do trajeto.

comportamentos de navegação seguir caminho ponto normal

O ponto vermelho representa o ponto normal. O ponto normal avança junto com o agente, porém ele sempre estará dentro do trajeto independente da posição atual do agente. Invés de buscar o nó destino, o agente busca pelo ponto normal e o ponto normal busca pelo nó destino.

getNormalPoint(predictLocation, startPoint, endPoint) {
    // Diferença entre o local previsto e o ponto inicial
    let diffToPredictLocation = predictLocation - startPoint
    // Diferença entre o ponto final e o inicial
    let diffToEndPoint = endPoint - startPoint
    // Normaliza o vetor
    diffToEndPoint.normalize()
    // Encontra o produto escalar
    let scalarPoint = diffToPredictLocation.dot(diffToEndPoint)
    // Multiplica pelo produto escalar
    diffToEndPoint *= scalarPoint
    // Encontra o ponto normal
    let normalPoint = startPoint + diffToEndPoint
    return normalPoint
}

A função acima usa três parâmetros. Esses parâmetros serão passados dentro da função “followPath”. Apagamos a implementação do exemplo anterior e escrevemos o algoritmo abaixo:

followPath(path) {
    // Prevê o movimento do agente usando um número arbitrário
    let predict = this.velocity.normalize() * 20
    let predictLocation = this.position + predict
	
	// Obtém o número nó de início e o nó de destino
    let currentNodeIndex = this.currentPositionIndex
    let nextNodeIndex = currentNodeIndex + 1 == path.nodes.length ? 0 : currentNodeIndex + 1
	
	// Obtém o nó de início e o nó de destino
    let startPoint = path.nodes[currentNodeIndex]
    let endPoint = path.nodes[nextNodeIndex]

	// Encontra o ponto normal
    let normalPoint = this.getNormalPoint(predictLocation, startPoint, endPoint)

	// Coloca o ponto normal mais a frente do agente com um número arbitrário
    let direction = endPoint - startPoint
    direction = direction.normalize() * 30
    normalPoint += direction

	// Busca pelo ponto normal
    this.seek(normalPoint)

	// Se o ponto normal chegar ao nó destino, passa para o próximo nó da lista
    let distanceFromEndNode = normalPoint.distance(endPoint)
    let range = 10
    if (distanceFromEndNode < range) {
        if (this.currentPositionIndex < path.nodes.length - 1) {
            this.currentPositionIndex += 1
        } else {
            this.currentPositionIndex = 0
        }
    }
}

Em seguida, invocamos a função “move” para que o agente possa se deslocar. Na função “followPath”, as seguintes tarefas estão sendo efetuadas:

  • Prevê o movimento do agente (prevê o futuro)
  • Obtém dois nós da lista para usar como caminho inicial e final
  • Encontra o ponto normal
  • Aumenta o valor do ponto normal para que ele possa ficar na frente do agente eternamente
  • Fazer o agente buscar o ponto normal
  • Se o ponto normal chegar no nó destino, passar para o próximo nó

O resultado é mais satisfatório do que no exemplo anterior. Agora o agente retorna para dentro do trajeto além de buscar pelo nó destino.

O ponto verde é o ponto normal. O ponto azul é a previsão do movimento do agente. Os pontos preto e vermelho, são o ponto inicial e o ponto final.

O agente ainda sai do trajeto em curvas acentuadas, porém agora ele está preocupado em voltar para o trajeto e não apenas no nó destino.

Conclusão

O comportamento de seguir caminho pode ser implementado de várias formas. Um método eficiente é encontrar o ponto normal entre o nó inicial e o nó final. Assim, o agente tenta se manter dentro do trajeto e buscar pelo nó destino. “Path following” pode ser combinado com outros comportamentos de navegação como prevenção de colisões para desviar de obstáculos.

Projetos práticos

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.

Tutorial de programação do jogo da serpente em javascript

Programando o clássico jogo da serpente usando o framework p5.js. Tutorial indicado para iniciantes da programação que querem aprender os conceitos básico da área criando jogos.

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.

Usando dados fornecidos pelo TSE para simular o gráfico das eleições presidenciais de 2022

Simulação dos gráficos do segundo turno das eleições presidenciais, utilizando python e ferramentas de análise de dados, pandas e jupyter.

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

Ainda nos primórdios da internet discada, o maior medo de um usuário era o telefone tocar...

Esperávamos horas para baixar apenas alguns megabytes. Nessas horas, quando o telefone tocava nós fazíamos de tudo para não atender o telefone. Mas infelizmente nem sempre dava certo....

Uma das vantagens de ter um robô trabalhando para você é o aumento da produtividade

Hoje em dia não é mais necessário gastar o nosso tempo com tarefas que podem se automatizadas. Os robôs estão aqui para nos ajudar...

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.

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.

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.