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

Adaptive/Dynamic Categorization

Any static partitioning of data flows using a static algorithm (like a geometric grid) will break down. Either due to something intrinsic, or because the players are evil, and delight in ignoring your simplifying assumptions.

So for stability and performance/scale reasons a categorization policy that is dynamic will be better. Periodically a centralized or distributed computation can inspect the in-use categories and determine whether there is a better mapping.

Imagine there was a flash-crowd come to see an epic battle. The initial mapping had that area mapped to one category. The area can be split into two area and given two distinct categories. At a specific point in time, the new mapping will be instituted. Call that the next epoch. We need to do that across all users of those categories. The easiest way would be to broadcast the new mapping. Once all participants have acknowledged they have the new mapping and re-subscribe using that mapping, producers can start using the new categories. Once all participants have acknowledged adopting the new mapping, the old categories can be unsubscribed from.

There are many interesting dynamic categorization policies. They are based on live measurement of the system as the game is being played. The new categorization is then applied live. Clearly this can provide better efficiency than offline analysis and updating a static mapping, since in-game patterns can change minute to minute.

• Split and merge geometric grid cells or triangles. This is how many mmo systems work today, so if that is your preference you can keep it while migrating to using categories.
• Compute "nearness" between producers and consumers, and identify clusters of entities. The set of entities identified is given a category. As entities move around, they subscribe to other clusters of entities. Once the interconnections become too "stretched", a new clustering can be computed. There are pretty simple clustering algorithms, such as inspecting R-squared for an Entity against various proposed clusters to find the nearest one inside some threshold. Note that this approach can be applied to individual entities incrementally as they move.
  
• A similar clustering algorithm can be applied to actual communication patterns as opposed to assuming that geometric nearness always indicates high interaction rates. The recategorization system would record and analyze metrics of interactions as they change in real time.
• The hosting software can detect overloads of various resources, and indicate to the recategorization system that splitting off instances of busy areas would be valuable (assuming your game design supports that approach).
• As dungeons or PvP arenas are spawned, a new set of categories especially for the players involved will be computed and used. Because the subscribers indicate which instance they are currently assigned to, the categorization policy will compute the Categories for that instance, and a player will not see anything from a different instance.
• A game may have unique capabilities like being able to add, remove or move land masses. As coordinate systems drift around, the categorization policy would need to take this into account. It may be able to do that using relative coordinates, or it may need to completely recategorize space.
• Changes in team or guild size may trigger recategorization.
  
• As a clarification, in contrast to dynamic categorization, consider this scenario: As density increases in an area, the policy can adjust the maximum sight distance. While this doesn't directly change the decomposition of the data, it will result in fewer categories being consumed. (This is really a subscription policy change, not a categorization policy change)

Really, the key thing is to consider that real time feedback can be used to help improve the data distribution performance of your system.

Obviously an algorithmic policy is better than an enumerated one, since distributing new parameters to factor into a computation requires less data than a complete enumeration of the descriptions for each category.

Like almost any distributed computation, recategorization can benefit from incremental changes. Local measurements and performance triggers can instigate a categorization change to just a few mappings, and may be able to be distributed to only a few machines. These incremental changes can quickly ripple through the category space and come to an approximately optimal mapping. One benefit of the incremental approach over the periodic approach is that the trigger to recompute can be an event as opposed to a polling of metrics and a recomputation that may have limited or no effect.