Right way to implement world of entities

Question

I'm looking for the right way to implement a world for my game. The world holds and updates every entity but some entities may modify the world back. I've tried to use RefCell but I got an error in Entity::update method:

use std::cell::RefCell;
use std::rc::Rc;

struct World {
    entities: Vec<Entity>,
}

impl World {
    fn update(&mut self) {
        for entity in self.entities.iter_mut() {
            entity.update();
        }

        println!("World has been updated");
    }

    fn influence(&mut self) {
        println!("World has been influenced");
    }
}

struct Entity {
    world: Rc<RefCell<World>>,
}

impl Entity {
    fn update(&mut self) {
        self.world.borrow_mut().influence(); // ERROR GOES HERE
        println!("Entity has been updated");
    }
}

fn main() {
    let world = Rc::new(RefCell::new(World {
        entities: Vec::new(),
    }));
    world.borrow_mut().entities.push(Entity {
        world: world.clone(),
    });
    world.borrow_mut().entities.push(Entity {
        world: world.clone(),
    });
    world.borrow_mut().entities.push(Entity {
        world: world.clone(),
    });
    world.borrow_mut().update();
    world.borrow_mut().update();
}

thread 'main' panicked at 'already borrowed: BorrowMutError', src/libcore/result.rs:1188:5

What is the right way to implement this kind of world?

Similar question was Passing mutable self reference to method of owned object but I need more complex logic since an entity may modify the world or other entities. I even plan to hold generic traits so that some entities will have different logic.

I know why I got this error, my question is more about design-pattern.

Answer 1

As you observed, a RefCell does not allow you to break Rust's shared/exclusive reference rules. The rules are that if some part of your program has an exclusive reference &mut x, no other part of the program can have any reference (shared or exclusive) to x.

Ultimately, you must at least make sure that e.update() cannot obtain another mutable reference to e (the first one being &mut self). This will require some trade-offs, since the most straightforward approach, in which an entity can obtain a mutable reference to the world, easily allows every entity to obtain a second mutable reference to itself.

Approach 1

If you could separate the state that an entity can update from the entities itself, structure it as follows, without using RefCells at all:

struct Influencable;

struct World {
    entities: Vec<Entity>,
    influenceable: Influencaeble,
}

impl World {
    fn update(&mut self) {
        for entity in self.entities.iter_mut() {
            entity.update(&mut self.influenceable);
        }
    }
}

struct Entity;

impl Entity {
    fn update(&mut self, influenceable: &mut Influenceable) {
        // update entity
        // modify influenceable
    }
}

Approach 2

If the state of the world is just the sum of the state of all its entities, maybe explore if the scope of influence is somehow limited. Maybe you can arrange the entities in a tree such that an entity can only modify its children. Then an entity can contain a list of its children and can automatically modify them given the mutable self reference.

Approach 3

If an entity potentially wants to modify the state of arbitrary other entities during its own the update, things get a bit more complex. There is a way to support this, again without RefCells:

struct World {
    entities: Vec<Entity>,
}

impl World {
    fn update(&mut self) {
        let mut entities: Vec<Option<&mut Entity>> =
            self.entities.iter_mut().map(|e| Some(e)).collect();

        for i in 0..entities.len() {
            let entity = entities[i].take().unwrap();
            entity.update(&entities);
            entities[i].replace(entity);
        }
    }
}

struct Entity;

impl Entity {
    fn update(&mut self, others: &[Option<&mut Entity>]) {
        // update entity and maybe others
    }
}

The idea is to get a vector of mutable references to all the entities. If we call the entities e1, e2, e3, e4, this vector looks like this:

entities = vec![Some(&mut e0), Some(&mut e1), Some(&mut e2), Some(&mut e3)];

To update the i-th entity, we first remove the mutable reference to it from the vector and store it in entity. For i=2, this looks like this:

entities = vec![Some(&mut e0), Some(&mut e1), None, Some(&mut e3)];
entity = &mut e2;

Then we call the update method on entity, passing in the mutable references to all the other entities:

entity.update(&entities);