こんにちは友人！

任意のグラフ上でパス検索のライブラリを作成しました 。 それをあなたと共有したいと思います 。

巨大なグラフでの使用例：

ここでデモを試すことができます。

ライブラリは、 NBA*と呼ばれるあまり知られていないバージョンのA*検索を使用します。 これは双方向の検索であり、ヒューリスティック関数の要件が緩和されており、非常に積極的な終了基準があります。 その曖昧さにもかかわらず、このアルゴリズムは最適なソリューションに対して優れた収束率を持っています。

さまざまなオプションの説明A*ハブで複数回会った この記事では繰り返し説明しないので、私はこれが本当に好きでした。 猫の下で、ライブラリがすぐに機能する理由とデモの作成方法について詳しく説明します。

ライブラリが高速なのはなぜですか？

「どういうわけかそんなに早く信じられない。前もって何も数えないのは間違いない？」
最初に図書館を見た友人の反応。

私はすぐに認めなければなりません、私の実装が可能な限り速いとは思いません。 それが置かれている環境（ブラウザ、javascript）を考慮すると、十分に高速に動作します。 その速度はグラフのサイズに大きく依存します。 そしてもちろん、現在リポジトリにあるものを加速して改善することができます。

統計

パフォーマンスを測定するために、ニューヨークからの道路のグラフを作成しました（約730 000リブ、 260 000ノット）。 以下の表は、ランダムに選択された250からパスを見つける1つのタスクを解決するために必要な時間の統計を示しています。

各アルゴリズムは同じ問題を解決しました。 A* は最速ですが、彼のソリューションは常に最適とは限りません。 基本的に、これは双方向のA*であり、両方の検索が一致するとすぐに終了します。 NBA*双方向、最適なソリューションに収束します。 99% 、最短パス（p99）を見つけるのに172ミリ秒もかかりませんでした。

最適化

ライブラリはいくつかの理由で比較的高速です。

まず、 優先度キューのデータ構造を変更して、キュー内の要素の優先度の更新にO(lg n)時間かかるようにしました。 これは、キューの再構築中に各要素がヒープ上の位置を追跡するという事実によって実現されます。

次に、ストレステスト中に、ガベージコレクションにかなりの時間がかかることに気付きました。 アルゴリズムがグラフを回るときに多くの小さなオブジェクトを作成するため、これは驚くことではありません。 オブジェクトのプールを使用して、ガベージコレクターの問題を解決します 。 これは、不要になったオブジェクトを再利用できるデータ構造です。

そして最後に、 NBA*検索アルゴリズムには、サイトを訪問するための非常に美しく厳しい基準があります。

率直に言って、これは完璧の限界ではないと思います。 ボリスが説明した階層的なアプローチを使用すると、さらに大きなグラフの時間を短縮できる可能性があります。

デモはどのように機能しますか？

もちろん、ライブラリの作成は非常に興味深いものです。 しかし、このデモプロジェクトには別の説明が必要だと思います。 私はいくつかの教訓を学びましたが、これが役立つことを期待して、皆さんと共有したいと思います。

始める前に。 誰かが私に尋ねました：「しかしこれはグラフですか？マップをグラフとしてどのように表現できますか？」 各交差点をグラフノードとして考えるのが最も簡単です。 各交差点には位置(x, y)ます。 道路の各直線区間をグラフの端にします。 道路の曲がりは、交差点の特殊なケースとしてモデル化できます。

データの準備

もちろん、 https：//www.openstreetmap.orgについて聞いたことがありますが、その外観は私にとってあまり魅力的ではありませんでした。 http://overpass-turbo.eu/のようなAPIとツールを発見したとき、これが私の目の前に新しい世界が開かれた方法です:)。 彼らはODbLライセンスの下でデータを提供します。これには、言及する必要があります（サービスについて多くの人が知っているほど、サービスは良くなります）。

APIを使用すると、非常に複雑なクエリを作成でき、驚くべき量の情報を提供できます。

たとえば、このようなクエリはモスクワのすべての自転車道路を提供します。

 [out:json]; //     `a` (area["name"=""])->.a; //     a    `highway == cycleway` way["highway"="cycleway"](area.a); //       (  ) node(w); // ,   out meta; 

APIの詳細については、 http ： //wiki.openstreetmap.org/wiki/Overpass_APIをご覧ください。

都市への道路の取得を自動化する3つの小さなスクリプトを作成し、グラフ形式に保存しました。

グラフを保存

OSMはXMLまたはJSONとしてデータを送信します。 残念ながら、両方の形式は大きすぎます-すべての道路を含むモスクワの地図には約47MBます。 私の仕事は、（モバイル接続であっても）できるだけ早くサイトをロードすることでした。

gzip 'ohmの圧縮を試みることができます-47MBのモスクワのマップは7.1MBになります。 しかし、このアプローチでは、データの解凍速度を制御することはできません。クライアント上のJavaScriptで解析する必要があり、初期化速度にも影響します。

グラフ用に独自の形式を作成することにしました。 グラフは2つのバイナリファイルに分割されます。 1つはすべての頂点の座標を持ち、2つ目はすべてのエッジの説明を持ちます。

座標を持つファイルは、 x, yペア（int32、座標ごとに4バイト）のシーケンスです。 座標のペアが位置するオフセット。頂点の識別子（ nodeId ）とnodeIdます。

グラフのエッジはfromNodeId, toNodeIdのペアの通常のシーケンスにfromNodeId, toNodeIdます。

図のシーケンスは、最初のノードが2番目を参照し、2番目が3番目を参照することを意味します。

VノードとEエッジを持つグラフの合計サイズは、次のように計算できます。

  storage_size = V * 4 * 2 + # 4       E * 4 * 2 = # 4      (V + E) * 8 # ,   

これは最も効率的な圧縮方法ではありませんが、実装が非常に簡単で、クライアントの初期グラフを非常に迅速に復元できます。 javascript'eの型付き配列は、JSON'aを解析するよりも速く動作します。

最初は、エッジの重みを追加したかったのですが、小さなグラフであっても、弱いモバイル接続での読み込みはさらに遅くなるため、自分自身を止めました。

最初に携帯電話

デモを書いたとき、私は彼について彼にTwitterで投稿すると思いました。 ほとんどの人は携帯電話からTwitterを読むため、デモは主に携帯電話向けに設計する必要があります。 すぐにロードされない場合、またはタッチをサポートしない場合-書き込みは行われません。

発表の数日後、上記の論理が正当化されたことを認識することができます。 デモの発表を伴うツイートは、私のツイッターの中で最も人気のあるツイートになりました。

主にiPhoneおよびAndroidプラットフォームでデモをテストしました。 Androidでのテストでは、最も安い電話を見つけて使用しました。 これは、小さな画面でのパフォーマンスと使いやすさのデバッグに大いに役立ちました。

非同期性

デモで最も遅い部分は、サイトの最初の読み込みでした。 グラフを初期化したコードは次のようになりました。

 for (let i = 0; i < points.length; i += 2) { let nodeId = Math.floor(i / 2); let x = points[i + 0]; let y = points[i + 1]; // graph  https://github.com/anvaka/ngraph.graph graph.addNode(nodeId, { x, y }) } 

一見-何も間違っていません。 ただし、これを弱いプロセッサと大きなグラフで実行すると、メインスレッドが反復処理を実行している間にページが無効になります。

ウェイアウト？ 一部のユーザーはWeb Workersを使用しています。 すべてがマルチコアになったことを考えると、これは素晴らしいソリューションです。 しかし、私の場合、Webワーカーを使用すると、デモの作成にかかる時間が大幅に延長されます。 ストリーム間でデータを転送する方法、同期する方法、バッテリー寿命を節約する方法、Webワーカーが利用できない場合の対処方法などを考慮する必要があります。

もっと時間をかけたくなかったので、もっと怠decisionな決断が必要でした。 ループを壊すことにしました。 しばらく実行して、経過した時間を確認し、 setTimeout()を呼び出して、イベントループの次の反復で続行します。 これらはすべて、 raforライブラリで行われます。

このソリューションを使用すると、ブラウザは内部で何が起こっているかを常にユーザーに通知することができます。

描画

グラフが読み込まれたので、画面に表示する必要があります。 もちろん、SVGを使用して100万個の要素をレンダリングするのはよくありません。最初の1万個を超えると速度が低下し始めます。 グラフをタイルに分割し、 リーフレットまたはOpenSeadragonを使用して大きな絵を描くことができます。

コードをより詳細に制御したい（そしてWebGLを学ぶ）ために、WebGLレンダラーをゼロから作成しました。 そこで、「シーングラフ」アプローチを使用します。 このアプローチでは、描画可能な要素の階層からシーンを構築します。 フレームのレンダリング中に、グラフを調べて、各ノードに変換を蓄積したり、画面に表示したりする機会を与えます。 three.jsまたは通常のDOMに精通している場合、このアプローチは新しいものではありません。

レンダラーはここで入手できますが、私は意図的にそれを文書化しませんでした。 これは私自身のトレーニングのためのプロジェクトであり、使用できるという印象を与えたくありません:)

バッテリー

最初は、各フレームでシーンを再描画しました。 すぐに、これにより電話が大幅に暖まり、バッテリーが驚くべき速度でゼロになることがわかりました。

