Pathfinding con mapas poligonales

[bnl]

Buenas

Hace tiempo implemente un A* para buscar caminos. El mapa lo dividí en celdas cuadradas que es la forma mas usual de implementarlo y cada una de ellas podia ser atravesable o no.
La cuestíón es que ahora quiero implementarlo pero basandome no en cuadrados sino en poligonos irregulares y no tengo muy claro como hacerlo. ¿Se os ocurre la forma en que se podría implementar? ¿Que función heuristica usariais para estimar la distancia al destino?

Saludos

[Vicente]

Normalmente se suelen partir los polígonos irregulares en triángulos, asignar a cada triángulo un nodo del grafo y aplicar A* como siempre (con heurística la distancia en línea recta entre la posición actual y la de destino). El problema es que triangular un polígono irregular es muy complicado :( (puedes encontrar cosas para empezar con triangulación de delaunay-diagrama de voronoi, el problema de la galería de arte, ears-cutting algorithm y FIST).

Un saludo!

Vicente

[bnl]

Lo de tomar como heurística la distancia en línea recta entre la posición actual y la de destino no se me habia ocurrido.

¿Lo de triangualar que ventajas aportaría?  ¿Como se calcularia el coste real de pasar de un nodo a otro?

A simple vista, triangular un area que no tenga angulos convexos (o concavos siempre me lio con cual es cual) parece facil. Bastaria con tirar lineas desde un vertice a todos los demas que no sean adyacentes ¿se me pasa algo por alto?

[tamat]

yo sería más partidario de marcar waypoints en el mapa para generar el grafo y despues cuando está en el puto más cercano pues que tire en linea recta hacia el destino.

[Vicente]

Generar waypoints también se puede hacer, pero si cambias el mapa tienes que volver a generarlos seguramente (y si tienes muchos mapas es muy aburrido). Generar el grafo por polígonos te permite hacerlo de forma automática.

Triangular te aporta que "estandarizas" el mapa en el sentido de que todo son polígonos de tres lados. Para calcular las distancias yo usaría distancias reales (no acabo de entender el problema, da igual que sean triángulos o cuadrados o lo que sea).

Y lo que dices de triangular es cierto, pero es que estás poniendo una propiedad ya que te facilita mucho las cosas :p

Un saludo!

Vicente

[bnl]

Si no fueran convexos se complicaria todo mucho, imaginate un area con forma de "U", casi habria que hacer otro pathfinding dentro de ese area par air de un extremo a otro.

El problema que yo veo para calcular el coste real de un area es que como no sabes cual será la siguiente area del camino no sabes entre que dos puntos calcular la distancia. Ya que el punto destino estará en diferentes diferentes lados del area dependiendo de cual sea la siguiente area. Incluso podria variar el punto dentro de un mismo lado

Tamat no me ha quedado muy claro lo que comentas de los waypoints, podrias explicarlo un poco mas por favor.

[Vicente]

A ver a ver, una vez has partido el mapa en triángulos, pones un nodo en el centro de cada triángulo y con esos nodos generas un grafo. Después cuando te mueves haces algo como:

- buscar el nodo más cercano a mi posición actual y moverme a él.
- buscar el nodo más cercano a la posición destino.
- hacer A* entre esos dos nodos.
- moverse del nodo final a la posición destino.

Para calcular la distancia entre los nodos del grafo simplemente usas la distancia que los separa en línea recta y listo.

Un saludo!

Vicente

[t-spy]

Si los polígonos son convexos se podría utilizar el punto medio de las aristas del polígono como nodos. El coste de recorrer un polígono sería la distancia entre el punto de entrada y el de salida (que se recorrería en línea recta).

La cuestión es cambiar un poco de filosofía. En lugar de tomar los centros de un grupo de celdas cuadradas como nodos se toman los centros de las aristas de los polígonos, y el coste se calcula con la distancia al punto de salida (hay que tener en cuenta también la distancia desde el punto origen dentro del polígono de salida al primer nodo y la distancia del último nodo al punto dentro del polígono destino).

No sé si me he explicado bien.

[Tei]

A mi lo mas sano es generar waypoints. Encima con la ventaja que si el mapa tiene pasillos o cosas asi, saldran menos nodos que con otros sistemas (como con tiles).
Ademas, y casi por el mismo precio, daria peso a los enlaces. Para que si hay dos rutas, y una es cuesta arriba por barro cenagoso,  y la otra no, que se elija la que no es cuesta arriba. En principio el valor mas obvio seria la longitud del segmento...

[tamat]

Tamat no me ha quedado muy claro lo que comentas de los waypoints, podrias explicarlo un poco mas por favor.

Por waypoints se entiende marcar puntos de paso manualmente en el mapa, zonas por las que es coherente que las entidades se muevan, como caminos, puentes, portales, etc. Luego unes esos waypoints formando un grafo (siendo coherente con las aristas del grafo, es decir, que unan puntos entre los que se puede mover uno), y para calcular rutas pues usas ese grafo, luego puedes refinar el resultado que te da el grafo usando splines o cosas por el estilo para que el movimiento sea más natural.

Claro que esto no funciona si el mapa es algo rollo Ago of Empires, donde todo son explanadas y bosques que van cambiando dinamicamente.

[gdl]

Supongo que este enlace es interesante. La idea es que sólo tienes que poner waypoints en las esquinas de los polígonos.

[bnl]

Muchas gracias a todos, ya lo voy teniendo mas claro :-)

A lo de los waypoints le veo la pega de que implica un esfuerzo adicional para la persona que diseñe el mapa, aunque simplifica el calculo de caminos.

¿Como hallarias el centro de un poligono? Parece algo complicado.

Lo de utilizar el punto medio de la arista parece sencillo de implementar.

[tamat]

¿Como hallarias el centro de un poligono? Parece algo complicado.

(A+B+C) / 3.0f

[bnl]

Ya casi lo tengo implementado, muchas gracias a todos.

Lo que he hecho ha sido utilizar como heuristica la distancia en línea recta como me comentasteis.
He impuesto la limitación de que los poligonos sean convexos y los nodos del grafo son los puntos centrales de cada lado de cada poligono.

Parece que funciona correctamente  :D

Cuando tenga algo de tiempo probablemente suba el código parcial o totalmente a mi blog por si a alguien le puede servir para algo.

Saludos