Guild Wars 2

Draygo.9473:

Basically

For each player
  otherplayer = player->get_visableplayers()
  For each otherplayer
     otherplayer->sendupdate(player)
  endfor
endfor

Also remember for every action you as a player take, all opponents in visible range need to be updated with the action you took, and your current location. If you cast a spell at a location, everyone else needs to know you cast that spell at a location.

There is pretty much no way around the O(n^(n-1)) problem here besides putting a limit on the n-1 via culling.

A nested loop does not make O(n^n), nor is O(n^n) considered to be exponential time.

Draygo.9473:

There is pretty much no way around the O(n^(n-1))

How exactly do you end up with O(n^(n-1)) for the algorithm you give? Comments in algorithm by me:

Draygo.9473:

For each player                                                            // executed O(n) times
  otherplayer = player->get_visableplayers()   // kind of O(n)
  For each otherplayer                                               // executed O(n) times in each iteration
     otherplayer->sendupdate(player)               // kind of constant w.r.t. n
  endfor
endfor

Even when doing this for all n players in sequence, this looks more like O(n^3) at worst to me.

saiyr.3071:

nor is O(n^n) considered to be exponential time.

Well, this depends on your precise definition of exponential time. You are correct that n^n is not O(exp(n)), but it is O(exp(poly(n))). And the class EXPTIME is actually defined as the latter one.

~MRA

MRA.4758:

True, and I am not arguing against the practical difficulty of the problem. But you are talking about systems that usually aim for quasi-linear time algorithms (or even sub-linear algorithms, using special data structures). What problems do you face that scale exponentially?

If no part of a system is at capacity, then yes adding more users/data is linear. However if a system has even one I/O subsection under load, adding one more node isn’t like adding the ones before it. Wait states do grow exponentially in a multi-threaded environment. It is completely unavoidable even with a more advanced versioning architecture or a locking/blocking one.

There is something awe inspiring seeing a couple TB of RAM installed into a server. It is equally disheartening to see it chewed up and yield a marginal performance improvement over the one TB it replaced.

Draygo.9473:

Jamais vu.5284:

Wryog.5073:

Because their engine isn’t made for this. I won’t explain the details because that’s already been said over 9000 times.
Also because StarCraft doesn’t calculate boons, armor, buffs, might, vulnerability, weapon damage, crit chance, crit damage, traits and distance from the center of AoEs.
And it’s not the 80 people being on the map, it’s the 80 people FIGHTING on the map.
It’s pretty much impossible to get that amount of people/AI fighting at the same time on 1 map in a MOBA.
Please don’t compare shooter calculations to RPG calculations. Shooters like CoD and Battlefield(as far as I know) don’t have armor, crit chance, crit damage, boons, power scaling and probably other things that I can’t remember right now. At the same time GW2 has projectile calculations like a shooter.
BTW aren’t shooters always limited to 64 players or even lower numbers? I remember interviews discussing 64 players in Battlefield 4 being a big thing.

I think I’d have caused you an aneurysm if I used a more abstract analogy.

Your defense of Anet’s ineptitude is noble, but misguided. This is a partially defective product/consumer service (if we count online-based games as the latter). There’s no excuse for it one year after it has been released.

Ok, here’s the excuse:

No other MMO has done 300+ man battles without lag.

DAOC lagged
WAR lagged
Planetside lagged
Planetside II lagged
EVE lagged (now they force the lag with time dilation)

so why are we expecting Arenanet to solve a problem no one else has really solved yet?

EvE doesn’t really get time dilation until you hit about 700-800+ players. Just saying.

MRA.4758:

Draygo.9473:

There is pretty much no way around the O(n^(n-1))

How exactly do you end up with O(n^(n-1)) for the algorithm you give? Comments in algorithm by me:

Draygo.9473:

For each player                                                            // executed O(n) times
  otherplayer = player->get_visableplayers()   // kind of O(n)
  For each otherplayer                                               // executed O(n) times in each iteration
     otherplayer->sendupdate(player)               // kind of constant w.r.t. n
  endfor
endfor

Even when doing this for all n players in sequence, this looks more like O(n^3) at worst to me.

saiyr.3071:

nor is O(n^n) considered to be exponential time.

Well, this depends on your precise definition of exponential time. You are correct that n^n is not O(exp(n)), but it is O(exp(poly(n))). And the class EXPTIME is actually defined as the latter one.

~MRA

Yeah your right, excuse me for lateposting. What I posted is n^2. I suspect anet has to deal with a lot of n^2, n^3 for damage, updates and the like. The more people in an area the worse it gets, and the faster we spam our abilities the worse it gets.

I am curious how often they are running the health update on damage, especially considering they want to display every bleed tick.

MRA.4758:

saiyr.3071:

nor is O(n^n) considered to be exponential time.

Well, this depends on your precise definition of exponential time. You are correct that n^n is not O(exp(n)), but it is O(exp(poly(n))). And the class “EXPTIME”:
E is actually defined as the latter one.

~MRA

http://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities

Nope.

Edit: Oh nevermind, you’re right, “exponential time” is ambiguous. E is not defined as the latter, though. And also in terms of big O, EXPTIME is never used as the definition.

ColinJohanson.2394:

We have folks working constantly on finding ways to improve over-all game performance, in particular when a large number of players gather together. You’ll continue to see updates and upgrades in this area as the year continues to get performance as smooth as possible.

Sorry when skill lag in WVW gets worse and things like loading times get worse and worse I can’t see any improvements in terms of optimisations.

I hear a lot of people saying that after the big (latest) patch, they are crashing and getting disconnect more then before.
Me included by the way.
I never crashed before so, and the lag is also more then before.
So don’t know what ANET changed to cause this?
Hope you guys can check it out what you changed in that patch and set it back to the old setting.

DevonCarver.5370:

Lead.1784:

EvE doesn’t really get time dilation until you hit about 700-800+ players. Just saying.

While I appreciate the spirit of this response, I think it is clear that EvE and our game have very different types and amounts of calculations to make.

In addition the mechanics of EvE are vastly different – it’s essentially 6DOF WoW. Don’t get hung up on the 6DOF, rather the WoW aspect. There is less for the network stack to do considering that you can press “1” and walk away from my computer (you wouldn’t in practice, but in theory you could). It’s not an action MMO – it’s a classic MMO which is a lot less chatty than something like GW2.

Another action MMO is specifically avoiding a WvW/RvR scenario is Wildstar – very likely because of the overhead involved.

A good example is that in classic MMOs a whether or not a projectile/ability hits is nearly always determined at the point it is launched (at the end of the channeling time). Action MMOs like GW2 have issues like players dodging out of the way and therefore can’t do lazy dice roll-based calculations.

zamalek.2154:

DevonCarver.5370:

Lead.1784:

EvE doesn’t really get time dilation until you hit about 700-800+ players. Just saying.

While I appreciate the spirit of this response, I think it is clear that EvE and our game have very different types and amounts of calculations to make.

In addition the mechanics of EvE are vastly different – it’s essentially 6DOF WoW. Don’t get hung up on the 6DOF, rather the WoW aspect. There is less for the network stack to do considering that you can press “1” and walk away from my computer (you wouldn’t in practice, but in theory you could). It’s not an action MMO – it’s a classic MMO which is a lot less chatty than something like GW2.

Another action MMO is specifically avoiding a WvW/RvR scenario is Wildstar – very likely because of the overhead involved.

A good example is that in classic MMOs a whether or not a projectile/ability hits is nearly always determined at the point it is launched (at the end of the channeling time). Action MMOs like GW2 have issues like players dodging out of the way and therefore can’t do lazy dice roll-based calculations.

Actually, EvE has a much more complex system than you guys are saying, taking into account transversals, turret rotation speeds, explosion velocities, and many other things that you probably aren’t aware of. For example, it is possible for a small frigate or even a cruiser to outrun an explosion from a missile by traveling faster than the explosion velocity. Missiles “never miss” in eve, but it is possible to outrun them during the flight time and/or “dodge” the explosion. A similar thing happens with turret rotation speeds, its a little more complicated than checking if someone is in a dodge state or not…. Although you could argue that there is less AOE in eve and they do have a MUCH more powerful and advanced server setup. So its not really a fair comparison. Although this game starts to chug whenever a large enemy blob is around, before combat is even entered. That would never happen in EvE. But I wouldn’t exactly call what happens in EvE lazy…. Even Gw2 uses rolls to determine damage, in the form of your weapon. Its a very simple calculation, too.

This is why Anet should have just bought some of the code instead of starting from scratch.

Luckily i live in Asia and have no skill lag problems

^you realize the NA servers are in America and the EU servers are in Europe right? You not having skill lag means the netcode is pretty top notch.

the problems being discussed here have nearly nothing to do with the netcode, but the cpu overhead of calculating a massive zerg v zerg v zerg battle.

Just an update:

You do not need O(n^3) approach to update the information to all players. The naive approach to send every single bleed stack + health information per each attack to all players in range, would generate absurd amount of unneeded network transfer and probably lead to network glitches as well (getting kicked out of the game). There are some rather well-known old school techniques to reduce this to:

1. Do all the calculations server side, as described in previous posts

2. Once per update tick, let’s say 10 times per second, send the 3D coordinates, direction, animation frame, actions to all players in range (culling included) and between those frames use interpolation and prediction techniques e.g. assume that each allied and enemy player continues to move to the direction it is moving at the same speed and continuing its action. E.g. if player is viewing the game 60 fps, every 6th frame has real information and 5/6 are predicted, interpolated frames. The prediction might sometimes show erroneous results, leading to short range teleporting players etc. but this would greatly reduce the network traffic and create impression of having much less latency (lag)

3. Once per second send the health, bleed stack information etc. to all players in range

I do not know the internals of Guild Wars 2, but I heard EVE Online uses asynchronous server side code. I have been teaching this topic and I am a firm believer than for many problems, especially those related to massively popular online chats and games, would benefit from asynchronous programming model. The more traditional approach, especially most Java and C++ programmers use synchronous input/output and threaded programming model. This is what most school are unfortunately teaching. And this scales very badly for very large amount of simultaneous users.

In asynchronous, aka non-blocking, model each input / output operation is just triggered. The program doesn’t wait them to finish, but goes on to accept new tasks. A callback function might be called when the asynchronous tasks gets ready. If the server program is divided into processes, which communicate efficiently using sockets, you can then easily divide the task to take advantage of not only multiple CPU cores, but also distribute the task over a network of multiple computers. This the model companies like Google are using.

Actually, EvE has a much more complex system than you guys are saying, taking into account transversals, turret rotation speeds, explosion velocities, and many other things that you probably aren’t aware of. For example, it is possible for a small frigate or even a cruiser to outrun an explosion from a missile by traveling faster than the explosion velocity. Missiles “never miss” in eve, but it is possible to outrun them during the flight time and/or “dodge” the explosion.

These things are really, really easy to calculate compared to collision. EVE also runs at 1 Hertz, which is not the case in GW2. EVE is just really easy on the servers compared to GW2. EVE’s main problem was their server architecture, they allocated few resources to any one zero zero system because they were largely empty. Suddenly battle and the relatively paltry resources were massively overtaxed. IIRC they finally implemented a system where they could allocate resources more dynamically+time dilation to fix problem.

Deniara Devious.3948:

Just an update:

2. Once per update tick, let’s say 10 times per second, send the 3D coordinates, direction, animation frame, actions to all players in range (culling included) and between those frames use interpolation and prediction techniques e.g. assume that each allied and enemy player continues to move to the direction it is moving at the same speed and continuing its action. E.g. if player is viewing the game 60 fps, every 6th frame has real information and 5/6 are predicted, interpolated frames. The prediction might sometimes show erroneous results, leading to short range teleporting players etc. but this would greatly reduce the network traffic and create impression of having much less latency (lag)

That is an O(n^2) function. But the packing function sending the data isn’t all that laggy, the lagstorms happen in big battles where the server is doing damage calculations/skill broadcasts at an incredible rate. I do think GW2 servers broadcast actions as players send them so we can see the abilities in time to dodge them. And as you said the problem with interpolation systems is it can make non-laggy situations seem laggy with players abusing interpolation to warp around (see planetside, tribes series).

Anyway I don’t think netcode is the problem here because even with 300+ people running around in the same area, I don’t get the chugging skill lag of zergfights.

Whatever is causing this, I wouldn’t hold your breath waiting for a fix folks. Arenanet has been having these problems since the release of Guild Wars 1 – anyone else remember having to login to the Wintersday finale 30 minutes before it started because the lag was so bad? Much as I love Anet, if they haven’t worked out how to fix their ‘crippling lag at peak times’ problem in eight years then they probably aren’t going to.

Edit: It could of course just be a latency issue. EU servers are hosted in Texas according to the address the /IP emote gives me. Perhaps big zergs and lots of skill cast / damage messages between client and server just can’t travel across the Atlantic Ocean quickly enough?

DevonCarver.5370:

Lead.1784:

EvE doesn’t really get time dilation until you hit about 700-800+ players. Just saying.

While I appreciate the spirit of this response, I think it is clear that EvE and our game have very different types and amounts of calculations to make. We are making strides to improve the skill lag, but it is a very large and very difficult problem to solve. We can’t do more than take little chips off of it at a time and eventually those should add up to sizable differences, but each little change isn’t going to make a major impact in and of itself.

I have all my settings at their maximums including the two “culling” settings and the only time I notice a problem is when I first load in to a city. The ground and buildings won’t be there for a few seconds and then they pop in. I consider it a very small price to pay for having the world actually feel lived-in.

I don’t have some powerhouse system; Intel i5 3.4ghz, nVidia GTX600, and a lowly 8gb of DDRIII 1600 ram. I’m hoping adding a second card will speed up the loading of assets in cities, but as I said before I’d rather have this than ghost towns.

Draygo.9473:

Anyway I don’t think netcode is the problem here because even with 300+ people running around in the same area, I don’t get the chugging skill lag of zergfights.

Well, obviously 300 people just running on the same map shouldn’t cause problems. You just need to update their 3D coordinates, direction, animation frames, action etc, but there are no combat calculations.

And if there would be 300 people spamming their auto attack at one legendary boss without much other monsters around (typical world event), the lag would be less than the 50vs50vs50 zerg fight.

I think the heart of the problem is those tightly packed battles where both or all three sides have massive amount of players attacking each other. AoE effects can take the largest time to resolve as they can affect so many targets. There are some skills, e.g. necro wells, which ignore the 5-man limit. Each grenade can hit up to 5 different targets and grandmaster grenadier engineer throws 3 grenades at a time. For some strange reason Arenanet buffed the radius of guardian symbols and necro marks by 50% (2.25x area increase). This obviously can lead to even more lag.

Now Arenanet developers should have a serious discussion:
Should we do something about the game breaking lag? (which can be so bad that no skill triggers, even skill #1 fails. At least I have several times logged out of the game because such mega lag makes it unplayable)

This is not just a programming problem. The current meta favors very tight blobbing, which is the worst thing for lag. All the smart groups do this to get the combo field effects, area heals and area condition cleansing. And if you stand in a tightly packed spot with 30+ allies, most enemy AoE skills can only affect up to 5 of you, thus most of you don’t get any damage whatsoever, without any dodging.

Here are game design changes to reduce this problem:

1. Reduce the effectiveness of some combo fields:
- fire field should give only 2 stacks of might for 10 seconds (allows crazy might stacking)
- water field healing should be reduced by 33% (allows crazy area healing)
- lighting field swiftness duration should be reduced by 50% (allows zergs to move with perma swiftness)
- smoke field stealth duration should not stack to more than 8 seconds total (currently allows permanent stealth, not much of a zerg battle problem, but overpowered)

2. Reduce the radius of AoE skills
- large AoE can hit more and as everybody wants maximum loot they just spam AoE all over in hopes of tagging as many opponents as possible
- aiming small AoE requires more skill

3. Player characters should occupy 3D space, which blocks others
- just like in GW1
- this would allow body blocking
- no possibility to be inside enemy or allied character model

4. Cap the WXP rewards per players involved
- e.g. max 5 players get full reward from killing an enemy invader, guard or capturing a supply camp and max 10 players get full reward for killing enemy tower lord and capturing enemy tower and so on. Others get diminished WXP rewards
- server side points and other rewards like XP, loot are unaffected

5. Limit number of players per map
- I do not know the current limits, but my guess is circa 120 players per side at EB, reducing this to max 80 players per side could potentially reduce the needed computations to half
- this would lead to longer queues on highly popular servers
- offer alternative to fight as mercenary for some other server match up (no need to wait)

I am suggesting these changes for WvWvW only. Probably implementing just 2-3 of the above would be enough to make the situation much better than it is.

DevonCarver.5370:

MRA.4758:

Deniara Devious.3948:

The amount of computations needed at the server side e.g. which targets your AoE or cleaving attack hits grows exponentially with the number of players in the same map area.

Please stop spreading this piece of misinformation. I know that this is a direct quote by Devon Carver, but there is no sane reason to believe that the need for computational resources is indeed exponential. As I tried to explain in another thread, it is much more likely that the growth is quadratic. While this still may be to much to find a viable real-time solution, quadratic growth is substantially different from exponential growth.

~MRA

It is not misinformation, it is the reality of our system.

This is exactly why Mac Users crash in zergs too- the Cider wrapper cannot process, and convert that many lines of code- and keep up for long. You have to remember every action in WvW makes a chain of actions occur. Now imagine 270 of these actions occuring at once, which multiples the action result by 5, then it must calculate the result of such actions.

Gw2 isn’t running on Frostbite you know, it’s not a very meaty engine.

[QUOTE]3. Player characters should occupy 3D space, which blocks others
- just like in GW1
- this would allow body blocking
- no possibility to be inside enemy or allied character model[/quote]
Hahaha that would lag so hard.