¿Posible bug con pathfinding?

[osk]

Hola.
Estoy intentando ejecutar el código que os paso adjunto, que pretende ser un ejemplo de pathfinding muy sencillito (el código está bastante comentado para que nadie se pierda), y el ejemplo funciona bien si existe algún camino libre (incluyendo obstáculos traspasables con path_wall()) , pero se queda colgado y sale al cabo de un rato si no hay camino libre posible. Para que lo comprobéis, si queréis, os paso "mapvisible.png", que es la imagen que se ve, y luego "mapcamino.png" que es el mapa de pathfinding sin camino libre, y para comparar, "mapcamino2.png" que es el mapa de pathfinding con camino libre (el cual deberéis renombrar "mapcamino.png" para usar en el programa en vez del anterior).

He comprobado que el tema está cuando se juega con path_wall() en el sentido de que si se utiliza el mapa de pathfinding sin camino libre pero se tiene un valor alto de su parámetro (haciendo que los obstáculos sean traspasables), no hay ningún problema. El problema viene de cuando path_wall se comenta (con lo que sólo hay dos posibilidades: camino libre o nada), que es cuando no existe posibilidad de camino alguno y se el programa de bloquea.

A lo mejor estoy haciendo algo mal yo, pero no sé, el ejemplo es bastante sencillo y no veo el fallo.

Venga, gracias.

[SplinterGU]

creo que no es que se bloquea, se queda calculando demasiado...

[DCelso]

A ver, a mi me pasó algo con el pathfind, tendría que revisar el post que puse sobre esto.
La verdad es que la función está muy limitada, intenté hacer la mia propia y crear un mod_mipath aparte para ello usando el algoritmo C, pero se quedó en proyecto, por ahí arrumbao debo de tenerlo.

[osk]

Gracias por contestar tan rápido.
Splinter, si lo que pasa es que se queda calculando demasiado...¿tiene solución posible este hecho?

[DCelso]

una de las soluciones simples para eso es el reducir la precisión haciendo la imagen del pathfind la mitad de chicha y luego pasándole las coordenadas reales divididas entre dos.
Así sería la mitad de cálculo.

Corregirlo ya por dentro sería intentar estudiar el código del mod_path e intentar buscar optimizaciones y simplificiaciones en el código y proponerselas a splinter.

[SplinterGU]

reducir el mapa es una posible solucion, otra es buscar un mejor algoritmo (si existe), soy un poco ignorante del tema del pathfind (me refiero al codigo)... la verdad que no me puse a analizarlo mucho...

[DCelso]

Lo encontré está aquí
Resumiendo, tienes que pasarle un map de un bit de profundidad al path_find de lo contrario no va bien.
Tienes que hacer que el pixel destino sea un pixel negro en el map de un bit de profundidad sino se cuelga.
Algorítmos alternativos son
Búsqueda A* enlace <- parece facilote

Búsqueda dijkstra enlace <- es mas eficiente pero mas engorroso incluso de entender, además se basa también en ponderaciones entre los caminos entre los puntos, claro está para nuestro caso es 1 ya que son pixeles.

Se podría intentar pasar a bennugd un path_find, no debe ser dificil, de los dos hay implementaciones en c, quizás tratándolos como cajas negras (sabiendo solo usar sus parámetros de entrada y salida) sea casi inmediato, Yo me quedé a medias con la tarea de hacerlo, pero es que no tengo mucho tiempo y esto me resulto un poco más aburrido que otras cosas, por eso lo tengo apartado. Si alguien se atreve, bienvenido sea :D.

[osk]

Muchas gracias DCelso!
Os contaré mis averiguaciones.
Hasta luego!

[Windgate]

Arg, yo también propuse en su día pasar un A* o similar a Bennu... Creo que sería mucho más eficiente que el actual path_find, que a mí no me termina de convencer, para "grandes" distancias no encuentra el camino :S