I just uploaded my GDCE 2016 talk on deterministic simulation. It’s not rocket science, but probably useful especially for beginning network coders. You can find it in the talks section. I even added a few bonus slides which I had to cut from the conference version for time reasons.
There is also a video of the actual talk in the GDC vault but you cannot access it without a paid subscription (which you also get with any GDC or GDCE conference ticket).
Unity has now put many of the Unite 2016 talks on youtube, including mine! Enjoy!
This is the second article in my Albion Online series, the first part can be found here.
Interest Management is the ability to efficiently determine which game object can “see” which other objects at a given point in time. This is important for multiple reasons.
First of all, we want to minimize the network traffic for each client by sending the client only updates of objects it can actually see right now. Second, players do cheat. Any information that is sent to the client can and will be extracted by cheaters. That means we absolutely need to restrict client knowledge to objects that are on the screen or at least very close to it. The whole mechanism is also useful for many other purposes; for instance, monsters are activated when a player comes near and deactivated when the player leaves.
All this needs to be as efficient as possible. Let’s illustrate this with some numbers: A single (1×1 km) cluster may contain more than 300 players, 500 monsters and more than 10.000 other interactive objects (most of which are trees, because you can cut down every single tree in Albion Online).
We achieve the efficiency by putting all objects into a grid-based hash. Each grid cell is roughly 10×10 meters and contains a list of objects inside. Very large objects may be in multiple cells at once but that is rare. The object itself is responsible for updating the hash if it moves. The grid cells fire events when objects are added or removed, so subscribing to these events already gives you a very efficient way of monitoring an area.
Each player is surrounded by something we call an Interest Area. It consists of two grid-aligned rectangles. When an object enters the inner, smaller rectangle, the player will start “seeing” the object, i.e. the server will send the client an initial “new object” message (“look, a monster!”) and subscribe to the various event the object itself offers. Whenever the object does something interesting (e.g. the monster attacks someone) it will fire an event, that event will be forwarded to the Interest Area of the nearby player and the Interest Area will forward the event to the client.
An object will be watched until it leaves the slightly larger blue area. When that happens, the client will receive an “object gone” message and stop receiving updates. The blue area is larger in order to keep the visible object set more stable over time.
I have recently given talks about the technology behind Albion Online at the Quo Vadis and Unite Europe conferences. You can find the slides in the talks section. The Unite talk is mostly a shortened version of the Quo Vadis talk. Since the slides are more interesting with a bit of an explanation, I decided to create a short series of articles to cover the material. Enjoy and please post questions/comments below!
Our elevator pitch goes something like: “Albion Online is a fantasy version of EVE Online, but with League-of-Legends-style combat.”
That means:
At the time of writing, Albion Online is in ‘Closed Beta’ stage with almost 120.000 ‘founding’ players. (You have to buy a ‘Founder Pack’ on our website in order to play.)
A project of the magnitude requires a lot of third-party-technology. Here are the key choices we made:
We use the Unity3D game engine to make Albion Online. Unity was up-and-coming when we started; it is powerful, flexible and inexpensive. Unity’s biggest strength, however, is the ability to publish on a huge number of platforms with very little additional effort. Even though we originally planned a PC-only game, we quickly realized that tablets and other mobile devices would be a crucial market in the future. Hence, Albion Online became a true cross-platform project.
As a network middleware, we use Photon. Photon comes with a server framework; the core is written in C++ for performance reasons, but the application code is C# – which is good because it means we can write the entire project in a single language and share code between server and client. C# is in fact an excellent choice for server development – very easy to use, fast, efficient and very stable thanks to garbage collection and exception handling.
Most of the game uses Photon’s reliable UDP protocol, movement messages are sent as unreliable UDP messages. For the chat server and for inter-server-communication we use TCP. We use Photon on the lowest possible level, i.e. only the server framework and the network protocols. There is also a cloud-based hosting solution, a chat system and even a MMO framework, but we decided to use none of that. Instead, we wrote as much as possible ourselves and we decided to host the game on dedicated bare-metal servers.
Finally, we needed databases. For the game, the biggest concern was the ability to scale the game database for the potentially “infinite” game world size. We decided to give Cassandra a try. Cassandra is a NoSQL database, i.e. it sacrifices the ability to do complex queries in favor of speed, high throughput and the possibility to scale horizontally.
Cassandra is essentially a distributed hash table. You can retrieve data only based on its hash key, but it is also possible to index additional data columns (which implicitly creates additional redundant hash tables). You can build a Cassandra cluster out of as many server instances (nodes) as necessary. They will automatically split the hash space with some redundancy, so a couple of nodes may fail and the cluster will still stay operational. A caveat is that Cassandra is only ‘eventually consistent’. Due to the distributed nature of the database cluster, it is possible to read ‘outdated’ data from the cluster, even though the ‘latest’ data will eventually be synchronized to all nodes. This can be fixed by either writing to or reading from a quorum of the database nodes, i.e. if you need consistent information, you can choose between slower reads or slower writes. Albion Online keeps most data in the game server’s memory while a player is logged in, so we choose slow reads but very fast writes. (Player data is only read when the player logs in or changes the game server, but it is written every time something changes – just in case the game server crashes.)
The biggest downside of NoSQL databases is the inability to do complex queries. For some purposes, e.g. the in-game market places, queries are important, so we use a couple of Postgres SQL databases as well.
It was clear from the beginning that we did not want to run Unity on the server. Unity is a closed-source environment we did not believe it was flexible, scalable and stable enough to support a game server for thousands of concurrent players.
In order to achieve this, we could not rely on Unity for core game systems. We needed our own definition of ‘game objects’, our own map file format, our own collision code, our own pathfinding etc.
While it seems excessive to ‘reinvent the wheel’ when Unity can already do all of these things, it is important to understand that we only need to do the simulation part of the game and we want these systems to be as lean and efficient as possible. I will shed some light at this in a later article.
Since the server code is already ‘Unity-free’, it makes sense to even go a step further and have a Unity-free client as well.
A key design principle of Albion Online is a strict Model-View-Controller pattern. In an online game the server must have absolute authority, meaning that all game world manipulations happen on the server and only the server can decide whether a player action is valid or not. We keep game data in memory and use databases as permanent storage; hence the server acts as the Model and the Controller here.
The Albion client is just a library (i.e. a DLL) that is able to communicate with the server. It will mirror the part of the data model that the player can “see” at a given point in time and offer a controller interface similar to that of the server. The client does validity checks and sometimes even prediction, but will ultimately send all valid requests to the server. The client library knows nothing about Unity. We do have a fully functional command-line version of the client that is very useful for load testing etc. The client code is maintained as a separate Visual Studio project that has no Unity dependencies, so it is easy to keep the separation in everyday work life.
Unity comes into play as a pure View component. It will subscribe to various events the client library offers, create a view for every game object and update the view whenever the game object changes. All of the UI and input code is in Unity as well, but the real business logic is in the client library and not in Unity.
The server farm consists of several different server types and databases. We host everything on bare metal machines since we need strong CPU time and memory guarantees. Albion is a single, unique game world for all players. We use instancing only for player islands and certain types of dungeons, so we would not benefit much from the ability to scale to dynamically allocated virtual machines. Instead, we simply distribute the game world across a fixed number of physical machines.
Most of the heavy lifting is done by the Game Servers. Depending on your character’s location in the game world your client will connect to a different Game Server. As you move through the world, you may have to connect to a different game server.
Your client will also maintain a connection to the Chat and Login Server. The Login Server handles all account operations like login, logout, character creation etc. and will tell the client which Game Server to connect to.
The World server is the single authority for all game features that work across Game Servers, for instance parties, guilds, guild vs. guild battles etc. The Backoffice server controls farm startup, shutdown and provides an API to “talk” to the entire farm.
Our game world consists of zones (“clusters”) that are roughly 1×1 km in size. There are currently around 600 of these. When you change zones, your client may have to connect to a different game server and you will see a short loading screen on the client. The game logic of a cluster is handled by a single thread. Making this multi-threaded would be very error-prone and not necessarily more efficient since there are numerous complicated interactions between game objects which would require locking. Instead, all incoming player commands are put into a synchronized event queue and processed in order of arrival. Any work that can be offloaded – like database operations, pathfinding or logging – are handed to separate thread pools that complete their respective tasks asynchronously and put the result back into the event queue.
A second mechanism we use extensively are scheduled events (or simply put: timers). There is no real game loop in Albion Online, meaning that game object have no Update() functions that are called every so often. Instead, objects will create timers whenever they need to. Monsters will create a recurring AI update timer as soon as a player gets near but delete the timer again when the player is gone.