Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I am implementing an entity system variant that has:

  • An Entity class that is little more than an ID that binds components together

  • A bunch of component classes that have no "component logic", only data

  • A bunch of system classes (a.k.a "subsystems", "managers"). These do all the entity logic processing. In most basic cases, the systems just iterate trough a list of entities they are interested in and do an action on each of them

  • A MessageChannel class object that is shared by all game systems. Each system can subscribe to specific type of messages to listen to and can also use the channel to broadcast messages to other systems

The initial variant of system message handling was something like this:

  1. Run an update on each game system sequentially
  2. If a system does something to a component and that action might be of interest to other systems, the system sends an appropriate message (for example, a system calls

    messageChannel.Broadcast(new EntityMovedMessage(entity, oldPosition, newPosition))
    

    whenever an entity is moved)

  3. Each system that subscribed to the specific message gets it's message handling method called

  4. If a system is handling an event, and the event processing logic requires another message to be broadcast, the message gets broadcast right away and another chain of message processing methods gets called

This variant was OK until I started optimizing the collision detection system (it was getting really slow as number of entities increased). At first it would just iterate each entity pair using a simple brute force algorithm. Then I added a "spatial index" that has a grid of cells that stores entities that are inside the area of a specific cell, thus allowing to do checks only on entities in neighboring cells.

Every time an entity moves, the collision system checks whether the entity is colliding with something in the new position. If it is, a collision gets detected. And if both colliding entities are "physical objects" (they both have RigidBody component and are meant to push each other away so as not to occupy the same space), a dedicated rigid body separation system asks the movement system to move the entities to some specific positions that would separate them. This in turn causes the movement system to send messages notifying about changed entity positions. The collision detection system is meant to react because it needs to update it's spatial index.

In some cases it causes a problem because the contents of the cell (a generic List of Entity objects in C#) get modified while they are being iterated over, thus causing an exception to be thrown by the iterator.

So... how can I prevent the collision system from being interrupted while it checks for collisions?

Of course I could add some "clever"/"tricky" logic that ensures the cell contents get iterated over correctly, but I think the problem lies not in the collision system itself (I also had similar problems in other systems), but the way messages get handled as they travel from system to system. What I need is some way to ensure that a specific event handling method gets do it's job without any interruptions.

What I have tried:

  • Incoming message queues. Every time some system broadcasts a message, the message gets added to message queues of systems that are interested in it. These messages get processed when a system update is called each frame. The problem: if a system A adds a message to system's B queue, it works well if system B is meant to be updated later than system A (in the same game frame); otherwise it causes the message to processed the next game frame (not desirable for some systems)
  • Outgoing message queues. While a system is handling an event, any messages it broadcasts are added to outgoing message queue. The messages don't need to wait for a system update to be processed: they get handled "right away" after the initial message handler has finished it's work. If handling of the messages causes other messages to be broadcast, they too are added to an outgoing queue, so all messages get handled the same frame. The problem: if entity lifetime system (I implemented entity lifetime management with a system) creates an entity, it notifies some systems A and B about it. While system A processes the message, it causes a chain of messages that eventually cause the created entity to be destroyed (for example, a bullet entity got created right where it collides with some obstacle, which causes the bullet to self destruct). While the message chain is being resolved, the system B does not get the entity creation message. So, if system B is also interested in entity destruction message, it gets it, and only after the "chain" is finished resolving, does it get the initial entity creation message. This causes the destruction message to be ignored, the creation message to be "accepted", and the whole system B now works as if the entity was never even destroyed (accessing a deleted entity also causes an exception).

EDIT - ANSWERS TO QUESTIONS, COMMENTS:

  • Who modifies the contents of the cell while the collision system iterates over them?

While the collision system is doing collision checks on some entity and it's neighbors, a collision might get detected and the entity system will send a message that will be reacted upon right away by other systems. The reaction to the message might cause other messages to be created and also handled right away. So some other system might create a message that the collision system would then need to process right away (for example, an entity moved so the collision system needs to update it's spatial index), even though the earlier collision checks were not finished yet.

  • Can't you work with a global outgoing message queue?

I tried a single global queue recently. It causes new problems. Problem: I move a tank entity into a wall entity (the tank is controlled with the keyboard). Then I decide to change direction of the tank. To separate the tank and wall each frame, the CollidingRigidBodySeparationSystem moves the tank away from the wall by the smallest amount possible. The separation direction should the opposite one of the movement direction of the tank (when the game drawing starts, the tank should look as if it never moved into the wall). But the direction becomes opposite of the NEW direction, thus moving the tank to a different side of the wall than it initially was. Why the problem occurs: This is how messages are handled now (simplified code):

public void Update(int deltaTime)
{   
    m_messageQueue.Enqueue(new TimePassedMessage(deltaTime));
    while (m_messageQueue.Count > 0)
    {
        Message message = m_messageQueue.Dequeue();
        this.Broadcast(message);
    }
}

