PathFinder (A*) ¿Algun matematico en la sala? :cry:

holaa realmente este es un caso de estudio jaja ya que hace mas de 5 horas estoy tratando de entender una parte del algoritmo A* para buscar rutas mas cortas.
si bien entiendo como es que funciona no logro entender como es que recorre los puntos y selecciona cuales van y cuales no..

lo que quiero hacer es el ejemplo de la figura 3:
http://lab.polygonal.de/2007/06/13/data-structures-example-the-graph-class/
el problema que tengo es que al recorrer los puntos no se con cuales se queda y con cuales no.
es difícil de explicar cual es el problema a ver..

si entiendo como es que funciona el algoritmo a* pero no se a la hora de seleccionar para que lado ir se queda con los puntos intermedios.
si se que selecciona el que tiene el valor h menor. pero siempre va a ser el ultimo punto si me explico..

alguno trabajo ya con esto?.. saludos.

He mirado el ejemplo que quieres hacer y no es igual al clásico ejemplo de una cuadrícula con obstáculos y elegir el cuadro que menor F tenga, me parece que este ejemplo el cual es más complejo, debe guardar un arreglo multidimensional donde cada punto guarda un arreglo de los puntos al que el puede acceder o desde los cuales el puede ser accedido (porque por ejemplo del punto 1 no se puede ir al 3), después que esté hecho esto ya lo demás me parace que funcionaría igual:

por ejemplo el principio del arreglo sería:

Código :

([1, 4, 22], [0, 2, 20], [1, 3, 18], [2, 4, 11]...

La recursividad no debe ser con un for, si no con un while que compruebe cuando se ha llegado al final, se empieza con el primer punto, se calcula de entre todos los puntos accesibles a él cual tiene menor F, recuerda que F = G + H (G = costo del movimiento y H = costo del movimiento con respecto al punto final), cuando encuentres el punto con menor F vuelves a comprobar de los puntos accesibles a él cual tiene menor F y así consecutivamente hasta que llegues al final.

Es lo que se me ocurre para resolver el problema, lo que llevaría más trabajo es construir el arreglo inicial.

Saludos

si tenes razon el problema que tengo es que dinamicamente los puntos los tengo en un array como cordenadas.. (puntos para el path sobre el mapa) los cuales ninguno son el punto inicial y final. (ese es otro problema jaja)

Código :

var puntos:Array= new Array();
puntos.push({x:87,y:226.6});
puntos.push({x:127.8,y:224.6});
puntos.push({x:232.5,y:290});
puntos.push({x:177.3,y:265.2});
puntos.push({x:166.6,y:184.7});
puntos.push({x:333.5,y:244});
puntos.push({x:287.5,y:315});

el problema es que esto mas a delante el cliente los va a colocar mediante un cms seleccionando los puntos sobre el mapa.. por lo cual no puedo saber cuales (al menos que le ponga esa opcion) de que elija cuales de los puntos tienen acceso entre si... (complejo para un usuario comun).

por eso , el calculo para saber que clip tiene un F mas bajo ya lo tengo pero el problema esta en que no puedo saber cuando los puntos son dinamicos como calcular cuales tienen acceso entre si. o un patro de orden.. seguire quemando neuronas jaja
muchas gracias por la respuesta.

Se me ocurre entonces otra cosa lo que creo que la recursividad iría un poco más lenta:
Vamos a llamarle a los puntos creados por el usuario "P" y a los puntos de las líneas a generar entre ellos "d":

La línea que une cada uno de los "P" está conformada por una función f(x) = m*x + n (creo que el valor de n aquí se puede obviar), bueno lo que te propongo es que desde el "P" de inicio pruebes hacer una serie de líneas hasta los demás "P" conformadas cada una por una serie de "d" bastante unidos eliminando aquellas líneas donde uno de estos "d" haga colisión con los obstáculos (que debe ser un solo objeto), por ejemplo:

Código :

//dentro del ciclo que crea la linea conformada por "d" compruebas
if(obstaculo.hitTestPoint(dX, dY, true)){

//eliminar este camino y terminar el ciclo que construye la línea y pasar a la siguiente línea posible

}

De esta manera vas guardando los "P" en los cuales las líneas a ellos ninguno de los "d" que la conforman hizo colisión con el objeto obstáculo en un arreglo temporal, y después a cada uno de los "P" de este arreglo los filtras sacando el que menor F tenga, y desde este vuelves a trazar lineas de "d" a los demás sacando el que menor F tenga y así sucesivamente, quizás sea una solución bastante recursiva pero es lo que se me ocurre.

Saludos

esta bueno lo que desis ahunque creo que si va hacerce lento y no dispongo demucho tiempo. pero lo tendre como plan b ..
voy a ver si puedo resolverlo ahunque sea dandole al cliente la posibilidad de que marque pasillos entre los puntos.
gracias