Toward more realistic pathfind (hacia un pathfind mas realista)

[Outlaw]

Hola gente! Anduve dando vueltas por la red, buscando algo para mejorar el path_find de bennu y di con esto que hasta el momento me parece de lo mejor que he visto explicando como se puede hacer para mejorar el clasico A*, copie todo el articulo y lo hice .doc, adjunte tambien el ejemplo que esta muy bueno, es en ejecutable, y ademas tiene las fuentes donde estan las rutinas de pathfind propiamente dichas, el detalle de los ejemplos está en la pág. 25. Saludos y espero les paresca interesante!

FUENTE: http://www.gamasutra.com/view/feature/3096/toward_more_realistic_pathfinding.php
P.D. : Está integramente en inglés.

[SplinterGU]

gracias! y la velocidad que tal es? lo probaste? hiciste un test comparando mismo mapa contra bennugd? y viendo que recorridos hacen ambos y que performance da?

si no tenes esa info, estaria bueno si lo podes hacer y ponerlo aca.

gracias!

karma por el trabajo de investigacion... y te reservo otro karma con los resultados del analisis... si ya lo hiciste te doy otro karma luego.

[Outlaw]

Tengo que estudiarlo al tema, ya que es bastante largo y encima implementarlo mas! Estoy con parciales de la facultad asi que me voy a retrasar un poco, por eso lo colgue aca, no para hacer algo ya sino para que todos los que puedan lo vayan leyendo porque me parece que es muy interesante y constructivo, saludos! :D

[SplinterGU]

ah, te habia entendido que habia codigo fuente y ejemplos, entendi mal entonces.

bueno, no te preocupes, ya lo vere.

gracias.

[SplinterGU]

acabo de ver el doc y el codigo fuente, y me da la impresion de que eso es muchisimo mas lento que BennuGD.

como sea, si mal no recuerdo las pruebas que hice hace tiempo, en bennugd no se dan tantos zigzag como se muestra ahi en los algoritmos simples.

te comento, que el codigo ese usa un algoritmo similar a bennugd, pero luego de obtener el camino, tiene algunas funciones que hacen curvas.

[Windgate]

El A* en teoría es de los mejores, sobre todo para problemas de IA simples como es el caso del típico tablero con obstáculos en media resuelve cualquier cosa en un tiempo muy bueno. Para un ajedrez ya la cosa cambiaría sobre todo por temas de consumo de recursos, pero no es el caso del tipo de path_find que nos ocupa :P

¿Está anotado en la documentación cuál es el algoritmo es el que usa Bennu ahora mismo? Creo que estaría bien tenerlo bien sabido, ya que si es por ejemplo un A* ya podemos darnos por contentos y en todo caso buscar una posible alternativa mejor.

Yo estoy seguro de que para este tipo de búsqueda de caminos habrá alguna web por ahí donde poder comparar la eficiencia de todos los algoritmos que haya, en su día usé escalada, A+, A*, búsqueda en profundidad y búsqueda en anchura.

También está la posibilidad de tener alguna mod_path no oficial que implemente los distintos algoritmos, a ver quién se atreve y tiene tiempo... :P