open All Channels
seplocked EVE General Discussion
blankseplocked Chaos theory and the EVE DESTINY
 
This thread is older than 90 days and has been locked due to inactivity.


 
Pages: [1] 2 3 4 5

Author Topic

Faife
Dreddit
Test Alliance Please Ignore
Posted - 2008.09.18 02:18:00 - [1]
 

saw this post from someone who attended some conference where CCP talked about how their engine works a bit. i had no idea it was this complex, but it sorta explains why lag vs ships is so non-linear

Quote:
Easily the most awesome lecture of the conference, CCP's CTO explaining the code and design of the simulation system behind the EVE Online servers: DESTINY.

The key point is a chaos-theory equation system of potential spheres of influence for every actor in a space. Essentially the algorithm goes something like this:

1) Begin server frame.
2) For each ship, calculate a sphere of possible client interaction based on the ship's dimensions, weapons systems, visual range, etc.
3) Using chaos theory equations of possible changes in a ship's behavior before the next time slice, fractally extrude out a set of event cylinders (with hemispherical caps) of the ship's possible influence before the next frame, within the 3D space.
4) Loop through the generated event cylinders and look for intersections. Lump intersecting masses together as "causality bubbles." Sets of events that could potentially influence one another.
5) Rapid cache out the causality bubbles as separate sets and defer the simulation of each bubble out through microtasklets in Stackless Python.
6) Send only the information relating to a player's intersected causality bubble/matrix to that game client. (Dump client's simulation state from pervious frame in lieu of the server's state if they disagree.)
7) Allow the client and server to run the simulation of that causality bubble in parallel. Continue the simulation on the client to make it appear seamless.
8) Yield to other causality bubble simulations in DESTINY and Sleep() for 1000ms.
9) Download any input changes by the ship's pilot from the client at the end of the server frame. As ships do not respond to inputs instantaneously in EVE, this is fine.
10) Push that input into the force equations in the physics simulation for next frame.
11) Push the causality bubbles' simulation result to TRANQUILITY, the actual server Main() process.
12) End server frame, loop while the execution context has not received a shutdown signal.

This prevents you from encountering a runaway O(n^y) algorithm of every ship in a solar system potentially acting on every other, and by only sending updates to clients based on that client's ship's causality bubble, it allows the game to be played on only dial-up modem speeds.

The only downside is in large space battles, in crowded spaces. In these scenarios, the intersection of extruded causality cylinders tends to encompass the entire system. This ship can influence this ship which can influence these ships which influence... etc. So the partitioning of simulation afforded by causality bubbles goes away. They tossed out some similarly awesome-sounding ways to fix this, that are in development, but I'm not allowed to talk about them.

Other really sweet things they did:

- Dynamically generated all solar systems in the universe using actual supercomputer-run disk accretion models. This means every solar system was formed the same way actual astronomical ones are, and no system is artificially held together by anything that would not work in real physics.

- Originally, the random seed to generate the EVE universe was taken from the server's Epoch Time at the start of the universe generation. The guy in charge decided, the night before launch, to regenerate the entire universe at the last minute with the seed "42."

- The location of solar systems relative to one another were modelled after cellular cohesion equations - the same thing that makes gold deposits form, blood vessels to grow in your body, and sets the pattern of the universe filaments as seen in the Cosmic Microwave Background Radiation.

Synapse Archae
Amarr
Viziam
Posted - 2008.09.18 02:29:00 - [2]
 

I would post that picture with the T-rex in the F-15, but honestly this thread can't get any awsomer.

Terianna Eri
Red Federation
RvB - RED Federation
Posted - 2008.09.18 02:30:00 - [3]
 

Edited by: Terianna Eri on 18/09/2008 02:31:10
I hardly understand any of that, but it's really, really cool Shocked

EDIT:
Originally by: Synapse Archae
I would post that picture with the T-rex in the F-15, but honestly this thread can't get any awsomer.

Calvin and Hobbes 4tmfw, to be honest.

Korizan
Hysterically Unforgiving
Posted - 2008.09.18 02:44:00 - [4]
 

Edited by: Korizan on 18/09/2008 02:44:55
YEh based on this alone.

10 ships each with in say 50 meters would cause ALOT more causality bubbles
THen say 10 ships 50 km apart.

And it can be scaled up with no issues.
BUt the denser the population in one area, say a fleet in formation under z (momentum) would create a bigger problem then the same number in a fleet spread out over greater distances.

