Hexagonal grid and movement cost based route finding

The articles written on this blog were created with the goal of teaching. Also, the information in the article may be incorrect, so please be careful.

The hexagonal grid cannot check only four directions, up, down, left, and right, like a square. In ProjectTBFTBHexCoordis used as the key, and GridManager calculates the neighbors and movement costs.

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

Separate coordinates and world location

Game rules are calculated using Hex coordinates, and screen layout isHexToWorld()Convert from

FTBHexCoord
Neighbor Search/Range/Route Navigation
        ↓ HexToWorld
FVector
Actor's actual location

This way, there is no need to recreate the path search rules even if the tile spacing or mesh size changes.

The range of movement is not limited to distance alone.

Plain land costs 1, swamp costs 2, and there may be inaccessible tiles. If you simply display a radius of 3 spaces, it will differ from the actual movement range.

ProjectTB's GridManager calculates the cumulative movement cost from the starting point.

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

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

This structure is similar to Dijkstra search. It expands starting from the tile with the lowest cost so far, and if a cheaper route is found, the cost and previous coordinates are updated.

The important thing in implementing a hexagonal grid is not drawing a hexagonal mesh. Separating logical coordinates, world location, terrain cost, and occupancy status into different responsibilities makes it easier to survive as movement rules grow.