#topicpath

// 翻訳元:
// 翻訳元ページへのリンクを書いてください
//
// 翻訳元 Rev.:
// 英語版Wikiの場合、翻訳元のリビジョンのリンク
// View History から翻訳時の最新更新の日付時刻リンク先の
// ページリンクを書いてください
//
// 最終更新バージョン:
// このページが対応している DF のバージョンを書いてください

|~翻訳元|[[DF2014:Path - Dwarf Fortress Wiki>http://dwarffortresswiki.org/index.php/DF2014:Path]]|
|~翻訳元 Rev.|[[Revision as of 22:22, 14 August 2015 by 79.200.87.130>http://dwarffortresswiki.org/index.php?title=DF2014:Path&oldid=220206]]|
|~最終更新バージョン|0.40.24|

'''Path - 経路, 通り道'''


''Pathing'' (経路指定, 経路探索) は、AI が点 A - B 間のルートとして選択する経路についての概念で、いわゆるビデオゲームでは頻繁に活用されています。

[[要塞の設計>Workshop design]] や [[安全性の設計>Security design]] にとっては重要な関係があります。
[[工房の配置>Workshop design]] や [[保安設計>Security design]] にとっては重要な関係があります。


* 目次 [#f7497931]

#contents


* Implications [#e5f34a08]
* 経路探索とは [#k2a51662]

&color(red){''未翻訳''};

Dwarf Fortress では、2点間の適切な経路を素早く計算する改良版の A* (A-star, エースター) 探索アルゴリズム ([[デモ>http://qiao.github.io/PathFinding.js/visual/]]) ([[ソース>http://www.gamasutra.com/view/feature/131954/interview_the_making_of_dwarf_.php?page=8]]) を利用しています。~
A* 探索アルゴリズムは点Aを取り、そこから点Bに到達しうる適切な経路を計算します。~
この経路は必ずしも最速ルートとは限りません。~
事実、Dwarf Fortress のように環境が複雑かつ流動的なゲームでは、最速ルートが選択されることは滅多にありません。~
このアルゴリズムの目的と有用性は処理能力をそれほど占めることなく経路を発見し、速度と計算可能性のバランスをとることにあります。~
~
素材への経路探索にはいわゆる[[マンハッタン距離>https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%B3%E3%83%8F%E3%83%83%E3%82%BF%E3%83%B3%E8%B7%9D%E9%9B%A2]]を利用しています。~
つまり素材は実際の経路探索に代わり、ドワーフの現在地からの距離をチェックされます。~
従って、何かを建築するときは利用可能な素材は近いものから順に並べられます。
しかし、これは道中の壁や障害物を無視したものです。~
要塞設計において重要な点は可能な限り開けた要塞にすること、出入り口を増やして最速経路を多く作る (パフォーマンスを向上する)こと、マンハッタン距離と実経路の乖離を避けることです。~
[[Workshop]] での作業では利用可能かつ最も近い素材が自動的に選ばれますが、建設に際してはどの素材を使うかを指定することができます。~

* Applications [#qaffb151]
* 応用 [#a683877b]

&color(red){''未翻訳''};

以下の例では "A" は生物、"B" は目的地を指します。~
&color(grey){(訳注： A も B も出てこない。原文の修正ミスか)};~
~
Workshop での作業では最も近くにある利用可能な素材が使用されます。~
経路探索を有効活用する簡単な方法は、使用したい素材のみを受け入れる [[Stockpile]] で Workshop を囲むことです。~
過去のバージョンでは、これが [[Magma]] に対して使うものに Magma-safe 素材を確実に使用する唯一の方法であり、特定のジョブを特定の方法で実行させる唯一の方法でした。~
現在では Stockpile のリンク設定を代用すればもっと簡単に同じことができます。~
それでも、なぜ [[Gem Setter]] が家具置き場の [[Bed]] ではなく隣の部屋の [[Mason's workshop]] にある平民用の Coffin を装飾しようとするのか、その理由を理解しきっていない段階なら有用でしょう。~
~
要塞を設計するにあたり、経路探索の仕組みを知っておかなければなりません。~
~
保安設計においてはもう少し徹底した結果をもたらします。~
敵対生物や用を実行しているドワーフは経路を選択する際マップ全域を検討することができ、A* 探索アルゴリズムの下では (選択肢の範囲内で) 常に最短経路を通ることになります。~
このことから Trade depot を目指すキャラバンと要塞内部への最短経路を取ろうとする [[Goblin]] [[Siege]] とを隔離することができます。~
この挙動を利用した Exploit の一例を下に挙げます。~
~
&color(grey){訳注：英語Wikiでは画像が挿入されていますが、日本語Wikiへの転載は避け、テキストで模式図を作成しました。};~
~
キャラバンは Trade depot がそちらにあるため常に上側、遮るもののないつづら折れの道を通り、侵入者たちはより短距離な罠満載の下側通路を進みます。~
(注意：左の跳ね橋が上がっている場合、商人用通路が最短経路となるため侵入者はそちらを通ります)~

 例.
       WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
       WW.......W.......W.......W.......W     W = 壁
       WW.......W.......W.......W.......W     . = 床
       WW.......W.......W.......W.......W     ^ = 罠
       WW...W...W...W...W...W...W...W...W     * = 跳ね上げ橋
       WW...W.......W...W...W...W...W...W
       WW...W.O   O.W...W...W...W...W...W
       .....W.     .W...W...W...W...W...W
 中 <- .....W.  O  .W...W...W...W...W...W
       .....W.     .W.......W.......W...W
       WW...W.O   O.W.......W.......W...W
       WW***W.......W.......W.......W...W
       WW***WWWWWWWWWWWWWWWWWWWWWWWWW...WWWWW
       WW......................^^^^^^........
       WW......................^^^^^^........ -> 外
       WW......................^^^^^^........
       WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW

* Other dwarves [#z43e074c]

ドワーフを始めとした実体を持つもの同士が、ひとつのタイル上を同時に移動してすれ違うことは可能です。しかしこのように移動するのは非常に動作が遅くなり、ドワーフは相手を避けられるよう別の経路を探そうとします。このことは要塞の設計において重要な検討材料となります。
** 経路の計算 [#bd12a4e0]

1人のドワーフが通行中の 1 タイル幅の長い通路があったとして、反対側から歩いてきた別のドワーフは他の経路を選ぶことで衝突を避けようとします。この通路が長く、近くに代わりになるルートもない場合、ドワーフの経路探索の負荷をたいへん著しく高めてしまう可能性があります。

この理由により、往来の量が多い通路では最低でも 2 タイル幅を確保しておくのがベストです。同様にドアや階段も単一で設置することは避けます。こうすることでドワーフ同士がすれ違うときに迂回するルートを探す必要がなくなり、始めにみつけていた最短経路を変更することなく通行できるようになります。
各タイルには値が設定されており、この値は複数の要因により決定されます。~
アイテムまでの距離と Traffic value &color(grey){(訳注：Traffic cost 設定とは別の値か)}; です。~
したがって計算過程は以下のようになります。~

+目的地に隣接する全タイルを確認し、値をつける
+目的地からドワーフに達するまで通行可能な全タイルを繰り返しチェックしていく
+ドワーフ側から値の最も低いタイルを選んでいき、経路が決定される
+ドワーフが経路を辿って目的地へ向かう

さまようもの (動物とかうろつく侵入者など) は上記の方式にランダムな移動を組み合わせたものを適用されます。~
~
移動するものを追いかける必要がある作業においては、この方式を何度も使うか別のアルゴリズムを利用します。~
~
加えて以下の派生があるものと思われますが、未検証です。~

-ドワーフは以前の作業で使用した経路を記憶し、その経路を試みたのち別経路を探索する
-ドワーフがあるアイテムに到達不能と判明すると、その後一定時間そのアイテムは内部的に Forbid されているものとして扱われ、経路探索において考慮されない



** 最適化 [#xd79430e]


経路探索速度と処理速度の向上のために:

-Workshop のすぐ隣に小規模な Stockpile を置く。Urist &color(black){Mc};Crafter が少ない経路探索で岩を手に入れることができる (とはいえ Urist &color(black){Mc};Hauler の経路探索は増えるかもしれない)。
-運搬係は運ぶ必要のある物 ( Butcher's shop など大量のアイテムを生み出す工房、余剰在庫、坑道) の近くに配置する
-工房のある区域を出入りしやすくする
-階段を要塞中央にまとめるのではなく部屋々々に置くと経路探索速度が大きく向上する
-Traffic cost を適切に設定すると経路探索が素早く終わる。部屋の隅は高く、主要な廊下の中央部や Stockpile のある部屋を低く設定するとよい。詳細は [[Traffic]] を参照


** 分割一方通行 [#n52327ee]


一方通行のみのエリアを作ることはできません (0.28バージョンにおいて、バグを利用したときのみ可)。~
しかし、別々の方向に経路探索する強い優先傾向を作ることは可能です。~
A* アルゴリズム自体が非対称で優先度に偏りが出るため、利用すれば方向によって通行を分割できることがあります。~
次のフロア図を考えてみましょう。~

 WWWWWWWWWWWWWW    WWWWWWWWWWWWWW
 WWWRR....HHWWW    WWW...->...WWW
 ....WWWWWW....    <->.WWWWWW.<->
 WWWHH....RRWWW    WWW...<-...WWW
 WWWWWWWWWWWWWW    WWWWWWWWWWWWWW
 
 W = 壁
 . = Normal traffic
 H = High traffic
 R = Restricted traffic

この部分を袋小路の洞窟と外部との間に設けると (起点と目的地の両方から遠かったとしても) ほぼ常に左側の通路を通ります。~
A* 探索アルゴリズムは「最良優先」、つまり付近のタイルのうち最も通過コストの低いところを強く優先するので、「 Dwarf Fortress は目的地から生物の所在地に向けて経路計算を行う」という推測がなされているわけです。~
(これは生物が開けたところから行き止まりや迷路に向かう場合がその逆より多いとき、より能率的でしょう)~
この通路分割は全生物に有効というわけではなく (たとえばペットは通行コスト設定を無視しますし、ドワーフがこの通路内にある物を拾おうとする場合、通り抜ける経路を持たないでしょう) 、~
十分な効果が出ないこともあります (距離の差による通行コストがコスト設定を上回ることがないよう、通路同士を近づける必要があります)。~
しかし、たとえば Pressure plate 自動化に際してドワーフが踏むか踏まないかを予想できるようになったりします。~
それも「突然閉まるドア/突然開くハッチ」式テクニック特有の経路再探索 (に伴うＣＰＵの負荷) なしにです。~
(厳密な一方通行にしたい場合２つの方法を組み合わせることもできますが、時おり再探索が起きてしまうことがあります)~
通路に動物やドワーフなどの邪魔者がいたとしても、一方通行路の入り口と出口 (図中の右と左) の間を広くとればとるほど方向指定を守りやすくなります。~
もちろん、全員が同じ方向へ移動すれば実際の衝突は少なくなるでしょう。~
~
''注意''：ドワーフが通らざるを得ないタイル (要塞入り口など) を "Restricted" 指定してしまうと、代替経路を探すため経路探索コストが高くなります。(要検証)~
&color(grey){(訳注：代替経路探索が増えて処理が重くなるということか？加修筆求む)};~
~
この通路分割法を利用する場合、こうした「通ることのできる通行制限区域」は可能な限り小さくした方がよいでしょう。~
一方で、通行コストが高ければそれだけドワーフが正しい通路を通りやすくなります。~
これは通路を長くした場合にも言えます。~
通路が長くなればなるだけ通路探索は減ります。~
トンネルが "Restrict" エリアのコストと同等以上に長くなれば、コスト追加に頭を使う必要はなくなります。~
ですから長いトンネルにのみ使うべきでしょう。~
要塞のほぼすべてを "Restrict" 指定するのでもないかぎり、要塞内の部屋間の交通制御には使わないでください！~


* ドワーフ同士のすれ違い [#z43e074c]

ドワーフを始めとした実体を持つもの同士が、ひとつのタイル上を同時に移動してすれ違うことは可能です。~
しかしこのように移動するのは非常に動作が遅くなり、ドワーフは相手を避けられるよう別の経路を探そうとします。このことは要塞の設計において重要な検討材料となります。~
~
1人のドワーフが通行中の 1 タイル幅の長い通路があったとして、反対側から歩いてきた別のドワーフは他の経路を選ぶことで衝突を避けようとします。~
この通路が長く、近くに代わりになるルートもない場合、ドワーフの経路探索の負荷をたいへん著しく高めてしまう可能性があります。~
~
この理由により、往来の量が多い通路では最低でも 2 タイル幅を確保しておくのがベストです。~
同様にドアや階段も単一で設置することは避けます。~
こうすることでドワーフ同士がすれ違うときに迂回するルートを探す必要がなくなり、始めにみつけていた最短経路を変更することなく通行できるようになります。
トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS