EVE online is a remarkable game. On Monday over 2000 people spent over 20 hours destroying virtual spaceships worth 200,000 USD in real money in what was the likely the largest battle in a video game ever. That EVE is capaple of supporting such large engagements is an amazing technical achievement, that thousands of players are willing to invest huge amounts of time and money in to a game that recently celebrated its 10th anniversary is an amazing game design achievement.
The reason that the scale of EVE battles continue to break records and make headlines is the introduction of Time Dilation (TiDi) in 2012. When the server simulating a solar system in EVE becomes unable to keep up with the rate of updates from connected clients it slows the simulation down so it can keep up. Before TiDi the server would become overloaded and start failing to process commands from players. After time dilation, game time slows down, but commands continue to processed fairly for all players. Up to a point.
In order to ensure that battles eventually get resolved, TiDi is only allowed to slow the simulation down to 10% of it’s normal speed, so at 10% TiDi one second of simulation time passes for every 10 seconds of real time. The 20+ hour Battle of B-R5RB on Monday was eventually brought to a halt due to a server upgrade, if TiDi was allowed to continue past 10% this would become increasingly common and battles would often be decided by one side’s willingness to put up with more simulation slowdown than the other.
In part due to the extra real time that TiDi gives players to join in, the scale of large EVE battles have now grown to the point where they regularly push TiDi to 10%, server CPU to 100% and cause the old problems of failing updates to reappear, as was seen in The Battle Of HED-GP a week ago in which many of the attacking forces were unable to issue commands successfully and so were destroyed. The limits of TiDi to allow battles in EVE online to scale up have been reached.
In his analysis of The Battle of HED-GP, CCP Veritas, talks about “one of the bounding scaling factors in large fleet fights, the unavoidable O(n2) situation where n people do things that n people need to see”. Avoiding this bounding scaling factor may be one way to allow EVE battles to scale beyond the limits of TiDi.
As the amazing screenshots from B-R5RB show, large scale battles in EVE quickly become difficult to navigate. With 1000s of pilots in space, simply finding the ship you want to target becomes hard. As a result EVE provides an overview that lists the ships in nearby space. This overview can be sorted in a number of ways allowing a particular ship to be selected and multiple lists can be set up filtering out different subsets of things in space. Often during a battle pilots will use an overview set up to only show enemy ships to avoid targeting friendly ships, for example.
Pushing these filtering settings to the server may be one way to scale EVE battles beyond the limits of TiDi. In the case where all pilots have their overview set up to only show enemy ships we would have a situation where n people do things that n/2 people need to see. With more aggressive filtering that only showed interacting ships plus the nearest ship of each type plus ships piloted by known pilots plus ships broadcast to your fleet it might be possible to get to a situation where the number of things people need to see does not depend on the number of people in a battle. The O(n2) problem could be avoided without significantly changing EVEs game play mechanics. If the number of ships of each type were also sent to the client, the overview could still be populated with one entry per ship, albeit with missing information, allowing for situations where fleets want to spread their fire rather than focussing it.
One potential weakness with this approach is that it would allow pilots to force the server back in to doing O(n2) work by simply disabling thier overview filters, something that might become impossible to resist in a situation where it’s clear that your fleet is going to lose hundreds of thousands of real dollars worth of virtual spaceships. In the Battle of B-R5RB, one side had ships filled with autonomous drones which they apparently chose not to deploy to avoid server load, but might well have decided to deploy if they had started losing the battle.
A potential solution here would be to prioritise updates from players with more aggressive filtering settings. If the server runs out of time at the limits of TiDi it simply stops processing updates and starts on the next frame, penalising pilots with too liberal filtering settings who could be made aware that their updates are being dropped by the UI. This would encourage pilots engaged in the battle to aggressively filter while potentially still allowing non-combatants to capture the occasional screenshot or even video of the entire battle.
Another weakness of this approach is that pilots will no-longer see every ship in the battle rendered at the correct position in space. A similar approach to populating the overview could be taken here by rendering the correct number of ships of each type at ranges beyond the minimum range for each type, or more symbolic approaches could be used to display the number of ships in the 3D scene. I did some related work on rendering symbolic abstractions of 3D environments in MASSIVE-3 many moons ago.
I no longer have a copy of the EVE source code to check whether any of this is possible and even when I was working on CREST I didn’t look at the simulation code in EVE much at all, but this might be one way around the O(n2) problem that currently limits the size of EVE battles. However they choose to tackle it, I wish CCP Veritas and the newly rehydrated Team Gridlock all the best in their scaling work and look forward to reading stories of ever more epic space battles for the next 10 years.
In mid-2004 I first started exploring Second Life. Version 1.4 had just been released and Philip Rosedale had said in the press release “My fantasy is to be Uma Thurman in Kill Bill, and now I can. I’d pay $10 for her yellow jumpsuit and sword moves and ...read more
Parse By The Sea
Brighton Digital Festival
The Brighton Digital Festival starts this week and I’m very happy to be helping out with Facebook London‘s contributions: Parse By The Sea, a mobile app Hackathon featuring Parse on the 26th of September, and helping to Connect The Brighton Digital Festival by sponsoring Metranet to provide high ...read more
One Universe, Many Scales
Following In My Father’s Footsteps
From 2 years before I was born, until just before I started working on Second Life at Linden Lab, my Dad worked at an innovative technology company with a large consumer photography business: Kodak. From January next year I’ll be working at an innovative technology company with a large ...read more
Caching Shared, Private Data With Ningx
As with many other social services, a large amount of the data in EVE Online and Dust 514‘s New Eden universe is shared between subsets of users. Some corporation data should only be accessible to the corporation’s members, market prices should only be accessible to capsuleers and infantry ...read more
Adding Vary Header Support To Nginx
Although Nginx supports proxy caching it doesn’t provide support for the HTTP Vary header out of the box. This is a problem if you want to use Nginx to proxy different versions of the same URI which Vary on Content-Language or proxy different representations of a RESTful resource specified ...read more
Load Balancing Stateful Services With Nginx
The EVE online network architecture uses stateful proxy servers which manage sessions for players connected to the cluster via the EVE client. The client sends requests to the proxy which are forwarded on to sol servers maintaining the game state and the sols send notifications to the proxy which are ...read more
Brighton Mini Maker Faire: The Movie
A few years ago nearly all the code I wrote was in C++, but increasingly I’m finding myself writing in a variety of mostly C-style languages and having to perform crunching mental gear changes as I switch between them.
In the interests of making these language switches less painful ...read more
100 robots Vs The Audience
100 robots Attack!
Lots of exciting 100 robots news! Our debut album, Attack!, has been professionally mastered by Chris at Melograf Mastering who has done an amazing job and made the album sound incredible. The new version is already available at bandcamp and will be available on itunes, amazon and many other download ...read more
Data Is Not Art
This week I experienced two remarkable combinations of music and the moving image.
This evening I watched Nature — Mira Calix and Quayola’s audio visual piece which took video footage of flowers blowing in the wind and used motion tracking technology to generate music ...read more