この記事では、地元の計画に従って、歩行者が道を外れて芝生を踏みつけ、汚れを広げ、すべての美しさを損なう場所を予測することを可能にするアルゴリズムを検討しました。 アルゴリズムは、変更されたA *と移動中に変更されたナビゲーショングラフの助けを借りて、特定のエリアでの歩行者の動きのシミュレーションでした。
このトピックは、予想外にHabréの訪問者に興味を示しました;コメントの中で、多くは彼らのデータでアルゴリズムを実行しようとする願望を表明しました。 その結果、アルゴリズムをWebサービスの形式で実装しました。 カットの下には、その機能の説明、ステップバイステップの手順、および実装の詳細があります。 サービスとアルゴリズムの動作をテストし、可能な限りプロジェクトでそれを使用するように、私は皆を招待します。
サンクトペテルブルクのStachek Avenueのこのセクションの例で、サービスを適用するプロセスを示します。
このサイト自体は、住宅地を設計する必要がない方法の素晴らしい例です。 レイアウトの失敗は、かつて高速道路を除いて近くに何もなかったという事実が原因である可能性があり、現在は大きな住宅団地があります。 知りません しかし、実際には、それに沿って歩道、横断歩道、歩道の存在がすべて非常に悪いということです。 そして、衛星画像でさえ、芝生を通して広い民俗の道が見えます。 アルゴリズムが実際の状況に似たものを生成するかどうかを見てみましょう。
フロントエンドは私の専門分野ではないことをすぐに認めなければならないので、私は初めていくつかのことをしました。 また、サービス自体はHeroku無料プランで開始され、habraeffectの下にある可能性があります。 悲しいかな、私はまだ通常のホスティングに支払う余分な資金を期待していません。
したがって、マップを描画するには、 http：//antroadplanner.ru/editor/editorにアクセスしてください。
エディターはYandex.Mapsに基づいています。 なぜこのマッピングサービスなのか？ 彼らはまだロシアの地図をより頻繁に、より詳細に更新しているからです。 たとえば、前の記事で言及した勝利公園には、再構築後のビューが更新されていますが、GoogleとOSMのマップはまだ古い計画を描いています。
それでは、地図を描いてみましょう。
右側には、障害物や歩行者ジェネレーターなど、マップにオブジェクトを追加できるツールバーがあります。 APIマップの観点から、各ボタンをクリックすると呼び出しが行われます
currentPoly = new ymaps.Polygon(...) // currentPoly.editor.startDrawing() //
以前は地図を操作していなかったので、編集のしやすさがとても気に入りました。 すべてが頂点と線の操作に関心があり、APIクリック処理が引き継ぎます。 とても快適です。
まず、主な障害物である家と木のグループに印を付けましょう。 人々は、しっかりと立っている幹の間を歩くのは本当に好きではありません。 これには、障害物パネルの「建物」および「植生」ツールを使用します。
次に、道路をマークします。 これは特別な種類の障害です。歩行者は道路に沿って歩くことはありませんが、横断することはできます。
テストの経験が示しているように、「ハイウェイ」と「歩行者の道」の地形タイプの違いが最も戸惑いの原因です。どちらもほとんどの場合アスファルトサーフェスであるためですが、シミュレーションの観点からの意味は根本的に異なります。
- 高速道路は主要な道路の車道です。 歩行者はそれに沿って歩くのではなく、横断するだけです。
- 歩行者用パスとは、歩行者があらゆる方向に歩くことができるすべての場所です。 これは、トラック自体だけでなく、たとえば、クォーター内の私道や駐車場でもあります。
主な障害物をマークアップすると、マップは次のようになります。
次に、トラックと歩道を追加する必要があります。 それとは別に、横断歩道に注意する価値があります-横断歩道は障害物「道路」の隙間によって作られていなければなりません。 それほど便利ではない、はい、しかし今のところ。
トラックを追加した後、歩行者ジェネレーターを追加します-歩行者ジェネレーターがマップ上を移動するすべての場所。 問題のサイトの場合、これは次のようになります。
1）Maxidomストア（右上の最大の建物）、カーディーラー、いくつかの小さな建物の入り口
2）高速道路沿いの2つのトラムとバス停
3）対象ゾーンの外側に続くすべてのトラック。
ジェネレーターは、「大」および「通常」で、シミュレーション中に生成されるトラフィック量が異なります。 この場合の大きなものはMaxidとその周辺の駐車場です。
これが最終的なマップの外観です。 トラックは明るい灰色で、ジェネレーターは茶色でマークされています。
小さなタッチが残ります-シミュレーションゾーンの正確な境界を示します。 これがなければ、非常に賢い歩行者の中には、周囲にマークされた近隣がないことを利用できるものがあります。結局のところ、地図は「オープンフィールド」にあり、関心のある領域の境界を越えて障害物を回避しているようです。 これを行うには、「border」要素を使用します。
カードの準備ができたので、処理のために送信します。 オプションで、結果の通知を受け取るメールを指定できます。
計算
シミュレーションには長時間（最大30分）かかるため、結果はすぐには利用できません。 計算には、 JPPFフレームワークを使用して構築された分散ネットワークが使用されます。 その結果、マップを送信した後、Webサーバーは単純にデータベースにマップを配置し、計算サーバーが使用可能になるまで待機します。 私は時々自宅のマシンでそれを実行していますが、常にそれを維持する方法はありません。
計算サーバーとの接続を確立すると、Webサーバーは彼にタスクの送信を開始し、計算ノードに従って実行を分散し、結果を収集します。
一般に、JPPFは非常に便利なものです。長い計算を必要とするさまざまなプロジェクトで長年使用してきました。バージョン2から始めて、現在は5つあります。 これには、制御サーバー、コンピューティングノード、監視用ツールが含まれますが、最近Androidで動作します（Androidで重い、長く、バッテリーを食べるものを読みたい人はほとんどいません）。 タスクを開始するときにノードの要件を柔軟に構成できます;一般に、分散コンピューティングの同様のソリューションから期待できるすべてが含まれています。 安定性を除いて、何らかの理由で長年にわたって改善されていません。
現時点では、計算ノードを2台のマシンで実行できます。 プロジェクトを支援するために自分のノードを接続することが可能かどうかはすでに尋ねられています。 ここで私はいくつかの困難にあります。 一方では、これに関して技術的に複雑なことは何もありません-アーカイブをオフサイトからダウンロードし、IPサーバーをサーバーの構成に登録して実行するだけです。 一方、サーバーを「エイリアン」タスクの実行から保護する方法はまだわかりません。 外部でアドレスを開くと、だれでも彼にタスクを送信でき、実際にノードでコードをリモートで実行できるためです。 これはおそらく、これらのノードの所有者の観点からはあまり安全ではありません（もちろん、Java仮想マシン、セキュリティマネージャー、すべてですが、だれがそれらを通過できないことを保証できますか？）。
そのため、計算は完了し、その結果はレターのリンク、またはサイトのヘッダーのフォームにカードIDを入力することで確認できます。
そして、私たちが見ているもの：しかし、私たちは衛星画像とほぼ同じように見えます。 このプログラムは、人々が実際にマクシドマの方向に停留所から歩いて行きたいこと、高速道路に沿って走っている十分な歩道がなく、人々が大きな芝生に沿って歩いていることを示しました（この経路は、Yandexマップでも見ることができますが、詳しく見る必要があります）。
まあ、人々は直角に曲がりたくない！ したがって、バス停からの人々は、斜めに、ゴールに向かって行く傾向があります。 アルゴリズムによって生成された計画と実際の衛星画像の両方で完全に見えるもの。
もちろん、結果は完璧ではありません。 これは、私たちがマークしたマップの不正確さによって決まります（1つの独立したツリーの位置でさえ、パスの画像を著しく変更することがあります）、一部-人間性の謎とコンピューターモデルの不完全な対応。 したがって、アルゴリズムが示唆する場所を正確に追跡するつもりはありません。 しかし今では、レイアウトの問題を検出するための強力なツールとして機能します。
おわりに
これで、Webサービスが完了しました。テストと使用に興味があるすべての人を招待します。 インターフェイスとアルゴリズムの両方の面でまだ多くの作業がありますが、この形式でもデザイナーに典型的な間違いを犯さないように警告できることを願っています。
より最新の更新されたチュートリアルは、 http：//blog.antroadplanner.ru/で入手できます。
サービスの更新、仕事の例、改善のテーマに関するあらゆる種類の考えについて書いているブログ：
https://blog.antroadplanner.ru
UPD 1： 「マップが接続されていません」というエラーが表示される場合：マップの境界線を手動で描画しない場合、ジオメトリ全体の境界ボックスが境界線として使用されます。 さらに、マップ全体に長い建物がある場合、BBはエッジに沿って構築され、マップは2つの無関係な領域に分割されます。 したがって、常に境界線を描画し、この場合はエッジに沿ってギャップを残すことをお勧めします。
UPD 2：建物を手動でセットアップするのが面倒な人には、OSMからのデータのインポートを使用できます。 これを行うには、OSMカードのフラグメントをGeoJSON形式に変換し（たとえば、JOSMツールを使用して）、エディターにロードする必要があります。 確かに、このようなマップは手動で調整する必要があります。OSMでは道路には太さがなく、ポリゴンではなく線で定義されているため、歩行者ジェネレーターと正しい道路を配置する必要があります。
OSMデータから派生した大きく複雑なマップの例を次に示します。
