Top / 翻訳 / Path
翻訳元DF2014:Path - Dwarf Fortress Wiki
翻訳元 Rev.Revision as of 22:22, 14 August 2015 by 79.200.87.130
最終更新バージョン0.40.24

Path - 経路, 通り道

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

工房の配置? や 保安設計? にとっては重要な関係があります。

目次 †

↑

経路探索とは †

Dwarf Fortress では、２点間の適切な経路を素早く計算する改良版 A* 探索アルゴリズム (デモ) (ソース) を利用しています。
A* 探索アルゴリズムは点Aを取り、そこから点Bに到達しうる適切な経路を計算します。
この経路は必ずしも最速ルートとは限りません。
事実、Dwarf Fortress のように環境が複雑かつ流動的なゲームでは、最速ルートが選択されることは滅多にありません。
このアルゴリズムの目的と有用性は処理能力をそれほど占めることなく経路を発見し、速度と計算可能性のバランスをとることにあります。

素材への経路探索にはいわゆるマンハッタン距離を利用しています。
つまり素材は実際の経路探索に代わり、ドワーフの現在地からの距離をチェックされます。
従って、何かを建築するときは利用可能な素材は近いものから順に並べられます。 しかし、これは道中の壁や障害物を無視したものです。
要塞設計において重要な点は可能な限り開けた要塞にすること、出入り口を増やして最速経路を多く作る (パフォーマンスを向上する)こと、マンハッタン距離と実経路の乖離を避けることです。
Workshop での作業では利用可能かつ最も近い素材が自動的に選ばれますが、建設に際してはどの素材を使うかを指定することができます。

↑

応用 †

以下の例では "A" は生物、"B" は目的地を指します。
(訳注： A も B も出てこない。原文の修正ミスか)

Workshop での作業では最も近くにある利用可能な素材が使用されます。
経路探索を有効活用する簡単な方法は、使用したい素材のみを受け入れる Stockpile で Workshop を囲むことです。
過去のバージョンでは、これが Magma に対して使うものに Magma-safe 素材を確実に使用する唯一の方法であり、特定のジョブを特定の方法で実行させる唯一の方法でした。
現在では Stockpile のリンク設定を代用すればもっと簡単に同じことができます。
それでも、なぜ Gem Setter? が家具置き場の Bed ではなく隣の部屋の Mason's workshop にある平民用の Coffin を装飾しようとするのか、その理由を理解しきっていない段階なら有用でしょう。

要塞を設計するにあたり、経路探索の仕組みを知っておかなければなりません。

保安設計においてはもう少し徹底した結果をもたらします。
敵対生物や用を実行しているドワーフは経路を選択する際マップ全域を検討することができ、A* 探索アルゴリズムの下では (選択肢の範囲内で) 常に最短経路を通ることになります。
このことから Trade depot を目指すキャラバンと要塞内部への最短経路を取ろうとする Goblin? Siege とを隔離することができます。
この挙動を利用した Exploit の一例を下に挙げます。

訳注：英語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
↑

経路の計算 †

各タイルには値が設定されており、この値は複数の要因により決定されます。
アイテムまでの距離と Traffic value (訳注：Traffic cost 設定とは別の値か) です。
したがって計算過程は以下のようになります。

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

さまようもの (動物とかうろつく侵入者など) は上記の方式にランダムな移動を組み合わせたものを適用されます。

移動するものを追いかける必要がある作業においては、この方式を何度も使うか別のアルゴリズムを利用します。

加えて以下の派生があるものと思われますが、未検証です。

↑

最適化 †

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

↑

分割一方通行 †

一方通行のみのエリアを作ることはできません (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" 指定してしまうと、代替経路を探すため経路探索コストが高くなります。(要検証)
(訳注：代替経路探索が増えて処理が重くなるということか？加修筆求む)

この通路分割法を利用する場合、こうした「通ることのできる通行制限区域」は可能な限り小さくした方がよいでしょう。
一方で、通行コストが高ければそれだけドワーフが正しい通路を通りやすくなります。
これは通路を長くした場合にも言えます。
通路が長くなればなるだけ通路探索は減ります。
トンネルが "Restrict" エリアのコストと同等以上に長くなれば、コスト追加に頭を使う必要はなくなります。
ですから長いトンネルにのみ使うべきでしょう。
要塞のほぼすべてを "Restrict" 指定するのでもないかぎり、要塞内の部屋間の交通制御には使わないでください！

↑

ドワーフ同士のすれ違い †

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

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

この理由により、往来の量が多い通路では最低でも 2 タイル幅を確保しておくのがベストです。
同様にドアや階段も単一で設置することは避けます。
こうすることでドワーフ同士がすれ違うときに迂回するルートを探す必要がなくなり、始めにみつけていた最短経路を変更することなく通行できるようになります。

トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS