勾配を考慮した経路探索のためのグラフ構築
山岳地形向け経路探索のためのグラフ作成のアイデアとその手法です。もっともらしい経路探索の結果のためには元となるグラフの構造が重要になります。 地形メッシュをグラフとして利用する まずはもともとのメッシュを加工してグラフを
道路
道路と交差点
シンプルな道路メッシュ生成についてのメモ。 ネットワーク 道路がつながった状態のポリラインを作成する。交差点はポイントを共有した状態にする。 始点と終点以外のポイントを削除した状態にして、交差点ポイントにはつながるポリラ
道路ネットワークの生成
地形メッシュ上に集落のポイントを置き、それらをつないだ道路のネットワークを生成します。部分的に「集落と街道の生成」という論文を参考にしています。 アルゴリズムの流れ 集落をノード、道をリンクとしたネットワークモデルとして
FindShortestPath SOP
勾配コストやターンコストを追加して、勾配を考慮した経路を探索する。 事前にメッシュをConvertline SOPでポリラインのグラフ構造に変換しておき、Wrangleノードをつないで、勾配コストとターンコストを設定する
最短経路探索（勾配コスト）
A-Starアルゴリズムをベースに、勾配コストを追加したアルゴリズム。 Input0にConvertline SOPでポリライン化した地形を、Input1に始点と終点を含むポリラインを差す。 ポイントから隣接するエッジか
最短経路探索（A-Starアルゴリズム）
ダイクストラ法との違いはヒューリスティックコストという推測値を利用して、ゴールに近いポイント順に処理をしていき、ゴールにたどり着いた時点で計算を止めるので、すべてを計算してしまうダイクストラに比べるとコストが低くなる。
最短経路探索（ダイクストラ法）
Input0にConvertline SOPでポリライン化した地形を、Input1に始点と終点を含むポリラインを差す。 ポイントから隣接するエッジからの情報を格納する。 Python SOPでダイクストラ法の経路探索を記
