👨🏻‍🎓 ⚓️ ✍🏾 Encontrar um caminho entre obstáculos redondos 👨‍👩‍👦‍👦 📩 ✋🏽

Navegação florestal

O * Path Finder Algorithm é uma ferramenta poderosa para gerar rapidamente os melhores caminhos. Normalmente, A * é mostrado ao navegar mapas de grades, mas pode ser usado não apenas para grades! Pode funcionar com qualquer gráfico. Você pode usar A * para encontrar o seu caminho no mundo dos obstáculos redondos.

No artigo original, todas as imagens são interativas.

Como um algoritmo resolve esses dois problemas? Vamos começar com uma breve descrição de como o A * funciona.

Algoritmo A *

O algoritmo A * encontra o caminho ideal do ponto inicial ao final, evitando obstáculos ao longo do caminho. Ele percebe isso, expandindo gradualmente muitos caminhos parciais . Cada caminho parcial é uma série de etapas desde o ponto de partida até um ponto intermediário no caminho para a meta. No processo de trabalhar com A *, os caminhos parciais estão se aproximando do ponto final. O algoritmo para de funcionar quando encontra o caminho completo, melhor do que as opções restantes, e isso pode ser provado.

Em cada etapa do algoritmo, A * avalia o conjunto de caminhos parciais e gera novos caminhos, expandindo o caminho mais promissor fora do conjunto. Para fazer isso, A * armazena caminhos parciais em uma fila prioritária, classificados pelo comprimento aproximado - o comprimento real do caminho medido mais a distância restante aproximada do destino. Essa aproximação deve ser subestimada ; isto é, a aproximação pode ser menor que a distância real, mas não maior que ela. Na maioria das tarefas de localização de caminhos, uma boa estimativa discreta é a distância geométrica em uma linha reta desde o final do caminho parcial até o ponto final. O melhor caminho verdadeiro para a meta a partir do final do caminho parcial pode ser maior que essa distância em linha reta, mas não pode ser menor.

Quando A * é iniciado, a fila de prioridade contém apenas um caminho parcial: o ponto de partida. O algoritmo remove repetidamente o caminho mais promissor da fila de prioridade, ou seja, o caminho com o menor tamanho aproximado. Se esse caminho terminar no ponto final, o algoritmo concluiu a tarefa - a fila de prioridade garante que nenhum outro caminho possa ser melhor. Caso contrário, a partir do final do caminho parcial que ele removeu da fila, A * gera vários outros caminhos novos, executando etapas da unidade em todas as direções possíveis. Ele coloca esses novos caminhos de volta na fila de prioridade e inicia o processo novamente.

Contagem

A * trabalha com um gráfico : um conjunto de nós conectados por arestas . Em um mundo baseado em grade, cada nó denota uma célula de malha separada e cada borda é uma conexão com células vizinhas ao norte, sul, leste ou oeste.

Antes de executar A * para a floresta a partir de obstáculos redondos, precisamos convertê-la em um gráfico. Todos os caminhos pela floresta consistem em segmentos alternados de linhas e arcos. Eles são as arestas do gráfico de caminho. Os pontos de extremidade dessas arestas se tornam nós.

Um caminho através de um gráfico é uma série de nós conectados por arestas:

Segmentos e arcos são arestas do gráfico. Vamos chamar os segmentos de arestas de transição , porque o caminho os usa para se mover entre obstáculos. Chamamos arcos de bordas envolventes , porque sua tarefa ao longo do caminho é contornar os lados dos obstáculos.

A seguir, exploraremos uma maneira simples de transformar uma floresta com obstáculos em um gráfico: geraremos todas as bordas e envelopes de transição possíveis.

Geração de borda de transição

As arestas da transição entre um par de círculos são segmentos de linha que mal tocam nos dois círculos; esses segmentos são chamados tangentes a dois pontos e, para cada par de círculos, existem quatro desses tangentes. As tangentes a dois pontos que se cruzam entre os círculos são chamadas tangentes internas a dois pontos , e as que passam para fora são chamadas externas .

Tangentes internas em dois pontos

No passado, a busca de tangentes internas era importante para o cálculo do comprimento da correia que conecta duas polias de tamanhos diferentes, de modo que a tarefa de criar tangentes internas em dois pontos é chamada de problema das correias . Para encontrar as tangentes internas em dois pontos, é necessário calcular o ângulo

t h e t a

$\ theta$ no desenho abaixo.

Como se viu, para círculos com centros

A

$A$ e

B

$B$ e raios

r_{A}

$r_A$ e

r_{B}

$r_B$ cujos centros estão à distância

d

$d$ :

t h e t a = a r c c o s r_{A} + r_{B} s o b r e d

$\ theta = \ arccos {{r_A + r_B} \ sobre {d}}$

Definindo

t h e t a

$\ theta$ podemos encontrar facilmente os pontos

C

$C$ ,

D

$D$ ,

E

$E$ e

F

$F$ .

Tangentes externas a dois pontos

Ao construir tangentes externas (esta é a tarefa das polias ), uma técnica semelhante é usada.

Para tangentes externas, podemos encontrar

t h e t a

$\ theta$ da seguinte maneira:

t h e t a = a r c c o s l v e r t r_{A} - r_{B} r v e r t s o b r e d

$\ theta = \ arccos {{\ lvert r_A - r_B \ rvert} \ sobre d}$

Não importa qual dos círculos é maior, A ou B, mas como você pode ver na figura,

t h e t a

$\ theta$ colocado no lado A mais próximo de B, mas no lado B mais distante de A.

Linha de visão

Em conjunto, as tangentes interna e externa a dois pontos entre os dois círculos formam as arestas da transição entre os círculos. Mas e se uma ou mais arestas de transição fecharem o terceiro círculo?

Se a aresta de transição for sobreposta por outro círculo, precisamos descartá-la. Para reconhecer esse caso, usamos um cálculo simples da distância entre um ponto e uma linha . Se a distância da borda de transição até o centro do obstáculo for menor que o raio do obstáculo, o obstáculo se sobrepõe à borda de transição, portanto, devemos descartá-lo.

Para calcular a distância de um ponto

C

$C$ para um segmento de linha reta

o v e r l i n e A B

$\ overline {AB}$ usaremos o seguinte método :

Primeiro, calculamos

u

$u$ - parte da distância ao longo do segmento

o v e r l i n e A B

$\ overline {AB}$ onde a perpendicular cruza o ponto

C

$C$ :

u = (C - A) c d o t (B - A) o v e r (B - A) c d o t (B - A)

$u = {(C - A) \ cdot (B-A) \ over (B-A) \ cdot (B-A)}$

Então calculamos a posição

E

$E$ em

o v e r l i n e A B

$\ overline {AB}$ :

E = A + m a t h r m g r a m p o (u, 0, 1) * (B - A)

$E = A + \ mathrm {grampo} (u, 0, 1) * (B - A)$

Distância

d

$d$ de

C

$C$ cortar

o v e r l i n e A B

$\ overline {AB}$ É a distância de

C

$C$ antes

E

$E$ :

d = | E - C |

$d = \ | E - C \ |$

Desde

d < r

$d <r$ , o círculo se sobrepõe à linha de visão de

A

$A$ em

B

$B$ , e a borda deve ser descartada. Se

d g e r

$d \ ge r$ então a linha de visão de

A

$A$ em

B

$B$ existe e a costela deve ser deixada.

Geração de envelopes de borda

Os nós do gráfico conectam a borda de transição à borda do envelope. Nas seções anteriores, geramos arestas de transição. Para gerar os envelopes das bordas, começamos a partir do ponto final da borda de transição, contornamos o círculo e terminamos no ponto final de outra borda de transição.

Para encontrar o conjunto de envelopes das arestas de um círculo, primeiro encontramos todas as arestas da transição que são tangentes ao círculo. Em seguida, crie os envelopes das arestas entre todos os pontos finais das arestas de transição no círculo.

Juntando tudo

Tendo gerado arestas de transição, envelopes de arestas e nós e descartado todas as arestas de transição sobrepostas, podemos criar um gráfico e começar a procurar o caminho usando o algoritmo A *.

Aprimoramentos

O procedimento de geração de gráfico que examinamos funciona bem o suficiente para explicar o algoritmo, mas pode ser aprimorado em muitos aspectos. Tais melhorias permitirão que o algoritmo gaste menos recursos de CPU e memória, além de lidar com mais situações. Vejamos algumas das situações.

Obstáculos que se preocupam

Você deve ter notado que nos exemplos mostrados acima, os obstáculos redondos não se sobrepunham e nem tocavam. Supondo que os círculos possam se tocar, isso complica a tarefa de encontrar o caminho

Tangentes de dois pontos

Lembre-se de que tangentes com dois pontos podem ser encontradas usando esta fórmula para tangentes internas:

t h e t a = a r c c o s r_{A} + r_{B} s o b r e d

