Systems requiring a lot of "Mutual Access"

[mothteeth]

Hi. I'm quite new to Rust, but am an experienced developer. (Primarily a game developer.) I have been doing daily rust study and practice for a few weeks. After spending some time just reading The Book, my approach was to write a lot of very small tests to just try out different features and discover what kind of knots I would find myself tangled up in. These tangles were pretty common, but I generally found a way around them by shifting my thinking. I have since moved on to trying to implement a few system that I would generally use for any kind of game development. These are systems I've written many times in various games and languages in the past, so I am quite familiar with how to implement them in languages without a single ownership rule.

The system I am having trouble on right now is that of a Spatial Hash. In my initial implementation I have a HashMap with tuple keys representing 2D chunks of the world and the entities in that region: 'HashMap<(i32, i32), Vec>' As entities move around the world, they must let the map know they have changed position, and if they have crossed the boundary from one cell to another, they must be moved from the Vector they are in to the other.

So far, I have that part working fine. The map owns the entities, and mutable references can be obtained from the Hash for use by the program. For the kinds of simulations I want to be able to do, entities will use the spatial hash to find out which entities that are nearby, and interact with them. Since entities need to be able to hold "references" to each other, something Rust does not allow, I plan to store these references as ids (simple numeric id generated uniquely for each entity that is created.)

The problem I now have is to find an efficient way to locate a particular entity based on its ID. For example, I have an entity with the id 42, and I want to get a mutable reference to it. Just as an example, say one entity holds the id of another entity it is chasing (maybe it wants to eat this other entity). To be able to find out where that entity is currently located, it must use its id to obtain a (possibly mutable) reference to that entity.

In another language I might have another lookup containing references to the entities by id, or simply hold a direct reference to the entity I am interested in, but in Rust this is impossible. I can't think of any other way to locate the Entites than to iterate through every cell until I find it, which pretty much defeats the purpose of using a spacial hash in the first place.

I know that I may be missing some important techniques in Rust that I just haven't learned about. I have been advised to look at RefCell as a way of solving some of my difficulties. So my question basically is this: what kinds of techniques can I use in Rust to handle situations where many entities must have the ability to know about and refer to one another in a dynamic way (as you would expect in a simulation or game.)

Holding references to "dead" entities is certainly a problem I have encountered in game development before. In GC languages, where we can simply hold a direct reference to other entities, it is generally safe to just have a "dead" flag or something similar. If entities are being pooled, we can use other validation techniques such as generation_id to confirm that the entity is still in the same lifecycle as it was the last time we looked at it. These kinds of tricks (which are not always elegant I will admit) are what I've come up with in those languages, but in Rust a new trick is needed. I just haven't come up with it yet. I'm hoping there is some magical Rustic technique that someone can enlighten me about. Thanks

PS I can post the code of my SpatialHash if anyone is interested, although it really is just a simple HashMap basically, and the problem is more a general question about "how to think" about these problems in Rust.

[ehiggs]

Hi,
Regarding Spatial Hashing, you may also be interested in my GiST crate that contains an RTree implementation.

As for multi-index data structures, I think there is a poverty of support for this type of thing not only within Rust but also in other languages. I would suggest sqlite but this is for a game, you might want something that doesn't have to faff around with sql queries. Maybe rocksdb is something you could use here with 2 lookups: 1 by spatial hash; second by id. rocksdb supports transactions so deletes can affect multiple objects if you code it that way.

In GC languages, where we can simply hold a direct reference to other entities, it is generally safe to just have a “dead” flag or something similar.

This is usually called a tombstone. And you might use GC here as well as what you are describing is what is done in MVCC data stores.

[kornel]

When people use a numeric ID as a replacement for a reference, the ID is an index into a Vec where the entities live.

In Rust the dead flag would be an enum:

enum Entity {
    Dead,
    Alive<EntityData>
}

(or just Option). This way you can't accidentally use a dead entity.

Instead of IDs you could use Rc & Weak. They can be used as a reference from anywhere, and Weak will provide a tombstone for the spatial hash.

Rc<RefCell<Entity>> is a solution for mutating the entity from anywhere.

For multithreaded programs Rc => Arc, RefCell => Mutex.

[mothteeth]

Thanks for your responses.

I had considered using the vector index as an id, but that becomes difficult in this system because the entity must move from vector to vector. Perhaps my mistake was to make the spatial hash the owner or the Entities. Maybe having a flat vector of reusable Entity objects would make more sense. Then the SpatialHash could just hold lists of ids rather than references, and would not interfere with the borrow checker rules. That does seem to solve the problems I have quite nicely. I'll try refactoring it to work that way. Thanks for the suggestion

[comex]

An underused approach I often recommend is to use Cell instead of RefCell. The general idea is that instead of wrapping your whole struct in RefCell, you wrap individual fields in Cell, and then you use immutable references for everything, relying on the interior mutability of Cell to allow mutating the fields. This makes it easier to replicate coding patterns from other languages that don't enforce uniqueness of mutable references. On the other hand, it does have various limitations, so of course it's only one possible approach to consider.

[mothteeth]

Just a quick update for anyone who is interested. I have been refactoring my system in the following way:

Rather than making the SpatialHash the owner of the Entities, the Entites are now owned by a struct called 'EntityPool', which is basically just a flat Vector of entities, with some additional data, including a 'u64' value I increment to generate unique ids.

Throughout the program, "references" to entities are held by a simple struct I call 'EntityLocator', which contains an index to the entity in the vector, and a uid value that I use to validate that the Entity at that index is the same entity it was when the locator was created (as opposed to an Entity that has died and been recycled by the Pool.) The locator allows the Pool to find and validate Entities and return mutable references when required.

I think this approach will work quite nicely in the larger context of a game. This is a good example of how Rust requires you to think carefully about ownership. My initial design was impossible to implement because the spatial hash was just a bad structure to give ownership to, mainly because it was in constant change. The responsibilities of a Pool are a much better fit for the ownership role.

Regarding the index based ID system, although it is a good fit for a Pool, I can imagine some situations where it would not be ideal. If the index of an object can not be allowed to change, then we can never really remove anything, either with 'remove()' or 'swap_remove()', without invalidating all our Locators. I guess this is not really a problem I have right now, so I should worry about it when and if it arises in practice.

Thanks again for the suggestions. They got me moving in the right direction.

[dcarosone]

@mothteeth

Rather than making the SpatialHash the owner of the Entities, the Entites are now owned by a struct called ‘EntityPool’, which is basically just a flat Vector of entities, with some additional data, including a ‘u64’ value I increment to generate unique ids.

Throughout the program, “references” to entities are held by a simple struct I call ‘EntityLocator’, which contains an index to the entity in the vector, and a uid value that I use to validate that the Entity at that index is the same entity it was when the locator was created (as opposed to an Entity that has died and been recycled by the Pool.) The locator allows the Pool to find and validate Entities and return mutable references when required.

I've seen this pattern of using Vec indices as pointers recommended a number of times, and contemplated using it a few times myself. I've held off, mostly because I haven't really needed it, but also partly it seems like it might risk reinventing unsafety (at least in some ways).

What I've wondered a couple of times is if there's a nice way to do 'smart pointers' directly around this indexing, that isn't the full Rc<RefCell<T> dance for every element. This scheme seems good, and useful, and perhaps could become its own utility crate?

[mothteeth]

What I’ve wondered a couple of times is if there’s a nice way to do ‘smart pointers’ directly around this indexing,

I was thinking something similar about my EntityLocator type, that it could end up functioning as a kind of smart pointer. (In a way that's sort of what it is already.) My way of using it involves bounds checking and validation to ensure the object still exists, so I would consider it safe. I'm not advanced enough at Rust yet to have any deeper thoughts about it, but I intend to keep exploring these ideas.