Menú

Mostrar Mensajes

Esta sección te permite ver todos los mensajes escritos por este usuario. Ten en cuenta que sólo puedes ver los mensajes escritos en zonas a las que tienes acceso en este momento.

Mostrar Mensajes Menú

Mensajes - Mantis

#406
Lo más difícil ya estaba hecho. Gracias a ti por el inicio de este hilo, que fue lo que me motivó a la hora de ponerme a estudiar a fondo estos algoritmos.

Ahora estoy pensando algún sistema para contemplar cambios de altura de las casillas, y rampas, etc.

Había pensado definir una matriz de estructuras o clases que además de tener un "valor de coste", tuvieran un valor de altura.
Y así a la hora de mirar las casillas adyacentes, se tuviera en cuenta la altura y se otorgase un valor u otro dependiendo de si es una rampa, o bien se le asignase un valor muy elevado de forma que esa casilla obtuviera un nuevo valor desde otro camino (no parace fácil), en caso de tratarse de otra altura inalcanzable desde donde se está comprobando.

De momento he cambiado que a las adyacentes en diagonal, se les asigne un valor de raiz de 2. Para eso he redefinido el valor de las matrices como float en vez de int.

Un saludo[/quote]

Que tal.

Animo en tu proyecto, veo que quieres adaptar el pathfinder para el juego de estrategia que estas haciendo.

Yo estoy puliendo un jueguecito que he hecho estilo Pac Man para Android pero con diferencias sustanciales. En la IA de algunos  enemigos estoy usando la primera version de pathfinder que posteé y el brushifire para otros. Tengo muchos proyectos iniciados pero este es el primero que he terminado.
#407
¿Raiz de 2?, pero por dios ¿porqué os complicais tanto la vida?

Leeros el post que puse sobre el pathfinder donde se explica paso a paso como es el brushfire, es mucho más simple de lo que lo estais haciendo vosotros[/quote]

Que tal Hosuko.

El Brushfire lo tenemos ya  dominado jeje :cheer: . Y funciona perfectamente.

Lo que esta haciendo aFisicos es perfeccionar su pathfinder para orientarlo a un juego determinado.Para tener en cuenta el relieve del terreno y demás.


Saludos
#408
Enhorabuena..por hacerlo funcionar. La verdad es que no es fácil.  A mi también me costó

Mi problema era que la funcion Flood() se quedaba ejecutandose un millon de veces pisando unos valores con otros. pero ya lo arreglé.

En cuanto pueda lo pruebo
#409
He estado haciendo cambios en Funcion Flood. La primera version era una locura, pisaba los valores de la matriz y se ejecutaba demasiadas veces.  Ahora compruebo que el valor de la casilla no ha sido asignado antes deañadir uno nuevo
#410
He estado probando la función y Siempre encuentra el camino :silly: .

Te pongo una imagen de uno de los caminos que le he puesto: ( Lo encontró perfectamente sin desviarse ni hacer cosas raras

Le he puesto una matriz de 40 x 40 . Aún no he encontrado la manera de  que pare y no siga rellenando la matriz cuando encuentre al Player.
#411
Creo que lo he conseguido con el método de colorear poligonos. :cheer:

He creado una función llamada Flood() que es la que "inunda" la matriz. y he dejado ActualizarMatriz para que la inicialice a 99 o como tu dices a 9999 para no tener problemas con una Matriz mayor. Esta es la muy buscada y trabajosa  función Flood() jeje: :silly:


function Flood(x : int, y : int, flood_val: int){
    if (Matriz
  • [y] > flood_val && x = 0 && y >= 0){
       //Debug.Log("pos "+x+","+y+":"+Matriz
  • [y]);        
       Matriz
  • [y] = flood_val;
       if (Matriz
  • [y]!=-1 && x+1 = 0)
          Flood(x-1,y,flood_val+1);
        if (Matriz
  • [y]!=-1 && y+1 = 0)
           Flood(x,y-1,flood_val+1);
   }
}



En el bloque :


if(Input.GetKeyDown(KeyCode.Mouse0)){

}



He añadido :


 ActualizarMatriz(); //inicializa los valores de la matriz a 99
Flood(Target.x,Target.y,0); //inunda Matriz para meodo Brushfire o Wavefront


Ahora mismo me rellena toda la matriz pero con una leve modificación haré que se pare al dar con el Player

Pruebala   a ver que tal
#412
He estado mirando lo de colorear poligonos y he encontrado algo parecido.

Ve a la pagina 13.

EDITADO: Tengo problemas para subir el archivo te lo pongo aquí directamente:



5.3 Naive shortest paths through
ooding
Our rst attempt was to use a slight modication of a shortest paths algorithm.
We call this a \
ooding" algorithm. This is a simple implementation of Kruskal's
shortest path algorithm made specic to mazes. Imagine a hose being placed
in a cell in the maze, and water being allowed to
ow from a cell to a neighbor
in one unit time. A simple recursive algorithm will yield the amount of time
12
it takes for water to reach any point in the maze from any other point in the
maze, and an appropriate traversal of the matrix of
ood values will yield the
shortest path.
Code for this algorithm is shown below. The
ood values are represented
as a 16x16 array of integers (maze), and the wall congurations are represented
with four 16x16 boolean arrays called north, south, east, and west.

void Flood(int x, int y, int flood_val)
{
if (maze[y]
  • > flood_val)
{
maze[y]
  • = flood_val;
if (!east[y]
  • )
Flood(x+1,y,flood_val+1);
if (!west[y]
  • )
Flood(x-1,y,flood_val+1);
if (!north[y]
  • )
Flood(x,y+1,flood_val+1);
if (!south[y]
  • )
Flood(x,y-1,flood_val+1);
}
}

Once we have a
ooding routine, it is easy to answer the question \what
is the best path from point a to point b". We simply
ood the maze starting
at b with a
ood value of zero, and then traverse the maze starting at a and
following decreasing
ood values until we reach b. This works because once

ooding is done, the
ood value at a is exactly the length of the path from a
to b. Therefore, if we follow the
ood values in a monotonic decreasing order,
we are guaranteed to reach b in exactly the minimum amount of steps. Note
that the path generated by this algorithm is not unique, as there may be several
paths from a to b with identical lengths.
Also, because we know that the center of the maze is open, the maximum

ood value for any
ood in any square is 254, so we can use 255 to initialize the

ood array, and can therefore represent the entire array of
ood values in 256
bytes of memory. This is because the worst case for
ooding is a spiral in which
the
ow has to touch every square. If our
ood starts at one corner of the maze,
and spirals towards the center, it will have length 252 when it enters the center
13
of the maze. Because we know that the center is an open 2x2 square, it will take
254 steps to get to the corner of the center, not 255 in the closed-center worst
case. Therefore, if all
ood values are initialized to 255, a
ood value of 255
represents an unreachable portion of the maze. MicroMouse maze designers will
often put these in the maze (i.e., a fully walled o square) to test the robustness
of the MicroMouse algorithms.
Although the straightforward
ooding algorithm works well for a shortest
path com***tion, it does not allow our mouse to take full advantage of its acceleration
capabilities, and its ability to traverse diagonal paths without turning.
That is, because of how thin our mouse is, and the precise spacing of the sensors,
if we intend to traverse a \stairstep" pattern in the maze, we can simply turn 45
degrees and go straight without turning at all. This is a huge advantage, and is
yet another thing that MicroMouse maze designers will intentionally put in the
maze. The maze
ooding algorithm is the one typically used by student mouse
projects when they are simply interested in getting something that works. It is
not a world class implementation of a physical maze solving algorithm, and we
clearly needed something better.


#413
Parece sencillo, si. Pero no entiendo el valor inicial que cogen las celdas adyacentes al target.
De donde sacan ese valor?

Por lo demás, parece que hay que usar recursividad para rellenar el tablero.

Cuanto más investigo lo del brushfire, más se me parece al A*... que lío.[/quote]

La diferencia parece estar en que el A* usa Heurística para encontrar el camino más cercano mientras que el brushFire No.

Estoy trabajando en como crear la matriz para el método BrushFire, por ahora no lo he conseguido.  Una vez consiga crear la matriz la sustituire por ActualizarMatriz() y deberia funcionar.  Pero no es tan sencillo crear la matriz

He encontrado este programita por si te interesa, donde se ejecuta el método Brushfire o WaveFront:

A mi me ha servido para ver como va contruyendo la matriz.
#414
Por lo que he visto con tan solo modificar la funcion ActualizarMatriz()  podemos tener el pathfinder.js por el método brushfire.

