Jump to content

  • Log In with Google      Sign In   
  • Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!


We're also offering banner ads on our site from just $5! 1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


How to deal with adding and destroying game objects in UDP?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
14 replies to this topic

#1 savail   Members   -  Reputation: 333

Like
0Likes
Like

Posted 03 July 2013 - 04:17 AM

Hey,

I'm using ENet library and it ensures that even packets sent with UDP protocol will be sequenced and packets with lower numbers than those currently received, will be discarded. So it ensures proper order of packets but as we know UDP is still not reliable.

And here's my problem. How to design the communication between peers and hoster to ensure that the info about game objects, which have just been created or destroyed, will be always delivered?



Sponsor:

#2 Kylotan   Moderators   -  Reputation: 3338

Like
0Likes
Like

Posted 03 July 2013 - 05:19 AM

Enet allows for some messages to be reliable. So you can make the important messages reliable.



#3 savail   Members   -  Reputation: 333

Like
0Likes
Like

Posted 03 July 2013 - 05:36 AM

hmm, yeah it's true but here comes another problem tongue.png. I store all game objects in one std::vector on hoster and when sending data from hoster to player, the thing which identifies which game object this packet belongs to, is the index of the vector. Therefore, after deleting 1 object on hoster the vector is reduced and so indexes change. What if the reliable packet containing information about deleting an object arrived to the client later than UDP packets which would already contain information with reduced vector indexes? The data would go to inappropriate objects until client will get the message about deleting the mentioned object.


Edited by savail, 03 July 2013 - 05:38 AM.


#4 Tispe   Members   -  Reputation: 1038

Like
1Likes
Like

Posted 03 July 2013 - 06:06 AM

You can store an ID in the player object. Use reliable packets to notify player what objects he need to create or destroy. 

 

Use an std::list or std::map as a container for your player objects. Forget about using indices as IDs.



#5 savail   Members   -  Reputation: 333

Like
0Likes
Like

Posted 03 July 2013 - 06:31 AM

hmm, yeah it's true but here comes once again another problem :P. How to attach ID to objects? In some MMO games which are based on UDP (DC Universe for example) server works all the time. That means that there are a lot of objects created and destroyed during server's lifetime. If they increase ID of new objects by 1 all the time, the ID would eventually exceed the maximum value and would cause server crash I guess. My game is based on matches so it is less likely to happen but I'm curious how ID should be attached in a MMO such as DC Universe?



#6 samoth   Crossbones+   -  Reputation: 4913

Like
2Likes
Like

Posted 03 July 2013 - 07:21 AM

In some MMO games which are based on UDP (DC Universe for example) server works all the time. That means that there are a lot of objects created and destroyed during server's lifetime. If they increase ID of new objects by 1 all the time, the ID would eventually exceed the maximum value and would cause server crash I guess.

 

First, the server will not crash (not necessarily, anyway) if you exceed the maximum value. What will happen is that the number will wrap around (overflow).

 

That, by itself, does not do anything special (not on any real, existing computer, anyway -- in theory there could exist CPUs that generate a trap on overflow). Of course you do have the problem that you will "reuse" old IDs, but that is no problem if they have been destroyed already. Running against physical memory limits (considering 4 billion game objects with a 32-bit ID!) is much more likely to happen, and much sooner.

You do need to make sure that you remember which indices have been deleted, if you want to be safe (in the easiest case, by remembering the lowest valid index, otherwise via a freelist or similar).

 

Quite likely, relying onto "luck" will work just fine, too (because you just don't create that many objects that fast), but I'd recommend doing it properly anyway. Relying on luck is rarely a good idea, if something can go wrong, it will eventually go wrong too (maybe in a few years when nobody remembers why).

 

Depending on what representation you use for your ID, overflow happens considerably sooner or later. Assuming your server creates a 10,000 new objects per second (which is an awful lot!), a 16-bit ID will overflow in 6 1/2 seconds, and a 32-bit ID will overflow after 23 hours, 18 minutes. A 64-bit ID will not overflow during your lifetime, or during the likely remaining existence of mankind on this planet. That is, unless you deem it reasonable to expect that we haven't had World War III, or otherwise completely destroyed the planet in 58 million years from now, and that your computer program is still running by then.

 

With that in mind, if you can't be bothered to keep track of used and freed IDs, use a 64-bit ID (or use a 48-bit ID and assume that the the server will reboot at least once every 800 years!). You'll never have to worry. Of course it eats up a few extra bytes of storage, but since most IDs that appear together will be very similar except in the last few bits, you can compress those away.


Edited by samoth, 03 July 2013 - 07:25 AM.


#7 savail   Members   -  Reputation: 333

Like
0Likes
Like

Posted 03 July 2013 - 07:47 AM

Thanks a lot for answer! I thought about using 64 bit ID but didn't expect it to survive for so long :D. It will work for me then I guess :P. Thanks for the info again.

Well, I have another question related to IDs. If all objects are identified by their IDs (not by indices of the container they are in) how could I quickly find the appropriate object in order to ascribe data to him? Is there no other way than iterating through all objects until I find the one with right ID?



#8 samoth   Crossbones+   -  Reputation: 4913

Like
2Likes
Like

Posted 03 July 2013 - 08:10 AM

Using a map (as in C++ std::map) would be one easy and obvious way of reducing "must iterate every element" to "must only touch log2(n) elements".

 

Another easy way (a hack, but nevertheless) would be to use the object's memory address as ID. There's nothing to look up and nothing to search, and the ID is guaranteed to be unique.

Just make sure you don't free and immediately reuse an address (as it's the case with most allocators) and then assume that the client "magically" knows that this is now a different object. But hey, hacks almost always come with a little "gotcha".

