2

補足: この質問がゲーム開発スタック交換サイトに属しているかどうかはわかりませんが、コンテキストはゲームですが、実装しようとしているアルゴリズム自体はかなりアプリケーションに依存しないため、ここに属していると思います。さらに、高度なテクニックを求めているわけではありません。すでに確立されていると感じているからです。代わりに、特定の問題に対するより具体的なヘルプを求めています。とにかく、質問に：

こんにちは、みなさん！

私は、サーバーがサーバー制御エンティティのパスファインディングを実行できる必要があるマルチプレイヤー ゲームに取り組んでいます。サーバーはストレートな C# アプリケーションで、クライアントは Unity ゲーム エンジンを使用します。サーバーで Unity を使用することはオプションではありません。さらに、ネイティブ ライブラリは完全に避けたいと考えています。

Detour の経路探索については既に調べました。これらには C# ポートがありますが、実際の経路探索ビットの独自の実装が必要です。プロセスは簡単なので、サーバー上の既存のコンポーネントとうまく連携できるように、自分のニーズに合わせて調整したいと考えています。

Unity には、Recast/Detour のサポートが組み込まれています。Unity で Recast を使用してナビゲーション メッシュを生成できるので、これは良いことです。次に、独自のパスファインディングを使用してサーバーで消費します。問題は、Unity/Recast によって作成されたメッシュに基づいてグラフを生成する適切な方法が見つからないように見えることです。

私がする必要があるのは、メモリ内にグラフを作成することです。ここで、各ノードはメッシュ内の三角形であり、グラフの各エッジは互いに隣接する 2 つの三角形を接続します。

Unity の API から抽出できるデータは、生成されたメッシュの頂点と三角形のインデックスだけなので、独自のグラフを再構築する必要があります。私の最初の実装では、単純に三角形ごとにノードを作成し、その三角形が他の 2 つのポイントを別の三角形と共有している場合、それらの間にリンクを作成して、グラフのエッジを形成しました。

これはメッシュの大部分でうまく機能しますが、2 つの頂点を共有していなくても、領域 (ポリゴン) 間に接続 (エッジ) を持つことができるメッシュを Unity が吐き出しているように見えるため、不十分です。Unity が生成した navmesh をレベル ジオメトリにオーバーレイする例を次に示します (Unity は三角形を凸面ポリゴンにマージしますが、私のコードはマージしません - ただし、どちらの場合も問題は依然として存在します)。

ユニティ ナビメッシュ

この例では、生成されたグラフは白い線で区切られたポリゴンを接続する必要があります (Unity で白としてレンダリングされる理由を説明するドキュメントは見つかりません) が、単一の頂点しか共有していないため、接続できません。

これらのケースを検出するための効率的なアルゴリズムがあるかどうか疑問に思っています。私が考えているのは、ポリゴンが接続されていると見なされるようにすることです:

if (sharedVertexCount == 2)
    connectPolygons()
else if (sharedVertexCount == 1)
    Vector3[] parallelLine = findParallelLineSharedByBothPolygons()
    if (parallelLine != null)
        Vector3 otherPoint = getUnsharedPointInLine(parallelLine)
        if (isPointInLine(parallelLine, otherPoint))
            connectPolygons()

これでうまくいくと思いますが、これを効率的に行う方法が見つかりません。また、「isPointInLine」の実装に少し問題があります。どうやら私の数学のスキルは、思ったよりも錆びているようです。

いずれにせよ、もっと簡単な解決策が必要です。それでも、その方向性を示すものはオンラインで何も見つかりませんでした...そのため、生成された navmesh を接続されたポリゴンのグラフに効率的に変換するためにできることがあるかどうか、素晴らしい人々に尋ねています。isPointInLine の実装に役立つか、より賢明なアルゴリズムの方向性を教えていただければ、言葉では言い表せません。

4

2 に答える 2

1

パスファインディングに関して言えば、ほとんどの方法は、操作が簡単なナビゲーション専用の事前に作成されたデータ構造を提案します (グラフィック データ構造が十分に単純でない限り、ここではそうではありません)。

いくつかの解決策を提案しています：

  • ボクセル ベースのナビゲーション システム: 3D 配列のブール値 (通れない/通らない) を使用してボクセル システムを実装し、それにA スターまたはD スターアルゴリズムを適用します。

  • AI がそこを通過できることがわかっているパス ベクトルを把握します。

  • 2 つのシステムのマージ (メイン パスは既知のパス ベクトルを使用し、メッシュは false と交差するボクセルに署名します。これはおそらくあなたが探しているソリューションです。

于 2014-02-08T11:59:49.020 に答える