「Wall-Eのための経路探索アルゴリズムの探求」

Exploring Pathfinding Algorithms for Wall-E

背後の物語

数年前、ヤンデックスは「ロボット宅配員」という魅力的な賞品が用意されたコンテストを開催しました。その賞品は、専門家向けの閉鎖型自動運転カンファレンスのチケットでした。このコンテストはゲームのような形式で、参加者は地図上で最適なルートを見つけ、ロボット宅配員を使用して配達を最適化することが求められました。

このテーマについて探求するうちに、ルート探索は解決済みの問題であるにもかかわらず、プロのゲーム開発コミュニティにとって依然として興味深いものであることが分かりました。2010年から2020年までの間に、エンジニアはA*アルゴリズムに大幅な最適化を加え、特に巨大なマップを持つAAAゲームにおいて非常に有益なものとしました。これらの最適化に関する記事や研究論文を読むことは、興奮を覚える経験でした。

さらに、コンテストの要件は、コンテストのテストシステムによるプログラムの出力の容易な評価を可能にするように設計されていました。その結果、視覚化にはあまり重点が置かれていませんでした。

私はこの分野を探求し、グリッド地図上で経験のあるグラフアルゴリズムを使用してルートを見つける小さなアプリケーションを開発することに興味を持ちました。私の発見を視覚化するために、SFMLグラフィックスライブラリを使用しました。

• 「LLMランドグラブ：AWS、Azure、およびGCPがAIを巡って闘っている」
• 「空気圧コンピューティングが重要性を増す」
• 「世界で最も洗練された道路を建設するためのプロジェクトの作業が開始されました」

目標

このプロジェクトは、以前の取り組みの一環として構築されており、四つの有名な経路探索アルゴリズム（BFS、DFS、ダイクストラ、A*）が根本的に異なるものではなく、汎用的に実装できることを示しました。しかし、そのプロジェクトではこれらのアルゴリズムの間に重要なパフォーマンスの違いを示すことは難しかったです。

この記事では、改善されたテストデータを使用して、視覚的に興味深いものを設計することを目指しています。先に述べたヤンデックスのコンテストのタスクは私の目標とよく一致していますが、現在使用できないテストシステムに大きく依存しているため、ここではその特定の問題を解決しません。

代わりに、そのコンテストから入力パラメータの一般的なアイデアを抽出し、独自の実装を作成します。

想像上の世界

未来が久しく訪れた技術的に先進的で革新的な都市を想像してみてください。この都市では、ほとんどの注文が宅配ロボットによって届けられ、カフェから注文を配達することは珍しくなりました。この課題では、効率的な配達ルートを見つけるためにあなたに参加してもらいます。

この都市を N × N の地図と想像してみましょう。単純化のために、各ロボットが正確に1つのセルを占有し、各セルはロボットにとって進行可能かどうかで分類されます。1ステップで、ロボットは上下左右のいずれかの方向に移動することができます（ターゲットセルが空いている場合）。

そして、私の元のタスクの残りを無視しています。テストの開始時に、注文を配送するために使用するロボットの数とその初期座標を出力する必要があります。各ロボットの構築には Costc ルーブルがかかります。

次に、T 回のシミュレーションが行われます。1回のシミュレーションは1分を表し、60秒で構成されます。各イテレーションで、あなたのプログラムには新しい注文の数が与えられ、それに対してプログラムは各ロボットが行うアクションを教えてくれます（ロボットごとに60のアクション）。

正常に配達された注文ごとに、注文の出現から配達までの時間である DeliveryTime を差し引いた max(0, MaxTips – DeliveryTime) ドルのチップを受け取ります。ここで、MaxTips は1つの注文に対する最大チップの数であり、DeliveryTime は秒単位の注文の出現から配達までの時間です。

1つのテストで獲得する総ポイントは TotalTips – R × Costc の計算によって決まります。ここで、TotalTips は獲得した総チップの数、R は使用したロボットの数、Costc は1つのロボットの構築コストです。Costc と MaxTips の値は各テストで設定されます。ロボットの製造に使ったチップよりも少ないチップを獲得した場合、総ポイントは0になります。また、不正なアクションを行った場合もテストで0ポイントを受け取ります。

入力

プログラムは標準入力を使用してパラメータを読み取ります。この方法により、入力ファイルを使用してさまざまな複雑さのテストデータを指定することができます。

入力の最初の行には、3つの自然数が含まれています：N（都市地図のサイズ）、MaxTips（1注文あたりの最大チップの数）、Costc（1つのロボットの構築コスト）。私の最初の実装では MaxTips と Costc のパラメータを無視し、将来的に考慮するかもしれません。

その後、次の N 行のそれぞれには、都市地図を表す N 文字が含まれています。各文字列は2種類の文字で構成される場合があります：

• ‘#’ – 障害物に占有されたセルを示します。
• ‘.’ – 空きスペースを示します。

次に、2つの自然数が与えられます：T と D（T ≤ 100,000、D ≤ 10,000,000）。T は相互作用の回数を表し、D は総注文数を表します。

出力

あなたのタスクは、SFMLグラフィックスライブラリを使用して地図と最適な経路を可視化することです。

地図のモデリング

私はセルのグリッドとして表される地図のファンです。そのため、結果をすべてレンダリングし、セルごとにグリッド上にマップして描画することを好みます。

また、追加のデータ構造を使用せずにグリッド上でパス検索を実行するオプションもあります（学習目的のためにこれも実装しました：コードを参照してください）。

しかし、グリッドのため、マップをある方法または別の方法でグラフとして表現することは簡単です。私はBFS、ダイクストラ、A-Starなどのほとんどのアルゴリズムにセルの隣接リストを使用することを好みます。Bellman-Fordのようなアルゴリズムでは、隣接リストの代わりにエッジリストを使用することは意味があるかもしれません。だから、もしコードベースを探検するなら、それらのすべてが見つかり、それらはすべて動作する例です。

論理と責任を分割するために、私はNavigatorエンティティを持っています。このエンティティは、指示とタスクの構成に従って経路探索を実行する責任を持っています。これはAppConfigファイルと関連するマップファイルを介して指定されます。

App Configは以下のようになります：

注意してください、map_、map__などは実際の設定プロパティではありません。アプリケーションの実行中に無視されます。JSONファイルの一部にコメントを記述する方法がないため、プロパティ名に下線を使用して、設定ファイルに残して使用しないようにしています。

マップファイルは以下のようになります：

25 50 150
#########################
#########################
#########################
###.......#####.......###
###.......#####.......###
###.......#####.......###
###...................###
###.......#####.......###
###.......#####.......###
.......................
######.###########.######
######.###########.######
######.###########.######
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
######.###########.######
#########################
#########################
#########################
#########################
2 4
2
6 6 4 20

これは、ブロックされたセルまたはブロックされていないセルのいずれかを含む最も単純な例の1つです。私は入力パラメータとテストデータのさまざまな例を用意しており、コードのデバッグと学習を可能にする非常に小さな部分から始まり、グラフアルゴリズムのパフォーマンスを測定するための非常に大きなマップ（実在する都市のもの）まで用意しています。

地図を描くにはどうすればいいですか？

地図にブロックされたセルまたはブロックされていないセルのみを含む場合、これは基本的にはグラフのエッジが存在するかどうかを表しています。

グラフ内のパスを見つけるには、効率的に表現する必要があります。前回の投稿で説明したように、関係を持つ隣接リストを使用しました：Vector[ノードID] -> ポイント -> Vector[隣接ノード]

興味深いことに、グリッドを探索するときは、実際にはグラフを使用する必要はありません。エッジについて考えることなく、BFS/DFSアルゴリズムをセルごとに使用してグリッドをトラバースすることができます。_GetPathByBFSOnGridメソッドを参照してください。

最初に、初期化コードはファイルを読み取り、行ごとにグリッドに変換します：

次に、実際のグラフを隣接リストとして作成します：

グリッド表現は、SFMLライブラリを使用して画面に描画するために役立ちます。小さなマップに対しては、幾何学オブジェクトを作成して描画することができます：

または、大きなマップに対して効率的にピクセル単位で描画することもできます：

最後に、ファイルtest_25_xmaxで定義されたマップはどのように見えるかを見てみましょう。

元々、このファイルは以下のように定義されていました：

SFMLでレンダリングされたマップは以下のようになります：

キーボードでユーザーによって制御されるようにしたかったため、ユーザーの動作ロジックはすべてmain.cppに残しました。私はそれを「コントローラー」ロジックと呼ぶのが好きです。

SFMLライブラリを使用すると、キーボードイベントを非常に簡単に処理できます：