private void Broadcast(Message message)
{       
    if (m_messageListenersByMessageType.ContainsKey(message.GetType()))
    {
        // NOTE: all IMessageListener objects here are systems.
        List<IMessageListener> messageListeners = m_messageListenersByMessageType[message.GetType()];
        foreach (IMessageListener listener in messageListeners)
        {
            listener.ReceiveMessage(message);
        }
    }
}

The code flows like this (let's assume it's not the first game frame):

  1. Systems start processing TimePassedMessage
  2. InputHandingSystem converts key presses to entity action (in this case, a left arrow turns into MoveWest action). Entity action is stored in ActionExecutor component
  3. ActionExecutionSystem, in reaction to entity action, adds a MovementDirectionChangeRequestedMessage to the end of message queue
  4. MovementSystem moves entity position based on Velocity component data and adds PositionChangedMessage message to end of queue. The movement is done using movement direction/velocity of previous frame (let's say north)
  5. Systems stop processing TimePassedMessage
  6. Systems start processing MovementDirectionChangeRequestedMessage
  7. MovementSystem changes entity velocity/movement direction as requested
  8. Systems stop processing MovementDirectionChangeRequestedMessage
  9. Systems start processing PositionChangedMessage
  10. CollisionDetectionSystem detects that because an entity moved, it ran into another entity (tank went inside a wall). It adds a CollisionOccuredMessage to the queue
  11. Systems stop processing PositionChangedMessage
  12. Systems start processing CollisionOccuredMessage
  13. CollidingRigidBodySeparationSystem reacts to collision by separating tank and wall. Since the wall is static, only the tank is moved. The tanks' movement direction is used as an indicator of where the tank came from. It is offset in an opposite direction

BUG: When the tank moved this frame, it moved using movement direction from previous frame, but when it was being separated, the movement direction from THIS frame was used, even though it was already different. That's not how it should work!

To prevent this bug, the old movement direction needs to be saved somewhere. I could add it to some component just to fix this specific bug, but doesn't this case indicate some fundamentally wrong way of handling messages? Why should the separation system care which movement direction it uses? How can I solve this problem elegantly?

  • You may want to read gamadu.com/artemis to see what they did with Aspects, which side steps some of the problems you're seeing.

Actually, I've been familiar with Artemis for quite a while now. Investigated it's source code, read the forums, etc. But I've seen "Aspects" being mentioned only in a few places and, as far as I understand it, they basically mean "Systems". But I can't see how Artemis side steps some of my problems. It doesn't even use messages.

  • See also: "Entity communication: Message queue vs Publish/Subscribe vs Signal/Slots"

I've already read all gamedev.stackexchange questions regarding entity systems. This one does not seem to discuss the problems I am facing. Am I missing something?

  • Handle the two cases differently, updating the grid does not need to rely on the movement messages as it's part of the collision system

I'm not sure what you mean. Older implementations of CollisionDetectionSystem would just check for collisions on an update (when a TimePassedMessage got handled), but I had to minimize checks as much as I could due to performance. So I switched to collision checking when an entity moves (most entities in my game are static).

share|improve this question
    
There's something that ins't clear to me. Who modifies the contents of the cell while the collision system iterates over them? –  Paul Manta Feb 13 '12 at 21:52
    
Can't you work with a global outgoing message queue? So all messages in there are send each time after a system is done, this includes the system self destructing. –  Roy T. Feb 13 '12 at 21:58
    
If you want to keep this convoluted design then you must follow @RoyT. 's advice, it's the only way (without complex, time based messaging) to handle your sequencing problem. You may want to read gamadu.com/artemis to see what they did with Aspects, which side steps some of the problems you're seeing. –  Patrick Hughes Feb 13 '12 at 22:48
    
See also: gamedev.stackexchange.com/questions/1119/… –  Crashworks Feb 14 '12 at 0:33
1  
You might want to learn how Axum did it by downloading the CTP and compiling some code - and then reverse engineering the result to C# using ILSpy. Message passing is a important feature of actor model languages and I am sure Microsoft knows what they are doing - so you might find they had the 'best' implementation. –  Jonathan Dickinson Feb 14 '12 at 8:06
show 1 more comment

3 Answers 3

How to properly implement message handling in a component based entity system?

I would say that you want two types of messages: Synchronous and Asynchonous. Synchronous messages are handled immediately while asynchronous are handled not in the same stack frame (but may be handled in the same game frame). The decision which is which is usually made on a "per message class" base, e.g. "all EnemyDied messages are asynchronous".

Some events are just handled much much easier with one of these ways. For example, in my experience an ObjectGetsDeletedNow - event is much less sexy and callbacks are much harder to implement than ObjectWillBeDeletedAtEndOfFrame. Then again, any "veto"-like message handler (code that can cancel or modify certain actions while they are executed, like an Shield-effect modifies the DamageEvent) are not going to be easy in asynchronous environments but are a piece of cake in synchronous calls.

Asyncronous might be more efficient in some cases (e.g. you can skip over some event handlers when the object gets deleted later anyway). Sometimes synchronous is more efficient, especially when calculating the parameter for an event is costly and you rather like to pass callback functions to retrieve certain parameters instead of already calculated values (in case nobody is interested in this particular parameter anyway).

You already mentioned another general problem with synchronous-only message systems: To my experience with syncronous message systems, one of the most cases of errors and grief in general are change of lists while iterating over these lists.

Think about it: It is in the nature of synchronous (immediately handle all after-effects of some action) and message system (decoupling receiver from sender so the sender does not know who is reacting to actions) that you will not be able to easily spot such loops. What I am saying is: Be prepared to handle this kind of self-modifying iteration a lot. Its kindof "by design". ;-)

