やりたいこと
ゲームエンジンを開発していると、よくあるパターンとして、 Entity の一つ一つにメソッドを呼ぶことがあると思いますが、そのときにゲーム全体の状態を渡したいことがあると思います。さらに、 Entity の応答に応じて GameState にも変更を加えたいということがあるでしょうから、ミュータブル参照を渡したいところです。
struct Entity { /* ... */ }
impl Entity {
fn simulate(&mut self, state: &mut GameState) { /* ... */ }
}
struct GameState {
entities: Vec<Entity>,
/* ... */
}
impl GameState {
fn simulate(&mut self) {
for entity in &mut self.entities {
entity.simulate(self);
}
}
}
C++ では簡単にできることですが、 Rust では当然ながらコンパイルエラーになります。 Entity 自体が GameState の一部なので、そのミュータブル参照を渡すということは、同じselfオブジェクトに2つのミュータブル参照からアクセスできてしまうからです。
error[E0499]: cannot borrow `*self` as mutable more than once at a time
--> src/lib.rs:14:29
|
13 | for entity in &mut self.entities {
| ------------------
| |
| first mutable borrow occurs here
| first borrow later used here
14 | entity.simulate(self);
| ^^^^ second mutable borrow occurs here
GameState を分ける方法
簡単な方法としては GameState を Entity のリストとそれ以外(RestState)に分けてしまうという方法があります。
struct Entity { /* ... */ }
impl Entity {
fn simulate(&mut self, state: &mut RestState) { /* ... */ }
}
struct RestState;
struct GameState {
entities: Vec<Entity>,
rest: RestState,
}
impl GameState {
fn simulate(&mut self) {
for entity in &mut self.entities {
entity.simulate(&mut self.rest);
}
}
}
しかしこれはあまりうまくいきません。 Entity のタイプが増えてくると、それぞれの Entity のリストとそれ以外を分けることが簡単にはできなくなってくるからです。例えば、下記のような GameState をどう分割できるか考えてみてください。
struct GameState {
entities_a: Vec<EntityA>,
entities_b: Vec<EntityB>,
entities_c: Vec<EntityC>,
}
一時変数に move する方法
で、かなりトリッキーですが、 Entity のリストを一時オブジェクトに std::mem::take してしまい、あとで move し戻すという方法があります。これは Vec が Default だからできることですが、そうでないコンテナでも Option にくるんでやれば同じことができると思います。
impl GameState {
fn simulate(&mut self) {
let mut entities = std::mem::take(&mut self.entities);
for entity in &mut entities {
entity.simulate(self);
}
self.entities = entities;
}
}
Entity のリスト全体を動かすので、パフォーマンス的に不利のようにも見えますが、実は Vec の指しているメモリ上のバッファは動かず、ポインタを移動しているだけなので、それほど悪い方法ではありません。ほかにも RefCell を使う方法もあると思いますが、 RefCell も貸し出し状態を管理する変数を必要とするので、オーバーヘッドという点では大差ないと思います。
同じ Entity のリストを参照するには？
ところでここで問題が生じます。上記の方法では、 Entity のリストをすべて GameState から退避してしまうので、同じ Entity のリストに存在する他の Entity を Entity::simulate から参照したいと思ってもできないということです。
impl Entity {
fn simulate(&mut self, state: &mut GameState) {
for entity in &mut state.entities {
// 常に empty!
}
}
}
これを実現するには、 Entity のリストの中で自分自身を除いたすべてのものをイテレートすることができればいいわけです。素直に考えれば、 Entity のリスト全体を GameState から退避するのではなく、自分自身だけを除いたリストを残せばいいわけですが、これを Vec に対してやるのはかなりの非効率です。
10000個の Entity があるときを考えてみてください。一つ目の Entity を扱う時には、 後ろの9999個の Entity を一つ前にずらし、 二つ目のときには9998個を動かし、…ということをしなければなりません。 HashMap なら定数時間で削除/挿入ができますが、このためだけに HashMap を使うのは、キャッシュの局所性を考えても避けたいところです。 swap_remove で要素のシフトを避けることもできますが、もっと良い方法があります。
ここで Rust のスライス型には split_at_mut という素晴らしいメソッドがあるという事実が役に立ちます。
impl Entity {
fn simulate(
&mut self,
state: &mut GameState,
first: &mut [Entity],
last: &mut [Entity])
{
for entity in first.iter_mut() {
/* ... */
}
for entity in last.iter_mut() {
/* ... */
}
}
}
impl GameState {
fn simulate(&mut self) {
let mut entities = std::mem::take(&mut self.entities);
for i in 0..entities.len() {
let (first, mid) = entities.split_at_mut(i);
let (center, last) = mid.split_first_mut().unwrap();
center.simulate(self, first, last);
}
self.entities = entities;
}
}
この方法は、 Vec 自体のサイズは変えずに、スライスの範囲を自分を除外するように設定するという方法で、動的メモリを使わすに自分自身を除いたオブジェクトをイテレートすることができるという魔法のような方法です。
しかし、ちょっとだけカッコ悪いところがあります。それは Entity::simulate() の中で自分より前のスライスと後ろのスライスを別々にループで回さなくてはならないということです。
for entity in first.iter_mut() {
/* ... */
}
for entity in last.iter_mut() {
/* ... */
}
理想的には、前の半分と後ろの半分を続けてイテレートするようなイテレータがあるといいわけです。実際、これはそれほど難しくないです。
for entity in first.iter_mut().chain(last.iter_mut()) {
/* ... */
}
しかし、このメソッドのシグネチャは、内部実装をさらけ出しているようでちょっと気持ち悪いです。
fn simulate(
&mut self,
state: &mut GameState,
first: &mut [Entity],
last: &mut [Entity])
理想的には、 Iterator トレイトでそのようなリストを生成する型を定義し、 simulate のシグネチャは次のようにしたいところです。
fn simulate(
&mut self,
state: &mut GameState,
entities: &dyn Iterator<Item = Entity>);
しかし、 Iterator は一度リストをイテレートし終わったら、再び巻き戻して最初からやり直すということができないので、スライスの代わりにはなりません。 Iterator トレイトの必要なメソッドは next() のみで、巻き戻すということはできないのです。 Entity のリストを何度か辿りたいということはゲームの中では珍しいことではありませんので、これは何とかサポートしたいところです。
つまり、「Iterator トレイトを何度も生成しなおせるトレイト」が必要になるわけで、それを先ほどの first last スライスから生成する型を実装すればよいわけです。この方針の素晴らしい点は、もし自分を除外する必要がなければ単純なスライスを実装すればより効率的な型が同じロジックでも使えるようになるということです。
ですが、ここまで来て自分の力では実装できそうにない気がしたので、私は公式フォーラムに助けを求めました。 Rust はコミュニティのクオリティが高いことに定評がありますが、その評判に違わず、私の求めていた実装を示してくれた人がいました。
以下が「巻き戻し可能なイテレータ」に相当するトレイトです。
pub(crate) trait DynIter {
type Item;
fn dyn_iter(&self) -> Box<dyn Iterator<Item = &Self::Item> + '_>;
fn as_dyn_iter(&self) -> &dyn DynIter<Item = Self::Item>;
}
impl<T, Item> DynIter for T
where
for<'a> &'a T: IntoIterator<Item = &'a Item>,
{
type Item = Item;
fn dyn_iter(&self) -> Box<dyn Iterator<Item = &Self::Item> + '_> {
Box::new(self.into_iter())
}
fn as_dyn_iter(&self) -> &dyn DynIter<Item = Self::Item> {
self
}
}
pub(crate) trait DynIterMut: DynIter {
fn dyn_iter_mut(&mut self) -> Box<dyn Iterator<Item = &mut Self::Item> + '_>;
}
impl<T, Item> DynIterMut for T
where
for<'a> &'a T: IntoIterator<Item = &'a Item>,
for<'a> &'a mut T: IntoIterator<Item = &'a mut Item>,
{
fn dyn_iter_mut(&mut self) -> Box<dyn Iterator<Item = &mut Self::Item> + '_> {
Box::new(self.into_iter())
}
}
そして、次にスライスの組から前述のトレイトを実装する型です。
struct MutRef<'r, T: ?Sized>(&'r mut T);
impl<'a, 'r, T: ?Sized> IntoIterator for &'a MutRef<'r, T>
where
&'a T: IntoIterator,
{
type IntoIter = <&'a T as IntoIterator>::IntoIter;
type Item = <&'a T as IntoIterator>::Item;
fn into_iter(self) -> Self::IntoIter {
self.0.into_iter()
}
}
impl<'a, 'r, T: ?Sized> IntoIterator for &'a mut MutRef<'r, T>
where
&'a mut T: IntoIterator,
{
type IntoIter = <&'a mut T as IntoIterator>::IntoIter;
type Item = <&'a mut T as IntoIterator>::Item;
fn into_iter(self) -> Self::IntoIter {
self.0.into_iter()
}
}
struct Chained<S, T>(S, T);
impl<'a, S, T, Item: 'a> IntoIterator for &'a Chained<S, T>
where
&'a S: IntoIterator<Item = &'a Item>,
&'a T: IntoIterator<Item = &'a Item>,
{
type IntoIter =
iter::Chain<<&'a S as IntoIterator>::IntoIter, <&'a T as IntoIterator>::IntoIter>;
type Item = &'a Item;
fn into_iter(self) -> Self::IntoIter {
self.0.into_iter().chain(self.1.into_iter())
}
}
impl<'a, S, T, Item: 'a> IntoIterator for &'a mut Chained<S, T>
where
&'a mut S: IntoIterator<Item = &'a mut Item>,
&'a mut T: IntoIterator<Item = &'a mut Item>,
{
type IntoIter = iter::Chain<
<&'a mut S as IntoIterator>::IntoIter,
<&'a mut T as IntoIterator>::IntoIter,
>;
type Item = &'a mut Item;
fn into_iter(self) -> Self::IntoIter {
self.0.into_iter().chain(self.1.into_iter())
}
}
使うときは次のようにします。
center.simulate(self, &mut Chained(MutRef(first), MutRef(last)));
正直、いまだにこの実装を完璧には理解できていません ^^;
ですが、動的メモリを使っていることはわかります。 DynIter の実装によって、生成される Iterator オブジェクトのサイズが変わるので、これは仕方のないことのように思います。もしかしたら impl Trait で静的ディスパッチすればコンパイル時にサイズがわかるので動的メモリを使わなくても済むかもしれませんが、これは次の改善案ですね。
fn simulate(&mut self, state: &mut GameState, others: impl DynIterMut<Item = Entity>);
オブジェクト指向への応用
ここまでの話は、 Entity が何らかの具体的な型である前提でしたが、実際、このテクニックが真価を発揮するのは、トレイトオブジェクトを使ったオブジェクト指向で Entity を実装した時です。
trait Entity {
fn simulate(&mut self, state: &mut GameState, others: &dyn DynIterMut<Item = Box<dyn Entity>>);
}
Entity のリストはトレイトオブジェクトのリストになります。
struct GameState {
entities: Vec<Box<dyn Entity>>,
}
それぞれのオブジェクトが実装しているのは動的ポリモーフィズムにより異なる関数となりますが、 GameState::simulate のロジックは全く変わることなく、そしてそれぞれの型のメソッドでは DynIterMut を使って巻き戻し可能なイテレータを何度でも使えるのです。
このような方法で実際に実装したブラウザゲームがこちらです。
ECS への応用
ECS (Entity Component System) は最近流行りのゲームアーキテクチャで、有名どころでは Unity が使っていますが、 Rust では specs というライブラリがサポートしています。
specs は、ゲームエンジンでありがちなミュータブル参照の問題の多くを回避するのに役立ちますが、やはりどうしても同じ型(コンポーネント)のリストの複数の要素を同時にミュータブル参照したい場合にはボローチェッカーと戦う羽目になります。
let entities = world.entities();
let mut components = world.write_component::<SomeComponent>();
for (entity, component) in (&entities, &mut component).join() {
component.simulate(entity, &components);
}
このような場合も、前述のスライストリックが役に立ちます。
let mut component_bundle = (
&entities,
&mut component,
)
.join()
.collect::<Vec<_>>();
for i in 0..component_bundle.len() {
let (first, second) = component_bundle.split_at_mut(i);
let (center, last) = second.split_at_first();
center.simulate(self, first, last);
}
難点としては、一度スライスに直さなくてはいけないので、 Vec に Collect する必要があるということです。実際のコンポーネントではなく、そのコンポーネントへの参照のスライスなので、サイズはそれほど大きくありませんが、動的メモリの生成が必要になります。
複数の Entity の同じコンポーネントへのミュータブル参照を同時に取りたいことなんて、そんなにあるか？と思う方もいるかもしれませんが、私の場合は流体のコンテナコンポーネントで隣の接続した Entity との間で流入/流出のシミュレーションをするために必要でした。
おわりに
パフォーマンスに関わること一般に言えることですが、 n 個のオブジェクトがあったときに総当たりで n^2 のチェックを行うのは筋が良いとはいえません。 n に対してスケールするには、何らかのインデックスを使ってチェック対象を絞り込むべきでしょう。しかしながら、小さなゲームについてはこのような単純な方法でもそこそこうまくいきます。
このスライストリックは、私の知る限り HashMap や BTreeMap には使えません。元のデータ構造に変更を加えずにサブセットへのミュータブル参照を複数同時に返すメソッドがないからです。もし、できるよ！という人がいたら教えてください。 