One solution to this issue is, by the way, the same as you use in lockfree concurrent algorithms to combat the ABA problem: Exploit the fact that objects are aligned (most of the time to 8 or so bytes) so the lowest few bits are all zero and you can put a counter into these.


Edited by samoth, 03 July 2013 - 08:15 AM.


#9 savail   Members   -  Reputation: 333

Like
0Likes
Like

Posted 03 July 2013 - 08:56 AM

This idea about using object's memory address is just brilliant! Though I'm afraid I'm still not pro enough to implement it tongue.png but I would like to find out sth more about this if you don't mind ^^.

I'm not sure how could it work? The server would create an object on its side and would send it to client together with its memory address? Then client would have to create the object in the same memory location, as it had been created on the server, using sth like http://www.parashift.com/c++-faq-lite/placement-new.html? But do I have certainty that the memory address which was free on the server will be free on the client as well? Or maybe I'm completely wrong with my assumptions?tongue.png


Edited by savail, 03 July 2013 - 08:57 AM.


#10 hplus0603   Moderators   -  Reputation: 5514

Like
1Likes
Like

Posted 03 July 2013 - 09:54 AM

This idea about using object's memory address is just brilliant!


That will be different between the server and each of the clients, so the clients would still need a look-up dictionary if you used the server's memory address. That may still be OK. Personally, I'd just use an incrementing 32-bit integer. If I create 100 objects per second, that will still let me go 40,000,000 seconds before wrapping. That's almost 463 days, or over fifteen months.

Btw: The "go-to" container for "bags of stuff I need to find again" is a hash table. In C++, it's called the std::unordered_map<>. It is O(1) for insert, find, and delete. However, if you iterate over it, items will come out in some undetermined order; not nicely sorted as in std::map<>. If you don't yet have a C++11 standard library, you probably have this container as std::tr1::unordered_map<> instead.
enum Bool { True, False, FileNotFound };

#11 samoth   Crossbones+   -  Reputation: 4913

Like
1Likes
Like

Posted 03 July 2013 - 10:43 AM

This idea about using object's memory address is just brilliant! Though I'm afraid I'm still not pro enough to implement it tongue.png but I would like to find out sth more about this if you don't mind ^^.

I'm not sure how could it work? The server would create an object on its side and would send it to client together with its memory address? Then client would have to create the object in the same memory location, as it had been created on the server, using sth like http://www.parashift.com/c++-faq-lite/placement-new.html? But do I have certainty that the memory address which was free on the server will be free on the client as well? Or maybe I'm completely wrong with my assumptions?tongue.png

 

Rather the client would obtain "some number" from the server that it uses to refer to an object. It doesn't know where the server had that number from, the server could have used sequential numbers or pulled a random number out of its rear opening.

 

The client doesn't need to know, since what the number is or where it came from is entirely irrelevant. If the server tells you "Your friend Joe logged in as 43664", and later "43664 is messaging you", or you tell the server "I am casting a 'heal' spell at 2352978",  everybody who is involved knows what to do with the information.

 

Now, as to where the number came from, this could be just the memory address of the object as stored on the server.

 

There exists one big problem, however. Imagine "Joe" logs off and "Jim" (whom you do not know at all!) logs in. Joe logging off means the object is destroyed and the allocator puts the now invalid memory location to its free list. As Jim logs in, the allocator spits out the same address again from the top of its free list (this is common allocator behaviour, because it's cache-friendly).

 

As it happens, Jim is an annoying person who asks random people for cash. So eventually the server sends you "43664 is telling you 'got any cash for me?'". And of course, your client knows that 43664 is your friend Joe. So you see that your friend Joe needs money and you give him some. Bang.

 

Let's say that your objects have a size of 16 bytes (and the first one is properly aligned), this means that in every object's address the lowest 4 bits are zero.

Therefore, when you free an object and your allocator reclaims the memory address into its free-list, it can increment a 4-bit counter in those useless bits.

 

When Joe logs off (i.e. Joe's object is destroyed), the allocator puts the memory block at 43664 back to the free-list. But before doing so, it increments the counter, so the pointer becomes 43665. When Jim logs in, the allocator returns 43665 (and on subsequent iterations, 43666, 43667, and so on up to 43679, after which it wraps back to 43664). This could happen in the server's logic outside the allocator too, of course (doesn't matter how it's done).

 

Now, what's important, the logic in the server knows about this pointer modification, so before doing anything with a pointer obtained from the allocator, it does an & 0xfffffff0 operation on it. This is effectively a no-op on a fresh pointer, and properly aligns any recycled "meddled" pointer back to the correct address. However, the server tells the client "43665", not "43664". Your client doesn't know any of this and doesn't care where the number came from. However, it can tell that 43664 and 43665 are not the same number, so this is most definitely not Joe.


Edited by samoth, 03 July 2013 - 11:05 AM.


#12 savail   Members   -  Reputation: 333

Like
0Likes
Like

Posted 03 July 2013 - 04:47 PM

Thanks a lot everybody for answers and sharing your knowledge!

@samoth, thanks for such detailed explanation. It seems not to be as perfect as I made it up in my previous post :P but still does not require server to waste time on searching for appropriate object - only clients have to. Anyway, it's much more clear now and I can even try to implement it on my own :D. Thanks a lot



#13 Icebone1000   Members   -  Reputation: 1112

Like
0Likes
Like

Posted 04 July 2013 - 07:41 AM

Using a map (as in C++ std::map) would be one easy and obvious way of reducing "must iterate every element" to "must only touch log2(n) elements".

 

Another easy way (a hack, but nevertheless) would be to use the object's memory address as ID. There's nothing to look up and nothing to search, and the ID is guaranteed to be unique.

Just make sure you don't free and immediately reuse an address (as it's the case with most allocators) and then assume that the client "magically" knows that this is now a different object. But hey, hacks almost always come with a little "gotcha".

One solution to this issue is, by the way, the same as you use in lockfree concurrent algorithms to combat the ABA problem: Exploit the fact that objects are aligned (most of the time to 8 or so bytes) so the lowest few bits are all zero and you can put a counter into these.

It got me thinking...Instead of go to the burden of using mem address and caring about reusing the same address (which is very likely), why not keep using the indexes, AND a count of reused/changed index? I think I just figured out an osome algorithm \o/..

 

I also use vectors to store game objects, iterating a map is horrendous, (I decided to always avoid any containers in favor of vectors after testing with A star, seriously, I believe vectors performance are hardly beaten by big O notations, memory use just counts more, thats my current mantra, would you guys opine?)

 

Anyway, when I kill an object, I do the swap to last element and reduce vector size trick, so what I could do here is count the times a object changed index (store in the object itself). So to communicate to the server, you send not only the index, but the use count, if the server get the count different for the same index, he knows it needs to white for the reliable packet saying stuff changed..

 

Not sure, it just poped on my head. Isnt it much more intuitive then using mem addresses?



#14 samoth   Crossbones+   -  Reputation: 4913

Like
0Likes
Like

Posted 05 July 2013 - 03:10 AM

It got me thinking...Instead of go to the burden of using mem address and caring about reusing the same address (which is very likely), why not keep using the indexes, AND a count of reused/changed index?


Using indices instead of pointers to refer to objects is basically the same, maybe more elegant. Indices are contiguous without alignment (i.e. there are no unused bits as in a pointer), after element 5, element 6 follows. Plus, you have the nice property that indices start at zero, so it is easier to do bounds checking (only need to test against the largest allowed index).

However, you still need to be careful that a new object with the same index is recognized as a different object on the other side, so you would need to do something different to make them unique.

This could be done by adding a counter to every object that isn't ever touched by the constructor, but incremented by the destructor. Of course this invokes UB (as the counter is used but never initialized) but it will work, as "uninitalized +1" is still different from "uninitialized" every time, no matter what the value is. You don't care that it's something in particular, you only care that it's different for different objects.

However, the server already knows anyway, it's the client that is troublesome. To communicate the fact that objects A and B are different (although they have the same index) you'd have to send that counter to the client, and there you have exactly the same as with the other approach again.



#15 wodinoneeye   Members   -  Reputation: 856

Like
0Likes
Like

Posted 13 July 2013 - 06:04 PM

Servers often have to be very robust (like handling disconnects/client restarts/long delays)  so on sending a message directed to an object if that objects unique ID doesnt exist (on Client) then the Client can generate a query to the Server to fetch all the pertinant object info to reestablish it on the Client  (this beyond a general reconnect process that pulls all the needed gamestateefficiently as a batch - but that itself needs patching for any changes WHILE that download stream is built)

 

ALot of this stuff is higher level than the network protocol which is one reason to use lower level UDP which then allows Application level decisions to be made (versus TCP which can lock you into repeated sends of out of date/irrelevant data)


--------------------------------------------Ratings are Opinion, not Fact




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS