Pathfinding básico con evitación de obstáculos en un espacio 2D continuo

Question

Estoy escribiendo una simulación en la que un objeto criatura debería ser capaz de moverse hacia algún otro objeto arbitrario en el entorno, deslizándose por obstáculos en lugar de hacer un pathfinding inteligente. No estoy tratando de tenerlo plan un camino - solo para moverse en una dirección general, y rebotar alrededor de los obstáculos.

Es un entorno 2D (vista aérea), y cada objeto tiene un rectángulo delimitador para la detección de colisiones. No hay cuadrícula, y no estoy buscando una solución A *.

No he podido encontrar ningún tutorial sobre este tipo de pathfinding "tonto" basado en colisiones, por lo que podría no estar describiendo esto usando los términos más comunes.

¿Alguna recomendación sobre cómo implementar esto (o enlaces a tutoriales)?

Answer 1

Ampliando lo que dijo Guillaume sobre la prevención de obstáculos, una técnica que funcionaría bien para usted es anti-gravity movement. Tratas los obstáculos locales como fuentes puntuales de antigravedad, el destino como gravedad, y tu personaje controlado por computadora se deslizará (¡como el jabón!) Alrededor de los obstáculos para llegar al destino.

Answer 2

he publicado un algoritmo de búsqueda de caminos en C# hace un tiempo

Here's the link

se puede tratar de utilizarlo como punto de partida, es decir, se puede modificar la función que comprueba la siguiente celda para ver si se trata de válido para verificar los obstáculos, y podría alimentarlo con intervalos pequeños en lugar de los puntos inicial y final, como varias rutas de mini pahfinding.

(El texto está en español, pero se puede descargar la aplicación desde el enlace situado en la parte superior)

Answer 3

Tal vez usted podría utilizar Pledge's algorithm

Answer 4

Cada vez que su criatura, viajando en la dirección del vector v, choca con una pared cuya dirección está representada por el vector w, la dirección que necesita para "deslizar" viene dada por el vector que es la proyección de v en w. Este se puede encontrar utilizando

v . w 
--------- w 
|w|*|w| 

donde . es el vector dot product y |w| es la magnitud del vector w (= sqrt(w . w)). Si w es un vector unitario, esto se convierte simplemente

(v . w) w 

Utilizando el vector resultante como la velocidad de su criatura significará su criatura viaja rápidamente cuando se acaba de "pasta" de la pared, y poco a poco cuando golpea la pared casi muerto- en. (Así es como la mayoría de los juegos de disparos en primera persona administran colisiones para el jugador humano.)

Si en cambio quieres que tu criatura viaje siempre a toda velocidad, solo necesitas el signo de v . w - siempre estarás viajando en la dirección que mira la pared (w) o en la dirección opuesta (-w).

El problema que tendrás es cuando tu criatura golpea el muro de forma continua. En ese caso, su vector proyectado será (0, 0), y necesita alguna otra técnica para decidir qué camino tomar (w o -w). El enfoque habitual aquí es A *, aunque esto puede ser innecesario si su entorno posee suficiente estructura.

Answer 5

puede combinar dos algoritmo de dirección:

buscan: se aplica una fuerza de dirección en la dirección que es la diferencia entre la velocidad actual y la velocidad deseada hacia el objetivo

Evitación de Obstáculos : anticipa el futuro del vehículo usando una caja cuya longitud es un tiempo constante multiplicado por la velocidad actual del vehículo. Cualquier obstáculo que cruce esta casilla es una posible amenaza de colisión. La amenaza más cercana se elige para evitarla. Para evitar un obstáculo, se aplica una fuerza de dirección lateral opuesta al centro del obstáculo. Además, se aplica una fuerza de frenado (desaceleración). Estas fuerzas varían con la urgencia (la distancia desde la punta de la caja hasta el punto de posible colisión). La dirección varía linealmente, el frenado varía de forma cuadrática.

Puede encontrar más en la página web "Steering Behaviors For Autonomous Characters"

respecto

Guillaume

PD: Este asumen que está utilizando un método de punto/velocidad/aceleración para el movimiento del objeto.