これらの条件下でコードを書くことは、同様に不便でした。 このプロジェクトに取り組むために、私はいつも空き時間にコーヒーショップに座っていました。 したがって、私はより速く考えることを学ぶか、ラップトップをそれほど速く着陸させない方法を見つけなければなりませんでした。

2番目のオプションを選択したため、より速く考える方法をまだ見つけていません。 ソリューションは単純なものであることが判明しました。

すべてのフレームにシーンを描画しないでください。 尋ねられた場合、または変更されたことがわかっている場合にのみ描画します。

今ではあまりにも明白に見えるかもしれませんが、最初はそうではありませんでした。 結局のところ、基本的にWebGLを使用するすべての例は、単純なループを説明しています。

 function frame() { requestAnimationFrame(frame); //    renderScene(); //   . //     ,        } 

「保守的な」アプローチでは、 requestAnimationFrame() frame()関数から取り出す必要がありました。

 let frameToken = 0; function renderFrame() { if (!frameToken) frameToken = requestAnimationFrame(frame); } function frame() { frameToken = 0; renderScene(); } 

このアプローチにより、誰でも次のフレームの描画を要求できます。 たとえば、ユーザーがマップをドラッグして変換マトリックスを変更すると、 renderFrame() 。

frameToken変数は、フレーム間でrequestAnimationFrame再度呼び出すことを回避するのに役立ちます。

はい、コードを書くのが少し難しくなっていますが、バッテリー寿命は私にとってより重要でした。

テキストと行

WebGLは世界で最も簡単なAPIではありません。 テキストと太い線（幅が1ピクセルより大きい）を扱うのは特に困難です。

私はこのビジネスに完全に慣れていないので、テキスト/行のサポートを追加するとかなり時間がかかることにすぐに気付きました。

一方、テキストからは、ラベルAとBいくつか描画するだけで済みましA B そして太い線の-2つのピークを接続するパスのみ。 このタスクはDOM'aにかなり対応しています。

ご存知のとおり、レンダラーはシーングラフを使用します。 現在の変換を... SVG要素に適用することがタスクであるシーンに別の要素を追加してみませんか？ このSVG要素を透明にして、キャンバスの上に配置しましょう。 マウスからすべてのイベントを削除するには、 pointer-events: none;設定しpointer-events: none; 。

それは非常に迅速かつ怒って判明しました 。

マップ内を移動する

ナビゲーションを通常のマップの動作のようにしたかった（たとえば、Googleマップのように）。

SVG用に作成されたナビゲーションライブラリanvaka / panzoomをすでに持っていました。 タッチと動的減衰をサポートしました（慣性によりカードが動き続ける場合）。 WebGLをサポートするために、ライブラリを少し調整する必要がありました。

panzoomはユーザーからのイベント（ mousedown 、 touchstartなど）をtouchstartし、変換マトリックスにスムーズな変換を適用し、SVGを直接操作する代わりに、マトリックスを「コントローラー」に渡します。 コントローラーのタスクは、変換を適用することです。 コントローラーは、SVG、DOM、またはWebGLシーンに変換を適用する独自のコントローラーである場合があります。

クリックされたものを理解する方法は？

グラフをロードする方法、グラフを描画する方法、およびグラフ内を移動する方法について説明しました。 しかし、ユーザーがグラフに触れたときに押されたものをどのように理解するのですか？ 道を開く場所と場所

ユーザーがマップをクリックすると、グラフ内のすべてのポイントを簡単に回って、その位置を見て、最も近いポイントを見つけることができます。 実際、これは数千ポイントにとって素晴らしい方法です。 ポイントの数が数万/数十万を超える場合、生産性は許容できません。

インデックスツリーにクアッドツリーを使用しました。 ツリーが作成された後-最近傍の検索速度は対数になります。

ところで、「クワッドツリー」という用語が威圧的に聞こえる場合は、動揺しないでください。 実際、四分木は通常の二分木に非常によく似ています。 それらは学習しやすく、実装しやすく、適用しやすいです。

特に、自分の実装であるyaqt libraryを使用しました。これは、データ形式のためにメモリ内で気取らないからです。 適切なドキュメントとコミュニティ（ d3-quadtreeなど ）を備えた、より良い代替手段があります。

方法を探しています

これで、すべての部品が配置されました。 グラフがあり、グラフの描画方法、クリックされたものがわかります。 最短経路を見つけることだけが残っています。

 // pathfinder   https://github.com/anvaka/ngraph.path let path = pathFinder.find(fromId, toId); 

これで、見つかったパス上にある頂点の配列ができました。

おわりに

グラフとショートカットの世界へのこの短い旅行を楽しんだことを願っています。 ライブラリが役に立つかどうか、またはライブラリを改善するためのヒントがあれば教えてください。

よろしくお願いします！
アンドレイ。