$\ theta = \ arccos {{r_A + r_B} \ sobre {d}}$

e fórmulas para tangentes externas:

t h e t a = a r c c o s l v e r t r_{A} - r_{B} r v e r t s o b r e d

$\ theta = \ arccos {{\ lvert r_A - r_B \ rvert} \ sobre d}$

Quando dois círculos se tocam ou se cruzam, não há tangentes internas entre eles. Nesse caso

r_{A} + r_{B} a c i m a d e d

${r_A + r_B} \ acima de d$ mais de um. Como o valor da arccosina está fora do domínio da definição

[- 1, 1]

$[- 1, 1]$ não definido, é importante verificar a interseção dos círculos antes de encontrar a arccosina.

Da mesma forma, se um círculo estiver completamente localizado em outro, não haverá tangentes externas entre eles. Nesse caso

r_{A} - r_{B} a c i m a d e d

${r_A - r_B} \ acima de d$ fora de alcance

[- 1, 1]

$[- 1, 1]$ , isto é, não possui arccosina.

Linha de visibilidade da borda de transição

Se permitirmos a possibilidade de tocar ou atravessar obstáculos, surgem novos casos nos cálculos da linha de visão das arestas de transição.

Lembre-se do cálculo

u

$u$ - parte da distância ao longo da borda da transição na qual a perpendicular ao ponto toca a borda. Se não for permitido tocar nos círculos, o valor

u

$u$ fora de alcance

[0, 1]

$[0,1]$ , ou seja, o círculo não pode tocar na aresta, pois para isso teria que tocar em um dos pontos finais da aresta. Isso não é possível porque os pontos finais de uma aresta já estão tangentes a outros círculos.

No entanto, se permitirmos a possibilidade de sobreposição de círculos, os valores

u

$u$ fora de alcance

[0, 1]

$[0,1]$ pode sobrepor a linha de visão ao longo da borda. Isso corresponde aos casos em que o círculo está localizado além do final da aresta de transição, mas sobrepõe ou toca o ponto final. Para rastrear esses casos matematicamente, limitaremos

u

$u$ intervalo

[0, 1]

$[0,1]$ :

E = g r a m p o A + (u, 0, 1) * (B - A)

$E = grampo A + (u, 0, 1) * (B - A)$

Linha de visão do envelope

Quando obstáculos podem se tocar ou se cruzar, os envelopes das bordas podem ser bloqueados por obstáculos da mesma maneira que as bordas de transição. Considere a borda do envelope da figura abaixo. Se o envelope da nervura tocar outro obstáculo, a nervura está bloqueada e deve ser descartada.

Para determinar se o envelope da borda está bloqueado por outro obstáculo, usamos o método a seguir para determinar os pontos nos quais dois círculos se cruzam. Se círculos têm centros em pontos

A

$A$ e

B

$B$ e raios

r_{A}

$r_A$ e

r_{B}

$r_B$ onde

d

$d$ - distância entre

A

$A$ e

B

$B$ , para iniciantes, precisamos verificar vários casos. Se os círculos não se tocam (ou seja,

d > r_{A} + r_{B}

$d> r_A + r_B$ ),
são um dentro do outro (

d < | r_{A} - r_{B} |

$d <| r_A - r_B |$ ) ou corresponder (

d = 0

$d = 0$ e

r_{A} = r_{B}

$r_A = r_B$ ), os círculos não podem afetar os envelopes um do outro.

Se nenhuma dessas condições for atendida, os círculos se cruzam em dois pontos; se os círculos se tocam, esses dois pontos coincidem. Considere o eixo radical que liga os pontos de interseção; é perpendicular à linha que liga

A

$A$ e

B

$B$ em algum momento

C

$C$ . Podemos calcular a distância

a

$a$ de

A

$A$ antes

C

$C$ da seguinte maneira:

a = r_{A}^{2} - r_{B}^{2} + d^{2} s o b r e 2 d

$a = {r_A ^ 2 - r_B ^ 2 + d ^ 2 \ sobre 2d}$

Encontrando

a

$a$ podemos encontrar o ângulo

t h e t a

$\ theta$ :

t h e t a = a r c c o s a o v e r r_{A}

$\ theta = \ arccos {a \ over r_A}$

t h e t a

$\ theta$ é zero, então os círculos tocam em

C

$C$ . Caso contrário, existem dois pontos de interseção correspondentes a positivo e negativo

t h e t a

$\ theta$ .

