六角グリッドと移動コストベースのルートナビゲーション

本ブログ作成文は、講義を目指して製作されました。 また、作成された文章の情報も間違っている可能性がありますので、ご注意ください。

六角グリッドは正方形のように上下左右4方向だけ確認できない。 ProjectTBではFTBHexCoordをKeyとして使用し、GridManagerはネイバーと移動コストを計算します。

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

座標とワールド位置を分離する

ゲームルールはHex座標で計算し、画面配置はHexToWorld()から変換する。

FTBHexCoord
ネイバー検索/範囲/ルートナビゲーション
        ↓ HexToWorld
FVector
Actorの実際の位置

これにより、タイル間隔やメッシュサイズを変更してもパスナビゲーションルールまで再作成する必要がなくなります。

可動範囲は距離だけ見るべきではない

平地はコスト1、沼はコスト2で、入場不可タイルもあり得る。 単に半径3マスを表示すると、実際の移動可能範囲と異なる。

ProjectTBのGridManagerは開始点から累積移動コストを計算します。

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

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

この構造はDijkstraの探索に似ています。 現在までにコストが最も小さいタイルから拡張し、より安いパスを見つけたらコストと前の座標を更新します。

六角グリッドの実装で重要なのは、六角形メッシュを描くことではありません。 論理座標、ワールド位置、地形コスト、占有状態を異なる責任で分離しなければ移動規則が大きくなっても持ち運びが容易である。