私たちの都市のすべての居住者によく知っていると思います。 永遠に踏みつけられた芝生は、雨が降るたびに泥沼に変わり、それを介して歩行者は私道を歩み続けます。 汚れた服と泥をアスファルトの上に乗せます。
明らかに、ここの人々は一般的に非難されるべきではありません、それは私たちの性質です-常に最短経路を探します。 そして、公共の領域のレイアウトがこの願望を満たすならば、それは素晴らしいでしょう。 しかし、これはそうではありません。建築家とプランナーは、定規に沿って、交差点が直角になり、歩道を可能な限り描き、歩行者は可能な限りこれらの角を切り、草を踏みつけ、土を広げます。
私はかつて小道を歩いて、引きずり回さなければならないか、靴を汚さなければならないという事実についてだらだらと考えました。 「愚か者がこれを設計している」などのinりで、思考は、ある科学都市についてかつて聞いた話にスムーズに流れました。そこでは、中庭の道は最初はまったく作られていませんでしたが、人々が踏んだ道を舗装し、住民にとって便利なルートのネットワークを得ました。 そしてそこから、思考は「なぜ同じことをするのではなく、コンピューターで行うのか」という考えに移行しました。 与えられた地図に従って、人々が芝生を踏みつける場所とアスファルトを作るのが良い場所を予測するプログラムを開発するには？
Under the cut-アルゴリズムの説明と、実際のピーターズバーグヤードでのその作業のいくつかの例。
まず、造園を担当する地方自治体が芝生の上を歩く問題とどの程度一般的に闘っているのかを検討します。
オプション1：フェンスを設置する
ほとんどの場合、非効率的な方法です。 フェンスは遅かれ早かれ壊れます。 下の写真では、彼らはそれを何度も壊し、それを何度も掛けて、無駄なお金を捨てました。
オプション2：エラーを認めて修正する
はい、それも起こります。 この点で、私はモスコフスキー・プロスペクト周辺の庭が好きです-そこで彼らは道を通常の道に変えました、そして誰も芝生の上を歩きません-単にそれの必要はありません。 しかし、それはすべて地元当局の熱意にかかっています-誰かが、誰かが購読を解除し、お金があれば5年以内に行うことを約束し、ほとんどの場合、彼らは最初の方法に従って戦おうとします。
3番目のオプションがあります：設計段階で問題を予測して修正する
正直なところ、私はデザイナーや開発者がこれのために何をしているのか分かりません。 私が見たスキームから判断すると-何も、彼らは審美的な考慮だけによって導かれるすべてを彫刻します。 コメントで、この分野での経験を持つ人が何かを伝えることができたら嬉しいです。
このオプションに従事します。
問題の声明
では、何がありますか？ そして、私たちがいるエリアの地図があります：
- さまざまな程度のクロスカントリー能力と歩行者（小道、芝生）に対する魅力を備えた土地区画
- 障害物（家、フェンス）
- 歩行者が移動する場所-ポーチ、屋台、ベンチ-何でも。 それらは歩行者発電機と呼ばれます
歩行者が芝生のどこを歩くかを正確に予測する必要があります。そのため、これに基づいて、パスの代わりに通常の道路を作成することを決定できます。
解決策として通常最初に思い浮かぶ2つのエッジケースにすぐに注目します。 最初のグラフは完全なグラフです。つまり、各発電機を使用して各発電機を接続し、道路を直線状に舗装します。 簡単に言うと、もちろん歩行者にとっては便利ですが、最終的には庭全体がアスファルトになり、高価で見た目が悪くなります。 2番目のケースは、グラフの最小スパニングツリーであり、その頂点がジェネレーターになります。 残念ながら、人々はまだロボットではなく、最小のスパニングツリーを歩きません。これは、人間の軌跡システムの進化のモデリングの研究者によって示されました（D. Helbing、J。Keltsch、P。Molnar）。次の画像を提供します。
完全なパスのシステムは左側に示され、上記の作業からの実験の結果として得られた示されたポイント間のパスのシステムは右側に示されています。 完全なツリーでもスパニングツリーでもないことがわかります。
歩行者の交通シミュレーションをテーマにした記事の考察と研究の結果、次のアルゴリズムが発明され、実装されました。
アルゴリズム
準備。
対象地域の地図がGeoJSON形式で表示されます。 歩行者用発電機と地形パッチには、手動でマークが付けられています。
初期化。 マップに基づいて、ナビゲーショングラフG（V、E）が構築されます。 グラフVの頂点は多くの地形ポイントです。 このペーパーでは、このセットを構築する最も簡単な方法が選択されています。長方形のグリッドがマップに重ねられ、そのノードがグラフの頂点になります。 人が2つの隣接するグリッドノード間を通過できる場合、そのようなノードはセットEを構成するエッジで接続されます。 各エッジeの初期ウェイトは、2つのコンポーネントの差の形式で表されます。地形のタイプによって決定される固定Wconst（e）と、以下では踏みつけと呼ばれる変数Wvar（e）です。 最初はゼロです。 一部の地形タイプ（ハードコートトラック）には、可変コンポーネントがない場合があります。
踏みつけは、下からゼロ（手つかずの芝生）に制限され、最も上に踏みつけられたパスでさえ、同様のパスよりもわずかに魅力的でないように、選択された数Wmaxによって制限されます。
さらに、歩行者pごとに良識係数k（p）が導入されます。 この係数は、歩行者のさまざまなカテゴリをシミュレートするために使用されます。両方の「まともな」歩行者は、たとえ合計距離がはるかに大きくなる場合でも常にパスに沿って歩くことを好みます。 歩行者pのエッジeの重みW（e、p）を計算する式の形式は次のとおりです。
この場合、 k（p）> 1の値では、式でのWvarコンポーネントの役割がより高くなるため、特定の歩行者の短い直線経路は非常に魅力的です。 k <1の場合、「まともな」歩行者が得られ、歩行者はより頻繁に線路に沿って歩こうとします。
シミュレーション
P人の歩行者は発電機に均等に分布しています。 それらの目標は、他のジェネレーターのリストからランダムに選択されます。 良識係数k（p）は、次のように選択されます。
ここで、 Kbadは不正な歩行者の義務的な割合です（アルゴリズムの収束を加速するために、社会では常に最も直接的で短い方法で旅行したい人の特定の割合があると仮定します）、 Nは正規分布です。 係数の値は経験的に選択され、 Kbadの場合は値0.1が選択されます。
シミュレーションの各ステップで、次のアクションが実行されます。
1）歩行者は、特定の速度に応じて特定の距離を移動します。
2）歩行者が通過したグラフのエッジのトランプルは、通過した各歩行者に対して固定値∆Wpedだけ増加します。
3）目標を達成した歩行者は新しいものに置き換えられます。
4）グラフのすべてのエッジのトランプルは 、固定値∆Wtime （時間とともに過成長）減少します。
したがって、シミュレーションステップiの後のエッジeのトランプルの合計変化は次のようになります。
ここで、 Pcount（e、i）は、ステップiでエッジeに沿って歩いた歩行者の数です。
歩行者はA *アルゴリズムを使用して経路を直線化するためのヒューリスティックを使用してルートを作成します（私はもともと平凡なダイクストラを使用しましたが、長方形のグリッドでは不自然に見える経路を生成するのが好きです）。 シミュレーションは、収束するまで、パスマップの変更が停止するまで、または指定された数のステップまで継続します。 シミュレーションの完了後、踏みつけの分布を示すマップには、歩行者が最も頻繁にトラックから地面に降りるエリアが表示され、ハードサーフェスで舗装する必要があります。
作業例
仕事の例として、このプログラムを作成するように促した中庭を引用します。 これは、サンクトペテルブルクのガガーリン通りにある住宅の近所で、私が以前住んでいた場所で、私は定期的に呪われていました。 実際には、フェンスがリボンで結ばれている私の階段の写真があります。そのため、プランナーや建築家の顔写真の知り合いが通りから始まりました。
これは、この家が衛星からどのように見えるかです。 家の中央、その左と右にある-パネル5階建ての建物。 右側には、家と障害物の概要を示すエリアのマーク付きマップがあります。
残念なことに、障害物の規模と形状は非常に近似しています。私に知られている写真サービスにはこの庭の詳細な計画が含まれておらず、衛星画像は十分に詳細ではないためです。
シミュレーションの結果、数百回の反復の後、そのような絵が描かれました。 プログラムによってマークされたブラックポイントは、芝生の踏みつけを予測しました。
比較のため、番号付きセクションに対応する現実の写真：
家の隅に斜めに1つのパス
2-家全体に沿ってトレイル
3-記事の冒頭からの写真、入り口からの道
一般に、プログラムの予測は非常に正確であることがわかります。
例2
さて、私は少しcheしましたが、この庭で、現実に近いバージョンを取得するようにアルゴリズムのパラメーターを調整しました。 主に歩行者の行動に関連するパラメーター-移動速度、歩道の過成長率、歩行者数など
これと他のいくつかの近隣のヤードのパラメーターを調整して、私はデザインの愚かさのもう一つの目立った例を取り上げました-ビクトリーパーク。 数年前、特に何らかの理由で、この公園は再開発され、家から地下鉄駅まで公園を通る便利な広い道路ではなく、巨大な丸い芝生を作り、道路を回らせました。
したがって、プログラムの予測：
そして実際の衛星画像（もちろん、せっかちな芝生のせっかちな市民は踏みにじられて、宇宙からも明らかになった）：
もちろん、この写真には小さなパスは表示されていませんが、実際には存在します（実際、予測されたプログラムよりも多くのパスがありますが、一般に構成は非常に似ており、十分な写真がありますが、ここではそれらをアップロードしません。バスト）。 特定の矛盾は、地図の不正確さによるものです-まだ公開されていない元の記事を書いている時点で、すべての地図サービスでは、再構築後に公園の新しい地図はありませんでした、それはメモリとスケッチから描く必要がありました。
結論
そして、結論は非常に簡単です。 どういうわけか中庭の設計に従事しているようなツールを導入することが可能であった場合-生活が良くなり、草がより緑になります。 私自身は最近、サンクトペテルブルクの新しい現代の小地区である「バルト海の真珠」に引っ越しました。中庭の通路がどのように作られているかを見ると、頭をつかんでいます。 おそらく衛星からは美しく見えますが、完全に機能していません。 記事の最初の写真はそこからです。 地元当局への申し立ての送信は役に立たない-正式にはその地域はまだ市に移転されておらず、誰も責任を負わない。 最初から正しく行う必要がありました。
しかし、私はコードを書くのが好きで、後で誰にもそれを課したくないので、この状況で何かができるかどうか、もしそうなら、どうすればいいのかわかりません。 habrazhitelの誰かがプロンプトを表示できますか？
UPD：コメントでは、コードとデータで実行する機能について尋ねます。 実装はむしろ概念実証の一種であり、それほどフレンドリーではないインターフェースを備えています。 このトピックは興味をそそるので、私はそれをもう少し人間的な形で完成させ、少し後で投稿します。
UPD 2：完了、アプリケーションはantroadplanner.ruで利用可能ですフロントエンドは私の専門ではないので、使いやすさは両方の足で足を引きずっています。 しかし、あなたはあなたのデータを運転することができます。