This document is about: QUANTUM 2

SWITCH TO

QUANTUM 1 QUANTUM 2 QUANTUM 3

Tilemap Pathfinder

Available in the Gaming Circle and Industries Circle

概要

このサンプルは、タイルに基づく一般的な経路探索システムの実装を示しています。これは、ナビメッシュでナビゲートするよりもシンプルかつ安価で、タイル、グリッド、ヘックスグリッドをベースにした多くのゲームに適用できます。

このサンプルでは、トランスフォームを使ったステアリング、キネマティックキャラクターコントローラー、カスタムパッシングの可能性を示しています。このプロジェクトのシステムはカスタマイズ可能でさまざまなゲームプレイスタイルに対応できますが、X軸とZ軸を使用した平面(2D)レベルに限定されます。Y軸は無視されます。

注: このシステムは内部でTransform3Dの3D軸を使用しており、Transform2Dコンポーネントを持つエンティティを使用しては動作しません。

この経路探索システムは3つの部分から成ります:

Tile Map Data: タイルの数、規模、隣接するタイル。これらのデータはすべて、編集モード時にツールを使ってベイクされます。
Pathfinder Function: このサンプルでは、A*アルゴリズムを使ってタイルマップの点のリストを見つけます。点はインデックスに変換され配列に格納されます。
Agent: ゲームワールドでウェイポイントのリストを使ってマップ内を移動できるエンティティ。

注: これはゲームではありません。

技術情報

このプロジェクトは以下を使用して開発されました：

Unity 2021.3.11f1.32
Quantum 2.1.1 Stable 1123

ダウンロード

バージョン	リリース日	Download
	2.1.1	2022年11月10日	Tilemap Pathfinder 2.1.1 Build 29

サンプルシーン

このプロジェクトには4つのサンプルがあり、TilePathfinderコンポーネントの使用方法を示しています。機能はシステム間で共有されます。

1) Simple Click Movement

このシーンはTilePathfinderとPlayerLinkを持つ単純なエンティティを示しています。任意の場所をクリックして移動してください。ClickMoveSystemを参照するにはQuantum Codeプロジェクトを開きます。

alternative text — ギズモがウェイポイントとエージェントの動きを示します。

Unity Editorのシーンビューでは、ターゲットのギズモとパスが描画されます。

2) Move With Callback

ClickMoveSystemはプレイヤーの入力を読み込み、エンティティの対象を設定します。CUSTOMに設定された移動タイプがTileAgentConfigにある場合、エンティティは自動的には移動しません。代わりにOnTileMapMoveAgentコールバックをリッスンし、エンティティのトランスフォーム位置を移動するためにdesiredDirectionベクトルを使用する必要があります。

システムがパスを探索しない場合やエージェントがパスに達した場合には、CallbackMoveSystemで他のコールバックが呼び出されたかを確認してください。

3) Edit Tile Map

各グリッドセルはビットセットとしてフレーム内に表示されます。このビットセットにより、タイルがトラバース可能かが分かります。ビットセットの初期値はゲームスタート時に、シーンにベイクされたデータを元に編集時に構築されます。

ランタイム時にタイルマップを変更することもでき、これがこのサンプルシーンの目的です。マウスの右ボタンをクリックし、TileType (None or Wall) と位置をともなうQuantum Commandを送信します。EditTileMapSystemはこの位置をインデックスに変換し、タイルがトラバーサブルな場合にはビットセットを使用して保存します。

このエンティティはCUSTOM移動を使用し、移動の方向に壁があるか各ステップを評価します。そうでない場合には、移動をリパスします。

4) Decide the best target

このサンプルは地図上の点を追いかけるエンティティを表しています。このサンプルは、地図上の点を追いかけるエンティティを表しています。これは、__Dijkstraの__アルゴリズムを持っており、どれが追いかけるべき最適なアイテムかを決定するためにこのアルゴリズムを使用します。A*アルゴリズムとは異なり、1回の探索でマップ上の複数のエンティティの移動コストを測定することができます。AIDecisionSystem の目的は、NPCやBotsにマップ内の興味深い点の距離に基づいて、どれが最適な決定かを評価する方法を提供することです。

エージェントは利用可能なすべてのアイテムをマップし、最も近いものを選んで追いかけます。上記の画像では、青いエンティティが地図上の黄色いアイテムを交互に追いかけています。赤い点が現在のターゲットで、すべてのアイテムを訪問し終えると検索を繰り返します。

どのエンティティが検索に有効かを特定するために、このサンプルではItemTileSystemを使用しています。これは、ItemTileコンポーネントですべてのエンティティのインデックスをマップします。もしエンティティが地図上に存在すれば、その位置インデックスはグローバルなTileMapItemsディクショナリで見つけることができます。

アセット、コンポーネントおよびシステム

Tilemapアセット

TileMapDataは、インデックスを1次元配列にしたアセットです。ワールドポジションはインデックスに変換でき、インデックスはワールドポジションに変換することができます。この変換には様々な関数を使用できますが、グリッドベースのタイルマップでは通常この関数を使用します：

インデックスを使用すると、パスファインダーアルゴリズムでさらに安価かつ柔軟に使用することができます。TileMapData.csにあるIndexToPositionとPositionToIndexというメソッドの実装を参照してください。これらのメソッドは、通常X-Y座標で与えられる入力を処理するためにプロジェクト内で毎回使用されます。

// gets the index position of a world point position

var map = f.GetSingleton<RuntimeTileMap>();
var asset = map.Asset(f);

var worldPosition = frame.Get<Transform3D>(entity);
var positionIndex = asset.IndexToPosition(worldPosition);

positionIndexを使用して、特定のタイルや隣接するタイルがトラバーサブルか確認します。 GetNeighborsメソッドの戻り値のインデックスをワールドポジションに変換することができます。

var isPassable =  map.IsWall(positionIndex);
var neighbors = asset .GetNeighbors(positionIndex);

TileMapDataにはその他のフィールドがあり、必要に応じてアセットを拡張できます。このアセットには読み取り専用のデータのみを含める必要があります。ランタイム時に修正が必要なデータはコンポーネントに含める必要があります。このプロジェクトは、RuntimeTileMapと呼ばれるシングルトンを使用して、どのタイルが壁なのかについての情報を保存します。

フィールド	説明
タイル	マップ内の各タイルのインデックスのリスト
HEIGHT	Tilemapの行数
WIDTH	Tilemapの列数
TileWidth	ワールドサイズにもとづくタイルの幅
TileHeight	ワールドサイズにもとづくタイルの高さ
OffsetX	レベルの中心から、tilemapの最初のタイルの中心までの水平距離。
OffsetY	レベルの中心から、tilemapの最初のタイルの中心までの垂直距離。
Neighbors	マップ内の各タイルに対応するインデックスの配列のリスト。各インデックスは 1つの隣接領域を表し、負の値は無効なタイルを表す。

TilePathfinderコンポーネント

TilePathfinderコンポーネントには移動を実行するために必要なデータがあります：

。

フィールド	説明
エージェント	動きを制限しステアリングするためのいくつかのパラメータを持つ、TileAgentConfigへのリファレンス。
ウェイポイント	ターゲットへのパスを順次表すタイルのインデックスのリスト
TargetPosition	ターゲットタイルのインデックス。
CurrentWaypoint	次に進むべきタイルのインデックス。

通常、Waypointsの最初の値はターゲットで最後の値は次に進むべき点です。次のウェイポイントのワールドポジションを取得するには、CurrentWaypointをウェイポイントリストのインデックスとして使用します。

// gets the asset reference
var asset = f.GetSingleton<RuntimeTileMap>().Asset(f);

// gets the next point
var pathfinder = f.Get<TilePathfinder>(entity);
var index = pathfinder.Waypoints[pathfinder.CurrentWaypoint];
var nextPoint = asset.IndexToPosition(index);

CurrentWaypointとTargetPositionのデフォルト値は-1です。この値はパスやターゲットがそれぞれないことを意味しています。これらの値を-1に設定すると、エージェントの移動がキャンセルされます。

エージェント

エージェントは、TilePathfinderコンポーネントとウェイポイントをリファレンスとして使用し、マップ上で移動できるエンティティです。コンポーネントが移動するには、パラメータのあるTileAgentConfigが必要です。下表はTileAgentConfigのフィールドを示しています。

フィールド	説明
移動タイプ	ゲームプレイスタイルに合わせた移動のタイプ。
速度	移動タイプTRANSFORMで使用する移動速度。キャラクターコントローラーは独自の移動パラメータを使用します。
到達距離	次のウェイポイントに変更するための、エージェントからウェイポイントまでの最短距離
ウェイポイントの最大数	コンポーネント内のウェイポイントの最大数を制限します。
ウェイポイントの最大数	コンポーネント内のウェイポイントの最大数を制限します。
探索の最大コスト	移動コストにもとづき、探索距離を制限します。
描画ギズモ	ウェイポイントとエージェント移動のターゲットを描画します。

移動タイプはenum型としてTileAgentConfig アセットファイルに設定できます。使用する移動タイプを選択するには、このオプションを変更します。

サンプルでは、3つの可能な移動タイプを示しています：

Transform: 移動方向とエージェント速度を掛け合わせたものを使って、エンティティのトランスフォームの位置を設定します。
Kinematic Character Controller(KCC): 次に追うべきウェイポイントにもとづき、KCCへの移動方向の設定のみをおこないます。
Customized: エンティティリファレンスと正規化された移動方向で信号を送信します。ユーザーの好みに応じて動きをカスタマイズし、さまざまなシステムに適用することができます。

TilePathFinderSystem

TilePathFinderSystemはパスを計算し、TilePathfinderコンポーネントの中にウェイポイントを設定します。これは、ウェイポイントを用いてエージェントをターゲットに移動させるか、カスタマイズされた移動タイプに信号を送ります。エージェントの移動を開始するには、コンポーネントにターゲット位置を設定します。SetTarget関数はWaypointsをクリアし、ターゲットへの新しいパスを見つけようとします。

var pathfinder = frame.Unsafe.GetPointer<TilePathfinder>(entity);
pathfinder->SetTarget(frame, pathfinder, target);

その後、システムはAstartメソッドを呼び出すA*アルゴリズムを実行します。タイルマップとエージェントの移動の制限にもとづき、パスは見つかるかもしれないし見つからないかもしれません。見つからない場合には信号が送られ、負の値を設定することでインデックスが無効にされます。見つかる場合にはターゲットが確定され、CurrentWaypointはWaypointsリストの最後の値を指します。

以下のスニペットは、Astartがどのように使われ、またどのようにパラメータが適用されるかを示しています。このメソッドは静的なもので、必要に応じて他のカスタムシステムで使用することができます。この関数は多くの一時的なデータを生成するので、GC割り当てを避けるために最初のパラメータは、いくつかのリストの参照をキャッシュするPathfinderDataオブジェクトとします。

var result = AStar(pathfinderData, asset, frame, entityPosition, targetPosition, waypoints, maxCostOfSearch, maxNumberOfWaypoints);

if (result == PathFindStatus.NOT_FOUND) {
    waypoints.Clear();
    pathfinder->CurrentWaypoint = -1;
    pathfinder->TargetPosition = -1;
    f.Signals.OnTileMapSearchFailed(entity);
    return;
} else {
    pathfinder->TargetPosition = targetPosition;
    pathfinder->CurrentWaypoint = waypoints.Count - 1;
}

パスが見つからない、または探索の最大コストに達した場合、この関数はNOT_FOUNDenumを返します。ターゲットが見つかるとSetPath関数が呼ばれ、パスのインデックスでウェイポイントを埋め、SUCCESS enumが返されます。

カスタムの移動ステアリング

TileAgentConfigの移動タイプがCUSTOM に設定されている場合、エージェントの動きはコールバックを使ってカスタマイズできます。コールバックを受け取るには、システムは対応するシグナルインターフェースを実装する必要があります：

インターフェース	説明
`ISignalOnTileMapMoveAgent`	エージェントが有効なターゲットを持つ間、TilePathfinderSystemの各フレームで呼び出されます。エージェントがCUSTOMタイプの場合のみ呼び出されます。
`ISignalOnTileMapWaypointReached`	エージェントがリストからのウェイポイントに到達すると呼び出されます。
`ISignalOnTileMapSearchFailed`	ターゲットが無効な場合または見つからない場合、AStar関数内で呼び出されます。

以下の例では、ISignalOnTileMapMoveAgentインターフェースを実装してエージェントの動きをステアリングする方法を示しています。

public class MoveSystem : SystemMainThread, ISignalOnTileMapMoveAgent{
    public void OnTileMapMoveAgent(Frame frame, EntityRef entity, FPVector3 direction) {

        if (f.Unsafe.TryGetPointer<Transform3D>(entity, out var transform)){
            transform->Position += direction.Normalized * frame.DeltaTime;
        }
    }
}

レベルのセットアップ

プロトタイプには、TileMapBakerツールを使用すると3Dレベルからタイルマップを簡単に作成することができます。このツールは、Unityのコライダーコンポーネントがあるかどうか、各タイル位置をチェックします。そして、TileMapDataにタイルのインデックスとそのタイプを設定します：NONEまたはWALLを設定します。

Baker Toolでタイルマップアセットを作成

新しいタイルマップアセットを作成します：DBフォルダで右ボタンをクリック> Create > Quantum > TileMapData > TileMap
空のゲームオブジェクトで、TileMapBakerコンポーネントを追加します。

フィールド	説明
Level	ゲームオブジェクトレベルのルート。
Width	タイルマップのグリッドの列数。ワールド位置からインデックス位置への変換に使用される値です。
Height	ターゲットが無効または見つからない場合、AStar関数内で呼び出されます。タイルマップのグリッドの行数。

ゲームオブジェクトルートをTileMapBakerにドラッグします。
TileMapBakerコンポーネントの「Bake」ボタンをクリックします。

ベイキング後にトラバース可能なタイルは緑で、トラバースできないタイルは赤で表示されます。

マップの初期化

デフォルトのQuantumシーンで、エンティティプロトタイプを作成しコンポーネントRuntimeTileMapを追加します。このコンポーネントはシングルトンコンポーネントで、初期化時にアセットを読み込み、タイルのタイプに関するデータをビットセットにロードします。このビットセット構造体は実行時にタイルの状態を読み書きするために使用されます。

タイルマップアセットをこのコンポーネントにドラッグします。

このシーンが開始するとRuntimeTileMapはシングルトンコンポーネントとして開始し、アセットでベイクされたデータをビットセット構造体にロードして各ビットはタイルが壁であるかどうかを示します。

拡張と適応

タイルベースのマップは、異なるタイプのレイアウトを持つことができます。異なるレイアウトにアルゴリズムを適応させるために、TileMapData アセットを継承することができます。Astart関数はタイルの近隣を確認してパスを見つけようとしますが、タイルがいくつの近隣を持つことができるかは制限されていません。各タイルは他のノードにリンクされたノードであり、これらのノード間の関係を変更する異なるプロパティを持つカスタマイズされたTileMapdataを作成することが可能です。

このサンプルは2つの異なるレイアウトを示しています: Hexagonal__と__8-directions mapです。

8方向に移動できるタイルマップ

近隣のサイズやオフセットを上書きすれば、8方向のタイルマップを簡単に作成できます。GetNeighborsOffset関数は、インデックスにもとづいて近隣の数や方向を取得するために使用されます。

public class TileMap8 : TileMapData{
    public override int[] GetNeighborsOffset(int index) {
        return new int[8] {
            WIDTH, -WIDTH, 1, -1, WIDTH+1, WIDTH-1, -WIDTH-1, -WIDTH+1
        };
    }
}

