Rust/specs – what is the good/idiomatic way of design level walls/static objects handling in an ECS architechture

Question

Warning: long question ahead, don't be afraid, I just tried to be as precise as possible about details for who wants them but many paragraphs are skipables if you already understood what I want ;).

Context:

I passed the last few weeks learning Rust (reading The Book, writing small apps and toying), and I'd like to start building a bit bigger application, so I thought writing a game (to also learn Rust's bindings for SDL2, as I've already worked with this fantastic library).

There aren't lots of up-to-date tutorials out there on how to do that, so I basically followed the documentation. That's when I found the specs crate, which looked very interesting as I read over Internet the ECS pattern is quite good, and very idiomatic for Rust. So, let's dive in! (previously I was writing games in python where ECS isn't much known – at least as far as I saw)

---

So, I create the basic components, such as Sprite (for every entity that needs to be printed), Position (self explanatory), Hitbox, KeyboardControlled, Mass, Speed…, setup some Keyboard and Physics systems (I don't include any code as everything up to here is very self explanatory, and my implementations are all three bugged, standard and very simple, and as so quite redundant with the name).

Ok, now I have a nice little sprite (a rectangle) which I can control with Left/Right. I would like to add some ground so it doesn't fall forever (there is some gravity), but I'm stuck in finding any appropriate way of doing so. I would like my whole ground/level as well as static objects to be somehow efficient (I don't want to check collisions against the whole world for each entity in order to see if it's falling).

---

The question: what is the “good” way to do so? I think that every part of my level should be entities (so at least I can load/drop them dynamical), but if so, how can I control how they are stored? I mean, suppose I had a marker component for walls Wall or stuff like that, then I could try to match every entity that has a hitbox against walls, like that:

// data is (WriteStorage<Hitbox>, ReadStorage<Wall>)
for (entity,) in (&mut data.0,).join() {
  for (wall,) in (&data.1,).join() {
    // compute collision, eventually change push the hitbox out of the wall or what so ever
  }
}

But this is so inefficient: O(m·n) where m is the number of hitboxed entities and n the number of walls, whereas in python I would probably do it with HashMaps (~O(m·k/n) time to retrieve colliding objects where m is the number of hitboxed entities, k is the size of the hitbox and n the size of walls), or with any decent search tree, with witch I can get something like O(m·ln(n)), where n is the number of walls, and this is just applying standard databases (one can memoize data from one query to the following ones, and get super fast colliding algorithms for bunch of objects)).

But algorithms are not really the concern here, my question is: what is the idiomatic way of doing it? Where/how should I store all of that? Should specs do it for me, and if so, how?

---

All I could find in doc is to specify the type of collection to be used to store entities, and then to retrieve them when I do the computation, but I couldn't find many examples or explanations so I am unsure about this solution.

---

I specified I coded in Rust because, as a novice, I would enjoy any tip or reference to specific crates/docs, but feel free to answer the question on a more abstract level, even if you know few or nothing about Rust, but you are still used to ECS.

Answer 1

Typically you'd store these types of things in the standard ECS scene as usual with the data in one or more components. Where I'm thinking you might be hung up a bit is that the ECS isn't there to give you things like efficient collision detection or frustum culling off the bat. It's there to give you a very flexible way to store, access, transform, manage, and organize your game state. If it's a very efficient ECS implementation, it's generally optimized for sequential loops over components for algorithms that typically won't be better than linear-time in complexity.

Usually, if you want to do efficient collision detection in those, for example, you'd build a spatial index on the side like a loose quadtree for 2D cases or a spatial hash. These data structures typically don't own the memory of the game objects. Instead, they usually store links to them (references, pointers, or indices) with a layer of indirection along with something like an axis-aligned bounding box. It tends to actually improve efficiency in these cases to have that layer of indirection even when the engine is not an ECS and can store game objects directly since if you imagine a search query involving linear probing in a spatial hash, just storing a link (but keys, of course, by value) can substantially reduce the stride to get from one entry in the hash table to the next while allowing more entries in that hash table to fit in a cache line if we avoid having to store an entire entity or component's data by value.

As for where to store these data structures used to accelerate searches, I'm not sure what is idiomatic. ECS specs tend to be pretty loose with respect to details like this, and I'm sure a variety of solutions exist. What I tend to do in cases where the data structure is accessed by multiple systems is to just store or directly associate with the scene, like:

// logarithmic search
entity_or_component_refs = scene.quadtree.find_intersection(...);

You could store such a structure in a component but I find it a bit clumsy since, in many cases, it would convolute systems if they can't safely assume that there's going to be only one for the entire scene, and typically an ECS is designed around storing a variable number of components of each type unless your engine specifically handles such cases.

In cases where the data structure is only used by one system, like a physics system, I tend to relax the strict separation rule of data in components and logic in stateless systems and just store the data structure as a private member of the system object. I think that's still reasonably idiomatic since most ECS implementations I see do allow systems to store some state (including specs from what I can gather). What I would do is try to avoid storing what constitutes the central program state in a system, like the type of state that gets serialized, since that blurs responsibilities. Yet I'd exclude something like a spatial index or physics cache from that category, as it is really just an implementation detail used to help make one or more systems execute more efficiently.