学習経路探索アルゴリズムを簡単にする試み

経路探索アルゴリズムは、ゲーム開発に不可欠な部分です。 さまざまなナビゲーションシステム、オリエンテーションなどがあります。 ただし、ゲーム業界とそれに使用されるアルゴリズムに焦点を当てます。

各ゲーム開発者は、すべての壁を収集せずに、キャラクター（またはボット）をあるポイントから別のポイントに移動させる必要があるタスクに直面しています。 また、戦略開発者は、セル（道路、沼地、森林など）の開通性を考慮する必要があります。 これは、パス検索アルゴリズムが助けになる場所です。

なんで？

上記から、遅かれ早かれ、ゲーム開発者は対処し、方法を見つけ、後でそれを自分のプロジェクトに合わせて修正および最適化する必要があると結論付けることができます。 また、非常に多くの新人がGameDevに直接アクセスするため、複数の記事を読んで1つまたは別のアルゴリズムを理解することは必ずしも容易ではありません。 この投稿では、検索アルゴリズムの仕組みを理解するプロセスを促進するのに役立つソフトウェアを作成する試みについて説明します。

基本的なアルゴリズムについて一言

3つの主要なアルゴリズムを検討します。 メインアルゴリズムのそれぞれについて簡単に説明し、プログラムでの作業の視覚化のスクリーンショットを（イベントの少し前に）紹介します。

ダイクストラのアルゴリズム

1959年にオランダの科学者Edsger Dijkstroyによって設計されました。 アルゴリズムは、元の頂点への最短パスが見つかるまで、グラフの各頂点をチェックします。 詳細については、たとえばこちらをご覧ください 。

A *（星印）

このアルゴリズムは、1968年にPeter Hart、Niels Nielson、およびBertram Raphaelによって初めて説明されました。 個々の頂点を考慮すると、その隣接する頂点への遷移が行われ、目的の頂点までの推定パスが最短になります。
ここから研究を始めることができます 。

ジャンプポイント検索

このアルゴリズムは、2011年にD. HarborとA. Grastienによって導入されました。 JPSはパスの検索を高速化し、表示すべき多くの場所を「ジャンプ」します。 「ジャンプポイント」を使用すると、「必要な」ノードのみを考慮して、パス検索アルゴリズムを高速化できます。 ここでの動作原理は非常によく説明されています。

小さな予約

プログラムに表示されているGrowing Treeジェネレーターは、下の図のように「古典的な迷路」を作成します（拡大のみ）。設定の高さと幅は、それに合わせてさらに設定されます。 このジェネレーターは、初心者向けの「すごい効果」を作成し、最も基本的なアルゴリズム（右または左手のルール、DFS）によって構築されたパスを実証するために追加されました。

検索基準-市松模様のフィールド

検索はグラフで機能します。地図からグラフを作成する最も簡単な方法は、地図を市松模様のフィールドに変換するウェイポイントを設定することです。 目標は基本の理解を容易にすることなので、正方形のセルを使用します。

まず、セルのクラスを決定する必要があります。 ユーザーは、入り口、出口を設定し、通過できない障害物をフィールドに配置できる必要があります。また、アルゴリズムの実行中にセル、その親、およびステータスの特性を調べることも役立ちます。 その結果、提示されたクラスを取得します（スペースを節約するためにset-、get-functionsを削除しました）：

enum Status{ Click, Unclick, Enter, Exit, NoStatus }; enum ListStatus {NoList, InClosed, InOpen}; class GraphicsCell : public QGraphicsRectItem { public: GraphicsCell(int, int, int, bool *, bool *, bool *, QGraphicsItem *parent = 0); void pressButton(int buttonID); void showInfo(QPoint pos); void updateStatus(int upd); void deleteInfo(); private: int x; int y; int f; int g; int h; int weight = INT_MAX; Status status; ListStatus listStatus; bool *isEnter; bool *isExit; bool visited; GraphicsCell *par; QGraphicsRectItem *infoBox; }; 

pressButtonおよびupdateStatus関数は、セルのステータスと色の変更を処理します。 インフォボックスのshowInfoおよびdeleteInfo。これについては後述します。 変数xとyは座標を担当します。 f、g、h、検索アルゴリズムの動作に必要な特性の重み、ステータスおよびステータス
セルステータス、マップ上に入力と出力があるかどうかのisEnterおよびisExit、親セルのパー（構築されたパスを復元するために必要）。

フィールドワーク

市松模様のフィールドを作成しました。今度は、ユーザーに出し入れを行い、壁を設定し、前述の情報ボックスを呼び出す機会を与えるといいでしょう。

幸いなことに、インターフェイスを作成するQtフレームワークのQGraphicsViewクラスは、クリック、ダブルクリック、カーソル移動の仮想機能（それぞれ、mousePressEvent、doubleClickEvent、mouseMoveEvent）を提供します。 私たちは細胞を含む教室のシーンでそれらをオーバーロードします。

checkPos関数は、カーソルがセルオブジェクト上にあることを確認します。

 void MazeWindow::mousePressEvent(QMouseEvent *event) { checkPos(event); GraphicsCell *currCell = static_cast<GraphicsCell *>(scene()->itemAt(mapFromGlobal(cursor().pos()), QTransform())); if (currCell == NULL) return; if (startStatus == Status::NoStatus) { if (currCell->status == Status::Click) startStatus = Status::Click; else startStatus = Status::Unclick; } if (event->button() == Qt::RightButton) { currCell->showInfo(mapFromGlobal(cursor().pos())); cellWithInfo = currCell; } else currCell->pressButton(event->button()); } 

クリック機能の実装。 クリックしたセルを特定し、ステータスの更新を依頼します。 InfoboxはRMBにインストールする必要がありました。Qtではダブルクリックを使用するときに通常のクリックの機能が最初に呼び出され、これによりセルがちらつきます（シングルクリックでセルの状態を更新し、ダブルクリックを認識したときにそれを返しました）。

入力は「Ctrl + LMB」に配置され、出力はマウスホイールまたはタッチパッドの「Alt + LMB」に配置されます。 十分に快適。 壁には通常の塗装が施されています。

 void MazeWindow::mouseMoveEvent(QMouseEvent *event) { checkPos(event); GraphicsCell *currCell = static_cast<GraphicsCell *>(scene()->itemAt(mapFromGlobal(cursor().pos()), QTransform())); if (currCell == NULL) return; if (cellWithInfo != NULL && currCell != cellWithInfo) { cellWithInfo->deleteInfo(); cellWithInfo = NULL; } if (currCell->status == Status::Enter || currCell->status == Status::Exit) return; if (event->buttons() & Qt::LeftButton) { if (startStatus == Status::Click && currCell->status == Status::Click) currCell->updateStatus(1); else if (startStatus == Status::Unclick && currCell->status == Status::Unclick) currCell->updateStatus(0); } } 

また、通常のグラフィックエディターで行われているように、ユーザーがLMBを上下に動かして壁を描くことができるようにしたかったのです。

これを行うには、mouseMoveEvent（）関数をオーバーロードします。 セルの上にいることを確認し、カーソルの下のセルの状態を更新するように要求します。 空のセルから描画を開始する場合は壁を描画し続け、壁を消去した場合は「消しゴム」モードを続行します。 関数は、呼び出されたセルからカーソルを削除した場合、情報ボックスを削除する役割も果たします。

インフォボックスを通常の長方形として作成します。この長方形は、重量、F、G、Hの特性（上記のアルゴリズムに精通している場合はこれらの表記法を知っています）、セルとその親の現在の状態を示します。



それだけです。私たちは視覚化のために現場の仕事を提供しました。難しい仕事の半分は完了です、乾杯！

パスを見つける作業の進行状況の視覚化

プログラムの最も興味深い部分は、退屈な（またはそうでない）記事を次のようなものに変えるべきものです。



ステップバイステップモードもあります。これは、インフォボックスと組み合わせて、各アルゴリズムの動作を100％理解するのに役立ちます。

ここで、これがどのように実装されたかについて少し説明します。 例として、AStarアルゴリズムの機能を考えてみましょう。残りのアルゴリズムも同様に実装されます。 また、ボタンから関数自体への信号送信はそのままにします。

 bool MazeWindow::ASolve(int mode) { currMode = 0; if (a == NULL) { //  ,    if (aL != NULL) scene()->removeItem(aL); clearLabyr(); a = new A(&labyr); a->solveMaze(0); } if (mode == 0) { while (!a->solveMaze(1)); // updatePictureSolve(Algorithms::AStarAlgo); currMode = 1; return true; } else { if (a->solveMaze(1)) { // updatePictureSolve(Algorithms::AStarAlgo); QMessageBox msgBox; msgBox.setText(tr("Sucsess")); msgBox.setIcon(QMessageBox::Information); msgBox.exec(); currMode = 1; return true; } } return false; } 

1つの関数にステップバイステップモードと完全なソリューションを実装したため、モードIDを転送する必要があります（0-完全なソリューションと1-次のステップ用）。 さらに、これが完全なソリューションまたは段階的な方法の最初のステップである場合、前のソリューションの残りからフィールドをクリアし、セルのステータスを消去し、clearLabyr関数を使用して特性を更新します。 アルゴリズム自体の機能は、検索エンドポイントに到達した場合や検索を続行できない場合はtrueを返し、作業を続行できる場合はfalseを返すように実装されます。 したがって、while演算子による完全なソリューションでは、trueが返されるまで関数を呼び出し、updatePictureSolve関数を呼び出してシーンにパスラインを描画します。 ステップバイステップモードでは、クリックするたびに関数を呼び出します。パスが見つかった場合は、ユーザーが誤って決定の瞬間をクリックしないように、メッセージを描画して表示するために送信します。

検索アルゴリズム自体は、セルが開いたリストまたは閉じたリストにリストされているときにセルのステータスを更新します。

制御盤

プログラムに含まれるもの：

• 2種類のジェネレーター： 成長ツリーと手動モード（上記の市松模様のフィールド）
• 5種類のアルゴリズム：DF​​SおよびGrowing Treeジェネレーターの手動ルール検索 、および手動モードのDijkstra、AStar、JPS。

ユーザーが名前付きオプションを簡単に切り替えられるようにする必要がありました。 優れたデザインの結果、ワークスペースに小さなメニューバーが表示され、ツールバーから非表示にしたり呼び出したりできます。 カラーフィールドをクリックして、パスラインの色を変更することができます。 （私の好みが気に入らない場合）

統計を操作する

このプログラムを使用して、特定の状況に最も効果的なアルゴリズムを選択することもできます。

• 必要なマップを大まかに描くと、写真のようになります
• 3つのアルゴリズムすべてを開始し、作業を目で評価します。

明らかに、多かれ少なかれ深刻なプロジェクトでは「目で見る」だけでは十分ではないため、統計を表示する必要があります。

これは、ワークスペース内の現在のアルゴリズムの簡単な統計とセッションごとのすべてのアルゴリズムの操作を表示し、Excelなどでコピーできるレポートを作成し、そこでグラフを作成できる別のウィンドウを使用して、ウィジェットの形式でこれを行います。

簡単な統計を使用したウィジェットの実装は、設定を使用したウィジェットの実装と非常に似ており、ほとんど同じように見えます。



アルゴリズム自体が操作の数を計算します。 パスの長さは出口セルの特性から知ることができ、時間をタイマーと見なし、描画に費やした時間を差し引きます（ただし、これはあまり正確ではありません）。 アルゴリズムの動作が完了すると、ウィジェットに統計を渡し、関数を呼び出してテーブルにエントリを作成します。 その結果、次の表があります。


A *とDextraの結果が同じである理由を個別に言及する価値がありますが、JPSは優れています。 これは、2つの異なる方法を使用してセル間の距離を計算するためです。A*とダイクストラは、垂直および水平遷移10と対角線14のコストを使用し、合計結果を10で除算します。 JPSはそれぞれ1とsqrt（2）を使用し、何も分割しませんが、切り捨てます。 JPSはパスの長さをより正確に表示するため、数値が異なります。

おわりに

プログラマーだけでなく、初心者がパス検索アルゴリズムを扱うのに役立つプログラムを入手しました。 少なくとも私はまだ数人の友人を助けました）

著者は、試験を書いたらすぐにあなたの希望に耳を傾け、それらを満足させます。
おそらく、一連の改善により、アルゴリズムを備えた強力なライブラリが得られるという事実につながり、プログラムはそのための素晴らしいデモになります（ PathFinding.jsのように 、より良いだけです）。

ウェイの検索に関する記事を書きたい場合は、このプログラムを添付できます。



→実験研究資料： PathFinding.js
→このプログラムは、 poisonまたはDropBoxからアーカイブをダウンロードできます 。
UPD：最初は誤って不完全にデバッグされたバージョンが公開されていましたが、現在はすべて問題ありません。 謝ります 2017年3月14日（はい、約4日間、タグ付きバージョンがハングしました：C）
→オリジナルプロジェクトVS2013：Poison and Dropbox