• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
savail

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

10 posts in this topic

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?

0

Share this post


Link to post
Share on other sites

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

0

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

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.

1

Share this post


Link to post
Share on other sites

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?

0

Share this post


Link to post
Share on other sites

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
2

Share this post


Link to post
Share on other sites

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?

0

Share this post


Link to post
Share on other sites

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
2

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

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.
1

Share this post


Link to post
Share on other sites

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
1

Share this post


Link to post
Share on other sites

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

0

Share this post


Link to post
Share on other sites

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?

0

Share this post


Link to post
Share on other sites
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.

0

Share this post


Link to post
Share on other sites

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)

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0