実験として、開発者の「日記」を保存し、経験を共有し、実験の興味深い結果を強調することにしました。 これは、UnityゲームエンジンのアセットであるPathfinder 3Dプロジェクトに関するデビュー記事で、3次元空間でパスを検索できます。 その中で、アイデアの起源から本格的な製品への道と、私たちが遭遇した問題のいくつかについてお話します。 この資料は、将来プロジェクトを開始してサポートしたい人や、空間内のパスの検索を実装したい人に役立ちます。
2人のチームが資産の作業を開始しました。 最初のものは、複雑なグラフ上でリアルタイムで動作するのに十分な最短経路を見つけるプロセスを高速化できる開発がいくつかあり、それらの実用的なアプリケーションを見つけたいという要望があり、2つ目はUnityでの作業経験があり、スタートアップのアイデアを探していました。 彼らはしばしば相互に通信するため、ある時点で、3次元空間でパスを検索するためのアセットを作成する可能性についてアイデアが生まれたのは驚くことではありません。
Unityアセットカタログを調べると、2次元空間でパスを見つける多くのソリューションが見つかりましたが、3次元では見つかりませんでした。 特に期待される結果の可視性とエンターテイメント性を考慮すると、これがUnityソフトウェアアドオン市場に参入する絶好の機会であることが明らかになりました。
目標は、3次元空間のパスの検索と、2次元空間のパスを見つけるための既存のソリューションの典型的な機能を直接実装することでした。 作業を開始しました：パス検索メカニズム、パス検索プロセス、構成インターフェイス、テストシーン、ドキュメント、プロジェクトサイトを管理するための2番目のクラスとメソッドを直接開発し、資産の販売に必要なサービスアカウントの登録と設定も行いました。
作業の開始後すぐに、チームがメモを取るためにいくつかの共通のリソースが必要であることが明らかになりました：解決する必要があるタスクと問題のリスト、下された決定に関する情報、将来興味深いアイデアと研究結果。 既存のソリューションを分析した後、 Trelloの機能、シンプルさ、利便性、快適な外観のために停止しました 。 実践が示しているように、このサービスは小さなチームにとって非常に便利です。 チームに5人以上の人がいる場合は、本格的なプロジェクト管理システムを使用することをお勧めします。
次に、アセットの最初のバージョンの開発中に下された決定、およびそれらを作成する際に従ったロジックについて説明します。 Unityの経験があり、経路探索アルゴリズムに精通している人々は、将来問題が発生する場所をすぐに理解できます。 これらの場所では、熱意が制限されており、一貫性がないため、動揺しないように、アセットの最初の作業バージョンが受信されるまで開発時間を短縮するために、単純なソリューションを使用しました。 そのため、このようなスタートアップを閉鎖する最も一般的な理由の1つに取り組みました。その理由は、多くのプロジェクトが生まれることなく死ぬからです。 すべての問題領域は、資産の公開後に修正されました。
パスを見つけるために、 A *（Aスター）アルゴリズムが選択されました。これは、大きなオープンスペースでの高速動作のためです。 ほとんどのパス検索アルゴリズムは、離散行列で表されるグラフで機能します。 事前にこのマトリックスを構築することは可能ですが、障害物のある3次元空間での1回限りの構築プロセスは、その時点ではかなり困難な作業と見なされていました。 さらに、アセットの作業を開始した時点で、Unityのバックグラウンドプロセスとマルチスレッド、および一般的なマルチスレッドの経験がなかったため、パフォーマンスを犠牲にすることなくこれを行う方法は明確ではありませんでした。 グラフは、検索の方向に物理的な光線（Physics.BoxCast）で空間をプローブすることにより、リアルタイムで形成されました。 見つかった軌跡は、中間点の少ない壊れた軌跡に縮小され、スプラインによって平滑化されました。
主な困難は、エンジンの物理メソッドをメインスレッドでのみ動作させることができるため、エンジンの物理メソッドを非同期で使用できないことでした。 複雑すぎないシーンでは、20人以下のエージェントが同時に検索機能を使用しても、フレームレートに大きな影響はありませんでした。 FPSのまれで強力なドローダウンを取り除くために、コルーチンを使用して計算負荷の時間間隔を空けました。 これにより検索速度は低下しましたが、大幅には低下しませんでした。
モデレートのためにアセットを送信する前に、コードを整理し、 要件に従って詳細なドキュメントを作成し、サポートメールを登録および構成する必要があります。 また、開発ニュースやデモが便利に表示されるプロジェクトサイトを作成することをお勧めします。 これは、節度の経過中、および購入前にユーザーが資産を調査する場合の両方で大きなプラスになります。 ホスティングとメールサービスはBeGetから注文されました。当時は最も有利なオファーを提供していたため、年間1000rの費用がかかりました。
Unityストアのアセットページのドキュメントとデザインに非常に慎重にアプローチしたため、アセットのモデレーションは22日間続き、初めて合格しました。 公開後、アセットはすぐにScripting / AIカテゴリで1位になりました。 その瞬間から、特定の問題を解決するための支援を求める手紙がサポートメールに届き始めました。 時には1日に数回、時には1か月ではありません。 平均すると、1か月以上で2人が質問をし、それに対応するのに合計2〜3時間かかりました。 それほど多くはありませんが、現在のワークロードに関係なく、怒っているユーザーが製品について悪いレビューを書かないように、非常に迅速に対応する必要がありますが、それどころか、質の高いサポートに熱心であり、肯定的なものを残してください。 また、「...ならば資産は機能しますか？」のような非常に多くの質問がメールに来ます。 また、このような手紙は無視されるべきではありません。なぜなら、これは去ることができる潜在的な買い手だからです。
最初の顧客から苦情が寄せられると、多くのユーザーが迷路またはその他の接続された空洞の構成を持つ複雑なシーンでアセットを使用することが明らかになりました。 そのようなプロジェクトでは、衝突チェックに基づいた、そしてメインストリームでさえ、パス検索スキームは十分に効果的ではありませんでした。 そのため、物理学を使用せずにシーンオブジェクトにアクセスすることなく、サイドストリーム内のパスを検索できるように、グラフの初期構築の実装を開始しました。
3次元空間を離散化すると、キューブに分割されます。 すべてのパーティションキューブに関する情報の保存は冗長であり、非常に多くのメモリを消費します。 したがって、不可能なセルの座標のみを保存することは論理的です。
ゲームの障害は多角形であり、三角形で構成されています。 検索グラフで障害物を考慮するには、障害物の三角形と交差するパーティションのすべてのキューブを見つける必要があります。 すでにこの段階で、障害物を動的に削除してステージに追加する可能性が生まれ、占有されたキューブの座標だけでなく、その中にあった障害物の識別子も保存されました。 ゲームプロセスの開始前にナビゲーショングラフを作成できるようになりました。また、パスの検索中に多数の複雑な計算が排除されるため、パフォーマンスを損なうことなく200人以上のエージェントが同時に実行できます。
私たちが知っている別の問題も感じました。A*アルゴリズムとその修正は、大きなパワーグラフ上の限られたスペースでは非常に不十分に動作します。 アルゴリズムはターゲットポイントに近づく方向にルートの方向を優先するため、ターゲットにつながるデッドロックはパスの検索を大幅に遅くします。「発芽」の異なる方向を選択する前に、アルゴリズムは最初に行き止まり内のスペース全体を「埋める」からです。
このような状況では、空間を「埋める」ために必要な操作の数が少ないため、 波探索アルゴリズム（Lieアルゴリズム）が非常に効果的であることがわかります。 したがって、代替として資産に追加されました。 迷路のステージでテストすると、パスの検索時間が30倍以上短縮されました。
シーンの事前処理を高速化し、アセットへのパスを見つけるために、プロセスの並列実行の可能性が追加されましたが、占有セルの座標を格納するコンテナーで作業する場合、フローを同期する必要があるため、並列処理の効率は非常に低かったミューテックス。競合するコレクションや効果的な同期を保証する他の多くのツールは.NET Framework 4.5標準でのみ実装され、Unityでは2018リリースまで.NEバージョンが使用されていたため Tフレームワーク3.5。 利用可能なツールを使用してこの問題を解決しようとしましたが、非常に平凡なパフォーマンスがあり、2018 Unityリリースに切り替えた後にのみ望ましい結果が得られました。 競争力のあるコレクションの使用は、シーン内の障害物の動的な変化を実現する可能性も開きました。
ある段階で、利益の分配に関してチーム内で意見の相違が生じ始め、チームに加わった第三者がチームに加わりました。第三者はチームの各メンバーの時間投資を評価するシステムを導入し、コードの検査とテストにも取り組み始めました。これにより、製品の品質が大幅に向上しました。
現時点での時間コストを見積もるシステムは、Excelテーブルの形式で作成され、月に一度、過去1か月に完了した販売およびタスクに関する情報を入力する必要がある自動化されたシステムです。 チームメンバーは、特定の問題を解決するのに必要な時間を評価する必要があります。 したがって、タスクの時間の複雑さを評価するとき、各参加者の速度が考慮されます。 参加者の一人による異常な誇張または控えめな表現は、彼の以前の評価の蓄積された統計からすぐに明らかになります。 そして、満足のいく説明がない場合、この問題はチーム全体によって決定されます。 このアプローチは6か月間の使用に適していることが証明されており、興味深い統計を収集することができました。 説明した機能を提供する既製の無料ソリューションは見つかりませんでした。 したがって、現時点では、小規模なチームの場合、Excelテーブル形式での実装が最適であると思われます。 比較的大規模なチームの場合、ほとんどの場合、データベースの設計、サーバー部分とクライアントの開発、または既存のプロジェクト管理システムのいずれかの拡張機能の実装が必要になります。
まとめると。 開発が開始されてから、最低限必要な機能と実際のプロジェクトで使用するのに十分なパフォーマンスを備えた最初のバージョンまで1年が経過しました。 パフォーマンスの改善と資産のマルチスレッド作業の実装にさらに6か月が費やされました。 現時点では、このプロジェクトの時間コストは1065人時と見積もられ（これはかなり楽観的な見積もりです）、その月の平均利益は9.5トンです。 現時点での1時間の作業の平均コストは約160ルーブルであると計算するのは簡単ですが、それほど多くありません。 ただし、このイベントの主なものは、各参加者が得た経験です。 チームワークの経験とソフトウェア製品サポートの経験を含みます。 プロジェクトは成功したとみなすことができます。
現在、私たちのチームは追加の有用な機能の実装を開始しています。 ゲームオブジェクトをポータルに割り当てる機能。 動的障害物サポート; 衝突を防ぎ、ローカルルートを計画するためのエージェント間のローカルナビゲーション。
この資料が、誰かが自分のプロジェクトをゴールに導くのに役立つことを願っています。