A* Pathfinding, parte 1 (pruebas)

[Prompt]

Muy buenos días a todos.

Acabé recientemente con mi altgoritmo A* y el como haré el movimiento de los NPCs y jugadores. Este A* está preparado para un juego por turnos  solamente, como los juegos de tablero para un juego tipo RTS habría que modificarlo un poquitin para tener en cuenta ciertas cosas en la lógica de juego.

Notas adicionales:
- El tablero puede ser irregular y se contempla para la heuristica.
- La heuristica es de diagonales. Aunque me estoy pensando que no lo sea y escoger manhattan para hacer movimientos tipo "caballo de ajedrez"
- Los colores de DEBUG son muy feos, si xD pero cumplen con su cometido.
Color Gris, area de movimiento del jugador
Color Verde, cuadros en los que se ha buscado
COlor Azul, path que seguirá la instancia finalmente

Camino facil de resolver para la IA:


Camino medio de resolver para la IA:


Camino costoso de resolver para la IA:


Por qué ha costado de resolver la IA, pues porque miro los cuadros adyacentes en orden de las agujas del reloj empezando por la izquierda y terminando por la celda abajo-izquierda. Con lo cual el 1er cuadro más optimo fue el derecho y ahí se comenzó a buscar sin mucho exito hasta encontrar el cuadro que le convenia.

Esto quizás se podría paliar un poco modificando la lógica de busqueda o analizando si hay futuros cuadros a los adyacentes que no son posibles de cruzar. Como si fueramos un ciego pero en vez un palo para distancias cercanas tuvieramos uno más grande.

El tipo de movimiento está inspirado en Shining Force ( no he jugado a otro con ese tipo de movimiento ). Me encantaron el 1 y el 2. Al 3 no jugué. De hecho jugué 1º al 2 y me gustó tanto que jugué luego el 1 xD

Shining Force 1: http://www.youtube.com/watch?v=zXxCzq6GF7w
Shining Force 1 Final Battle: http://www.youtube.com/watch?v=K1L0VcV4T7I

Shining Force 2: http://www.youtube.com/watch?v=1qt-C0U6Zg0
Shining Force 2 Final Battle: http://www.youtube.com/watch?v=3jHQZe9cRLo

Para un futuro paso, muy futuro para probar la IA y varios elementos más como stats de personajes, items, tiendas, compras etc... se podria hacer un RPG de cachondeo en el que el principal personaje seria sin duda Jove en busca de su amada :)

Pero antes, haré una demo más sencilla para probar IA y eventos.

Un saludo! :P

[AK47]

Lo de Jove mola, como se llamara el juego? Jove and the revenge of the pinguin troupe?   :lol:

[Prompt]

A Jove una panda de pinguinos rabiosos le roban la novia en torremolinos y luego el, y su mafia GrafosYakuza tendrán que rescatarla xD

[Vicente]

Mola mucho tio, aunque no me queda claro porque tienes tanto cuadro verde el último ejemplo, incluso tienes cuadros verdes fuera del área de movimiento del bicho! :S

Un saludo!

Vicente

[Prompt]

incluso tienes cuadros verdes fuera del área de movimiento del bicho

Si porque al pintar, recalcula según la posición actual del "Pato" ( es que yo a los pinguinos por algo muy largo les llamo patos ) y pinta el nuevo area de movimiento. Pero en verda deja por donde pasó.

He mirado otras demos y tal:

1ª demo


2ª demo


En la 1ª demo se ve que es mucho peor, o puede que marque en verde la lista abierta y la compruebe enterita y no filtrando 1º por celdas adyacentes.

En la 2ª demo podemos ver como prueba unos pocos de cuadros alrededor (azul) ya que su orden es empezar por la derecha y al contrario de las agujas del reloj.

[Prompt]

Puede ser por la heuristica, o que en esas ocasiones sea normal, he llegado a probar cosas en la demo y hace cosas super chungas. Aunque bueno, es posible que en algun calculo esté haciendo algo indebido, es cuestion de ir viendolo.

La 2ª demo una en teoria Manhattan y se ve que al evitar las diagonales le ha salido a cuenta.

Aun tengo que testear cosillas, pero no me preocupa en exceso.

[Vicente]

No sé, por más que lo miro no me sale a cuenta que se expandan tantos nodos en el último ejemplo... A ver si luego hago una prueba casera en casa.

Un saludo!

Vicente

[Prompt]

La misma circunstancia gano:

Recordemos que en verde está la lista cerrada, que es == a los nodos por los que he pasado, en la demo 2 eso corresponde a los nodos azules.



