Tidbits about the WoW backend

This discussion with Joe Rumsey, a software engineer for World of Warcraft at Blizzard, took place in 2013, but I'm only posting about it now.

• Their database has 50% read and 50% write. There used to be more writes because the durability of player's equipment used to decrease often in combat. They have a proxy in front of the DB. The proxy flushes to DB periodically. Around 20 shards per DB. Transactions: inventory, trade, zone change, but not combat/monsters state.
• 800-meter zones. Sort of dynamic zone borders. Would rather have one big zone on one server than two zones with a lot of exchange between them on different servers. Objects are mirrored on adjacent zones. If a zone falls, the entire server falls. To move an entity between two servers, server 1 flushes the entity to DB then server 2 retrieves it from DB; the two servers never exchange the player data.
• The game server ticks at 2.5 times per second.
• The clients connect to a proxy.
• JSON vs binary messages: JSON's performance is fine 95% of the time.

House architectural styles

Software architecture professors often make an analogy between software architecture and building architecture. I have been looking at software architectural styles for a while. What are building architectural styles about? I looked at 4 books on architecture, and liked Architectural Styles, by Carson Dunlop. This book only provides a typology of house styles, which seems to be the only meaning of architectural styles for building architecture. I wondered why bridge trusses were not included in the architectural styles. It seems that bridge trusses is a particular structural engineering concern, which is only one part of studying architectural styles.

Criteria

• detached vs semi-detached
• Floor plans: positioning of the rooms: 1x1, 2x1, 2x2, 5x1, etc.
• Roof shapes: flat (with or without parapet), shed, gable (with or without projecting beams, exposed trusses, gingerbread, ...), hip, mansard, ... with or without bell-cast eaves, widow's walk, turrets, cupola, ...
• Chimney types
• Dormers: gable, hip, arched, eyebrow, ...
• Entablature
• Walls: brick nogging, half-timbered, stucco, adobe, quoinning, ...
• Windows: fixed, double-hung, single-hung, casement (opening in or out), sliders, awning, hopper, jalousie, ... with various types of muntins (separation between glass panels), mullions (separation between windows), panes, sashes (e.g. wood or metal holding the glass), and sills. Window shapes: Gothic, Palladian, curved top, ... Window crowns: fanlight, pediment, hood, ... Shutter styles, ...
• Doors: each with their own style of fanlight and transom light (glass above the door), side light (glass next to the door), pilaster, and pediment.
• Columns: the classical orders are Doric, Tuscan, Ionic, Corinthian, and Composite. A column is made of a base, a pilaster, and a capital (top).

Styles

• The Ancient Classical style is common on government and institutional buildings. The columns, symmetry, low roof slopes, and entablatures are influenced by Greek and Roman classics. Substyles include Classic Revival, Greek Revival, and Neoclassical.
• The Renaissance Classical style is based on European interpretations of Greek and Roman classics. Symmetry is important, and doors, eaves, and windows have distinctive details. Substyles include Italianate, French Colonial, Georgian, Adam, and Colonial Revival.
• The Medieval style can be found mostly in cathedrals and churches. Usually asymmetric, with steep roofs, chimneys, parapets, turrets, and towers. Substyles include Gothic, Victorian, Romanesque, Tudor, and Queen Anne.
• The Modern style dates from the 20th century and can be divided into Arts and Crafts, and Machine Age. Arts and Crafts have low-sloped roofs with wide overhangs. Substyles include Prairie (emphasis on horizontal lines) and Craftsman (tapered pillars on porches, exposed structure). Machine Age buildings eliminate decoration: asymmetric, and flat roofs with no overhang.
• The Spanish style features adobe or stucco exterior walls, arched windows, and red-tiled roofs. Substyles include Spanish Colonial, Mission, Pueblo Revival, and Monterey.

Take-aways

Functionally, house styles are heavily influenced by the climate and the cost. Aesthetically, they seem influenced by the historic period and the artist/inventor behind them.

It seems that the aesthetic elements do not matter so much in software architecture. Rather, it seems that only the structural elements matter: how the weight is supported, how snow falls off the roof, how the house stays cool, etc.

In building architecture, it is difficult to separate the aesthetic from the functional. For example, the steep roofs of the Gothic style are very aesthetic, but they are very functional too: they prevent snow to accumulate.

Game Architecture and Design - part 2 and 3: Management and Architecture

Game Architecture and Design - parts 2: Management and 3: Architecture, by Rollings and Morris, 2004

Ch9 - Current methods of team management

Several developer stereotypes pose problems.

• Mavericks are skilled and trust no one else.
• Prima donnas know they are the best and consider others as threats.
• Shy guys are ... shy, so they don't always say everything, which reduces the project visibility.
• Sleepers appear nice to their boss, but actually attack the management in their back.
• Jacks of all trades are overconfident and sell themselves too well. They can get overwhelmed.

Ch16 - Current development methods

Two quotes in this chapter exemplify the two main concerns I have with this book:

• Games are less original that they used to be. The authors explain further down that in a dozen years, graphics have improved a lot, but gameplay not as much. I disagree: with the blooming indie scene, and more and more games being made every year, this sentence sounds more like nostalgic bitterness than a constructive remark.
• C++ was considered too slow to be useful for game programming. The authors refer to Michael Abrash and his Assembly skills with so much awe that it gets a bit awkward. I think mentioning Assembly optimizations is worthless, and maybe even detrimental, to a 21st-century introductory book about video games. We have engines and high-level languages now!

Ch17 - Initial design

Tokens are elements of the game directly or indirectly manipulated by the player. Tokenization is the process between game design and implementation. Start with the token interactions and basic state machines, then the token-property interactions, and finally the property-property interactions. Example for Pacman:

Token interactions

	X	X	X
	Pacman death	X	X
	Ghost eaten	X	X

And the state machine for the ghosts.

Token-property interactions

Token	Properties	Hungry	Strong	Eddible	Weak
	Hungry	X	Pacman death	Score++	Ghost eaten
	Strong	Pacman death	X	X	X
	Weak	Ghost eaten	X	X	X
	Eddible	X	Score++	X	X

Ch18 - Use of technology

Game reviewers do not have time, so they give good reviews to the shallowest aspects of games: the graphics, not the mechanics.

Research and development is risky. Why not teaming up with a local university?

Ch19 - Building blocks

A bunch of design patterns useful for game programming. Here's chain of responsibility.

Observer:

Below is State:

Strategy:

And finally, Template:

Ch21 - Development

• Plan for reuse
• Document
• Design then develop
• Schedule ad communicate
• Catch mistakes as you go
• Limit R&D
• Know when it is good enough
• Team ownership/"invisible" management
• No feature creep
• Team solidarity

Game modes and MVC, part 2/2

This article follows a high-level architecture overview of two pygame projects. In this article, I show why it is difficult to engineer a game in modes when following MVC, and suggest two ways of solving the problem, detailing their pros and cons.

MVC and modes: cross-cutting concerns

-	Menu mode	Game mode
Models	None	World, Inventory
Views	MenuWidget	WorldRenderer, HUD
Controllers	MenuController	CameraController, HUDController

MVC vs modes

In the previous article, I showed two veteran pygame developers using two different techniques to implement modes in their game. Shandy Brown uses a main controller (view) that relays events to its sub-controller(s) (sub-view(s)), so that when the mode changes, only the sub-components inside the main controller (view) change. The event manager is still sending events to the same main controller (view). This approach starts with MVC as a basis, but mode switching has to be implemented in both the controller, the view, and possibly even in the model. In short, the logic for switching between modes is scattered in each of the MVC components. This is called a cross-cutting concern.

On the other hand, Joe Wreschnig first assumes a state machine to handle the game modes. Then, in each mode, there may be an MVC. This is just another way of looking at the previous cross-cutting concern: each mode has to implement an MVC. There is an easy object-oriented answer: a Mode abstract class, with a list of models, views, and controllers as attributes, such that when a mode is created, it directly starts with an MVC structure. But now we have coupled the mode logic to the MVC logic, and this tangling is typical of cross-cutting concerns.

And this is how we end up with two ways to look at the same problem: either per MVC component (horizontally in the table nearby), or per mode (vertically in the table).

Any silver bullet?

I'm not completely sure, but I think object-oriented programming can not solve this problem by itself. Aspect-oriented programming aims at answering those problems, and there are some aspect libraries in Python. However, some Python programmers argue that Python is a dynamic language with powerful introspection mechanisms, and this allows for decorators and monkey patching to do the work just fine. I have not tried any of these solutions (although decorators seem quite interesting). Rather, I want to keep my code simple and readable, and I try to mix the previous two approaches in one, aware that there is no silver bullet. Let us look at the pros and cons of each approach.

The first approach involves a central event manager, main model, main view, and main controller. The single event manager makes debugging relatively easy, since all events have to go through a central point. However, since the main view and the main controller forward messages to their sub-components, there is no single point of control in a given mode anymore. There is another advantage of keeping the MVC at a higher level than the mode management: the view implementation can switch at any time in development from pygame to pyglet or panda3d.

There are also disadvantages. The first happens in an event manager with pubsub: let's say the HUD widgets in the view subscribe to the main view for ScoreUpdateEvent. The main view itself must subscribe to ScoreUpdateEvent from the central event manager. When the view changes mode, it should unsubscribe from ScoreUpdateEvent from the event manager, but should still subscribe to tick events. This means unsubscribing happens per event, and not per component. Thus, the view should memorize which events it subscribed to in the previous mode, and unsubscribe from each of them. This is awkward. Another architectural problem shows up when, say, a model component tries to create a controller component. The new controller component will have to subscribe to the model event broker. This is bad: there is a now controller in the model.

In the second approach, the mode state machine is central, and each mode implements its own event manager and MVC. Unlike the first approach, there is a single entity managing mode transitions, which is a good point. Another advantage is that sub-components do not need to unsubscribe from the central event manager: they stay subscribed to their mode's event manager until the mode is killed. But this has the drawback that the mode state machine must subscribe to each mode's event manager to be able to receive events for mode switching. Moreover, each mode now has its own model. For simple menu modes, there is no model, so it's not a big problem. But the config menu may change some values that the game may need to know about. It seems that data can be exchanged between modes only through 1) events, 2) init arguments, or 3) config files. A last disadvantage is the fact that there is no central place where the view is: each mode has a view, so switching from pygame to pyglet will require updating all the modes.

Conclusion

After giving a try to the first approach, I did not like having to unsubscribe to the event manager. So I went with the second approach: each mode has its own event manager and clock. I think that each mode having its own context is actually a good thing: a game instance should not need anything that is not in a config file or too big to fit as an argument or attribute of an event. For example, if the character selection mode returns the character name as a string, it passes it as an attribute of a GameStartEvent, so that the game instance can determine which character to play with. And finally, to fix the problem of changing from pygame to pyglet, my views exist in their own files, not with the mode's controller or model.

Links

• Using a stack for managing game states
• More on screen stacks
• Shandy Brown's MVC tutorial
• Joe Wreschnig's Angry Drunken Dwarves
• AOP libraries for python
• Python code for a view brokering events to its sub-components

Game modes and MVC, part 1/2

Following a previous article about MVC and event managers, I look at how two veteran pygame developers are using MVC and/or event managers, in particular with respect to switching between modes (e.g. menu vs game vs config).

Example 1: Fool The Bar

In Fool The Bar, an MVC tutorial by Shandy Brown last updated in 2011, a central event manager publishes all the events it receives to the model, the main controller, and the main view. There is a pub/sub in place, but all components subscribing to the event manager receive all the events. The GameStartRequest event is used to switch from the main menu mode to the game mode.

The main controller subscribes to the event manager for all events, and forwards all of them, except the events like GameStartRequest that cause mode changes, to its single current subcontroller. Thus the subcontroller does not subscribe to the event manager, but only publishes to it. And when a GameStartRequest event is fired, the main controller switches its subcontroller from SimpleGUIController for the menu, to MainBarScreenController for the game.

Each subcontroller has its own input mapping. When the SimpleGUIController is active, if the user pushes the DOWN arrow key, the controller fires a GUIFocusNextWidgetEvent. When the MainBarScreenController is active, in game mode, pushing the DOWN arrow key does not fire any event.

Similarly, when the main view receives a GameStartRequest from the event manager, it switches from the menu mode to the game mode. But when the main controller has only one subcontroller active at a time, the main view can have multiple subviews active for one mode. For example, the game mode requires both the MainBarScreen (where the game is displayed) and the MainGUIView (where the HUD with score and possible actions is displayed) to be active at the same time. Thus the main view acts as an event manager for its subviews: subviews subscribe to the main view, and the main view relays events from the event manager to its current subviews. When the mode changes, the main view kills all its current subviews, and instantiates the new subviews.

Example 2: Angry Drunken Dwarves

Angry Drunken Dwarves is a 2004 falling-block puzzle game by Joe Wreschnig. It does not really follow MVC: instead of having distinct models, views, and controllers, modes simply stack up on top of each other. For example, when the player pushes the "Play a game" button, the button's callback stacks the character select mode on top of the main menu mode. When the player has selected a character, the character select mode returns with the selected character, and the callback starts the game mode, passing the character in argument.

Each mode instantiates its own event manager, but unlike Fool The Bar, the event manager is directly polling pygame.events for keyboard or click events. When a component decides that the previous mode should be brought back, such as when the game is over and the main menu should be brought back, that component sends a QuitEvent to pygame.events.

Event managers and MVC - part 2

I wrote about MVC and event managers in January. Here's more!

Ordering of tick events in the game loop

A traditional game loop follows roughly this pattern:

• process inputs on model (keyboard, mouse, network rcv)
• process tick on model (update each entity and the world)
• tick the renderers (graphics, sound, network send)
• eventually wait for next frame, and repeat

Problem: Let's start with a simple event manager that does not make any difference between the inputs, models, or renderers. In other words, the event manager has no clue about MVC. Then, two annoying things happen. First, and most importantly, the event manager could publish a tick event generated by the clock to the model first, to the controllers second, and to the views last. It's as if we were running a different loop: tick the model, process inputs, and render. Since inputs need a whole frame to be processed on the model, the controls may feel laggy to the player (33ms lag at 30 FPS). This is terrible in twitch games like FPS or fighting games. Second, the dispatching of events could be non-deterministic: in one frame, controllers are ticked first, while in another, models are ticked first. The lag to process player commands would be random, and they may not be able to adapt to it.

Solution: We need an event manager that follows the game loop described above. Poll the controllers first, and send the events they generate right away on the model, views, or other controllers that subscribed to those events. Then tick the model and publish any resulting events right away. And finally, send the tick event to the views.

Implementation: the original simple event manager had a dictionary mapping each event type to a list of callbacks. The simple event manager was not differentiating between tick events and other events. Now, we need to distinguish between tick and non-tick events. And for tick events, we must distinguish between controllers, models, and views. This results in a set of controller callbacks, another set of model callbacks, and a third set of view callbacks for the tick events, and the usual dictionary mapping each non-tick event type to a list of callbacks.

Events that generate new subscribers

Problem: We're sending a tick event to the model. The model happens to create a new creature in the game. Let's say that the data of this creature needs to be updated every simulation step, so it should subscribe to the tick event as a model. However, the event manager is currently iterating on the set of model entities currently subscribed to be ticked. And in Python, when a set is iterated on, it can not be modified. I'm also guessing that lockless sets do not belong to the standard library of most programming languages, so this problem may not be unique to Python.

Solution 1: Before starting to process the tick event on the models, make an empty set. This set will store the callbacks of each model entity that started to subscribe to the tick event during this current frame. So we call this set new_callbacks. Our newly-created creature will be put in that set by the event manager when it subscribes to the tick event. When the event manager has finished iterating on the usual set of model entities, it makes a copy of new_callbacks, and replaces new_callbacks by an empty set. Then, the event manager iterates on the copy set, ie our new creature. If the creature spawns 3 minions at the first tick of its existence, the event manager will store the 3 callbacks from the minions in new_callbacks. Then, when the event manager is done with processing the copy, it adds the copy's callbacks to the usual set. Then, it replaces the copy by new_callbacks, and ticks the 3 minions. This can go on until both new_callbacks and the copy set are empty. Then, all old and new models have been ticked. Below is the output I'm expecting:

Created controller
Created model
Created view
---- Clock tick 0
Ticked controller
Ticked model
Created boss
Ticked boss
Created minion
Ticked view

The code does not exactly output this: the view is ticked before the boss is created. Oh well ... :-)

Solution 2: Solution 1 involves 3 sets and is quite convoluted, but there is simpler (and more dangerous!): using a data structure that is not locked when iterated on. In Python, this means using a list instead of a set. However, it's not the perfect data structure for the job: if an entity happens to subscribe twice to an event, the entity will receive the event twice. Most likely, your entities only need to be ticked once per frame, so if a bug causes an entity to act twice faster than expected, you'll know where it might come from. That's why modifying a list while iterating over it is not recommended.

Bots for load-testing

A list of MMOs, MOBAs, and FPS games that have been load-testing using bots.

TERA

Koo, 2010, How to support an action-heavy MMORPG, slides

Their system to load-test a shard is called Sisyphus, and runs 1500 clients per machine. The behavior of the bots is based on the behaviors from real players (probably from alpha). A WAN simulator is used between bots and realm servers; the average latency is set to 200ms. A high-performance machine and a "dedicated line" were needed.

EVE

Press, 2011, Orchestrator: A post-mortem on an automated MMO testing framework, slides

EVE started to make a thin client from its game client in 2010. Orchestrator is the tool they use to load-test and integration-test their architecture and code. Orchestrator does not send one script to each client, proxy, and server. Instead, it runs a single master script, and tells them, as they progress in the test, what the next operation is. The test can be stopped right when a client reports a bug, not until everything scheduled has been sent.

OpenSim

Lake, 2010, Distributed scene graph to enable thousands of interacting users in a virtual environment, paper

The limitations we have encountered with avatar scaling during these experiments have been in getting enough hardware to generate the load of over 1000 clients and the limited physics simulation capabilities of a single thread on the scene server.

League of Legends (allocating games to servers)

Delap, 2010, League of Legends: Scaling to millions of ninjas, yordles, and wizards, video + slides

• Load-testing in a realistic setup: more than 50 machines with the same spec as those in production
• EC2 is a good tool, but the network is not reliable, so careful not trying to fix problems that only happen in the test setting.
• With thousands of clients, logs may not be the best way to gather test results.

League of Legends (chat)

McArthur, 2011, Building the chat service for League of Legends, slides

Dozen of EC2 machines, each running 5-9k bots. Each bot is an XMPP chat client (they used the Smack API). Load-testing is useless without proper modeling.

Crysis 2

Hall, 2011, A Programmer's Post-mortem Crysis 2 Multiplayer, slides

They wanted to check the frame rate with lots of moving entities, and detect bugs or gameplay issues. They used automatic testing. "Lots" of bots are run for 10 minutes per level to stress-test the builds. The bots do random actions like walking, jumping, or shooting.

Gears of War 3

Weilbacher, 2012, Dedicated Servers in Gears of War 3 Scaling to Millions of Players, slides

Their bots are clients without renderer and user input. They run automated bot matches to check the performance of their server platform. For Gears 2, they used to run 2.5 games per core in 2009. For Gears 3, they run 7 games per core in 2011.

Guild Wars 2

Patrick Wyatt, a lead programmer on Guild Wars and Guild Wars 2, discourages using bots: bot's behavior differs too much from actual users. Instead, he recommends recording live play data, and replay it on the server to fix bugs or check the load.

TERA's free-targetting combat: server-side

In the May 2012 issue of GD mag, Seungmo Koo, the server architect for TERA, wrote about how their studio implemented the server back-end for the game's free-targeting combat system. Some parts of the technical solution described in the article were unclear, or the problems were not obvious, so I filled the gaps by guessing their approach.

Basics

During fights, the player uses various kinds of attacks and skills. For the player, free-targeting means paying attention to the avatar's orientation and position. There is no monster selection like in WoW. Looking at actual gameplay footage, the combat feels more lively, but there is a lot of hit and run.

From a system perspective, free-targeting means the server does not know which enemy the avatar is targeting. Hence, the server has to detect if a skill's volume of effect collides with any of the monsters around the avatar. To ensure quick computation of the collision, the server runs at 60 FPS. These features are similar to traditional multiplayer FPS requirements, except that for security and simplicity, there is no lag compensation running on the client-side. All the computations happen on the server-side. However, for an MMO to reach a gameplay as responsive as an FPS, the client should be able to execute the player's actions immediately, account for lag, and eventually run some of the NPCs. TERA accounts for lag like an MMO: in PvE, NPCs are slow to give players time to react. In PvP, however, players with a lower ping to the server have an advantage.

Game design

Every creature in the game world is made of cylinders. A skill reaches its target when the skill's volume of effect collides with one of the target's cylinders. A skill's volume of effect can be a cylinder (e.g. usual AoE around a target or self), a portion of a cylinder (e.g. rotating attack using an axe), a portion of a cone (e.g. a frontal attack using a spear), and so on.

Since skills may last for some time, they are discretized in two to more than a dozen targeting times, and each targeting time is associated with a particular volume of effect. Each targeting time consists of two phases: a search (read) phase, and an update (write) phase. For instance, using a rotating attack, the avatar spins for 360 degrees in 300ms, inflicting damage during its turn. The first targeting time fires at 50ms: in the search phase, the server searches for a target standing in a particular volume in front of the avatar, and, in the update phase, inflicts that target 200 damage. The second targeting time fires at 100ms: the server searches for a target standing in another particular volume on the left of the avatar, and inflicts that target 100 damage. And so on for the remaining targeting times.

Multi-threading and performance

Task	Example
Timer	Damage over time or NPC AI movement scripts
Region update	Add/remove/update the position of a creature in a region
Creature update	Update HP, status, position of a creature

Each TERA server runs the whole world for approximately 6k concurrent players. The server has a few things to do in the main loop. First, it processes client packets, and generates timer, region, and/or creature tasks from them. That is when the search-for-target phase happens. Then, it executes scheduled timer tasks, which will likely themselves generate region and creature tasks. And finally, it executes region tasks. The update phase happens in the creature tasks, and also in the region task in case of creature movement, spawn, or death events.

To come up with their final design, the TERA engineers may have followed this train of thoughts:

• Problem: an 8-core server running Windows reaches 100% CPU with 3k players. How can this be improved?
• Solution: use asynchronous IO such as Window's IOCP. It automatically creates a task queue for client packets and a worker thread pool to process that packet queue in parallel.
• New problem: The threads spend too much time waiting for locks when trying to read or update region data (e.g. list of creatures in the region, or creature position).
• Solution: Avoid contention by replicating the world in each thread. No lock: the thread searches in its own version of the world.
• New search-phase problem: When executing a region task, the region data of a particular thread becomes inconsistent with other threads.
• Solution: The thread pushes the region tasks it generates into a queue shared between all threads, so that each thread processes all the region tasks. As an example, when an 8-core server receives a client movement packet, one thread processes it and generates (for instance) one region task from that packet. The thread pushes this region task to the end of the queue with an execution counter of 8. Each of the 8 threads processes the task queue at its own pace. When a thread processes a task, it decrements the task's counter. When the counter reaches 0, the thread deletes the task from the queue. Hence, the task mentioned above will be removed from the queue when all the threads have processed it.
• New update-phase problem: frequently updating a particular creature causes lock contention.
• Solution: The world replica of each thread stores creature pointers. When a thread processes a packet or a timer task that results in a creature update, it pushes the creature's function to run (e.g. Creature.receiveDamage), with particular arguments (e.g. 200) to that creature's task queue. If the creature task queue is currently being iterated over by another thread, then the current thread returns to what it was doing before (e.g. main loop). Otherwise, the current thread iterates over the creature's task queue. The queue starts with the task the thread just pushed, but other threads may push tasks to the queue while the current thread is processing its task. The current thread will process those extra tasks too, until the queue is empty. Then, the thread will go back to its main loop. Hence, creature tasks are executed asynchronously; getting a return value for the task execution requires the active object pattern.

The resulting high-level architecture is something like the following:

Questions

Seugmo replied to my original questions (see the comment below); here are some more!

• How much CPU is caused by packet processing? How much does the CPU increase when 1000 players gather together versus when players are homogeneously scattered?
• When lots of creatures gather in the same region, the search phase (happening on only one thread) may consume a lot of that thread's CPU. Could the search phase happen faster if the regions were smaller? Could it happen faster if the regions were using Binary Space Partitioning?

Spline: Locales and Beacons - Barrus 1996

Locales and Beacons by Barrus et al in 1996

• Locales are regions of the world containing objects and split statically by designers. Locales can be children of another locale. Ex: car locale contains rear-view mirror + tires + ..., and the car's parent locale can switch from garage to street.
• Absolute object positions in the world are obtained by converting their position in their locale's frame of reference into the world's locale by a series of transformations between locales. Ex: make a locale neighbor of itself using a reflection transformation gives a mirror effect.
• A locale is run by only one server, and users in that locale belong to that locale's multicast address. Objects push updates to their locale's multicast.
• A beacon maps a tag to a locale's mutlicast address. A beacon is handled by its beacon server (not a locale server). That beacon server is found by hashing the beacon's tag.
• Beacon usages:
  • If someone creates a part of a virtual world and wants other people to visit, he can mark the area with a beacon and publish the tag.
  • Private tag only seen by people in the object's locale; people that run into the beacon can subsequently keep track of it no matter where it moves. Useful to follow an object across locales.
  • Someone who wants to provide a service can publish a tag, without creating a beacon. For example, suggest the tag "car", and car-makers tag their cars with "car". All the cars are addressable from that beacon's multicast.
• Demo: Tour Diamond Park

Scalability for Virtual Worlds - Gupta 2009

Scalability for Virtual Worlds, Gupta 2009

• Clients run the logic. Since server is only used for persistence and message forwarding, it can handle more clients.
• Problem: weak clients may not be able to execute all the updates they receive in a timely manner. Solution: action-based server-side IM: find the read/write sets each action impacts (transitive closure of the following actions), and notify concerned clients to rollback.
• Clients apply local actions to an optimistic model, and apply remote actions to a stable model. When applying the same action to optimistic and stable models, and the resulting models differ, need to rollback: the client asks the server to broadcast a fix it proposes. All other clients execute the fix, and if they conflict, send their own fix.
• Problem: solving long chains of conflict resolutions takes bandwidth and time. Solution: reject fix messages that cause a chain longer than a certain threshold.
• Experiment: 64 client machines running 1 bot each, moving every 300ms. When a bot collides into walls or another bot, it switches direction (more walls = more time to execute collision detection, more bots = more frequent conflicts). 1 server machine. Emulab with average latency between 2 machines of 238ms. Java.
• Good: Collision detection takes 7ms per action, while computing an action closure takes 0.04ms. Hence, a traditional server executing the logic lags after 30 bots, while the simply-forwarding server lags after 3000 bots.
• Bad: at least 20% extra bandwidth compared to server with logic. Drop 10% of actions to break long closure chains if bots are clustered together and move fast.

Scaling League of Legends

Notes from a 2011 Qcon talk about scaling the non-gaming server side of League of Legends. They are not worried about persistence during a game, but rather in the match-making, lobby, or store. They have soft real-time requirements: not the order of 10ms, more the order of a few seconds. [Twitter and Facebook are soft RT too]

Scaling

Scalability: it's easier to constrain what the logic developers are allowed to do, than to define what they are not allowed to do. Examples: Map/Reduce is a whole paradigm (you have to make your logic fit into a map() and a reduce()), NoSQL's unstructured data is a double-edge sword (you lose the ability to join, but queries come back faster), and when you're partitioned, you pick to be either atomic/consistent or available

46:50: Scaling should be dynamic/elastic; you need cluster recomposition and stateless growth patterns. Hence the system should be dynamically configurable. On the fly, you should be able to adjust the thread pool size, add/remove roles to machines, and switch logic or system algorithms.

Food for thought: list all the benefits/tricks a load balancer can provide to your system.

Caching

Caching provides flexibility: failovers, distribution of workload (hot code updates or restarts). Coherence is a distributed cache used between Hibernate and the DAO layer as "cache-through". If the DAO asks Coherence and there's a cache miss, then Coherence asks Hibernate (itself using a Coherence cache, or calling MySQL over the network if cache miss).

24:00: How to be sure that cache and DB are consistent? Do not cache! Query the DB directly, latency of few sec is OK for soft RT.

11:30: Serialize the work, not the data. It's faster to serialize the work to the data, than to unserialize the data, work on it, then serialize the result. Avoid moving the data all over the network towards where the process is. It's also easier to distribute the work to all the DB nodes than to send to/receive from all the nodes.
The objects sent on network between server and DB should be small: if you have to edit only one field, you should not have to send a big object of 1MB.

Logging and Testing

42:30: They log each function call with how long it took; overhead of 1% performance, but huge value if able to graph/plot the logs. Compare the average call duration in the last few minutes to the usual average to detect problems.

17:15: Keep in mind that the code will be used/executed in a data center, not on your laptop. 51:25: They use EC2 for load testing. 1000 threads per node, each thread simulating 1 user. Realistic because not all clients (threads) are same speed in real-life, and EC2 network is not always the best/reliable. It's not the most performant, but it looks like a quick-and-dirty way to load test. One of their scale testing environment has more than 50 machines.

Event Manager and MVC

After mentioning MVC a few times, I've stumbled, like many others on Sandy Brown's pygame guide. The guide contains three parts: MVC for single-player games, using Twisted for multiplayer games, and GUI widgets. You can also find the code on github.

Event Manager

The problem: Multiple heterogeneous components, say the network controller and the model, are interested in an event such as a user click from the input controller. The code in the input controller would look like this:

nw_ctrler.send(click)
model.perform(click)

If a new component, say the audio output, becomes interested in user click events, then the input controller code has to be modified. This is not ideal.

Two design patterns exist to help us here: the observer and the mediator. The differences between the two are very subtle , but combining the two allows 1) the possibility to add or remove components from the system without touching the other components, and 2) a component to notify all the others through an intermediate. In our case, an Event Manager is the intermediate receiving events from all components, and notifying those interested in that event. See the diagrams below from Sandy Brown's guide.

Improvements

A stackoverflow post remarked that isinstance() is not quite Pythonic : instead of using isinstance(), one should appropriately use duck-typing.

Moreover, listeners should tell the Event Manager which events they are interested in, so that they are not notified for all of the events.

Panel on MMOs from Netgames 2011

Panel at NetGames 2011 about the future of MMO research.

Cheating (no control of the client-side) and performance (weakest node performance conditions the other nodes' performance) are issues in p2p architectures. I could p2p when I play with friends, but not competitively. Even with friends, the developer has no control over the network, NAT traversal problem. Potential solutions: match-making on server, then one peer hosts the game. If host disconnects, the game migrates to another peer. Problem: how to partition and replicate the game world between peers?

How to integrate scaling into game mechanics?

Researchers can get data from companies if they show that it is worth the company's time (taken to fetch and anonymize data).

Problems shared across p2p, client-server and cloud architectures: scalability, cheating, latency, concurrency, synchronization, and replication.

Using the cloud is cheap for small user bases, but very expensive for very large user bases.

Casual Connect and GDC Online are industry conferences that also deal with network and system support for MMOs. But they're expensive.

MVC for games

Second thoughts on MVC (following a first article about the use of MVC by game developers). Let's assume that the user inputs are first caught by a controller, and a view is displayed to the user at the end. What are the communication possibilities in-between?

Vanilla MVC

As seen on Wikipedia, the theoretical 'vanilla' MVC refers to an architecture where the controller updates the model, then notifies the view, which in turn fetches the data to display from the model.

Application for games: the system is event-based: it is only awakened by the actions of the user. If the world has NPCs, they can not act independently of the user. It may be OK for turn-based games like Chess, but not so much for games with living worlds like Morrowind or Harvest Moon.

Web MVC

In web development, the "logic" is often split into multiple controllers. To determine which controller the user's action is targeted to, web frameworks such as ASP.NET or Spring use a front controller pattern. The front controller maps URLs to actions to execute (and which controllers to call). I'm not entirely sure, but compared to the vanilla MVC, it seems that the (front) controller is now giving the model to the view, instead of having the view fetching the model by itself. Therefore, the model to be displayed is carried from M to C, and from C to V, twice more data going around than in vanilla MVC (where it used to be moved only from M to V).

In games, the model can get quite large, and moving it around can get costly. It would not be so costly if only resulting differences to the model (instead of the whole model) were exchanged, but it depends on the modernity of the rendering. Alpha compositing makes it possible to render variations of the game state (ie the model) by layering image elements. Many games/game frameworks such as pygame still use bit blitting, which requires to erase and reprint the whole screen.

Game MVC

This nice article about MVC for games explains:

• The controller handles the input and flow of the game logic. This is akin to the states your game can be in. My primary two controllers are main menu controller and an in-game controller. They are responsible for converting input into something the game world (model) can understand. Eg "Create unit x at base y".
• The model handles all game logic. It has nothing to do with input, rendering or networking. It is a pure view into the game world. Designers need only worry about what’s in the model.
• The view DOES know about the model. The [view] has read-only access to the model. This model can be anything. For my main menu it’s a list of UI controls the controller has built. For the in game view, it’s the game world. Rather than "reusing views in different controllers" what is more important is "having multiple views on a single controller". For example there might be a 2D and a 3D view of the game world.

What is still missing from the picture is the game loop. In games, the model is rendered by the view 60 times per second, and the inputs of the user are processed at the same frequency. As mentioned in the quotes above, some component, be it a controller or something else, still has to determine which view should be active at any given frame, and which controller it is associated with.

Links

• Organizing the game code to fit MVC (Stack Overflow)
• Is MVC used in commercial games? (Stack Overflow)
• MVC in game dev (TIG source)
• Design patterns for games from Zach Simpson's 1998 GDC talk

MVC and game developers

MVC in software engineering

The model stores data, and runs domain-specific logic. An example of domain-specific logic in the banking domain is if customer's account is below zero, refuse withdrawals. The view gets data to display from the model. Some MVC have the view pull data from the model itself, others have the view notified by the model, and others have the controller tell the view to update itself. The controller receives and converts user inputs in actions understandable by the model. In web development, such as ASP.net or Java servlets, the controller picks which view is going to be displayed, and then the selected view is actually in charge of displaying information on the screen. If this description is not clear enough, the wikipedia page about MVC has a scenario that helps explain how the model, view and controller fit together.

MVC in games

Many amateur game developers say ideas from MVC can be applied to games but in general it is just a waste of time. For many, there is no such thing as game architecture: The only difference with classic MVC is that in a game, the graphics data, logic and game algorithm is fused together. Others argue that in a rapid prototyping context, where iterating is key, one should not waste time conceiving a modular/maintainable system, but rather focus on testing the game as fast as possible.

Many non-indie games are made with MVC in mind. Splitting data from presentation induces extra work on the code and managing slightly more objects in memory. However, this is exactly what allows an easier testing and debugging of mechanics, UI, and network components. In fact, MVC has been applied to game programming since at least 1998. A blogger at TigSource states that MVC can be applied in any part of a game. Taking the example of a network connection: The input view in this case is a network receiver running in it's own thread and listening for data from a socket. When the view receives data, it's translated into an internal class and sent to a controller for processing.

Middle ground

I find that explicitly implementing an MVC pattern for the network connection is a bit of an exaggeration. Heads-up displays and other UI input perfectly fit as controllers, and are naturally decoupled from the model. On the other hand, there is a strong tendency by many game developers to ignore software engineering practices. Some even put forward the Extreme Programming side of rapid prototyping to justify their ignorance of any architecture. Agile methods do not contradict the use of any architectural pattern.
That may explain why so many of pygame's projects contain a single file with thousands of lines of code ...

Scalability definitions and milestones

Definitions

Scalability is a major technical focus for MMOG, but there are actually many different meanings and assumptions hidden behind the word. In general, Scalability is the capability of a software system to be adapted to meet new requirements of size and scope (Taylor et al. p467).

For system and network engineers, scalability can be achieved in two ways: horizontally (load balancing and clusters of multiple computing resources) or vertically (adding more power to a current computing resource). In both cases, if any of the layers of the stack (hardware, database, application and so on) does not scale, then the whole system won't.

For software engineers, a system scales well if its rate of growth is not greater than the corresponding rate of complexity increase (Taylor et al. p468-474). This definition looks a lot like positive scalability in system and network. However, software architecture scalability also deals with adding new components and takes into account the dependencies between components and connector logic.

Milestones

To my mind, there are so many definitions of scalability that it makes more sense to talk about domain-specific metrics meaningful to the end-users and stakeholders. The number of users is a perfect example. So here is a list of situations illustrating different meanings of scalability with different numbers of users.

Configuration	System/Example	Scalability meaning
Scalability milestones reached so far
2 or more players sharing the same game world state	Game development platforms such as Unity have quite hard times providing a transparent interface to sharing game world state. Each object in the world has to explicitly contain a Network View for it to be sent to other players.	Being able to send all relevant game objects to other players without the hassle of having to add a networking layer on top of them.
From 40 to 100+ users in the same world	Throughout 2009, Intel has worked on scaling OpenSim. They noticed that the number of users (as well as the number of object prims and scripts) were independent of the number of hardware threads available. This meant OpenSim could host no more than 100 clients, even if more resources were added.	Scalability was achieved through an impressive cleaning and optimization work from both software and netsys engineering perspectives. Adding a server to the back-end means being able to handle more users (thanks to an inter-shard daemon mechanism of some sort). There is still a problem, though: if everyone goes on the same shard, the shard crashes. Sharding originally comes from the database community. It has been applied to the software architecture of military simulations in 1995: 1000 users can be supported simultaneously. Current MMOG architectures still cut their world in maps (shards) to be able to use this principle.
Inter-server events	Cross-realm pick-up groups in WoW. Opensim's hypergrid foreign user information stored locally and non-persistently on remote servers.	In this case, scalability sounds more like portability and data compatibility (as the number of users involved stays relatively small). Also, an extra layer of logic can be added: in WoW, experienced players can be grouped with novices so that cross-realm groups are more balanced. But ... on which server shard(s) are these instances stored and computed?
Cloud gaming (Gaikai or OnLive)	Streaming video to computers that do not have enough graphics power to run the game themselves	A pure example of horizontal scalability: more computers in the cloud means more users.
Scalability milestones not reached yet
1000 players seeing and interacting with each others	Giant boss battles, live events, voting in Parliament	1) Clients must still be able to compute the graphics and 2) the server has to be able to cope with the sudden and unusual overload (dynamic resource re-allocation? Hybrid architectures mixing P2P and client-server?)
Cloud gaming for MMOG	Cloud gaming NOT as a service on top of existing gaming infrastructures, but as a graphics help for weak clients of an MMOG	Some MMOGs have high-end graphics. And there is always a server doing various computations. In the end, the overall architecture would approach something like: weak client <-> "middlebox" shared with a few other weak clients for the graphics <-> game logic server. But this naive method consumes a lot of resources and can certainly be optimized. It sounds a little bit like booster boxes.
10.000+ players seeing each other and interacting with some	Stadiums, French demonstrations	For the server, scalability means 1) being able to distinguish who can interact with who, 2) allocate resources dynamically (as these events are temporary and can be spontaneous) and 3) approximate distant actions and determine which clients share the same content locally so that some computations can be factorized. For the client, graphics might get demanding.

List of conferences and journals

Based on the ACM library and several links, here is a list of current conferences, workshops and journals dealing with games. It is not totally complete, but covers a wide spectrum: from software engineering, databases and networking (tech) to game design (GD), sociology and anthropology (soc), game studies and humanities (hum), and arts (art). Also, some acceptance rates have been collected by professors for the areas of computational intelligence, networking, software engineering and database.

Name	Full name	Rate	Domain	Notes	Society
DIMEA	Digital Interactive Media in Entertainment and Arts	-	tech	2008, incorporated into ACE	-
DISIO	DIstributed SImulation & Online gaming	-	tech	workshop	ICST
FSE	Foundations of Software Engineering	18%	tech	also named SIGSOFT	ACM
GDC	Game Developer Conference	-	tech|GD	industry-oriented	GDC
Globe	International Conference on Data Management in Grid and P2P Systems	-	tech	-	-
ICSE	International Conference on Software Engineering	14%	tech	-	ACM/IEEE
IJCGT	International Journal of Computer Games Technology	-	tech	-	Hindawi
IMSAA	Internet Multimedia Systems Architecture and Applications	-	tech	-	IEEE
MMVE	Massively Multiuser Virtual Environments	-	tech	workshop	ACM
MMTA	Multimedia Tools and Applications	-	tech	2010, online journal	Springer
NetGames	NetGames	40%	tech	2008, 2009, 2010	ACM
NIME	Networking Issues in Multimedia Entertainment	-	tech	workshop	IEEE
NSDI	USENIX Symposium on Networked Systems Design & Implementation	19%	tech	part of SIGCOMM	ACM
OOPSLA	renamed into SPLASH	27%	tech	see SPLASH	ACM
P2P	Peer-to-Peer (IEEE)	20%	tech	2008, 2009	IEEE
P2PNVE	Peer-to-Peer Network Virtual Environments	-	tech	2008, 2009	-
NOSSDAV	Network and Operating System Support for Digital Audio and Video	37%	tech	workshop, paper list	ACM
SIGCOMM	Special Interest Group on Data Communication	10%	tech	paper list	ACM
SIGMM	SIGMM conference on Multimedia systems	17%	tech	-	ACM
SIGMOD	Special Interest Group on Management Of Data	20%	tech	-	ACM
SPLASH	Systems, Programming, Languages and Applications: Software for Humanity	27%	tech	used to be OOPSLA	ACM
TCIAIG	Transactions on Computational Intelligence and AI in Games	-	tech	-	IEEE
TOMCAP	Transactions on Multimedia Computing, Communications and Applications	-	tech	-	ACM
TOIT	Transactions on Internet Technology	-	tech	-	ACM
TOSEM	Transactions on Software Engineering and Methodology	-	tech	-	ACM
VLDB	Very Large DataBase	-	tech	archives	ACM
VRCAI	Virtual-Reality Continuum and its Applications in Industry	-	tech	-	ACM
Name	Full name	Rate	Domain	Notes	Society
ACE	Advances in Computer Entertainment Technology	-	tech|soc	conference that gets published in CIE, EntCom and IJART incorporates NetGames and DIMEA 2007, 2008, 2010	ACM
CIE	Computers in Entertainment	-	tech|soc	journal, paper list	ACM
CIG	Computational intelligence and games	49%	tech	2010	IEEE
CGames	CGames	-	tech|soc		IEEE
EntCom	Entertainment computing	-	tech|soc	journal	Elsevier
FAG	Fun and Games	36%	tech|soc|GD	biannual	ACM
FDG	Foundations for Digital Games FDG	30%	tech|soc|GD	conference and workshop papers	ACM
GIC	Games Innovations Conference	-	tech|soc	papers	IEEE
IGIC	International Games Innovation Conference		tech|soc|GD		IEEE
ITS	Internet Technologies & Society	-	tech|soc	-	IADIS
VR	Virtual Reality	-	tech|soc	-	IEEE
Name	Full name	Rate	Domain	Notes	Society
DiGRA	Digital Games Research Association	-	soc|hum|GD	library, biannual?	DiGRA
Eludamos	Eludamos, Journal for Computer Game Culture	-	soc|hum	online journal, biannual	-
FM	First Monday	-	soc	online journal	self-pub
GAC	Games And Culture	-	soc|hum	online journal, long review process	SagePub
Game studies	the international journal of computer game research	-	soc|GD	online journal, once or twice issues per year	-
IJART	International Journal of Arts and Technology	-	art	-	Inderscience
JGVW	Journal of Gaming & Virtual Worlds	-	soc	online journal	Intellect
JVWR	Journal of Virtual World Research	-	soc	online journal	self-pub
Loading	Loading... the Journal of the Canadian Games Studies	-	soc|hum|GD	online journal	-
SAG	Simulation and Gaming	-	soc	online journal	SagePub