Em seguida, determinamos se algum dos pontos de interseção está entre os pontos inicial e final do envelope da aresta. Nesse caso, o obstáculo bloqueia a borda do envelope e devemos descartá-la. Observe que não precisamos considerar o caso quando o envelope da aresta está totalmente dentro do obstáculo, porque o recorte ao longo da linha de visão das arestas de transição já descartou essa aresta.

Depois de fazer alterações no cálculo das tangentes em dois pontos e na linha de visão das arestas de transição e dos envelopes das arestas, tudo funciona corretamente.

Raio variável do ator e extensão de Minkowski

Ao calcular a navegação de um objeto redondo no mundo dos obstáculos circulares, pode-se levar em conta observações que simplificam a solução do problema. Primeiro, pode-se simplificar o trabalho observando que o movimento de um círculo de raio r através da floresta é semelhante ao movimento de um ponto através da mesma floresta com uma única alteração: o raio de cada obstáculo aumenta em r . Este é um caso extremamente simples de aplicação da soma de Minkowski . Se o raio do ator for maior que zero, antes de começar, simplesmente aumentamos o tamanho dos obstáculos.

Geração de borda diferida

Em geral, um gráfico para uma floresta de

n

$n$ obstáculos contém

O (n^{2})

$O (n ^ 2)$ arestas de transição, mas como cada uma delas precisa ser verificada quanto à linha de visão com

n

$n$ obstáculos, o tempo total de geração do gráfico é

O (n^{3})

$O (n ^ 3)$ . Além disso, pares de arestas de transição podem levar à criação de arestas de envelope e cada uma delas deve ser verificada com cada obstáculo para a linha de visão. No entanto, devido à alta eficiência do algoritmo A *, ele geralmente olha apenas parte deste grande gráfico para criar o caminho ideal.

Podemos economizar tempo gerando pequenas partes do gráfico rapidamente durante a execução do algoritmo A *, em vez de fazer todo o trabalho antecipadamente. Se A * encontrar o caminho rapidamente, geraremos apenas uma pequena parte do gráfico. Fazemos isso movendo a geração de borda para a função neighbors() .

Existem vários casos. No início do algoritmo, precisamos de vizinhos do ponto de partida. Essas são as arestas da transição do ponto inicial às arestas esquerda e direita de cada obstáculo.

O próximo caso é quando A * chega ao ponto

p

$p$ à beira de um obstáculo

C

$C$ ao longo da borda de transição: os neighbors() devem retornar os envelopes das bordas que saem da

p

$p$ . Para fazer isso, determinamos quais arestas de transição saem do obstáculo calculando as tangentes em dois pontos entre

C

$C$ e todos os outros obstáculos, descartando todos aqueles que não estão na linha de vista. Então encontramos todos os envelopes das bordas conectando

p

$p$ com essas arestas de transição, derrubando as que estão bloqueadas por outros obstáculos. Retornamos todos esses envelopes das bordas, salvando as bordas da transição para retornar em uma chamada subsequente aos neighbors() .

O último caso é quando A * contornou a borda do envelope ao longo do obstáculo

C

$C$ e ele precisa sair

C

$C$ ao longo da borda da transição. Como a etapa anterior calculou e salvou todas as arestas de transição, você pode simplesmente encontrar e retornar o conjunto correto de arestas.

Cortamos os envelopes pontiagudos das costelas

As bordas do envelope conectam as bordas de transição que tocam em um círculo, mas acontece que muitas dessas bordas do envelope não são adequadas para o uso ideal. Podemos acelerar o algoritmo eliminando-o.

O caminho ideal através da floresta de obstáculos sempre consiste em alternar arestas de transição e envelopes de arestas. Suponha que insira um nó

A

$A$ e decida como sair dela:

Entrar através

A

$A$ significa que estamos nos movendo no sentido horário (

c i r c l e a r r o w d i r e i t a

$\ circlearrowdireita$ ) Devemos sair pelo nó, o que nos permite continuar movendo no sentido horário (

c i r c l e a r r o w d i r e i t a

$\ circlearrowdireita$ ), ou seja, só podemos sair pelo nó

B

$B$ ou

D

$D$ . Se você sair pela

C

$C$ então uma inflexão (

c u r l y w e d g e

$\ curlywedge$ ) maneiras que nunca serão ideais. Precisamos filtrar essas arestas pontiagudas.

Primeiro, observe que A * processa cada extremidade não orientada de qualquer maneira.

P l o n g l e f t r i g h t a r r o w Q

$P \ longleftrightarrow Q$ como duas arestas orientadas