El usa manhattan creo, aunque un manhattan raro, porque usa diagonales... pero bueno.

[Isilion]

El problema de Manhattan es el desequilibrio de movimiento que puede provocar: las unidades necesitan muchos más puntos de movimiento porque tienen que dar muchas vueltas para llegar a donde quieren.

Esto puede que sea requerido en el diseño. Si por ejemplo no queremos que una unidad puedra traspasar a 2 unidades juntas diagonalmente. No se si me explico, puedo hacer una screenshot luego si eso.

Otra cosa que podríamos hacer es simular Manhattan en cierto modo, pero utilizando diagonales. Esto lo podríamos conseguir haciendo que el coste del movimiento diagonal fuera superior (por ejemplo, un 50% más caro) que el del movmiento recto. De este modo compensaríamos la distancia ganada mediante el movimiento diagonal y se podría equilibrar el juego más fácilmente (lo digo porque imagino que luego seré yo quien se coma ese marrón :P).

Esto ya se hace, incluso en la heuristica Manhattan para la demo2 esa kk ( que ni es manhattan ni es náh! se ha inventado ahi lo que le ha dao la gana y no es optimo ni nomal y quereis lo explico )
El movimiento diagonal es 1.141 veces más caro de hacer que uno recto en celdas regulares. Por lo tanto se tiene en cuenta:

* sqrt(2)/2 * tamañoDeUnLado == 1.141 * tamañoDeUnLado ( creo que era algo así ) Vamos yo mido distancias, no puntuo, por lo tanto sale solo que es más costoso el movimiento diagonal pero menos costoso que 2 movimientos rectos hacia la misma dirección, aquí se ve claramente la elección:

¿Acaso queremos ser nosotros más listos que las abejas? :D

Al ser cuadrados y no hexganos se reduce las permutaciones del grid, es decir la combinatoria es menor y por lo tanto más facil. Tomemos como ejemplo un tablero de ajedrez, si ya es complejo ganarle al Casparof este... imaginate que lo hicieran de tipo hexagono, aumentaria las combinaciones y aquello duraria un mes una partida Casparof VS Maquina xD

Por lo tanto hacer un grid regular, rectangular para el jugador es más facil y menos costoso para la IA. Esto habría que tenerlo en cuenta.

[Prompt]

Post original. Acaba el foro de aplastar el mensaje de isilion y hacerlo mio con mi post, el foro se viene abajo!

El problema de Manhattan es el desequilibrio de movimiento que puede provocar: las unidades necesitan muchos más puntos de movimiento porque tienen que dar muchas vueltas para llegar a donde quieren.

Esto puede que sea requerido en el diseño. Si por ejemplo no queremos que una unidad puedra traspasar a 2 unidades juntas diagonalmente. No se si me explico, puedo hacer una screenshot luego si eso.

Otra cosa que podríamos hacer es simular Manhattan en cierto modo, pero utilizando diagonales. Esto lo podríamos conseguir haciendo que el coste del movimiento diagonal fuera superior (por ejemplo, un 50% más caro) que el del movmiento recto. De este modo compensaríamos la distancia ganada mediante el movimiento diagonal y se podría equilibrar el juego más fácilmente (lo digo porque imagino que luego seré yo quien se coma ese marrón :P).

Esto ya se hace, incluso en la heuristica Manhattan para la demo2 esa kk ( que ni es manhattan ni es náh! se ha inventado ahi lo que le ha dao la gana y no es optimo ni nomal y quereis lo explico )
El movimiento diagonal es 1.141 veces más caro de hacer que uno recto en celdas regulares. Por lo tanto se tiene en cuenta:

* sqrt(2)/2 * tamañoDeUnLado == 1.141 * tamañoDeUnLado ( creo que era algo así ) Vamos yo mido distancias, no puntuo, por lo tanto sale solo que es más costoso el movimiento diagonal pero menos costoso que 2 movimientos rectos hacia la misma dirección, aquí se ve claramente la elección:

¿Acaso queremos ser nosotros más listos que las abejas? :D

Al ser cuadrados y no hexganos se reduce las permutaciones del grid, es decir la combinatoria es menor y por lo tanto más facil. Tomemos como ejemplo un tablero de ajedrez, si ya es complejo ganarle al Casparof este... imaginate que lo hicieran de tipo hexagono, aumentaria las combinaciones y aquello duraria un mes una partida Casparof VS Maquina xD

Por lo tanto hacer un grid regular, rectangular para el jugador es más facil y menos costoso para la IA. Esto habría que tenerlo en cuenta.

[Prompt]

Ya he concluido sin optimizaciones mi A*, haré un nuevo hilo :)