Google's Protocol Buffers (for messages and files?)

This is an interesting package:

http://code.google.com/apis/protocolbuffers/docs/overview.html


It can be used for on-the-wire and for file formats. It is much more efficient than XML, and has multiple language API’s (e.g. easier to send a message between apps of different languages). It deals with versioning, and has automated class and serialization code generation.


I haven't used it yet. Any thoughts? How good is it for archive files/pack files? How good is its historical version handling wrt up-converting or semantic changes (like feet to meters)?

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?

Off Topic: Most common solid waste?

OK. Weird thought... If you went to a landfill, what would be the most common solid waste you saw? A number of years back, a greeny asked that question and challenged people to go see for ourselves. It's been bugging me ever since. Here are some quick Googled results.

The most common waste product is paper (about 40 percent of the total). Other common components are: yard waste (green waste), plastics, metals, wood, glass and food waste. The composition of the municipal wastes can vary from region to region and from season to season. (U of Cal)

Paper, Organics (in Canada, from an Amazon "search inside" book)

Malaysia: Plastic waste is the most common solid waste that we generate in the country accounting for 7-12 percent by weight and 18-30 percent by volume of the total residential waste generated.

Throwaways (diapers) comprise 2 percent of the nation's solid waste by weight, making them the third most common solid waste item after newspapers and beverage and food containers. (diaper "activist" site, NY)

So "paper" is #1 and is quite recyclable, and energy rich. Plastic and organics too (possibly #2 and #3, if you include diapers; heh!).

Still doesn't answer what the "source" of the paper and plastic is. Fast food bags and wrappers? Retail boxes/packaging, grocery packaging, industrial/wholesale packaging? Books, junk mail, printouts?

I'd love to have a reference to a more detailed discussion of the source data. Not the reinterpreted-for-an-agenda summaries. And then make my own conclusions about reducing. (Maybe I should just look in *my* trash can at the end of the week).

Online Hard Problems

I've tried to keep a list of "hard problems" for online games. Sometimes it is to impress folks with how much work is involved in trying to build the technology itself (and redirect them toward middleware), and sometimes it is to remind me of how much work we have left as a middleware company. Here is my current collection. It is not every system needed, but the ones that are particularly tricky or challenging and require the right architectural decisions early. I'd appreciate if folks would add to this.

Hopefully, over time I'll be able to publish my conclusions about how to actually solve these problems. Many interact, and need a unified approach to be able to be solved at all.

Distributed and parallel nature

• Load balancing.
• Latency hiding.
  
• Timing, synchronization and ordering.
• Anticheating/security

Performance

• Threading,
  
• Execution performance,
• Memory performance,
  
• Network performance and message streaming,
• Persistence performance,
• Bandwidth reduction,
• Content streaming/background loading

Scale and seamlessness

• Scale for both casual and intensive styles (reusing the same infrastructure)
  
• Seamlessness at runtime
  
• Entity interaction across server "boundaries"
  
• Seamlessness at edit time
• Transactional entity interaction
• Shardless worlds
  

Ease of Use/Development/Operations

• Ease of use for designers, game developers (code and assets)
  
• Ease of developing large scale content
• Development efficiency and rapid iteration (assets and code),
• Fault tolerance, debuggability of large distributed system,
• Performance debugging,
• Script/behavior debugging, script/behavior ease of use,
• Hosting, operations ease of use (server deployment, control, monitoring, ...)
• In game microtransactions (security)
• Integration to multiple platform services
• Client deployment, patching, binary patching

Bin/Res process synch

Back in the 80's Graham Birtwistle developed Demos (ala Greek citizenry, not that canned thing the publisher is shown), a library extension to Simula. It is one of the earliest and most intuitive process-oriented simulation systems around. Here's one link:
http://cs.ubishops.ca/ljensen/simulation/sync.htm

There is a particular synchronization mechanism I have always liked about Demos. It is called bin/res. These are two queue-like objects that are most easily described as elements in an assembly line. A res is a resource that can be obtained and returned. (Yes, like a semaphore.) A bin is a collection into which items can be placed and removed. The items can contain arbitrary information.

What is interesting here is that when an entity pulls from a bin or a res when it is empty, the entity blocks until something becomes available. If an entity puts something into a bin or res that exceeds its configured maximum the producing entity blocks.

In process-oriented entity modeling, this is a great simple synchronization technique. In the middle of a complex bit of behavior logic, the Entity can block until something important happens.

Another cool thing about bin/res is that it has an event-oriented optimization. When an Entity is blocked, it inserts itself into an entity queue and blocks. When the other Entity changes the bin/res, it uses that queue to notify and wake up the blocked entity. This avoids all polling. It also works between processes using messages. That can be very important and useful in an online game.

Also note that bin/res can have a lot of other extensions. There can be multiple producers/consumers. The queues can be LIFO, FIFO or randomly serviced. And it is easy to put statistics like wait-times on them.

There are a million uses for bin/res. You can make your behavior scripts wait until some property reaches a desired value without polling. You can make two entities wait for each other before proceeding no matter what order they get to the staging area. You can deal with fairness and race conditions between multiple players. Any kind of queuing can be automatically flow controlled.

I've been a fan for almost 30 years. Ever since I came across Demos at University of Calgary. Hi Graham!

Smart pointer leak code worked

I have to brag on a prototype I finished last week. I'd mentioned previously a way to track smart pointer leaks. Well, I used a buddy's stack trace snapshot library and was able to inspect where in code all the smart pointers were set for an arbitrary object.



void LoggerTest::testInit()
{
void *temp = (void*)efd::GetLogger();
if (true) {
efd::SmartPointer thing;
thing = efd::GetLogger(); // assignment should be recorded here.

DarrinTestDumpStack(temp);
}
DarrinTestDumpStack(temp); // The reference above disappears in this printout.
}

And the output:
efd::SmartPointer::SmartPointer + 44
LoggerTest::testInit + 80 <<<<------ See, this was where I grabbed the ref. TestDescription_LoggerTest_testInit::runTest + 22 CxxTest::RealTestDescription::run + 67 CxxTest::TestRunner::runTest + 116 CxxTest::TestRunner::runSuite + 170 CxxTest::TestRunner::runWorld + 172 CxxTest::TestRunner::runAllTests + 80 CxxTest::ErrorFormatter::run + 21 main + 106 __tmainCRTStartup + 424 mainCRTStartup + 15 efd::LoggerSingleton::Initialize + 459 <<<<------ See. This is the only other reference (the factory). InitializeTestApp + 300 EEGlobalFixture::setUpWorld + 22 CxxTest::RealWorldDescription::setUp + 94 CxxTest::TestRunner::runWorld + 103 CxxTest::TestRunner::runAllTests + 80 CxxTest::ErrorFormatter::run + 21 main + 106 __tmainCRTStartup + 424 mainCRTStartup + 15 RegisterWaitForInputIdle + 73 0xffffffffcccccccc *************************************************************** Second dump (only the factory reference is left): efd::LoggerSingleton::Initialize + 459 InitializeTestApp + 300 EEGlobalFixture::setUpWorld + 22 CxxTest::RealWorldDescription::setUp + 94 CxxTest::TestRunner::runWorld + 103 CxxTest::TestRunner::runAllTests + 80 CxxTest::ErrorFormatter::run + 21 main + 106 __tmainCRTStartup + 424 mainCRTStartup + 15 RegisterWaitForInputIdle + 73 0xffffffffcccccccc