Entity Concurrency

Ever since Simula and Demos in the 60's, object-oriented (or process-oriented) simulation has been considered the most natural and intuitive approach to representing a system. Certainly it is the way we think when we write programs using imperative languages (like C++), even when taking advantage of multithreading.

Over simplifying things, process oriented entities have a "main loop" which continues to be in scope, on the stack but possibly suspended even as the entity is idle or blocked waiting for something. An example would be a vehicle that stops at a red light. After the light goes green, the program continues with the next line of code (perhaps navigating to the nearest gas station). Conversly in an event-oriented simulation, the car would be unscheduled and the light would have to signal the car change its state from waiting to driving the next leg of the route. In the one case, the programmer can write all the code from the perspective of the entities (the vehicle, the light...). In the other, they write a soup of events and state changes that is very hard to visualize and see whether the logic is correct.

The easiect way to realize process oriented entities is to take advantage of coroutines built in the scripting language of your choice. Using a thread per object can get horribly expensive, even if they were cooperative threads. Using a coroutine allows a program to choose to block between two statements and go idle, context switching to another entity. When the resource being blocked on is available, the system can switch back to the suspended entity.

So the challenge is coordinating the objects. You can look at a previous article on bin/res for some ideas.

You can even have multiple concurrent activities running on an entity. E.g. monitoring your fuel level, driving a route, and listening for new orders from a taxi-dispatcher. Each would consume another coroutine. A complication here is that when a coroutine blocks and goes idle, the others might run and change the value of states in the entity. Fortunately this does not result in race conditions because coroutines are cooporative and only switch at a point that the programmer chooses. They can then be very aware that other processing might change things before they wake up again.

Coroutines can also be used to spread computation across multiple ticks without having to refactor the algorithm you are using. If you have a long AI or path planning algorithm, you could suspend at any point and resume during the next tick. The exact context is restored by the scripting language coroutine system. It might also make it easier to cancel such a computation at those suspend points.

When thinking about online games, load balancing is critical. We do it by migrating entities. But if an entity has a suspended context in a coroutine at the point you want to do the migration, things get harder. How do you pick up the stack context and reconstruct it on the target machine?

One way is to refuse to migrate until the entire context tears down (e.g. it returns to the "main loop"). Better would be to make use of the scripting language facilities to serialize and restore a coroutine. Various folks have shown that Stackless Python is capable of pickling an entity that has an outstanding context, and reconstructing it (either after a save/load, or after migration).

Has anyone tried "pickling" a coroutine in Lua? It's been on my todo list for a while. The question is whether references to (global) variables outside the coroutine can be "reattached" when it is unserialized on the other side. And what format is the coroutine "printed" and trasmitted as?