how can I prevent the collision system from being interrupted while it checks for collisions?

For your particular problem with the collision detection, it might be good enough to make collision events asynchronous, so they get queued up until collision manager is finished and executed as one batch afterwards (or at some later point in the frame). This is your solution "incoming queue".

The problem: if a system A adds a message to system's B queue, it works well if system B is meant to be updated later than system A (in the same game frame); otherwise it causes the message to processed the next game frame (not desirable for some systems)

Easy:

while (!queue.empty()) { queue.pop().handle(); }

Just run the queue over and over until no message remains. (If you scream "endless loop" now, remember that you most probably would have this problem as "message spamming" if it would be delayed to the next frame. You can assert() for a sane number of iterations to detect endless loops, if you feel like it ;))

share|improve this answer
    
Note that I do not spoke about exactly "when" asynchronous messages get handled. In my opinion, its perfectly fine to allow the collision detection module to flush its messages after it finishes. You could also think of this as "synchronous messages, delayed until end of loop" or some nifty way of "just implement the iteration in a way that it can be modified while iterating" –  Imi Feb 17 '12 at 22:29
add comment

You've probably heard of the God/Blob object anti-pattern. Well your problem is a God/Blob loop. Tinkering with your message passing system will at best provide a Band-Aid solution and at worst be a complete waste of time. In fact, your problem has nothing specifically to do with game development at all. I've caught myself trying to modify a collection while iterating over it several times, and the solution is always the same: subdivide, subdivide, subdivide.

As I understand the wording of your question, your method of updating your collision system currently looks broadly like the following.

for each possible collision
    check for collision
    handle collision
    modify collision world to reflect change // exception happens here

Written plainly like this, you can see that your loop has three responsibilities, when it should only have one. To solve your problem, split your current loop into three separate loops representing three different algorithmic passes.

for each possible collision
    check for collision, record it if a collision occurs

for each found collision
    handle collision, record the collision response (delete object, ignore, etc.)

for each collision response
    modify collision world according to response

By subdividing your original loop into three subloops, you no longer ever attempt to modify the collection over which you are currently iterating. Note also that you are not doing more work than in your original loop, and in fact you might gain some cache wins by doing the same operations many times sequentially.

There is also a further benefit, which is that you can now introduce parallelism into your code. Your combined-loop approach is inherently serial (which is fundamentally what the concurrent modification exception is telling you!), because each loop iteration potentially both reads and writes to your collision world. The three subloops I present above, however, all either read or write, but not both. At the very least the first pass, checking all possible collisions, has become embarrassingly parallel, and depending on how you write your code the second and third passes might be too.

share|improve this answer
    
I totally agree with this. I'm using this very similar approach in my game and I believe this will pay off in the long run. This is how the collision system (or manager) should work (I actually believe it's possible to not have a messaging system at all). –  Emiliano Nov 15 '13 at 19:29
add comment

If you're actually trying to get make use of the data-oriented-design nature of ECS then you might want to think about the most DOD way of doing this.

Take a look at the BitSquid blog, specifically the part about events. A system that meshes well with ECS is presented. Buffer all events into a nice clean per-message-type queue, the same way systems in an ECS are per-component. Systems updated afterward can efficiently iterate over the queue for a particular message type to process them. Or just ignore them. Whichever.

For example, the CollisionSystem would generate a buffer full of collision events. Any other system run after collision can then iterate through the list and process those as needed.

It keeps the data-oriented parallel nature of the ECS design without all the complexity of message registration or the like. Only systems that actually care about a particular type of event iterate over the queue for that type, and doing a straight single-pass iteration over the message queue is about as efficient as you can get.

If you keep components consistently ordered in each system (e.g. order all components by entity id or something like that) then you even get the nice benefit that messages will be generated in the most efficient order for iterating over them and looking up corresponding components in the processing system. That is, if you have entities 1, 2, & 3 then messages are generated in that order and component lookups performed while processing the message will be in strictly increasing address order (which is the fastest).

share|improve this answer
1  
+1, but I can't believe this approach has no disadvantages. Doesn't this force us to hardcode interdependencies between systems? Or maybe these interdependencies are meant to be hardcoded, one way or another? –  user Jul 26 '13 at 18:56
2  
@Daedalus: if game logic needs physics updates to do the correct logic, how are you not going to have that dependency? Even with a pubsub model, you have to explicitly subscribe to such-and-such message type which is only generated by some other system. Avoiding dependencies is hard, and is mostly just figuring out the right layers. Graphics and physics are independent, for instance, but there will be a higher level glue layer that ensures interpolated physics simulation updates are reflected in graphics, etc. –  Sean Middleditch Jul 26 '13 at 19:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.