P l o n g r i g h t a r r o w Q

$P \ longrightarrow Q$ e

Q l o n g r i g h t a r r o w P

$Q \ longrightarrow P$ . Podemos tirar vantagem disso marcando as bordas e os nós com orientação.

Nós $P$ tornar-se nós com orientação - no sentido horário ( $P \ circlearrowdireita$ ) ou no sentido anti-horário ( $P \ circlearrowleft$ ) setas.
Bordas de transição não orientadas $P \ longleftrightarrow Q$ tornar-se arestas orientadas $P, p \ longrightarrow Q, \ hat {q}$ e $Q, q \ longrightarrow P, \ hat {p}$ onde $p$ e $q$ São orientações e $\ hat {x}$ significa a direção oposta $x$ .
Envelopes de costela não orientados $P \ longleftrightarrow Q$ tornar-se arestas orientadas $P \ circlearrowright \ longrightarrow Q \ circlearrowright$ e $P \ circlearrowleft \ longrightarrow Q \ circlearrowleft$ . É aqui que ocorre a filtragem: não habilitamos $P \ circlearrowdireita \ longrightarrow Q \ circlearrowleft$ e $P \ circlearrowleft \ longrightarrow Q \ circlearrowright$ , porque uma mudança de direção cria torções ( $\ curlywedge$ )

Em nosso circuito, o nó

A

$A$ vai se transformar em dois nós,

A c i r c l e a r r o w d i r e i t a

$A \ circlearrowdireita$ e

A c i r c l e a r r o w l e f t

$A \ circlearrowleft$ tem uma borda de transição de entrada

l o n g r i g h t a r r o w A c i r c l e a r r o w d i r e i t a

$\ longrightarrow A \ circlearrowdireita$ e borda de transição de saída

A c i r c l e a r r o w l e f t l o n g r i g h t a r r o w

$A \ circlearrowleft \ longrightarrow$ . Se pegarmos a estrada através

A c i r c l e a r r o w d i r e i t a

$A \ circlearrowdireita$ então deve sair através do nó

c i r c l e a r r o w d i r e i t a

$\ circlearrowdireita$ que será uma borda de transição

B c i r c l e a r r o w d i r e i t a l o n g r i g h t a r r o w

$B \ circlearrowdireita \ longrightarrow$ (pela borda do envelope

A c i r c l e a r r o w r i g h t l o n g r i g h t a r r o w B c i r c l e a r r o w r i g h t

$A \ circlearrowright \ longrightarrow B \ circlearrowright$ ) ou borda de transição

D c i r c l e a r r o w d i r e i t a l o n g r i g h t a r r o w

$D \ circlearrowdireita \ longrightarrow$ (pela borda do envelope

A c i r c l e a r r o w d i g h t l o n g r i g h t a r r o w D c i r c l e a r r o w r i g h t

$A \ circlearrowdight \ longrightarrow D \ circlearrowright$ ) Não podemos sair completamente

C c i r c l e a r r o w l e f t l o n g r i g h t a r r o w

$C \ circlearrowleft \ longrightarrow$ , porque o sentido de rotação mudará dessa maneira e filtramos o envelope da borda

A c i r c l e a r r o w r i g h t l o n g r i g h t a r r o w C c i r c l e a r r o w l e f t

$A \ circlearrowright \ longrightarrow C \ circlearrowleft$ .

Ao filtrar esses envelopes pontiagudos de arestas do gráfico, aumentamos a eficiência do algoritmo.

Cortar arestas que se cruzam

Os caminhos parciais podem ser cortados, cujas últimas arestas cruzam a penúltima aresta da transição.

Obstáculos poligonais

Veja Gemas de Programação de Jogos 2 , Capítulo 3.10, Otimizando a Localização de Pontos de Visibilidade, escrito por Thomas Young. Este capítulo discute nós de recorte, mas não para círculos, mas para polígonos.

Encontrar um caminho entre obstáculos redondos

Navegação florestal

Algoritmo A *

Contagem

Geração de borda de transição

Tangentes internas em dois pontos

Tangentes externas a dois pontos

Linha de visão

Geração de envelopes de borda

Juntando tudo

Aprimoramentos

Obstáculos que se preocupam

Tangentes de dois pontos

Linha de visibilidade da borda de transição

Linha de visão do envelope

Raio variável do ator e extensão de Minkowski

Geração de borda diferida

Cortamos os envelopes pontiagudos das costelas

Cortar arestas que se cruzam

Obstáculos poligonais

Referências

More articles: