🍓 💳 🚱 Encontrar un camino entre obstáculos redondos 📕 📥 👩🏽‍⚖️

Navegación forestal

A * Path Finder Algorithm es una herramienta poderosa para generar rápidamente rutas óptimas. Por lo general, se muestra A * al navegar por mapas desde cuadrículas, ¡pero se puede usar no solo para cuadrículas! Puede funcionar con cualquier gráfico. Puedes usar A * para encontrar tu camino en el mundo de los obstáculos redondos.

En el artículo original, todas las imágenes son interactivas.

¿Cómo un algoritmo resuelve ambos problemas? Comencemos con una breve descripción de cómo funciona A *.

Algoritmo A *

El algoritmo A * encuentra la ruta óptima desde el inicio hasta el punto final, evitando obstáculos en el camino. Se da cuenta de esto, expandiendo gradualmente muchos caminos parciales . Cada camino parcial es una serie de pasos desde el punto de partida hasta algún punto intermedio en el camino hacia la meta. En el proceso de trabajar A *, las rutas parciales se están acercando al punto final. El algoritmo deja de funcionar cuando encuentra la ruta completa, que es mejor que las opciones restantes, y esto se puede probar.

En cada paso del algoritmo, A * evalúa el conjunto de rutas parciales y genera nuevas rutas, expandiendo la ruta más prometedora fuera del conjunto. Para hacer esto, A * almacena rutas parciales en una cola de prioridad, ordenadas por longitud aproximada : la longitud de ruta medida real más la distancia restante aproximada al objetivo. Esta aproximación debe ser subestimada ; es decir, la aproximación puede ser menor que la verdadera distancia, pero no mayor que ella. En la mayoría de las tareas de búsqueda de ruta, una buena estimación subestimada es la distancia geométrica en línea recta desde el final de la ruta parcial hasta el punto final. El verdadero mejor camino hacia la meta desde el final del camino parcial puede ser más largo que esta distancia en línea recta, pero no puede ser más corto.

Cuando se inicia A *, la cola de prioridad contiene solo una ruta parcial: el punto de partida. El algoritmo elimina repetidamente la ruta más prometedora de la cola de prioridad, es decir, la ruta con la longitud aproximada más pequeña. Si esta ruta termina en el punto final, entonces el algoritmo ha completado la tarea: la cola de prioridad asegura que ninguna otra ruta pueda ser mejor. De lo contrario, comenzando desde el final de la ruta parcial que eliminó de la cola, A * genera varias rutas nuevas más, dando pasos unitarios en todas las direcciones posibles. Vuelve a colocar estos nuevos caminos en la cola de prioridad y comienza el proceso nuevamente.

Cuenta

A * funciona con un gráfico : un conjunto de nodos conectados por bordes . En un mundo basado en cuadrícula, cada nodo denota una celda de malla separada, y cada borde es una conexión con celdas vecinas al norte, sur, este u oeste.

Antes de poder ejecutar A * para el bosque desde obstáculos redondos, debemos convertirlo en un gráfico. Todos los caminos a través del bosque consisten en segmentos alternos de líneas y arcos. Son los bordes del gráfico de ruta. Los puntos finales de estos bordes se convierten en nodos.

Una ruta a través de un gráfico es una serie de nodos conectados por bordes:

Ambos segmentos y arcos son bordes del gráfico. Llamaremos a los segmentos los bordes de transición , porque el camino los usa para moverse entre obstáculos. Llamamos arcos a los bordes envolventes , porque su tarea en el camino es rodear los obstáculos.

A continuación, exploraremos una forma simple de transformar un bosque con obstáculos en un gráfico: generaremos todos los bordes de transición y envolventes posibles de los bordes.

Transition Edge Generation

Los bordes de la transición entre un par de círculos son segmentos de línea que apenas tocan ambos círculos; dichos segmentos se llaman tangentes a dos puntos , y para cada par de círculos hay cuatro tangentes. Las tangentes a dos puntos que se cruzan entre los círculos se llaman tangentes internas a dos puntos , y las que pasan afuera se llaman externas .

Tangentes interiores a dos puntos

En el pasado, la búsqueda de tangentes internas era importante para calcular la longitud de la correa que conectaba dos poleas de diferentes tamaños, por lo que la tarea de crear tangentes internas en dos puntos se denomina problema de las correas . Para encontrar las tangentes internas en dos puntos, debes calcular el ángulo

t h e t a

$\ theta$ en el dibujo de abajo.

Al final resultó que, para círculos con centros

A

$A$ y

B

$B$ y radios

r_{A}

$r_A$ y

r_{B}

$r_B$ cuyos centros están a distancia

d

$d$ :

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

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

Definiendo

t h e t a

$\ theta$ podemos encontrar fácilmente los puntos

C

$C$ ,

D

$D$ ,

E

$E$ y

F

$F$ .

Tangentes externas a dos puntos

Al construir tangentes externas (esta es la tarea de las poleas ), se utiliza una técnica similar.

Para tangentes externas podemos encontrar

t h e t a

$\ theta$ como sigue:

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 o v e r d

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

No importa cuál de los círculos sea más grande, A o B, pero como puede ver en la imagen,

t h e t a

$\ theta$ tendido en el lado A más cercano a B, pero en el lado B más alejado de A.

Línea de visión

En conjunto, las tangentes internas y externas a dos puntos entre los dos círculos forman los bordes de la transición entre los círculos. Pero, ¿qué pasa si uno o más bordes de transición cierran el tercer círculo?

Si el borde de transición se superpone con otro círculo, entonces debemos descartar este borde. Para reconocer este caso, usamos un cálculo simple de la distancia entre un punto y una línea . Si la distancia desde el borde de transición hasta el centro del obstáculo es menor que el radio del obstáculo, entonces el obstáculo se superpone al borde de transición, por lo que debemos descartarlo.

Para calcular la distancia desde un punto

C

$C$ a un segmento de línea recta

o v e r l i n e A B

$\ overline {AB}$ utilizaremos el siguiente método :

Primero calculamos

u

$u$ - parte de la distancia a lo largo del segmento

o v e r l i n e A B

$\ overline {AB}$ donde la perpendicular se cruza con el punto

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)}$

Luego calculamos la posición

E

$E$ en

o v e r l i n e A B

$\ overline {AB}$ :

E = A + m a t h r m a b r a z a d e r a (u, 0, 1) * (B - A)

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

Distancia

d

$d$ de

C

$C$ cortar

o v e r l i n e A B

$\ overline {AB}$ Es la distancia de

C

$C$ antes

E

$E$ :

d = | E - C |

$d = \ | E - C \ |$

Desde

d < r

$d <r$ , el círculo se superpone a la línea de visión de

A

$A$ en

B

$B$ , y el borde debe descartarse. Si

d g e r

$d \ ge r$ entonces la línea de visión de

A

$A$ en

B

$B$ existe y la costilla debe dejarse.

Generación de envoltura de borde

Los nodos del gráfico conectan el borde de transición con el borde del sobre. En las secciones anteriores, generamos bordes de transición. Para generar las envolventes de los bordes, comenzamos desde el punto final del borde de transición, rodeamos el círculo y terminamos en el punto final de otro borde de transición.

Para encontrar el conjunto de sobres de los bordes de un círculo, primero encontramos todos los que son tangentes al círculo de los bordes de transición. Luego, cree los sobres de los bordes entre todos los puntos finales de los bordes de transición en el círculo.

Poniendo todo junto

Después de generar bordes de transición, envolventes de bordes y nodos, y luego descartar todos los bordes de transición superpuestos, podemos crear un gráfico y comenzar a buscar la ruta utilizando el algoritmo A *.

Mejoras

El procedimiento de generación de gráficos que examinamos funciona lo suficientemente bien como para explicar el algoritmo, pero puede mejorarse en muchos aspectos. Dichas mejoras permitirán que el algoritmo gaste menos recursos de CPU y memoria, así como manejar más situaciones. Veamos algunas de las situaciones.

Obstáculos que se preocupan entre sí.

Es posible que haya notado que en los ejemplos mostrados anteriormente, los obstáculos redondos no se superponen y ni siquiera se tocan. Asumiendo que los círculos pueden tocarse entre sí, esto complica la tarea de encontrar el camino

Tangentes de dos puntos

Recuerde que se pueden encontrar tangentes a dos puntos utilizando esta fórmula para tangentes internas:

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

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

y 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 o v e r d

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

Cuando dos círculos se tocan o se cruzan, no hay tangentes internas entre ellos. En ese caso

r_{A} + r_{B} s o b r e d

${r_A + r_B} \ sobre d$ más de uno Dado que el valor de la arcocosina está fuera del dominio de definición

[- 1, 1]

$[- 1, 1]$ no definido, es importante verificar la intersección de los círculos antes de encontrar el arcocoseno.

Del mismo modo, si un círculo está completamente ubicado en otro, entonces no habrá tangentes externas entre ellos. En ese caso

r_{A} - r_{B} s o b r e d

${r_A - r_B} \ sobre d$ fuera de rango

[- 1, 1]

$[- 1, 1]$ es decir, no tiene un arcocoseno.

Línea de transición visibilidad del borde

Si permitimos la posibilidad de tocar o cruzar obstáculos, entonces surgen nuevos casos en los cálculos de la línea de visión de los bordes de transición.

Recordar el cálculo

u

$u$ - parte de la distancia a lo largo del borde de la transición en la que la perpendicular al punto toca el borde. Si tocar los círculos no está permitido, entonces el valor

u

$u$ fuera de rango

[0, 1]

$[0,1]$ , es decir, el círculo no puede tocar el borde, porque para esto tendría que tocar uno de los puntos finales del borde. Esto no es posible porque los puntos finales de un borde ya son tangentes a otros círculos.

Sin embargo, si permitimos la posibilidad de superponer círculos, entonces los valores

u

$u$ fuera de rango

[0, 1]

$[0,1]$ puede superponerse a la línea de visión a lo largo del borde. Esto corresponde a casos en los que el círculo se encuentra más allá del final del borde de transición, pero se superpone o toca el punto final. Para rastrear matemáticamente tales casos, limitaremos

u

$u$ intervalo

[0, 1]

$[0,1]$ :

E = A + a b r a z a d e r a (u, 0, 1) * (B - A)

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

Línea de visión de sobre

Cuando los obstáculos pueden tocarse o cruzarse, los sobres de los bordes pueden ser bloqueados por obstáculos de la misma manera que los bordes de transición. Considere el borde del sobre de la figura a continuación. Si la envoltura de la costilla toca otro obstáculo, entonces la costilla está bloqueada y debe descartarse.

Para determinar si la envoltura del borde está bloqueada por otro obstáculo, utilizamos el siguiente método para determinar los puntos en los que se cruzan dos círculos. Si los círculos tienen centros en puntos

A

$A$ y

B

$B$ y radios

r_{A}

$r_A$ y

r_{B}

$r_B$ donde

d

$d$ - distancia entre

A

$A$ y

B

$B$ , para empezar, necesitamos verificar varios casos. Si los círculos no se tocan (es decir,

d > r_{A} + r_{B}

$d> r_A + r_B$ ),
son uno dentro del otro (

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

$d <| r_A - r_B |$ ) o partido (

d = 0

$d = 0$ y

r_{A} = r_{B}

$r_A = r_B$ ), los círculos no pueden afectar los sobres de los demás.

Si no se cumple una de estas condiciones, los círculos se cruzan en dos puntos; Si los círculos se tocan, estos dos puntos coinciden. Considere el eje radical que conecta los puntos de intersección; es perpendicular a la línea que conecta

A

$A$ y

B

$B$ en algún momento

C

$C$ . Podemos calcular la distancia

a

$a$ de

A

$A$ antes

C

$C$ como sigue:

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}$

Encontrar

a

$a$ podemos encontrar el á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$ es cero, entonces los círculos se tocan en

C

$C$ . De lo contrario, hay dos puntos de intersección correspondientes a positivo y negativo.

t h e t a

$\ theta$ .

A continuación, determinamos si alguno de los puntos de intersección se encuentra entre los puntos inicial y final de la envolvente del borde. Si es así, entonces el obstáculo bloquea el borde del sobre y debemos descartar este borde. Tenga en cuenta que no necesitamos considerar el caso cuando la envoltura del borde está completamente dentro del obstáculo, porque el recorte a lo largo de la línea de visión de los bordes de transición ya ha descartado este borde.

Después de realizar cambios en el cálculo de las tangentes a dos puntos y la línea de visión de los bordes de transición y las envolventes de los bordes, todo funciona correctamente.

Radio de actor variable y extensión de Minkowski

Al calcular la navegación de un objeto redondo en el mundo de los obstáculos circulares, se pueden tener en cuenta las observaciones que simplifican la solución del problema. Primero, uno puede simplificar el trabajo al notar que el movimiento de un círculo de radio r a través del bosque es similar al movimiento de un punto a través del mismo bosque con un solo cambio: el radio de cada obstáculo aumenta en r . Este es un caso extremadamente simple de aplicar la suma de Minkowski . Si el radio del actor es mayor que cero, entonces, antes de comenzar, simplemente aumentamos el tamaño de los obstáculos.

Generación de borde diferido

En general, un gráfico para un bosque de

n

$n$ obstáculos contiene

O (n^{2})

$O (n ^ 2)$ bordes de transición, pero dado que cada uno de ellos debe verificarse para ver la línea de visión con

n

$n$ obstáculos, entonces el tiempo total de generación del gráfico es

O (n^{3})

$O (n ^ 3)$ . Además, los pares de bordes de transición pueden conducir a la creación de bordes de envolvente, y cada uno de ellos debe verificarse con cada obstáculo para la línea de visión. Sin embargo, debido a la alta eficiencia del algoritmo A *, generalmente solo se ve una parte de este gran gráfico para crear la ruta óptima.

Podemos ahorrar tiempo generando pequeñas partes del gráfico sobre la marcha durante la ejecución del algoritmo A *, en lugar de hacer todo el trabajo por adelantado. Si A * encuentra la ruta rápidamente, generaremos solo una pequeña parte del gráfico. Hacemos esto moviendo la generación de bordes a la función neighbors() .

Hay varios casos. Al comienzo del algoritmo, necesitamos vecinos del punto de partida. Estos son los bordes de la transición desde el punto de partida a los bordes izquierdo y derecho de cada obstáculo.

El siguiente caso es cuando A * acaba de llegar al punto

p

$p$ al borde de un obstáculo

C

$C$ a lo largo del borde de transición: los neighbors() deben devolver los sobres de los bordes que van desde

p

$p$ . Para hacer esto, determinamos qué bordes de transición salen del obstáculo calculando las tangentes en dos puntos entre

C

$C$ y todos los demás obstáculos, descartando todos aquellos que no están a la vista. Luego encontramos todos los sobres de los bordes conectando

p

$p$ con estos bordes de transición, dejando caer aquellos que están bloqueados por otros obstáculos. Devolvemos todos estos sobres de los bordes, guardando los bordes de transición para devolverlos en una llamada posterior a los neighbors() .

El último caso es cuando A * rodeó el borde del sobre a lo largo del obstáculo

C

$C$ y necesita irse

C

$C$ a lo largo del borde de la transición. Como el paso anterior calculó y guardó todos los bordes de transición, simplemente puede encontrar y devolver el conjunto correcto de bordes.

Cortamos los sobres puntiagudos de las costillas.

Las costillas del sobre conectan los bordes de transición tocando un círculo, pero resulta que muchas de estas costillas del sobre no son adecuadas para su uso de una manera óptima. Podemos acelerar el algoritmo eliminándolos.

El camino óptimo a través del bosque de obstáculos siempre consiste en alternar bordes de transición y envolventes de bordes. Supongamos que entramos en un nodo

A

$A$ y decide cómo salir de él:

Inicie sesión a través de

A

$A$ significa que nos estamos moviendo en sentido horario (

c i r c l e a r r o w r i g h t

$\ circlearrowright$ ) Debemos salir a través del nodo, lo que nos permite continuar moviéndonos en el sentido de las agujas del reloj (

c i r c l e a r r o w r i g h t

$\ circlearrowright$ ), es decir, solo podemos salir por el nodo

B

$B$ o

D

$D$ . Si sales por

C

$C$ entonces una inflexión (

c u r l y w e d g e

$\ curlywedge$ ) formas que nunca serán óptimas. Necesitamos filtrar esos bordes puntiagudos.

Primero, tenga en cuenta que A * procesa cada borde no orientado de todos modos.

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

$P \ longleftrightarrow Q$ como dos bordes orientados

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

$P \ longrightarrow Q$ y

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

$Q \ longrightarrow P$ . Podemos aprovechar esto marcando los bordes y nodos con orientación.

Nudos $P$ convertirse en nodos con orientación - en sentido horario ( $P \ circlearrowright$ ) o en sentido antihorario ( $P \ circlearrowleft$ ) flechas.
Bordes de transición no orientados $P \ longleftrightarrow Q$ convertirse en bordes orientados $P, p \ longrightarrow Q, \ hat {q}$ y $Q, q \ longrightarrow P, \ hat {p}$ donde $p$ y $q$ Son orientaciones, y $\ hat {x}$ significa la dirección opuesta $x$ .
Sobres de costilla desorientados $P \ longleftrightarrow Q$ convertirse en bordes orientados $P \ circlearrowright \ longrightarrow Q \ circlearrowright$ y $P \ circlearrowleft \ longrightarrow Q \ circlearrowleft$ . Aquí es donde ocurre el filtrado: no habilitamos $P \ circlearrowright \ longrightarrow Q \ circlearrowleft$ y $P \ circlearrowleft \ longrightarrow Q \ circlearrowright$ , porque un cambio de dirección crea torceduras ( $\ curlywedge$ )

En nuestro circuito, el nodo

A

$A$ se convertirá en dos nodos,

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

$A \ circlearrowright$ y

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

$A \ circlearrowleft$ tiene un borde de transición entrante

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 r i g h t

$\ longrightarrow A \ circlearrowright$ y borde de transición saliente

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$ . Si salimos a la carretera

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

$A \ circlearrowright$ entonces debería salir por el nodo

c i r c l e a r r o w r i g h t

$\ circlearrowright$ que será un borde de transición

B 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 \ circlearrowright \ longrightarrow$ (a través del borde del sobre

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$ ) o borde de transición

D 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

$D \ circlearrowright \ longrightarrow$ (a través del borde del sobre

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 D c i r c l e a r r o w r i g h t

$A \ circlearrowright \ longrightarrow D \ circlearrowright$ ) No podemos salir por

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 la dirección de rotación cambiará de esta manera, y filtramos la envoltura del borde

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$ .

Al filtrar estos sobres puntiagudos de los bordes del gráfico, aumentamos la eficiencia del algoritmo.

Cortar bordes de intersección

Las rutas parciales se pueden cortar, cuyos últimos bordes de la transición se cruzan con el penúltimo borde de la transición.

Obstáculos poligonales

Ver Game Programming Gems 2 , Capítulo 3.10, Optimización de Pathfinding de puntos de visibilidad, escrito por Thomas Young. Este capítulo trata sobre los nodos de recorte, pero no para los círculos, sino para los polígonos.

Encontrar un camino entre obstáculos redondos

Navegación forestal

Algoritmo A *

Cuenta

Transition Edge Generation

Tangentes interiores a dos puntos

Tangentes externas a dos puntos

Línea de visión

Generación de envoltura de borde

Poniendo todo junto

Mejoras

Obstáculos que se preocupan entre sí.

Tangentes de dos puntos

Línea de transición visibilidad del borde

Línea de visión de sobre

Radio de actor variable y extensión de Minkowski

Generación de borde diferido

Cortamos los sobres puntiagudos de las costillas.

Cortar bordes de intersección

Obstáculos poligonales

Referencias

More articles: