knagaiPathfinding(パスファインディング)とは、パスをファインドすること、つまり目的地までの経路を見つけることで、一般的には「ある場所から他の場所に移動するときの最短経路を導き出す方法」を言います。エースター)探索アルゴリズム」です。どの方法もそうやすやすと始められる代物ではありません。本稿では、最も取り組みやすそうな「幅優先探索アルゴリズム」をp5.jsで実装する方法を見ていきます。Javascript)」(基本的な経路探索アルゴリズム(JavaScriptによる実装))ページに記載されている記事の翻訳です。こんな状況を思い浮かべてみてください。みなさんは2次元のボードにある”A”という名前の付いた正方形の上にいて、”B”という名前の正方形までの最短経路を見つける必要があり、この地図が与えられています。難しくはありませんね。人間なので、正方形”A”から”B”への最適な経路はいくつか簡単に見つけることができます(0.5秒もかからないうちに)。(少し)難しいですが、ほどなく解けるでしょう。障害物がもっと多いと、問題の解決にはもっと多くの努力が要るでしょう。言え、コンピュータはごく単純なアルゴリズムでこれが解決でき、さらに気が遠くなるほど難しい経路探索(パスファインディング)問題すらも解決できることが分かっています。以下ではこのアルゴリズムの書き方を学んでいきます。Search)」と呼ばれる手法です。Googleで調べてみても構いませんが、基本的には、通ることのできる長さが1の経路を全部調べ、次に通るのことのできる長さが2の経路を全部調べるということを、正方形”A”から”B”への最短経路が見つかるまでつづけるという方法です。これは言うほど非効率的ではありません(非常に大きな経路探索問題も、今時のコンピュータが実行不可能だと音を上げる前に解決するでしょう)が、覚えておいていただきたいのは、この手法を使った経路探索問題の解決に必要なメモリと時間は、ボードのサイズが大きくなるにつれ、比較的急速に増大する、ということです。ステップ1:キューが要るまず必要なのは、最適な経路決定のために調べる正方形全部を追跡するキュー(待ち行列)のデータ構造です。これは経路に順位付けをする”to-do”リストと考えてください。キュー(queue)は”待ち行列”と訳され、FIFO(先入れ先出し)の方法でデータを扱います。上級レベルの読者へ:このキューは技術的に言って、リンク付けしたリストを実装する方が高速になる。この方がよりシンプル。ステップ2:新しい位置を”発見した”とき、それをキューに追加する必要があるキューは探索する位置の”to-do”リストのようなものだということを思い出してください。これはひっかけ問題です。近いのはスタート位置です。したがって、このスタート位置をキューに入れることから始めます。ステップ3:探索開始!探索は次の流れで進めます:キューから最初の位置を取り出すキューから取り出した位置から1だけ”移動”した位置を走査する(この例では、現在のタイルの北と南、東、西にあるタイル)これらの位置の1つが目的地なら、終了!そうでない場合;まだ調べていなくて有効な位置(つまりボード上にあり”障害物”でない位置)なら、その新しい位置をキューの末尾に追加するこの過程を繰り返す(キューから最初の位置を取り出す...)探索は、目的地の状態が見つかるか(上記の3)、探索する位置がなくなる(キューが空になる)までつづけます。目的地が見つかった場合には、その最短経路が答えだと分かります(つねに最も近い位置を最初に追加しているので、それが最短経路だと分かります)。探索する位置がなくなった場合には、それは、終了位置までの有効な経路がなかったということです(キューが空になったということは、探索する有効な位置がなくなったということです)上記の手順を進めるとこの結果になる、ということはもう十分お分かりかも知れませんが、すっきりしない方のために(ただ文字を追っているだけなので無理からぬことです)、具体的な例を見ていきましょう。ページに掲載されているアルゴリズムと疑似コードです。クィックサンプル:アルゴリズムを1つずつ見ていく上の例を再利用して、位置”A”から位置”B”に行きたいとします。この(実にシンプルな)問題をここまで見てきたアルゴリズムを使って解決してみましょう。ステップ1:キューが要る。[]ステップ2:スタート位置をキューに追加する必要がある位置は座標として次のように表すことにします。(3,2)の正方形に隣接する有効な位置を追加するとき、(2,2)が目的地であることを知るので、アルゴリズムは停止する。これで位置Aと位置B間の最短経路を見つけることができたコードにするでは、”グリッド”をコードにするとどのように見えるかをやってみましょう。"Obstacle";“グリッド”を表すことができたので、スタート位置とボード配列を取り、最短経路の配列を返す関数を記述しましょう(そして全部をひとまとめにします)。注意:実際に最短経路を返すにはもう少し複雑になります(この後分かります)。その根幹では、ここまで述べてきたアルゴリズムをただ実装しているにすぎないことが分かります。grid));ハードルが少し高いかも知れませんが、コードをコピーして、ブラウザのコンソールにペーストするか、Node.jsを使って実行すると、最短経路が次のように表示されることが分かります。‘North’何より重要なのは、非常に複雑な経路探索問題であっても、目的地までの最短経路を高速で計算できることです。コメントをキャンセルメールアドレスが公開されることはありません。*サイト上に表示された文字を入力してください。WAAPIに関する注意WAAPIを利用するにはブラウザに特別な設定が必要です。ブラウザの実験的な機能を有効化する方法に書いているので、必ずお読みください。楕円(円)、円弧を描く。APIやTensorFlow.jsについて調べたことを書いています。freebiescafe.com。