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:
- Run an update on each game system sequentially
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)
Each system that subscribed to the specific message gets it's message handling method called
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 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):
- Systems start processing TimePassedMessage
- InputHandingSystem converts key presses to entity action (in this case, a left arrow turns into MoveWest action). Entity action is stored in ActionExecutor component
- ActionExecutionSystem, in reaction to entity action, adds a MovementDirectionChangeRequestedMessage to the end of message queue
- 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)
- Systems stop processing TimePassedMessage
- Systems start processing MovementDirectionChangeRequestedMessage
- MovementSystem changes entity velocity/movement direction as requested
- Systems stop processing MovementDirectionChangeRequestedMessage
- Systems start processing PositionChangedMessage
- CollisionDetectionSystem detects that because an entity moved, it ran into another entity (tank went inside a wall). It adds a CollisionOccuredMessage to the queue
- Systems stop processing PositionChangedMessage
- Systems start processing CollisionOccuredMessage
- 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).
No comments:
Post a Comment