メインのアイデアは、ユーザーのトリガー（スペースボタンの押下）がマップファイルを読み込み、マップを表示し、次に2つのポイント間の最短経路を計算することです（スペースボタンの2回目の押下）。

より深く行く必要があります

私はさらに多くのグラフアルゴリズムで遊びたかったのですが、それらにはすべて制限がありますので、マルチカラーマップも実装することにしました。これはマルチウェイトグラフで表現できます。

すべてのセルには色が付けられており、その色はエッジが存在するだけでなく、いくつかのウェイト（または料金、または罰金、なんでも）が適用されることを意味します。つまり、エッジはブロックされているか、半分ブロックされているか、ブロックされていないか…ということです。

したがって、私はより楽しげでゲームに適したマルチカラーマップを実装しました（ファイルtest_31_multi_weight_graph_mapからの例）：

一部の設定ファイルには、実際に存在する都市のより複雑なマップが含まれています。例えば、test_29_yandex_weighten_real_mapです：

新たな課題として、非常に柔軟な構成のマップを扱う必要があります。RectangularMap.cppには、すべてのグラフアルゴリズムや、必要以上のロジックが含まれています（今のところは特に役に立たない場合でも、私は物事を試してみるのが好きです）。

BFS#Line 598、Dijkstra#Line 299、A-Star#Line 356、Bellman-Ford#Line 428のアルゴリズムを実装しました。また、Topological Sort、Single Source Pathなどの追加の「ユーティリティ」アルゴリズムも実装しましたが、現在のアプリケーションの状態では役に立ちません（それらは直接非循環グラフで動作するため、私が現在使用しているグラフの種類ではありません）。しかし、将来の改良で使用するアイデアがあります。

すべてのコードを完璧に磨き上げることはできませんでしたが、コードとパフォーマンスメトリクスを比較しながらコードで遊ぶことができます（そして、私はあなたが同じことができることを願っています）。

コメントアウトされた行や、汚いコードがあるかもしれませんが、それは学ぶ方法です。中身を把握するために、RectangularMap.hを確認することをお勧めします。

また、PgDownボタンやPgUpボタンを押すと、必要な部分を再描画してフォーカスを変更する「フォーカス」機能など、楽しい機能もあります。この機能を改善し、「ズーム」機能を実装するのは非常に簡単です。お好きなら、宿題として取り組んでみてください。

フォーカス機能を使用したマップファイルtest_29_yandex_weighten_real_mapの動作：

クラスのダイアグラムは以下のようになります：

実行して遊ぶ

私はこの小さなアプリケーションを実行し、その構成やアルゴリズムのバリエーションで遊ぶことが最も楽しい部分だと思っています。さまざまなマップファイルを入力パラメータとして使用したり、異なるテストデータで実験したり、コードのロジックを変更したりすることで、多くの実験を行うことができます。

起動後、SPACEキーを押す必要があります。アプリケーションは設定ファイルに基づいてマップを描画し、最も単純なテストケースから最も複雑なものまでを探索することが多くの意味を持つでしょう。

SPACEキーをもう一度押すと、ルーティングアルゴリズムが実行され、開始地点と最も近い注文の間のパスが見つかります。ちなみに、まだ完了していませんが、マップ設定ファイルに利用可能なすべての残りの注文を読み取り、それぞれに対してパス検索を実行することも簡単に実装できます。

以下は、ファイルtest_18_yandex_super_high_resで定義されたマップ上で見つかったルートです：

また、test_29_yandex_weighten_real_mapなどの既存の都市をシミュレートしたマップでも経路を見つけることができます：

BFSのようなアルゴリズムでは、2つの座標間の効率的な経路を見つけることは難しいですが、A-starでは簡単に行うことができます。

マップ設定ファイルで見つかるセルに基づいて、アプリケーションはマップをウェイト付きまたはウェイトなしのグラフとして扱い、それに適したアルゴリズムを選択します（これも簡単に変更できます）。BFSとA-Starのパフォーマンスの違いが簡単にわかります：

最後に

以上で、あなたにこれらのコード例をお任せし、遊んでもらいたいと思います。それを魅力的だと感じ、たくさんの学びを得ていただけることを願っています。

お楽しみに！

リンク

1. BFS、DFS、Dijkstra、A-Starアルゴリズムの汎用実装
2. Steve RabinによるJPS+：A*よりも100倍速い
3. Lucho SuayaによるA*の最適化と改善

We will continue to update VoAGI; if you have any questions or suggestions, please contact us!