Mostrando rango en cuadrícula hexagonal

Aquí está la situación.

Tengo un tablero hexagonal y una unidad en él, con velocidad o valor de movimiento 4. El terreno diferente tiene un costo diferente. Cuando hago clic en la unidad, el juego debería mostrarme un rango de movimiento.

Mi solución fue verificar cada hex en el rango de 4, con A * pathfinding, y si el costo de la ruta era inferior a 4, entonces este hex estaba en el rango. Finalmente, el juego me muestra muy bien el rango de esa unidad.

Mi pregunta es: ¿hay otra solución para buscar el rango en cuadrículas hexagonales o cuadrícula cuadrada, porque incluso si estoy realmente orgulloso de lo que hice en mi solución, creo que es un poco exagerado? :))

¿Qué me hizo hacer esta pregunta? Noté que cuando la velocidad de la unidad es 4 o 6 o incluso 8, el tiempo para calcular el rango de mi computadora era realmente bueno, pero cuando la velocidad era 10 y más, noté que necesitaba esperar unos segundos para calcular Bueno, en los juegos reales prefiero no ver algo como esto y mi pathfinding A * está bastante bien optimizado, así que estoy pensando que mi solución está mal.

Gracias por cualquier respuesta

Tienes razón en que A * es un poco exagerado, pero no mucho. No deberías ver retrasos como tú. A * es realmente solo un algoritmo modificado de Dijikstra . Como no está utilizando una posición final (ya que su posición final es "lo más lejos que puede llegar"), no es necesario usar A * con su heurística adicional. Simplemente usando Dijikstra o una simple búsqueda de amplitud será suficiente.

Por ejemplo, Dikikstra se extenderá de manera uniforme en todas las direcciones:

(Una primera búsqueda de amplitud simple será similar a esta)

Mantenga un registro del costo de viajar a cada nodo. Una vez que un nodo está al costo de viaje máximo, no procese más sus nodos conectados. (Similar a donde los nodos se topan con la pared de abajo).

Si tiene problemas de rendimiento con solo 10 nodos, querrá ver cómo accede a los nodos. Una primera búsqueda amplia debería ser capaz de navegar cientos de nodos sin un retraso notable (ciertamente no unos segundos). Considere almacenar una versión simple de su mundo en un formato gráfico, para un recorrido rápido.

Amit Patel ha proporcionado un excelente recurso para obtener rangos en su sitio . En el artículo, usa el siguiente algoritmo para recolectar fichas hexagonales dentro de un rango:

for each -N ≤ Δx ≤ N:
    for each max(-N, -Δx-N) ≤ Δy ≤ min(N, -Δx+N):
        Δz = -Δx-Δy
        results.append(H.add(Cube(Δx, Δy, Δz)))

Esto crea límites alineados con la cuadrícula hexadecimal:

Esto encontrará todos los hexágonos dentro de una cierta distancia del hexágono central, si desea considerar los obstáculos, use la búsqueda de amplitud primero de mi otra respuesta.

En caso de que alguien lo necesite, aquí está la implementación de C # del algoritmo de Patel:

IEnumerable<Hex> GetRange(Hex center, int range)
    {
        var inRange = new List<Hex>();
        for (int q = -range; q <= range; q++)
        {
            int r1 = Math.Max(-range, -q - range);
            int r2 = Math.Min(range, -q + range);
            for (int r = r1; r <= r2; r++)
            {
                inRange.Add(center.Add(new Hex(q, r, -q - r)));
            }
        }

        return inRange;
    }