pathfinding y risk

[RobiHm]

bueno ando intentando aplicar el "páfindi" a un jueguecillo tipo risk y me he quedado atrapado en el cálculo de h ...

yo aplico un coste de movimiento de una zona a una adyacente de 1, pero no tengo ni pajolera idea de como calcular h ya que las zonas son de forma diferente y la distancia no ejerce ningúna variación


¿alguien me puede orientar? xD

[Warchief]

No entiendo lo de que la distancia no ejerce variación.

[RobiHm]

tienes un mapa con regiones que no guardan ninguna proporcion ni escala con respecto al resto, usase tienes regiones que pueden acceder a otras regiones, en la fórmula de A*  para calcular la F que es el criterio que rige el camino a buscar, necesito de G y de H
siendo G el coste de la rejilla principal a la actual y H un cálculo aproximado de la rejilla actual hasta el final ...

en mi caso G vale siempre 1 porque cuesta lo mismo moverse de una zona a otra... lo que no logro es calcular H ya que no se cómo llegar hasta el destino


de ahí mi pregunta xD

[Warchief]

El número de países es pequeño, así que no creo que la heurística sea determinante en este caso. Puesto que es irregular supongo que distancia 2D funcionará mejor que manhattan (lo mismo si es 3D con latitud/longitud). Has probado a usar distancia (optimizado con distancia al cuadrado para evitar las raízes).

[RobiHm]

El número de países es pequeño, así que no creo que la heurística sea determinante en este caso. Puesto que es irregular supongo que distancia 2D funcionará mejor que manhattan (lo mismo si es 3D con latitud/longitud). Has probado a usar distancia (optimizado con distancia al cuadrado para evitar las raízes).

son unas 50 zonas (mapa ibérico), te mueves de provincia en provincia y cada coste te cuesta 1 sin tener importancia la longitud de la provincia, usease que no puedo trazar h como la distancia 2D entre provincias porque no es un dato que tenga relevancia

solo puedes moverte de una provincia a una provincia que se encuentra adyacente y no tengo ni idea de como calcular H xD

ya no se si es que no entiendo el procedimiento del pathfinding o es que me liado con algo

[Warchief]

La distancia desde el centro de cada provincia al destino parece adecuado. Problemas (y soluciones):

• h(i) no debe sobrevalorar el coste. Sol: Divide la distancia por el diámetro máximo (diámetro de la menor circunferencia que engloba a la provincia más grande). Lo he pensado en 5 minutos, así que puede que esté mal, pero así de pronto me parece que es válido. (El diámetro porque cada centro puede distar de su perímetro una distancia igual o menor al radio máximo, por lo que la distancia mayor sería de 2*r como mucho, dando x/2r < 1 (coste de 1 paso).
  
• Hallar la provincia más grande: Sol1 Coger muestras en los perímetros y calcular las distancias entre los puntos muestreados. Es cálculo offline (no durante el juego), por lo que no importa si no es ultrarápido. Sol2 Buscar en internet un algoritmo para inscribir polígonos en circunferencias :)
  
• Hallar el centro de cada provincia. Sol1 Centro geométrico de un polígono irregular (en internet seguro que está) :)
  

[RobiHm]

La distancia desde el centro de cada provincia al destino parece adecuado. Problemas (y soluciones):

me da que entonces evitaria siempre pasar por provincias grandes aunque en realidad le costase menos movimientos
de todos modos me quedo con la siguiente que era la que tenía, voy a trazar h según el eje x e y ,  y fuera y si veo k la ia es tontita pruebo otras cosillas xD

• Hallar el centro de cada provincia. Sol1 Centro geométrico de un polígono irregular (en internet seguro que está) :)
  

gracias por la ayuda

[Warchief]

La distancia desde el centro de cada provincia al destino parece adecuado. Problemas (y soluciones):

me da que entonces evitaria siempre pasar por provincias grandes aunque en realidad le costase menos movimientos
de todos modos me quedo con la siguiente que era la que tenía, voy a trazar h según el eje x e y ,  y fuera y si veo k la ia es tontita pruebo otras cosillas xD

Al contrario, en general irá por provincias grandes antes que las pequeñas, puesto que el centro geométrico está más cercano que en la pequeña.

Pillando una imagen de ejemplo...
<Update>
En el ejemplo, para ir del punto rojo al azul, de los hijos de la provincia con punto rojo, el 20 tiene menor distancia que el 7 (olvidemos los demás), por lo que prefiere ir por el 20 (a simple vista no veo cuál es más grande, pero está claro que el tamaño no influye directamente, sino en la situación del centro geométrico). Tras ir a 20, por heurística y coste debería seguir a 8 (habría que ver bien el efecto de asignar a H la distancia entre el diámetro máximo, porque tal vez explorase otros nodos antes que el 8).

Según X e Y es manhattan, tendrás que hacer una conversión similar (de radio) si quieres que la heurística sea admisible con respecto al coste, ya que X e Y pueden estar en píxeles, y el coste en provincias.



Uhm, cogí el peor ejemplo para mostrar lo del tamaño, pero espero que se entienda lo que quería reflejar.

[jelorol]

A ver si esto tiene sentido:

Si la geometría de las provincias no es relevante, yo separaría el cálculo del camino de su representación gráfica. Para calcular las provincias por las que debes pasar, modela las provincias como nodos con n conexiones. Con el A* determinas porqué nodos(provincias) debes pasar, asignando coste 1 a cada provincia.

Luego, gráficamente, mueves las unidades por las provincias que ha determinado el pathfinding, por ejemplo desplazándolas desde el centro de la provincia a un punto intermedio de la frontera con la provincia siguiente, y de ahí al centro de la otra provincia, etc. pero en definitiva de forma independiente a como has calculado el path.

[Warchief]

A ver si esto tiene sentido:

Si la geometría de las provincias no es relevante, yo separaría el cálculo del camino de su representación gráfica. Para calcular las provincias por las que debes pasar, modela las provincias como nodos con n conexiones. Con el A* determinas porqué nodos(provincias) debes pasar, asignando coste 1 a cada provincia.

Luego, gráficamente, mueves las unidades por las provincias que ha determinado el pathfinding, por ejemplo desplazándolas desde el centro de la provincia a un punto intermedio de la frontera con la provincia siguiente, y de ahí al centro de la otra provincia, etc. pero en definitiva de forma independiente a como has calculado el path.

La geometría en sí no es relevante, pero sí su situación. Si tu destino está a la izquierda, es más probable que llegues antes si pasas a tu provincia vecina a la izquierda, en vez de a la derecha. Eso es la heurística que usa A* para buscar el camino.

Lo que dices del movimiento del unidades es correcto, no tiene por qué ser igual que el grafo de pathfinding.

Con el A* determinas por qué nodos(provincias) debes pasar, asignando coste 1 a cada provincia.

Eso es lo que está haciendo, pero para ello necesita la heurística que indique qué nodos explorar primero, y ahí es necesaria la localización de las provincias.

[jelorol]

Por supuesto, warchief, si leyera los post con atención antes de contestar...  :roll:

Volviendo al problema:

¿se podría hacer lo siguiente para dar un valor razonable a h?

1) Desde la provincia actual, ir al mapa geográfico* y trazar una línea recta desde el centro de la misma al destino.
2) h = número de provincias distintas que atraviesa la línea hasta el destino

*PROBLEMA: Tendrías que crear una versión convexa del mapa deformando/simplificando las provincias para que se pudieran unir con una línea recta sin atravesar el mar o Portugal. Esta versión sólo la usarias para el pathfinding, claro.

[RobiHm]

el problema que tiene el hacer lo que menciones jelorol es que h sería la solución que buscas xD

se supone que hago el A* para calcular cuantos movimientos necesito xD
si una incognita es el valor que busco es imposible resolver la ecacuación porque es lo que quiero hallar... ainss que lio xD

como dice war el tema esta en saber en que dirección y creo que con el tema de las coordenadas (cosa que tengo de antemano calculada para poder  representar edificios y tropas)

lo otro que hablas es calcular el trayecto, eso no es preocupante xk ir uniendo lineas de una provincia a otra y recorriendola sobra

ten en cuenta que las tropas solo pueden moverse un movimiento asi que cada "turno" recalculo el pathfinding

un saludo y gracias por la ayuda

[bnl]

RobiHm, el enlace que tienes en tu firma a Twip Estrategic 1.0.1.3 dice que ha expirado, me he quedado con las ganas de echarle un vistazo.
Parece q a los 25 se cargan el fichero.

Saludos

[RobiHm]

RobiHm, el enlace que tienes en tu firma a Twip Estrategic 1.0.1.3 dice que ha expirado, me he quedado con las ganas de echarle un vistazo.
Parece q a los 25 se cargan el fichero.

Saludos

pos a mi me funciona xD

Filename:      InstaladorEstrategic.exe
Filesize:     12MB
Downloads:     117
Description:     Twip Estrategic 1.0.1.3 by Roberto Herrero
Direct Link:     http://www.badongo.com/file/2989884

Es el primer jueguecillo que hice

un saludo

[bnl]

Lo he vuelto a intentar y lo mismo.
Primero me pide que meta un código (las tipicas letras antirobots) y luego en otra pantalla al pulsar en descargar me dice q ha expirado.