この関数はベイカーツールが各タイルの近隣領域を登録し、それが有効であるかどうかをチェックするために使用されます。配列の値は方向のみで、近隣のインデックスはインデックス + 方向で求められます。

List<int> neighbors = new List<int>();
var neighborDirections = tileMap.GetNeighborsOffset(tile.Index);

// check if each neighbor is valid
foreach (var direction in neighborDirections ) {

    if (HasTileInDirection(tileMapAsset,tile.Index,direction)) {
        neighbors.Add(tile.Index + direction );
    } else {
        neighbors.Add(-1);
    }
}

// add the neighbors of that index to tilemap
tileMap.Neighbors[tile.Index] = new NeighborList() {
    Values = neighbors.ToArray()
};

六角形のマップ

六角形のタイルマップを扱うには複数のアプローチがありますが、最もシンプルな方法はグリッドベースのタイルマップの行または列にオフセットを適用することです。そして、近隣のロジックを変更する必要があります。

以下のサンプルでは、オフセットの希望する方向によってHexagonOffsetは+1または-1になります。また、タイルの上部がとがっているか平らであるかで、オフセットする列や行が変わります。

public override FPVector3 IndexToPosition(int index) {

    int x = index % WIDTH;
    int y = index / HEIGHT;
    FP offsetX = 0;
    FP offsetY = 0;

    if (HexagonTop == HexagonTop.Pointy) {
        offsetX += (y % 2) * (TileWidth / 2) * (int)HexagonOffset;
    } else {
        offsetY += (x % 2) * (TileWidth / 2) * (int)HexagonOffset;
    }

    return new FPVector3((x * TileWidth) + offsetX, 0, (y * TileHeight) + offsetY) + Offset;

}

六角形マップ実装のその他の詳細については、HexagonalMap.csファイルを参照してください。

ヒューリスティック

Astart関数は最短パスの探索にヒューリスティックを使用できます。ヒューリスティックはアルゴリズムの性能に大きな影響を与え、使用しない場合には常に最短経路を見つけることが保証されますがパフォーマンスは最低となります。TileMapdataから継承し、またHeuristicメソッドをオーバーライドすることによって距離の値は変更することができます。

// The Manhattan distance is better for grid base

public virtual ushort Heuristic(int from, int to) {
    FPVector3 a = IndexToPositionRaw(from);
    FPVector3 b = IndexToPositionRaw(to);
    return (ushort)(FPMath.Abs(a.X - b.X) + FPMath.Abs(a.Z - b.Z));
 }

// The linear distance is better fo hexagonal maps

public override ushort Heuristic(int from, int to) {
    FPVector3 a = IndexToPosition(from);
    FPVector3 b = IndexToPosition(to);
    return (ushort)(FPVector3.Distance(a, b));
}

ハイライト

ヒューリスティックによるトレードオフ

速度と精度はトレードオフの関係にあり、Aアルゴリズムで使用する関数のサンプルが2つしかないプロジェクトでは、最終的な結果を他のプロジェクトに適用できない可能性があります。ヒューリスティック関数がない場合や0を返す場合、AアルゴリズムはDijkstraのアルゴリズムに変わり最短経路が保証されます。しかし、ほとんどのゲームでは最短経路は必要なくヒューリスティックの値が移動コストと同じであれば、アルゴリズムは非常に速く実行されますが最短経路の探索は保証されません。

プライオリティ―キュー

A*アルゴリズムでは、タイルを移動のコストでソートするPriority Queueを使用しています。このプロジェクトでは、Priority Queueの実装が複数あり、性能テストでは、Binary Heapがこの問題を扱うのに最も高速なデータ構造であることが示されています。Insertion Sortや他のアルゴリズムでは、少なくともBinary Heapの2倍の所要時間となります。

PriorityQueueファイルで他の実装を確認してください。Priority Queueの実装は、選択されたタイルと最終的なウェイポイントリストに影響します。たとえばソート機能で比較信号を変更すると動きはより自然に見えますが、より多くのウェイポイントが追加されます。