Factorio風の電力システムを実装した時のメモ
やったこと1行まとめ
要素追加時にKD木で最近傍探索し、Dynamic Connectivityで要素のグループを統合/分割しました。コードは載せていません。
I have implemented a power system similar to Factorio. When adding new elements, I used KD-tree for nearest neighbor search and employed Dynamic Connectivity to merge/split groups of elements. I'm not posting the code here.
概要
Factorio風の電力システムを最近実装しました。（あくまで「風」であり、細かい部分は結構違います。）
ググれば何か参考になる記事が出てくるかと思っていましたが、手がかりが全くつかめず、設計や実装に悩んだので知識としてまとめることにしました。
Factorioの電力システムは主に次の要素で成り立っています。
- 発電施設（蒸気機関など）
- 分配施設（電柱など）
- 受電施設（組立機など）
発電し、電柱などを経由して、電柱の効果範囲内にある受電施設に電力を供給します。
これを満たすような仕組みをC#で実装しましたが、その過程で3つの問題に直面しました。
- 施設の設置場所から一番近い施設を探すには？
- 施設のグループを統合・分割するには？
- グループごとに総電力を計算するには？
ということで、それぞれ実際にどう解決したかを説明していきます。
1. 一番近い施設を探す
Factorioは2Dのグリッド状のマップで、施設は区切られたマスごとに置けます。
例として、5×5マスの正方形の範囲にある受電施設に電力を供給し、また距離が4マス以内の発電施設と分配施設へ電線を接続する仕組みを考えます。
分配施設の供給範囲と接続距離
各施設間を接続するためには次の2つの処理が必要です。
- 5×5マスの正方形の範囲にある受電施設を探す
- 直線距離4マス以内の発電施設と分配施設を探す
どちらも、「近くにある施設を探す」ことが必要です。
グリッド状のマップなら範囲内のマスを全探索できますが、接続できる直線距離が例えば30マスぐらいに伸びてくると、チェックするマス数が急激に増えていき非常に重い処理になってしまいます。
そこで探索を効率化する必要がありますが、実はこの問題には「最近傍探索」という名前が付いており、先人が既に効率的な解決策を導き出しています。
さまざまな方法がありますが、今回はKD木のC#実装を使いました。
施設の座標をKD木のキーとして追加していき、RadialSearchすれば範囲内の全施設が高速で見つかります。
このとき、座標間の距離をチェビシェフ距離で算出すれば正方形の範囲内にある施設が見つかり、ユークリッド距離にすれば直線距離の範囲内にある施設が見つかります。ということで、1つ目の問題が解決しました。
ちなみにFactorioは2Dゲーですが、このKD木の実装は多次元に対応しているので3Dゲーでも4Dゲー(?)でも同じように最近傍探索ができるはずです。また、floatやdoubleで座標を指定できるので、グリッドでない自由配置のゲームでも同じような仕組みが作れます。
2. 施設のグループを統合/分割する
電線が繋がっている施設同士は同じ総電力を共有しますが、電線が途切れたら別々の総電力を持たなければなりません。
総電力が分割されている例
そのため、接続されている施設をグループで管理する必要があります。
グループといえばまずUnionFindを思い浮かべますが、今回は要素の追加によるグループの統合だけではなく、削除によるグループの分割にも対応が必要なのでUnionFindは使えません。
施設同士の接続をマッピングしておけばパッと判定できそうな気もしますが、例えば電柱を削除したときに、次のような2パターンは削除した地点のマッピングからは判別できず、途切れる地点が見つかるまで全探索する必要があります。
分割不要なパターン
分割が必要なパターン
なので、全く別の方法が必要ですが、答えを先に言うとDynamic Connectivityというズバリ当てはまるデータ構造があります。簡単に言ってしまえば削除も可能なUnionFindです。
今回は次のC#実装を使いました。
初期化したあとは施設に連番でIDを振り、KD木で探した近傍の施設に対してLink/Cutしていけば施設がきれいにグループ化されます。ということで、2つ目の問題が解決しました。
3. グループごとの総電力の計算
ここまでで、施設の動的なグループ化ができるようになりました。
あとは、各グループがどれだけ電力を生産/消費しているかが分かればOKです。
もしそこまで施設の数が多くなく厳密さにこだわらないのであれば、リアルタイムで電力を計算せず、定期的に各グループの施設を全探索して計算結果をキャッシュするのもアリだと思います。O(n)かかりますが、簡単に実装できます。
一方、施設の数が非常に多くなったり、リアルタイムで電力を反映する必要がある場合は上の方法では厳しくなります。
なので、かなり泥臭い方法ですが、各施設の発電量や消費量が変わる全てのタイミングで差分をキャッシュへ反映するよう実装しました。
そのためにはグループごとのキーが必要ですが、Dynamic ConnectivityはRootが変わる木構造なので、キーにできるような情報がありません。悩みましたが苦肉の策でRootのHashCodeを使用し、木構造に要素の追加/削除があったタイミングでキャッシュのキーをその都度最新のRootに更新しています。
施設の追加/削除時は、Dynamic Connectivityから属しているグループのRootを取り、それをキーとして総電力を増減させます。
施設の追加によって2つ以上のグループが1つに統合された場合は、各グループの総電力のキャッシュを足し合わせて新グループの総電力にできます。
施設を削除して1つのグループが2つ以上に分割された場合は少しやっかいですが、グループのSizeが小さい方から順に全探索して各グループの総電力を計算していき、その合計を分割前の総電力から引けば最後の1グループの総電力が求まります。この方法なら、グループの末端付近で電柱を削除して小グループと大グループに分割されるような場合に軽く済みます。最悪ケースはグループの中心にあるような電柱を取り除いて一度に多数のグループに分割された場合などで、ほぼ全施設の総電力の再計算が必要です。そのような最悪ケースが頻繁に発生する場合は別の方法を考える必要がありますが、今回はそういった操作はあまりしないので妥協しました。
ということで、実装は全探索に比べて果てしなく面倒ですし、施設の追加や削除には細かいコストが掛かりますが、定期的なO(n)の処理が不要になり、厳密な総電力をリアルタイムに取れるようになって、3つ目の問題が解決しました。（もっと良い方法がある気はしますが、木構造の知識が足りませんでした。）
4. ほか実装で詰まったところ
-
KD木を使えば近傍の施設群を取得できますが、O(1)ではないので毎回取り直してたら重くなります。施設間の接続をMultiDictionaryなどでキャッシュしておくと早くなります。（Dynamic Connectivityはある2点が同じグループに属するかは分かっても、ある1点からどの点に直接リンクされているかは分からないので、このようなキャッシュが必要になります）
-
特殊ケースで、1つの受電施設が複数の独立したグループの供給範囲に入ってしまうことがあります。この場合、複数のグループに同じ消費電力を足すと総電力が不正になるし、かといって消費電力を等分して足すのもグループによって稼働判定が変わる奇妙な状況になるので、「受電施設は最も発電量の多い1グループにのみ属する」という制約を付けました。この制約を実現するため、分配施設の追加/削除時は供給範囲にある全ての受電施設を最適なグループに繋ぎ直しています。全ての特殊ケースで正しく動くわけではありませんが、総電力はズレなくなりますし、基本的に大きな1つのグループを作るよう電柱を配置するゲームなのでこの制約で妥協しました。
-
電柱間の電線の表現も厳密にやるならループを作らないように最小全域木を構築して、各操作で崩れないように細かく管理する必要がありそうです。しかし、そこまで気にせずマジカル配電を許容するなら、施設を追加/削除するタイミングで元々接続されていた周囲の分配施設の電線を最高2本繋ぎ直すようにするとお手軽にいい感じに見えます。
まとめ
あちこちに妥協はありますが、ネットを探しても設計方針が見つからなかったので知識として書くことにしました。
もっと良い方法があるはずだとは思っているので、「KD木とDynamic ConnectivityでFactorioの電力システムっぽいのが作れるんだ」ぐらいの理解でもよいと思います。
手を動かす時間は長かったですが、木構造の組み合わせで意外にあっさり実装できて面白かったです。それでは。
Discussion