network engine

[x3n]

Hm, if you just want to go through all objects, it's fast enough (like all lists), but if you search only a few objects, it might be better to store them in an extra list (or in an array, if you can manage the dynamic size). Oh, and a map ist very fast if you want to access something, but it's slow if you add or remove objects.

But I talked to bensch last week an he said, it might be a good idea to store all synchronisables in a map. if you send the data in the same order the objects are in the list, the list is probably fast enough, but if they are in random order, a map might be better.

But iterating through the whole list for every object is surely the worst idea.

[greenman]

Well, what we'll definitely do is send the items in the same order as stored in the list, but it would be better if we didn't update all items on each sync but only the items that changed (more efficient) then it would be inefficient to go through the whole list just to update some items in it ...

[patrick]

Just one small hint: never ever, ever, ever try to implement your own lists/stacks/queues/maps. Never!

Vectors for example are arrays and manage the size dynamically.

Never, really!

Use stl library, good documentation at: http://www.cplusplus.com/reference/stl/ There you also find informations about speed of the containers and some examples. Especially look at the table at the bottom of the page.

And: You want code run-time to be scalable so try to be below <= O(n^2). If you use stl::maps you will get O(n log(n)), which is the fastest way to do that (it's impossible to do it faster). Sure there is an overhead in adding elements to this map. But this is mainly at initialization time.
Maps help you also keeping the list on all computers in the same order, (because the keys are always the same).

Hope this helps.

[greenman]

Great site, thank you !

Will try to use stl as much as possible from now on
It's a shame that we never heard of that in info I...

I think maps will be a good thing for our gamestate processing and vectors for our client list.

btw x3n: Is it possible to have multiple gamestates accessible at the same time with our factory concept by now? this would be important to extend the network engine in the future.

cheers

[x3n]

btw x3n: Is it possible to have multiple gamestates accessible at the same time with our factory concept by now? this would be important to extend the network engine in the future.

Sorry, I don't understand the question... what is a "gamestate" from the factory's point of view?

[greenman]

Sorry, I don't understand the question... what is a "gamestate" from the factory's point of view?

What I mean with gamestate is all data every object has at a certain moment. This of course changes every tick and if we want to be able to calculate back (delay), then it's neccessary to not just keep a dump of the passed gamestates but also a list or tree or whatever the universe is built up like.

I hope you know now what I mean ...

[x3n]

I understand, but no, there is no history in the class-hierarchy...
but is this really necessary to calculate ping-compensation? I know of mutators for unreal tournament... In UT mutators are written in a script language and can't modify the engine, but they managed to simulate zero-ping situations, so I'm confident there's a way without engine-modifications but with math only.

[greenman]

Hm... well I think there has to be some kind of engine modification, either in the ode or in the universe.
We could maybe provide functions to simulate a (running) gamestate (with lists) for ode by using our dumps/snapshots (should theoretically be possible). But then ode would have to use the functions for the right gamestate and that would implicate modifications of the ode...

How does ode access objects in the world?

[x3n]

There is no ODE...

And you don't necessarily have to simulate something, there are different approaches:

Approach #1: slower than #2, easy, inaccurate for higher pings: (!!!SERVERSIDE!!!)
1) Iterate through all players (p1), remember the p1.ping
2) Iterate through all other players (p2), calculate p2.position -= p2.velocity*p1.ping
3) Iterate through all projectiles of p1, check collision between them and the p2's

Approach #2: fast, a bit more complicated, inaccurate for higher pings: (!!!CLIENTSIDE!!!)
1) Remember the clients ping
2) Iterate through all other players (p2), calculate p2.position += p2.velocity*ping
3) Display the players on the predicted position

approach #3: fast, a bit more complicated, security issue: (!!!CLIENTSIDE!!!)
1) Let the player calculate hit or no hit on his client
2) Send the result to the server

approach #4: slow, complicated, accurate: (!!!SERVERSIDE!!!)
1) Simulate

[greenman]

Until now I always thought #1-3 would be too inaccurate for our needs, but now I think they might be ok... I personally think #1 or #2 are best.

#2 maybe is probably bad looking if we have pings above 100-200 ms, because there will be a lot of "jumps" in the display...

Well, so we have at least an option to be a bit more accurate

[x3n]

Yes, you're absolutely right about #2, but I think there won't be much players with ping > 150. This is only the case with transcontinental or 3rd-world connections. I prefer #1 or #2 too for pings < ~150. Both fail with higher pings, but we can't have everything.

[x3n]

Oh, a sidenote:
I just remembered that I did some tests concerning movement prediction with unreal tournament some time ago. It was something like #1.
Tested it with ping ~250 (Well ok, I don't exactly know the way UT calculates the ping) and it worked really good. It wasn't perfect of course, as I for example couldn't reliably determine if it was a headshot or not (UT2004 with a utcomp mutator has really small headshot-boxes), but "hit or no hit" worked with around ~85% accuracy.

I used something like this:
if (on-ground)
position + ping*velocity
else
position + ping*velocity + 1/2*ping^2*gravity*(0,0,-1)

To be more accurate Ii should have predicted the on-ground condition too, but that would have been too much

So what I want to say: #1 and #2 should work up to ping 200, but I don't know, whether #2 may look strange.

[greenman]

Hm... now I got some problems with stl-maps.
I get an error compiling network/ConnectionManager.cc (branch FICN)

Could someone please have a look at that? I can't see what's wrong ...

Thanks in advance!

edit: Seems like stl maps and structs do not fit together ...
Does anyone know, what the problem is with:

Code: Select all

#include <map>
using namespace std;
struct test{
  int a;
  int b;
};

int main(){
  test t={0,0};
  map<test, int> map;
  map[t]=1;
  return 0;
}

The example for some reason wont compile ...
the problem here is, that I can't use pointers, because I need the key value to lookup the map ... (there are different structs with same value, but different addresses)

[x3n]

I think the problem is the following:
std::map needs a < operator to balance/sort the tree. Because you're using the user defined struct "ENetAddress", the < operator isn't defined and therefore the std::map doesn't work.

Because ENetAddress is defined in enet, we can't change it directly. but there are 3 options:
1) Use pointers
2) Define a standalone < operator
3) Use a wrapper class

[greenman]

Unfortunately #1 isn't possible, because we save the address once and then we get other packets with same ENetAddress, but different location of ENetAddress (was that clearly understandable? )

edit: Am I right, that it should work by using

Code: Select all

bool operator< (test a, test b){
  // .......
}

for the above example ?