Cómo utilizar el algoritmo A * hallazgo ruta en una cuadrícula menos plano 2D?

Question

¿Cómo puedo implementar el algoritmo A * en un plano 2D sin rejilla con ningún nodo o células? Necesito el objeto de maniobrar alrededor de un número relativamente alto de estática y obstáculos en movimiento en el camino de la meta. Mi implementación actual es la creación de ocho puntos alrededor del objeto y tratarlos como los centros de los cuadrados adyacentes imaginarias que podrían ser una posición potencial para el objeto. Entonces calculo la función heurística para cada uno y seleccionar la mejor. Las distancias entre el punto de partida y el punto de movimiento, y el movimiento entre el punto y el objetivo que calculan la manera normal con el teorema de Pitágoras. El problema es que de esta manera el objeto a menudo hace caso omiso de todos los obstáculos e incluso más a menudo se atasca en movimiento de ida y vuelta entre dos posiciones. Me di cuenta de lo tonta pregunta podría parecer mu, pero cualquier ayuda se agradece.

Answer 1

Crea una cuadrícula imaginaria a cualquier resolución es adecuado para su problema: Como grano grueso como sea posible para un buen rendimiento, pero lo suficiente de grano fino para encontrar huecos (deseable) entre obstáculos. Su rejilla podría estar relacionado con un árbol cuádruple con su obstáculo objetos también.

Ejecutar A * sobre la rejilla. La rejilla puede incluso ser pre-rellena con información útil como la proximidad a obstáculos estáticos. Una vez que haya un camino a lo largo del cuadrículas, post-proceso que camino en una secuencia de waypoints dondequiera que haya una inflexión en la trayectoria. A continuación, los viajes a lo largo de las líneas entre los puntos de referencia.

Por cierto, no es necesario la distancia real (compárese con su mención del teorema de Pitágoras): * Una fina trabaja con un estimación de la distancia. La distancia Manhattan es una opción popular: |dx| + |dy|. Si el juego de rejilla permite el movimiento en diagonal (o la red es "falso"), simplemente max(|dx|, |dy|) es probablemente suficiente.

Answer 2

Uh. La primera cosa que viene a la mente es, que en cada punto es necesario calcular el pendiente o vector para averiguar la dirección a seguir en el siguiente paso. A continuación, pasar por un pequeño épsilon y rehacer.

Esto, básicamente, crea una rejilla para usted, usted puede variar el tamaño de la celda por la elección de un pequeño épsilon . Al hacer esto en lugar de utilizar una rejilla fija que debe ser capaz de calcular incluso con pequeños grados en cada paso -. Más pequeño que 45 ° de su ejemplo de 8 puntos

En teoría es posible que pueda resolver las fórmulas simbólicamente ( eps contra 0 ), lo que podría conducir a la solución óptima en ... sólo una idea.

Answer 3

¿Cómo se representan los obstáculos? ¿Son los polígonos? A continuación, puede utilizar los vértices del polígono como nodos. Si los obstáculos no están representados como polígonos, podría generar algún tipo de casco convexo que les rodea, y el uso de sus vértices para la navegación. EDIT: Me acabo de dar cuenta, usted ha mencionado que usted tiene que navegar por un número relativamente alto de obstáculos. El uso de los vértices de obstáculos podría ser factible con a muchos obstáculos.

No sé sobre los obstáculos en movimiento, creo que un * no encuentra un camino óptimo de obstáculos en movimiento.

Se menciona que el objeto se mueve hacia atrás y cuarto - A * no deben hacer esto. A * visitas cada punto de movimiento de una sola vez. Esto podría ser un artefacto de la generación de puntos de movimiento sobre la marcha, o de los obstáculos en movimiento.

Answer 4

Me acuerdo que tiene este problema en la universidad, pero no utilizar un A * búsqueda. No puedo recordar los detalles exactos de las matemáticas, pero te puedo dar la idea básica. Tal vez alguien más puede ser más detallada.

Vamos a crear un campo potencial fuera de su área de juego que un objeto puede seguir.

1. Tome su campo de juego y la inclinación ni se deforman de manera que el punto de inicio se encuentra en el punto más alto, y el objetivo está en el punto más bajo.

2. Haga un pozo de potencial hacia abajo en la meta, para reforzar que se trata de un destino.

3. Para todos los obstáculos, crear una colina potencial. Para obstáculos no puntuales, que son los suyos, el campo potencial puede aumentar asintóticamente en los bordes del obstáculo.

Ahora imagine que su objeto como una canica. Si ha colocado en el punto de partida, se debe rodar por el campo de juego, alrededor de los obstáculos, y caer en el objetivo.

La parte difícil, la matemática no me acuerdo, es las ecuaciones que representan cada uno de estos baches y pozos. Si usted darse cuenta de eso, sumarlos para obtener su campo final, a continuación, hacer un poco de cálculo vectorial para encontrar el gradiente (igual que towi dijo) y esa es la dirección que desea ir en cualquier paso. Esperemos que este método es lo suficientemente rápido que se puede calcular de nuevo a cada paso, ya que sus obstáculos se mueven.

Answer 5

Parece que estás implementar Wumpus El juego basado en Norvig y Russel discusión de A * en Inteligencia Artificial: Un enfoque moderno, o algo muy similar.

Si es así, es probable que necesite para incorporar la detección de obstáculos como parte de su función heurística (por lo tanto usted tendrá que tener sensores que alertan a su agente a los signos de los obstáculos, como se ve aquí ).

Para resolver el problema de un lado a otro, es posible que necesite para almacenar el camino recorrido para que pueda saber si ya has estado en un lugar y tienen la función heurisitic examinar el pasado número N de movimientos (digamos 4) y el uso que como un juego de desempate (es decir, si puedo ir al norte y este de aquí, y mis últimos 4 movimientos han sido este, oeste, este, oeste, hacia el norte esta vez)