IF drones use the same mechanism and are treated as ships then you can see how it compounds the issue.

Also a fleet warping on to a grid would have a huge numbers of possible causality bubbles compared to singles. but that would also depend on your procimitly of other ships on warp in.

Very interesting none the less.
WOnder how many mathamatitions worked on it or would be interested in looking @ how it works.

At least that is how I interpretate it. Probably wrong though.

Crumplecorn
Gallente
Eve Cluster Explorations
Posted - 2008.09.18 02:49:00 - [5]
 

Words cannot describe the awesome.

Korizan
Hysterically Unforgiving
Posted - 2008.09.18 02:54:00 - [6]
 

NOw that I think some more about it.

IF they are using a ships potential for movement in thecausality bubble equations then...

A fleet of intercepter would actually create more bubbles then a a fleet of same numbers in a carriers.

So with that you could actually say that the faster ships go the more bubbles you get and the greater the problem.

So it is not only numbers but speed that also causes the problems.

Interesting even if it is pure speculation.

Reptzo
Channel 4 News Team
Veritas Immortalis
Posted - 2008.09.18 02:55:00 - [7]
 

I don't really understand any of that, but it rocks.

Dharyx
Posted - 2008.09.18 03:29:00 - [8]
 

uhm, ok..
So let's say I'm in a blasterfitted megathron..
I jump in and see a lone hulk in lowsec..
The chances for me just staying still in space, not doing anything are pretty slim..

So the system calculates that I'm locking the hulk and blasting it into pieces.. but when the lagspike ends everything is corrected and I'm just floating in space beside a hulk? Rolling Eyes

Sarah Tuttle
Aurelius Federation
Posted - 2008.09.18 03:31:00 - [9]
 

I think I understand what he is saying. What I don't understand is how any computer on earth can handle that kind of load and relay it correctly to 30,000+ users at the same time.


Faife
Dreddit
Test Alliance Please Ignore
Posted - 2008.09.18 03:31:00 - [10]
 

Originally by: Dharyx
uhm, ok..
So let's say I'm in a blasterfitted megathron..
I jump in and see a lone hulk in lowsec..
The chances for me just staying still in space, not doing anything are pretty slim..

So the system calculates that I'm locking the hulk and blasting it into pieces.. but when the lagspike ends everything is corrected and I'm just floating in space beside a hulk? Rolling Eyes


let's play scientist, in your experience, is that what happens? empirical data and all

Havohej
Du'uma Fiisi Integrated Astrometrics
Posted - 2008.09.18 03:32:00 - [11]
 

Sauce?

Faife
Dreddit
Test Alliance Please Ignore
Posted - 2008.09.18 03:32:00 - [12]
 

Originally by: Sarah Tuttle
I think I understand what he is saying. What I don't understand is how any computer on earth can handle that kind of load and relay it correctly to 30,000+ users at the same time.




many computers. Tranquility is a whole lotta computers.

Faife
Dreddit
Test Alliance Please Ignore
Posted - 2008.09.18 03:33:00 - [13]
 

Originally by: Havohej
Sauce?


locked livejournal. not sure what the proper internet protocol on this is, so i figured i'll copy paste it and hope the ethics don't come up :P

Havohej
Du'uma Fiisi Integrated Astrometrics
Posted - 2008.09.18 03:36:00 - [14]
 

Originally by: Faife
Originally by: Havohej
Sauce?


locked livejournal. not sure what the proper internet protocol on this is, so i figured i'll copy paste it and hope the ethics don't come up :P


rgr that. Welp, would've been cool to cite source when I talk about it on blog but due to circumstances beyond your control you will now receive 100% credit instead of just half Razz

Seriously though, good find. All seems to make sense enough, feels authentic. Not doubting you or the livejournal you found it on, but it'd be extra cool for a dev to post confirmation that this is how things work Very Happy

The first reply is quite accurate, this has all sorts of awesome all over it.

Dharyx
Posted - 2008.09.18 03:38:00 - [15]
 

Originally by: Faife
Originally by: Dharyx
uhm, ok..
So let's say I'm in a blasterfitted megathron..
I jump in and see a lone hulk in lowsec..
The chances for me just staying still in space, not doing anything are pretty slim..

So the system calculates that I'm locking the hulk and blasting it into pieces.. but when the lagspike ends everything is corrected and I'm just floating in space beside a hulk? Rolling Eyes


let's play scientist, in your experience, is that what happens? empirical data and all


Yeah, but if it's a system based on assumptions..
It would mean that each time someone did something really odd, you wouldn't see it until you got the correct data..

I mean, a small frigates warps in and starts scrambling and shooting at you..
But that's just an assumption by the system and suddenly everything reverses and apparently he selfdestructed as soon as he came out of warp :P

If it's supposed to work on that scale, then I think it will just be confusing..

Faife
Dreddit
Test Alliance Please Ignore
Posted - 2008.09.18 03:41:00 - [16]
 

Originally by: Dharyx

Yeah, but if it's a system based on assumptions..
It would mean that each time someone did something really odd, you wouldn't see it until you got the correct data..

I mean, a small frigates warps in and starts scrambling and shooting at you..
But that's just an assumption by the system and suddenly everything reverses and apparently he selfdestructed as soon as he came out of warp :P

If it's supposed to work on that scale, then I think it will just be confusing..


ever notice how people jump around in weird ways in FPS when you're lagged, like in the days of dial up?

same thing. even those games do motion prediction, and then correct when they're wrong.

this is how the sausage is made, so to speak.

Dharyx
Posted - 2008.09.18 04:23:00 - [17]
 

Edited by: Dharyx on 18/09/2008 04:26:20
Originally by: Faife
Originally by: Dharyx

Yeah, but if it's a system based on assumptions..
It would mean that each time someone did something really odd, you wouldn't see it until you got the correct data..

I mean, a small frigates warps in and starts scrambling and shooting at you..
But that's just an assumption by the system and suddenly everything reverses and apparently he selfdestructed as soon as he came out of warp :P

If it's supposed to work on that scale, then I think it will just be confusing..


ever notice how people jump around in weird ways in FPS when you're lagged, like in the days of dial up?

same thing. even those games do motion prediction, and then correct when they're wrong.

this is how the sausage is made, so to speak.


Yes, I'm aware of that..
But that's just movement.. basically they just continue in the same direction..

But if you'd take it a bit further and predict who they would shoot, the results might be hilarious.. like everyone dies.. no wait, everyone except 1 guy, no wait, he blew himself up with a grenade, ok you're stabbed in the back, no wait he missed..

But then again, I don't think I fully understand how the system would work, as it sounds now it's just silly..
Rather no information at all than the wrong information, imo..

I mean, would you really want fleet battles were 50% of the stuff you see actually doesn't happen?
Oh noes, I got caught with my pod in a dictor bubble.. oh well nothing to do about it, I'm screwed now..
5 sec later, oh wait, the dictor pilot forgot to bubble.. I'm free.. no wait, now I actually _am_ bubbled..

Kazuma Saruwatari
Posted - 2008.09.18 04:38:00 - [18]
 

so basically, to prevent fleet/blob lag we have to increase the distance between each ship and/or not have such tightly packed ship blobs to begin with?

Ugh, feeling dizzy.

BiggestT
Caldari
Amarrian Retribution
Posted - 2008.09.18 05:25:00 - [19]
 

Originally by: Faife
Originally by: Sarah Tuttle
I think I understand what he is saying. What I don't understand is how any computer on earth can handle that kind of load and relay it correctly to 30,000+ users at the same time.




many computers. Tranquility is a whole lotta computers.


Hivemind ftw Cool

Xessej
Posted - 2008.09.18 06:46:00 - [20]
 

Edited by: Xessej on 18/09/2008 06:46:45
Now that's some nifty design.

My degree is in math and I work as a programmer so I'll try and explain what they're doing in less technical terms.

Every second the server farm, Tranquility isn't a single box but a big collection of linked servers, determines every object you might interact with in the next second. Every object that might be acted on by more than a single player is marked and handled seperately.

So when you're alone in a belt or mission running solo your client and the servers are not worrying about anyone else nearby since they cannot interact with you in the next second. Therefore in this circumstance the only source of lag is the sheer number of clients each server node has to keep track of. This is likely where the weekend Jita lag comes from.

Now when you can interact with another person(s), things get a lot more complicated. Eve doesn't respond instantly to our input but delays until at least the start of the next second so all the involved clients as well as the server simulate each second together. With so much interaction happening, simply being able to see another ship is an interaction under this scheme, it is reasonable to expect increasing lag as more ships come into sight. This seems to be the primary source of lag involved with fleet battles.

A clever solution to the problem and one that accurately makes use of the low cost of powerful computing hardware. I would assume that eventually they will simply spawn off particularly busy stations or other locations where a lot of clients are at onto standby servers. For instance moving the simulation of the area surrounding a POS being attacked from the rest of the system would serve to reduce some of teh server load and still allow access to teh rest of te system even if the battle site itself is extremely lagged.

Software solutions are likely possible by pruning which simulations to run together and which to run seperately but simply making the decision on how to run each might take up enough time to give a very small net gain.

Saietor Blackgreen
Armored Saints
Posted - 2008.09.18 07:23:00 - [21]
 

Edited by: Saietor Blackgreen on 18/09/2008 07:24:07
So, the bubbles are calculated not to predict the actions - that woulld be silly - but to define the players and objects that may interact in theory, and thus define the information that needs to be collected to update each of them.

Or, rather, to reduce the amount of information sent and requested, so only relevant information is actually sent through to the client.

Makes sense.

On the last 3 buullets - OMG! CCP, you should release the info on such facts, they add so much flavor to the universe.

Evanade
Rionnag Alba
Against ALL Authorities
Posted - 2008.09.18 07:33:00 - [22]
 

Someone tell me whether this is true or not

Ryoji Tanakama
Caldari
Indicium Technologies
Hephaestus Forge Alliance
Posted - 2008.09.18 12:02:00 - [23]
 

Originally by: Evanade
Someone tell me whether this is true or not

It would neatly explain how you can individually press f1 to f8 yet still have all 8 modules activate together (as you pressed each key within the same interval/frame).

Roy Batty68
Caldari
Immortal Dead
Posted - 2008.09.18 12:49:00 - [24]
 

Originally by: Faife

Quote:

6) Send only the information relating to a player's intersected causality bubble/matrix to that game client. (Dump client's simulation state from pervious frame in lieu of the server's state if they disagree.)



Desync here...?

Makes one wonder how extended desync is even possible.


Juliette Leblanc
Gallente
Posted - 2008.09.18 13:13:00 - [25]
 

Originally by: Saietor Blackgreen
So, the bubbles are calculated not to predict the actions - that woulld be silly - but to define the players and objects that may interact in theory, and thus define the information that needs to be collected to update each of them.

Also to partition the actual simulation: each blob of intersecting bubbles will be handed over to a separate tasklet.

CCP Greyscale

Posted - 2008.09.18 13:17:00 - [26]
 

Originally by: Sarah Tuttle
I think I understand what he is saying. What I don't understand is how any computer on earth can handle that kind of load and relay it correctly to 30,000+ users at the same time.




I'm pretty sure it's just one line of code...

Juliette Leblanc
Gallente
Posted - 2008.09.18 13:20:00 - [27]
 

Originally by: Korizan
NOw that I think some more about it.

IF they are using a ships potential for movement in thecausality bubble equations then...

A fleet of intercepter would actually create more bubbles then a a fleet of same numbers in a carriers.

So with that you could actually say that the faster ships go the more bubbles you get and the greater the problem.

So it is not only numbers but speed that also causes the problems.

Interesting even if it is pure speculation.

It is not pure speculation.
CCP has been telling us several times that they are having problems with speed. They are working on nerfing ship speeds because (among other things) they cannot increase missile speed (travel and explosions speed) as their physics engine would have problems handling that.
Think about it and it perfectly fit the picture.


Winterblink
Body Count Inc.
Pandemic Legion
Posted - 2008.09.18 13:25:00 - [28]
 

13) Become self-aware, perceive humans as threat, launch nukes

Tippia
Caldari
Sunshine and Lollipops
Posted - 2008.09.18 13:37:00 - [29]
 

Originally by: Winterblink
13) Become self-aware, perceive humans as threat, launch nukes
Meh… could be worse.

13) Become self-aware, perceive humans as threat, launch MMO to keep them sedated.

deathatlaby
NAUCOM
Posted - 2008.09.18 13:41:00 - [30]
 

Originally by: CCP Greyscale
Originally by: Sarah Tuttle
I think I understand what he is saying. What I don't understand is how any computer on earth can handle that kind of load and relay it correctly to 30,000+ users at the same time.




I'm pretty sure it's just one line of code...


The internet is a series of tubes...


Pages: [1] 2 3 4 5

This thread is older than 90 days and has been locked due to inactivity.


 


The new forums are live

Please adjust your bookmarks to https://forums.eveonline.com

These forums are archived and read-only