Búsqueda de rutas basada en costos de movimiento y cuadrícula hexagonal

Los artículos escritos en este blog fueron creados con el objetivo de enseñar. Además, la información del artículo puede ser incorrecta, así que tenga cuidado.

La cuadrícula hexagonal no puede marcar solo cuatro direcciones: arriba, abajo, izquierda y derecha, como un cuadrado. En ProyectoTBFTBHexCoordse utiliza como clave y GridManager calcula los vecinos y los costos de movimiento.

UPROPERTY(BlueprintReadOnly, Category = "Grid")
TMap<FTBHexCoord, TObjectPtr<ATBHexTile>> Tiles;

Coordenadas separadas y ubicación mundial.

Las reglas del juego se calculan utilizando coordenadas hexadecimales y el diseño de la pantalla esHexToWorld()Convertir de

FTBHexCoord
Búsqueda de vecinos/alcance/navegación de ruta
        ↓ HexToWorld
FVector
Ubicación real del actor.

De esta manera, no es necesario volver a crear las reglas de búsqueda de ruta incluso si cambia el espaciado de los mosaicos o el tamaño de la malla.

El rango de movimiento no se limita únicamente a la distancia.

La tierra llana cuesta 1, el pantano cuesta 2 y puede haber casillas inaccesibles. Si simplemente muestra un radio de 3 espacios, será diferente del rango de movimiento real.

GridManager de ProjectTB calcula el costo de movimiento acumulado desde el punto de partida.

bool FindPath(
    ATBHexTile* StartTile,
    ATBHexTile* DestinationTile,
    TArray<ATBHexTile*>& OutPath,
    int32& OutCost
) const;

TArray<ATBHexTile*> GetReachableTiles(
    ATBHexTile* StartTile,
    int32 MovementBudget
) const;

Esta estructura es similar a la búsqueda de Dijkstra. Se expande empezando por el mosaico con menor coste hasta el momento, y si se encuentra una ruta más económica, se actualiza el coste y las coordenadas anteriores.

Lo importante al implementar una cuadrícula hexagonal no es dibujar una malla hexagonal. Separar las coordenadas lógicas, la ubicación mundial, el costo del terreno y el estado de ocupación en diferentes responsabilidades hace que sea más fácil sobrevivir a medida que crecen las reglas de movimiento.