Estoy en ello.
#415
He encontado esto sobre el algoritmo Brushfire o Wavefont:

Algoritmo brushfire en c++

web original:http://www.societyofrobots.com/programming_wavefront.shtml
#416
Que tal

He estado probando el proyecto. Ahora ya no va a (0,0) cuando no encuentra el camino y sigue buscando. En uno de los intentos ha estado buscando un buen rato pero al final lo ha encontrado jeje.

El algoritmo está bien y es rápido lo que pasa es que siempre estará en desventaja frente a el A* o el Brushfire ya que estos van almacenando el camino en un ArrayList y una vez encontrado es cuando empieza a moverse el personaje.

Habría que modificar el script pathfinder.js para que busque el camino y si existe lo almacene en un ArrayList, y una vez que tenemos todos los puntos del camino se dirija hacia el target. Y en el caso de que no lo encuentre no se mueva del sitio. Creo que es por ahí por donde se podría mejorar.

De todas formas sigo pensando que para un escenario simple funciona muy bien.  Yo voy a estudiar (cuando tenga tiempo) el Brushfire, que es muy parecido a este, pero te garantiza que va a encontrar el camino. Primero almacena los puntos y una vez tiene el camino es cuando el player se dirige hacia él.

Si lo implemento en unity lo colgaré en el foro.

Usaré tus scripts para la creación de la matriz.
#417

Por otro lado, sigo atascado con mi player, no se que pasa que desde que me creé la matriz con este método, con el que al final conseguí tenerla bien ordenada con el 0000 arriba a la izquierda, no he conseguido que trace bien los caminos. Todo el rato se me va al 0000, o incluso se pasa y se va fuera de la matriz y  se queda allí xD.
[/quote]

Puede que por algún motivo las cuadrículas no esten ordenadas. Revisa  el nombre de las cuadrículas a ver si tienes alguna cambiada. (Es algo que me ocurrió a mi.)  y no me funcionaba.

Si quieres puedes colgar el proyecto para poder ayudarte mejor.
#418


1.- Desconocia las instrucciónes: String.Substring y parseInt, gracias a tí ya las conozco   .

[/quote]

Las solia usar cuando programaba en Java. Supuse que también estarian en unityscript.




4.- Bloque 1 y Bloque 2. He entendido que ese código mira si se está o no en movimiento, de no estarlo llama a la función de movimiento teniendo en Cuadricula la posición donde ha de ir. La función Moverse(Cuadrícula) -llamada desde el Bloque 2- se encarga de ver si ha llegado al siguiente nodo. La verdad esta parte, junto con la función  Moverse(Cuadrícula) la he encontrado algo liosa.
[/quote]

Si es liosa esta parte. Lo que pasa es que la función te devuelve el siguiente punto, y en cuanto lo ha calculado, el player se dirige hacia él. Quiero decir que no se almacenan los puntos en un Array para después recorrerlo, que creo es lo que hacen los demás pathfinders. Va de punto en punto, calculando y moviéndose, caculando y moviéndose.

Está claro que es un pathfinder muy limitado.  Pero para el escenario donde iba a funcionar era suficiente.

Claro una cosa es escribir el código del algoritmo y otra es llevarlo a cabo en un escenario en Unity. Lo digo por el tema de la división del terreno. A mi se me ocurrió el tema de las cuadrículas pero he estado viendo otras formas en un post de foro de como escanear el terreno y dividirlo en cuadros. Seguro que lo conoceis. Es de un usuario que estaba trabajando en el A * Pathfinder.

Alñgoritmo A* para compartir

En cuanto tenga tiempo voy estudiar el algoritmo de Brushfire, y si consigo hacerlo funcionar lo subiré.

Es un tema apasionante esto de los pathfinders.
#419

El problema es que me lo crea de abajo a arriba y de izquierda a derecha... y luego el pathfinding no funciona, creo que debido a eso.
[/quote]

Recuerda poner el Tag "PuntoMatriz" y "Obstaculo" a las cuadriculas. Puede que sea eso
#420
El algoritmo , como ya dije en el primer post, es una traducción de uno escrito en C++. Lo posteó Hasho. Este es el enlace:

http://www.catsoft-studios.com/article/index.php?artid=74

Muy bueno el enlace que has puesto.