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.

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.

Netgames 2005

Summary of selected papers from the NetGames 2005 conference.

Traffic Characteristics of a Massively Multi-player Online Role Playing Game, by Kim et al.

• Port mirroring through 1Gbps hub and tcpdump of 92 hours of a Lineage 2 server in December 2004. TCP packets.
• Both upstream and downstream increase linearly with number of concurrent users.
• Play session duration: 3 hours average, 26 min median, 40+ hours 99%

Stream	Number of packets	Ratio of data packets	Payload (avg, median, and 99%)	Bandwidth	Bandwidth per user
Upstream (clients to server)	6.28 billions	23% (the rest are ACKs, SYNs, or FINs)	19, 20, 50 bytes	max 9 Mbps	1.6 kbps
Downstream (server to clients)	6.43 billions	98%	318, 161, 1459 (= MTU) bytes	max 140 Mbps	20 kbps

Dynamic Microcell Assignment for Massively Multiplayer Online Gaming, by De Vleeschauwer et al.

• Divide the world in atomic square microcells. Compute each microcell's load induced by processing player actions (weight=1), forwarding player actions to neighbouring cells (w=0.05 if cells on same machine, w=0.1 if cells on different machines), receiving forwarded actions from neighbouring cells (w=0.2, w=0.4), and moving players to and from neighbouring cells (w=3, w=15). Then, assign cells to servers so that no server has a higher load than another server.
• Algorithms to assign cells to servers:
  • Greedy: processes cells in descending order of their load, and assigns them to the server currently with the lowest load. Pro: fast. Con: does not take locality into account.
  • Clustering: start with each cell is a cluster. Merge two clusters that have the lowest load until there are as many clusters as servers. Con: in the last few steps, some heavy-load clusters are merged and may be assigned to servers that can't handle them.
  • Simulated annealing: start by randomly assigning cells to servers, then randomly swap or move cells around to find a better solution, and keep iterating to refine the solution. Able to find very good solutions if the initial solution comes from another algorithm.
  • Integer linear programming for the optimal deployment. Pro: optimal. Con: takes days to compute, but a timeout can be specified to get a suboptimal solution. (But then, other algorithms give better results faster).
• Evaluation: If player hotspots are spread randomly, the maximum server load can be reduced by 30% compared to the baseline with one large cell of constant size per server. But if hotspots are regularly spread, and there's as many hotspots as available servers, then the microcell algorithms are at least 10% worse than the baseline. In general, simulated annealing starting from a greedy solution was the most efficient of the algorithms.

Netgames 2004

Implementation of a service platform for online games, by Shaikh et al.

• How to provision a cloud infrastructure hosting games
• Each bot sleeps periodically to reduce CPU load and instantiate more bots. Bots connect to the game server according to a Poisson process with mean inter-arrival time of 1/λ=1s
• TIO polls game servers at regular intervals for their CPU load using SNMP. Using the raw CPU leads to occasional over-provisioning and higher costs, but using a moving average to smooth the CPU estimate misses CPU peaks and may result in inefficient QoS for some players.
• Since player load follows daily and weekly patterns, it's possible to anticipate the peaks; in that case, provision slightly ahead of the peak and keep a smoothed metric.
• Relevant metrics other than CPU: "slack time" = unused time during an iteration of the server loop

Zoned federation of game servers: a peer-to-peer approach, by Iimura et al.

• DHT implementation is Pastry. It uses SHA1 to map a game zone to its owner and runner.
• Experimentation with 296 P3 1Ghz 512MB, all connected to a single 100Mbps switch. 295 machines run from 100 to 1,000 members, and a single machine runs the zone owner. Time taken to update the state of everybody is exponential with the number of zone members (average of 50ms for 500 members, 100ms for 700, 200ms for 1,000).
• Spreading users uniformly on multiple zones, each with a single zone owner, reduces the load.

Scalable Peer-to-Peer Networked Virtual Environment, by Hu and Liao

• Scalability implies that nodes can be added or removed on the fly while keeping the whole system functional. Ultimate P2P goal: adding a node should increase overall system resources without consuming centralized resources.
• Cut the virtual space in Voronoi cells, where each user is at the center of his cell (deterministic algorithm). Each user connects with at least all his Vornoi neighbors (min 3, average 6, max n-1), and with more users if they are in his area of interest. Each time a user joins, moves, or leaves the game, his neighbors have to recompute their Voronoi diagram.

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.

MVC and modularity

More on the MVC pattern.
I wrote in September 2011 about which type of MVC would be more appropriate to make games, but this was all quite abstract. Here are more concrete thoughts, after having had to implement it myself using Pygame. But first: a diagram!

Main loop

Pygame provides a ticker that regulates the game loop with a 10-ms precision. The elements that need to be awaken by the game loop are colored in pink on the diagram above. In more details, they are:

• Mechanics: Some events independent of the player have to be triggered at some points. For instance, the screen could turn red after 5 minutes in a scenario, the player's money could generate interest every 10 seconds, or monsters' AI needs to process the game state to determine what to do next every 50ms in fight mode but every second in idle mode. That's why your mechanics have to be called every loop iteration.
• Renderer: In Pygame, this corresponds to blitting sprites onto the screen, and then flipping the screen, and/or playing sounds. With the architecture displayed above, the frame rendering rate (say, 60 FPS) is independent of the main loop frequency (say, 100 iterations per second). This is useful for machines with a decent CPU but a weak graphic card because the view could be configured to refresh the screen only 30 times per second, but the logic could still run at 60 or more iterations per second. But there's more! since the renderer accesses the game state, it can determine if the load is going to be too heavy with 30 fps, and decrease the frame rate gracefully without having to slow down the mechanics or input controller.
• Input Controller: events such as clicks or keys pushed are processed one after another during each loop iteration. The input controller then sends a translated version of these events (e.g. 'Q' stands for stop the game) to the Main Controller (e.g. MainController.stop_game()).
• Network Controller: events may be sent by the server at any time. The client may also need to send actions to the server at any time. Therefore, the network controller is called every loop iteration. This is done using PodSixNet: ConnectionListener.Pump() for the pulling and EndPoint.Pump() for the pushing. Under the hood, PodSixNet uses asyncore (which apparently calls a normal poll).
  Note: When the network controller needs to send a part of the game state on the network, it calls the Main Controller to return him the data from the game state itself.

Keys vs Clicks

When the player pushes a key, the scenario is very easy to follow:

1. Input controller translates
2. Main controller calls the appropriate mechanics
3. Mechanics update the state
4. Next frame, the renderer displays the state.

The scenario is slightly different for clicks.

1. Input controller receives click type (left/right/middle/both/...) and click position (x,y)
2. Input controller gives the view controller the click type and the position.
3. From the click position, the view controller parses the list of sprite coordinates and dimensions to detect which sprite(s) has been clicked.
4. For each click type, the clicked sprite has a callback to the main controller. This callback was set by the view controller when the view as a whole was created. Hence the solid arrow from view controller to main controller (true dependence), and the dotted arrow from sprites to main controller (blind callback set by another component).
5. Main controller calls the appropriate mechanics, etc.

How good is this?

From the two scenarios above, I see at least two aspects of this architecture breaking the traditional MVC. First, the view is not selected by the controller. Rather, the view looks at the model to know what subview or view mode to switch to. For instance, if I push the escape key, my MainController will ask the model to store it, and the renderer itself will decide what to do with that new information stored, whatever it means for the model.

Second, clicks require the controller to ask the view what those clicks mean. I was at first reluctant to affect the button behaviors dynamically because it decreases understandability. When you read the button code, you don't know what the button is doing at all. In fact, all you see in the code is a raise(NotImplementedError). You have to go look inside the view controller to see what is being affected to that button's on_left_clicked(). On the other hand, the gain in modularity is pretty sweet: you can change the presentation of an object, whether in the HUD or in the game world, independently of its logic. If you want to try another view (say 3d instead of the current top-down 2d), then that new view only needs to provide 2 "services": render() for the main loop, and process_click(pos,type) for the input controller.

Edit 31 Dec, 2011: Just saw this example from Shandy Brown on using the Mediator pattern as a middle-man that views and controllers pubsub to. I like the "loggers as views". However, I'm not sure the clock-triggered events should be in a controller; the model should have some game logic in it.

Netgames 2003

Modeling player session times of online games, by Chang and Feng

• network traces of a popular CS server for a week in April 2002
• 16k user sessions recorded
• 99% of players play less than 2 hours
• play session follows a Weibull distribution with k = 0.5 and λ = 20 (shape similar to 1/x exp(-x))
• For play sessions from 10 to 100 minutes, the chance of disconnecting (ie failure rate) remains constant at 2.5%.
• For play sessions shorter than 10 minutes, 10% chance of disconnecting. Possible reasons: connection problems, kicked out or leave because of server rules (such as friendly fire allowed, but kicked out if you kill your team-mates too often)

A Fair Message Exchange Framework for Distributed Multi-Player Games, by Guo et al.

• Assumptions: independent clocks with no synchronization mechanism, players react to server updates, updates only consist of creation and/or removal of object(s) (and NOT object position updates)
• Users have reaction time to act in response to server update messages. Ignore latency induced by network and only compare user reaction times to determine which update to actually run on the world state.
• the Fair-Ordering Service [...] dynamically enforces a sufficient waiting period on each action message to guarantee the fair processing of all action messages. But practically, the waiting period is bounded to ensure a relative level of interactivity.
• Proxies are game-agnostic and located near players (ie low latency between a player and her proxy). Proxy receives action message from user, then forwards that action message with a message identification number (to deliver messages in order) and the reaction time to the game server.

Causality and media synchronization control for networked multimedia games: centralized versus distributed, by Ishibashi et al.

• Causality control preserves the order of events of game data (keyboard inputs). No need for causality in voice or video
• Media synchronization control = intra-stream (temporal relation between MU such as voice or video packets) + inter-stream (timing among multiple streams) + group (timing among multiple end-points to ensure fairness) synchronization controls
• Compare C-S to P2P architectures in terms of success of the 4 previously mentioned control schemes. Voice and video don't need to go through the server (they're sent in P2P mode in both scenarios).
• Adaptive Δ-causality control used on game data in both scenarios: the recipient considers a packet still valid Δ = 50 ms after its generation timestamp. [That means the latency automatically increases by Δ ms for all packets]. Adaptive means that the value of Δ changes based on the network load. Smaller Δ = game more interactive, large Δ = less packets are discarded for being late/misordered. Unfairness appears when terminals have different Δ, hence need group sync control.
• Piggy-back an MU on the succeeding k=4 MUs to recover from lost UDP packets
• Experiment: two terminals in both C-S and P2P scenarios [only two?!]. Terminal 1 is connected to an overloaded hub with delay jitter, Terminal 2 is connected to its own hub. Connections are 10 Mbps ethernet. Server connected to T2's hub. Additional delay of 100 ms introduced between the two terminals by a data link simulator between T1's hub and T2's hub. Game MUs = 20 Bytes, sent 10 times per second, while voice MUs = 400 Bytes, sent 20 times per sec, and video MUs = 5kB, sent 20 times per sec [hence most of the load on the network comes from voice and audio, not game data]. Experiment ran for 2 minutes.
• For heavy loads (8Mbps), C-S is better for causality, but worse for consistency, fairness, and interactivity.

Bandwidth requirement and state consistency in three multiplayer game architectures, by Pellegrino and Dovrolis

• Compare C-S, P2P and PP-CA (= P2P with central authority/arbiter receiving moves from all players and notifying them when it detects inconsistencies)
• Tu = Duration of client loop, Lu = size of update messages
• CS: client upstream = Lu/Tu, client downstream = N.Lu/Tu, server downstream = N.Lu/Tu, server upstream = N(N.Lu)/Tu
• P2P: client upstream = client downstream = (N-1)Lu/Tu
• PP-CA: client upstream = N.Lu/Tu, client downstream = (N-1).Lu/Tu + f.N.Lu/Tu with f = ratio of inconsistencies to be corrected, arbiter downstream = N.Lu/Tu, arbiter upstream = f.N(N.Lu)/Tu

Access network delay in networked games, by Jehaes et al.

• Look at delays introduced from access networks (aka last mile links), not from back-bone. Goal: how to dimension the network to reach minimum delay possible.
• Network delay can be caused by propagation (mostly only in the case of back-bones though: 5µs/km), serialization (putting all the bits of a packet on the link), packet processing (route and DNS lookups, error correction), and queuing (other packets have to be treated before; differs from packet to packet, hence jitter, defined as 95% percentile RTT - 5% percentile RTT). AND = minimal RTT (packet processing delay) + S (packet size) / Reff (effective link rate) + Tque (total queuing delay in up- and downstream, results in jitter)
• Experiment: for 5 different values of S, throw 100 pings. Get RTT and jitter (= Tque) from 100 pings. Obtain Reff from taking the inverse of the best-fitting trend-line through the 5 points (S, average RTT). Obtain min RTT from the intercept of the trend-line through the 5 points (S, top-1% RTT).
• QoS improves RTT by separating game traffic from other traffics

A Zone-based Gaming Architecture for Ad-Hoc Networks, by Riera et al.

• Assumption: ad-hoc networks are going to multiply, but C-S and P2P architectures are not well-suited for them. Most interesting part of the job is to determine which device can/should be Zone server.
• Even the nodes that do not play the game assist the other nodes in delivering data
• Nodes are mobile: they do not always stay within reach of the same other nodes. Discovery of Zone servers is done through the SLP v2. When latency to a zone server gets too high, a client can pick another zone server, which in turn notifies all the other zone servers of its new connection. When a client does not reply for a while, a zone server can drop it.

A service platform for on-line games

• Middleware as transparent as possible to the game developer. This middleware sits on top of an existing grid infrastructure from IBM called Globus. Globus decides when to spawn a new game server instance based on current resources and demands.
• Player services are in charge of authentication, account handling, chat rooms, locating games/selecting a server taking into account player preferences (e.g. team or region), and actually playing the game.
• Publisher services deal with software deployment and updates, billing, monitoring server performance, service level agreement (e.g. no more than 5% of players suffer from more than 100ms delay)
• System services include resource management and directory services. These services are accessed by the grid provider.
• Clients submit jobs using a format containing the executable, its arguments, and resource requirements. Jobs can require spawning instances at different grid locations (e.g. different regions).
• Various services such as resource informations and information providers (CPU, OS, RAM, connectivity, ...) are indexed in an LDAP. Game-specific services (tracking player stats, server load, ...) could also be added on top of existing services.

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 ...

[Literature] NetGames 2002

Summary of selected papers about MMOG architecture from the NetGames 2002 conference.

Aarhus et al., Generalized Two-Tier Relevance Filtering of Computer Game Update Events.

• Two-tiered means network communication is limited to a dedicated concentrator layer
• TCP
• Consistency within the server layer requires to pass the world state between servers.
• Clients connect to concentrators based on network topology, not their position in the game world.
• The concentrators are constructed to be application independent
• Dead-reckoning schemes
• Clients connect to a concentrator, not to the server logic. Hence, client connection is never lost if a game server crashes.

---

Bharambe et al., Mercury: A Scalable Publish-Subscribe System for Internet Games.

• distributed content-based publish-subscribe system
• subscription language expressive enough to allow game-specific subscriptions (eg x in [10,20] && y <= [40,50], or team == "MyTeam"). In the subscription {x in [10,20] && y >0}, a hub for x is more efficient at relaying an event than a hub for y.
• routing mechanism based on a circle of modular software hubs, each hub storing subscriptions.
• Evaluation: network topology simulator in which nodes are randomly assigned as hubs [unrealistic]
• Metrics:
  • Number of publications routed by a node. All nodes end up having the same routing load (ie scalability achieved).
  • Number of subscriptions stored by a node. Virtual world is a square, hence the central zone receives more players and subscriptions than peripheral zones.
  • Delay for a publication to reach the interested subscribers. Increases linearly with the number of nodes [not scalable!]

---

Cronin et al., An Efficient Synchronization Mechanism for Mirrored Game Architectures.

• Trailing State Synchronization (TSS)
• Optimistic algorithm: execute commands as they are received and rollback when late messages are received.
• TSS runs a delayed "trailing" copy of the live game state. Trailing copy is able to re-order messages and execute them in chronological order.
• It's cheaper to execute a command multiple times than to make snapshots of the game state
• Preserving random events was hard

---

Farber, Network game traffic modelling.

• Traffic modeling from logs of a 36 hour LAN. Matches of 8 to 30 players.
• Server sends 16kbps to each client
• Each client sends 1 kbps to the server
• Both client and server receive 20-25 packets/sec.
• Packet size varies a lot.
• Probability density function of client-server and server-client packet size and latency modeled by Extreme Value distribution: F(x) = exp(-exp(-(x-a)/b)). (long-tail behavior)

---

Fiedler et al., A Communication Architecture for Massive Multiplayer Games.

• World cut in rectangle or hexagon tiles.
• Players subscribe to current and tiles adjacent to closest current tile corner.
• Each tile contains an environment and an interaction channel.
• Environment channel for static data. Static objects generate bandwidth only when someone interacts with them, not by themselves. A static object does not interact with other static objects. Consumes low bandwidth. Uses TCP.
• Interaction channel for active objects. Active objects interact with static and active objects.
• Tiles are managed by one or more servers (n to n relationship). Server only provides constant data such as terrain and objects within the map. Server only cares about the environment channel. Collision detection on clients. Scales with the number of tiles, not the number of clients.
• Authoritative objects are on the machine that instantiates them. Other clients have duplicates/"proxies". Collision detection and other object-object interactions are calculated on clients. Affected object instances publish their updates on the interaction channel of the object's current tile.

---

Griwodz et al., State replication for multiplayer games

• Player-to-player interactions require low latency (= high urgency).
• In case of congestion, less urgent events may be dropped. Results in a game of lower quality, but still running.
• Rare player-to-environment actions require high reliability
• Game designers define when they build the game which actions are urgent and which are relevant.
• Clients connect to a nearby proxy. Proxies are interconnected.
• Participants belong to target groups. Each target group can be contacted through a channel.
• Overlay network of proxies distribute events to target group members.

---

Henderson, Observations on game server discovery mechanisms.

• Analyzing network traffic to know how FPS servers work.
• Game servers register to server directories. Client gets server list from directory using UDP. Same structure as Napster.
• Method: 3 Half-Life US server directories were queried four times a day for a month.
• Problem of directories: single points of failure, stale information (70% of servers not active anymore), redundant info (90% of servers register to all directories), and no congestion control

---

Mauve et al, A Generic Proxy System for Networked Computer Games.

• Move intelligence and server functionality to the border of the network
• Some server functionality can be delegated to the proxies.
• Proxies located close to the players (need ISP support). Therefore, they could execute client code as well (anti-cheat).
• Proxies can reduce the server load in doing packet processing and filtering.
• Overlay network enables traffic rerouting around congested areas, network fault detection and node-failure recovery.