ECS (with specs) for turn-based game

I have been experimenting with the Entity-Component-System paradigm in game developement (specifically by using the excellent crate specs). Point in question, I am working on turn-based games, e.g. a roguelike.

After some effort I managed to get the whole thing running, but then I started wondering. The more I read about it, the more it looks to me like ECS was thought to be used on real-time games, where systems run continously and in parallel. Adapting it to my turn-based game produced some weird quirk: systems have to run one at a time, and are mostly exclusive!

E.G. I have a system making an entity step in some direction and changing its position accordingly, which only runs when the entity currently playing actually perform a step; otherwise, the step system remains silent.

While this seems to suggest ECS is not suited to my use-case, the Entity-Component part actually worked great: it gave my entities a great deal of flexibility, yielding the benefits ECS promises in this sense compared to OOP.

So I am wondering whether I should change my approach. I could, for example, define a single Entity type containing all possible components behind an Option, and then store those in a huge Vec. To make an explicit example of what I mean:

// an example component
struct Life {
  pub max_hp: u8,
  pub current_hp: u8,
}

// another example component
struct Movement {
  speed: u8,
}

// a generic entity, owning its components
struct Entity {
  id: usize,
  life: Option<Life>,
  movement: Option<Movement>,
}

// the main game type
struct Game {
  // storing all the components
  world: Vec<Entity>,
}

impl Game {
  // main method to interact with the game:
  // an entity performs some action
  pub fn play_action(&mut self, entity_id: usize, action: Action) {
    // apply action to game following the game's rules
  }
}

Pros and cons of this approach: I expect it to be unoptimized, but, after all, speed is not my main concern. On the other side, it is much more explicit and easy than a full-fledged ECS like that provided by specs.

So, am I grossly misunderstanding ECS? Should I stick to it, pursue my example, or something different altoghether?

3 Likes

I have a (somewhat hacky) example of using Specs in a roguelike here. The ECS runs at a real time tick rate, doling out 'energy' to game entities. When they have enough energy, it's their turn (and if they're marked as a player, the game stops giving out energy until the user inputs an action, effectively pausing).

This kind of real-time/turn-based hybrid is nice, because it means you can drive things that aren't turn-based off the same ECS instance (animations, maybe? I didn't get that far :p)

My implementation is probably a bit rubbish (and I definitely don't think I'm using Specs to its full potential), but hopefully it'll give you some ideas!

Other recommended reading:

http://journal.stuffwithstuff.com/2014/07/15/a-turn-based-game-loop

EDIT:

Oh, also! If I remember correctly Zemeroth (a turn-based strategy game written in Rust) uses some form of ECS. Their code is approximately 5000% better than mine, so check that out too :stuck_out_tongue:

4 Likes

That's great! I actually tried it and it worked without any issues. The mixed turn/real-time approach is really interesting.

I actually knew this post before and extensively took inspiration from it. I'm afraid my concerns apply here too: indeed, the author recognises that it's not using the system part of ECS. I'm doing something similar to its Actions, but I tend to see those as small systems, each executing their small task when required. It kind of works, but I'm worried I may be misusing the ECS concepts and making things overly complicated.

1 Like

The "turn based game" is kind of a myth, from an engine development perspective. Almost all games end up as interactive simulations (aka "real time") on the basis that they are... interactive programs. If you want to process input, render animations and menus, play music and sounds, compute AI decisions, load data from disk, etc., then you're going to want some kind of continuous async "game loop" driving things.

Now if your game has turn based gameplay, then that's something that you implement in game logic, independent of the fact that the program is an interactive simulation. Even real time games use turn-based logic, even if it doesn't look like it per se: many games use state machines to model the state of the game. In a turn-based game, your states are "waiting for input" and "responding to input", and you dispatch accordingly, depending on what is needed each frame. But a real-time game might do the same thing with states like "climbing a ladder" and "rolling after a jump", etc. So a turn-based game is just a more visible case of the behavior you'd implement in any other game.

A system is still a system, whether you need to process everything in one frame, spread out over many, or continuously. I don't think it is a misuse of ECS to do things your way. Turn-based gameplay just really has no significant bearing on how you build a game engine, unless you know up front that you don't want to animate or process anything between turns. Very few games want to take that road.

10 Likes

If I remember correctly Zemeroth (a turn-based strategy game written in Rust) uses some form of ECS.

I actually gave a short talk about structuring turn-based games in Rust a few weeks ago - video/slides - but everything is in Russian. (I should really consider a blog post in English about this theme)

Long story short, I believe that you don't need that much different systems for turn-based game logic, so Zemeroth uses just a hashmap-based storage for components and focuses on command->event dataflow + declarative animation system.

Soo, I mostly agree with the topic-starter :slight_smile:

4 Likes

Unfortunately my Russian is not very good, but if you ever write that post in English I'll be most interested! :sweat_smile:
PS: Zemeroth looks amazing, keep it up!

I see your point and I would expect it to hold in general. Though, I suspect (canonical) Roguelikes may be a notable exception to the rule. In those games there is little to no graphics and animations, but the game logic is quite complex. Maybe a pure turn-based engine* may still be adequate to their needs, while simplifying the game logic management.

(*) or, rather, the model of the game. The view/controller, if a MVC pattern is being used, can/should still be real-time based, thus even allowing some simple animation.

1 Like

Kind-of follow up question. The game takes place in a map/level/dungeon, which is thought of as a grid. Entities which have a position in the game map are placed at some coordinate. So, how to represent this?

I have the following implementation constraints:

  • Given an entity, I'd like to know where this entity is placed
  • Given a coordinate, I'd like to get a list of all entities placed there
  • A coordinate can contain any amount of entities
  • An entity can actually be placed at many different coordinates in the grid. Think of an entity grass: instead of creating a new grass instance for every coordinate I want to fill with grass, I will consider grass as an uncountable substance, and use it in every coordinate I need it to be. This can dramatically reduce the number of entities I have to store.

It may be unnecessary in my specific situation, but for sake of academia, let's say I want a game with HUGE maps, so that memory use and computation time are potential concerns. Which patterns and data structure(s) should I use?

My naive approach was to have a ndarray::Array2<Vec<specs::Entity>> (or a ndarray::Array2<HashSet<specs::Entity>>) to represent the map, and use it as a resource for the world. Moreover, entities which needs it also have a Position component which stores a coordinate.

This approach actually works, and it's reasonably fast to look up positions of an entity and occupants of a coordinate. Though, it uses quite a lot of memory (I calculated that, on avarage, it uses 1k for every coordinate of the map) and I suspect it's due to the overhead of having that many arrays, which usually contain just a few entries each.

A more advanced approach was to use the crate bisetmap, but the memory issue persists (and I believe the underlying reason is fundamentally the same).

Is there a canonical solution for this kind of issues? Am I using the wrong data type?

IIUC, the entities are owned by your Game struct. It probably makes sense to keep that structure and share ownership with the map using Rc. Or use Weak if you need to avoid cycles, by not sharing ownership. This will probably resolve some of your initial memory concerns, especially with entities like Grass where you only need a single instance and you just populate a large map with pointers.

I don't actually know what kind of overhead ndarray::Array2 or bisetmap have, but the leanest data structure you can use for the map is a plain old array. Arrays are not ideal to work with, though. Unless you have a large number of Array2 instances, it shouldn't contribute much to memory bloat.

Final thought, I just checked the source for ndarray, whose Array2 type is already generic over Vec. Is there a reason you are making it generic over a second Vec explicitly? I don't have a compiler on this machine right now, and the playground doesn't support ndarray. So I'm not able to run any tests with and without the additional Vec generic. Cross that. I just remembered you listed 'multiple entities per map location' as one of the design requirements. That explains it.

1 Like

If I understood correctly how specs work, all the data of the entities is stored in the components by specs. The Entitys are just a label, so an usize or little more. My map only stores this labels, so the actual data in it should be little. That is why I suspect most of the memory is just overhead from using Vecs (e.g. don't vectors reserve more space than they are actually using?).

The vector will not allocate until elements are pushed onto it.

Yes but as soon as the first element is pushed (and I have precisely a lot of Vecs with one element) won't it allocate enough space to hold many elements, which then may not be used? I think that's what gives me most of the overhead.

You can use Vec::with_capacity to allocate space for an exact number of items. I haven’t looked at any of the source to determine how it grows the capacity. The simplest method is probably doubling the capacity. If that was the case, you could allocate with a capacity of 1, and save memory that way. At the cost of runtime allocations to grow each vector as needed.

1 Like

This might be a good use of the smallvec crate. If most of your cells really just have one or two entities in them, then you might come out ahead in terms of memory use.

3 Likes

I gave just a quick look at the smallvec crate, but I can't really see how it would help. As far as I understand, a SmallVec is like a normal vector, but it allocates a certain (and fixed) amount of memory on the stack. It would be somewhat faster than a normal vector, but wouldn't it still use the same amount of memory?

1 Like

A specs entity is 8 bytes. If I'm remembering correctly, a smallvec that can store two of those on the stack would take 32 bytes, while a normal Vec with a capacity of two elements would be 24 bytes on the stack plus 16 on the heap. Depending on your usage patterns, you could come out ahead or behind.

2 Likes

@EGhiorzi Just spotted this thread, I wonder if there's any way to get notifications for posts with "ECS" or "Specs" because I tend to miss them.

Whether ECS is a good choice or not depends on multiple things. The most important one is probably how you like to think about your game and how you want to structure it. I personally prefer how data is organized in an ECS, but that you have to decide for your own.
As for tile maps, those are a little more complex with an ECS. By default, Specs just allocates entity ids and reuses them as soon as an entity gets deleted. But in your case, you want to do the entity allocation yourself. For this use case I created an experimental crate: https://github.com/torkleyy/specs-static

It allows you to use whatever id you want. So you can just define that a tile at (x, y) has the id y * width + x. I created a little demonstration here: https://github.com/torkleyy/specs-static/blob/master/examples/basic.rs
I didn't use it myself yet, so I cannot say how well it works, but maybe you want to try it out :slight_smile:

As for the allocation "problem": 1) I wouldn't worry about that at first. 2) You can define your own low-level storages for the components. You don't have to use VecStorage, you could create a ShrinkedVecStorage for example that only allocates one additional element using Vec::reserve_exact.

3 Likes

Thanks for the suggestions!

After some experimentation, I think I found what works best for me: I use specs to store and manage entities, but I don't use systems for the main loop. That is because in (my) turn based games all actions performed on the world have to be sequential, and usually involve only one entity. Eg: entities move on the map one at a time, so I cannot iterate over all entities with a velocity component at the same time (which is a classic example of how to use systems in ecs). Also, only one system at a time would run: in a given turn, either an entity moves, or attacks, etc... (There are some things that happen every turn, e.g. health regeneration, poisoning, hunger etc., but overall I don't think it's worth changing the whole game's structure for that.)

I think I didn't explain clearly enough how I am handling the map: I use a map indexed over my coordinates, and with value for each coordinate a set (or a vec) of entities. That is stored as a resource for the world. A tile is just an entity like any other, to be added to the set corresponding to the relevant coordinate(s) (an "uncountable" entity could be present in many places at once, like a sand entity). So, I don't need to pick special indexes for my entities. Moreover, that map is what I think is eating my memory by creating a huge lot of sets (or vecs), not specs storages, which are already highly optimized anyway.