• 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
Pfaeff

Reliable UDP and packet order

6 posts in this topic

Hi,

I have a working basic network communication via udp for my hack&slay RPG game. I implemented reliability using acks.
Messages will be resend, if the ack didn't arrive within 2*RTT. Everything seems to work pretty nicely, but there is still one problem to be solved: the case when reliable messages are received out-of-order, which will lead to inconsitencies among the players.

As far as I know there are two ways to solve this problem:
[list=1]
[*]let all players live x ms in the past and hope that all necessary packets arrive during that time, if not, resynchronize the player, or kick him from the server
[*]do a rollback and send anti-messages for any reliable messages that where sent (those might in return trigger more anti-messages and so on)
[/list]

I don't like the second solution, because it is rather complicated to implement and anti-message introduce much extra traffic. So I would opt for the first method. Or are there other more suited techniques that I don't know about?

Greetings,
Pfaeff
0

Share this post


Link to post
Share on other sites
[quote]if the ack didn't arrive within 2*RTT.[/quote]

I'd start with 20*RTT. And if client cannot continue without receiving past ack, UDP is the wrong choice anyway, just use TCP. UDP is good choice if can ignore some lost packets without resending them.

Even on best networks, hiccups happen. And 20x over low-latency connection of 100ms is only 2 seconds. Spikes up to 5 seconds happen regularly. Then there's drift and spikes, maybe shared wifi and someone downloads something big-ish and stalls the others or just generally increases latency.

IMHO, unless you don't completely tolerate up to 1000ms latency, let alone disconnect those that exceed this, the protocol will be next to useless in real world.

it's true that dedicated players want to have <50ms ping, but for majority having reliable connection will be worth much more. Look at Minecraft, people are ecstatic over how nice it looks and how much fun it is, only to learn that for them it runs at 2-3 fps and takes 5 minutes to load.

[quote]because it is rather complicated to implement[/quote]

Yes it is. And that's even without real world testing, which will throw even the best designs off.


For hack&slash, evented simulation over TCP on global scale works fine. 3 examples: Starcraft2, Diablo3, [url="http://www.realmofthemadgod.com/"]Realm of mad god[/url]. Edited by Antheus
1

Share this post


Link to post
Share on other sites
Thanks a lot, what you're saying about resending packets sounds reasonable.

I want to use UDP, because I plan on implementing some gameplay elements that require a bit more responsiveness. This project is also for me to learn some network programming, because I've never done such before. Even if UDP is overkill for my application (which might or might not be the case, but it gives me some tolerance), I will be able to apply those techniques to future projects that require a fast and responsive network system.

The problem I have is the following:[list]
[*]Let's say a player with 10 life drinks a potion at t0 and gains 10 additional life
[*]That player gets hit for -10 life at t1
[*]The first packet gets lost for one client and is resent some time later. For him the player will get hit and die, while for all other players he will be alive.
[/list]

I know that this can be prevented if the server just sends the absolut life values for the players. In this case he will die either way, but a bit later for one of the players.
The thing is that I am not sure if that will always work. There might be other mechanics that I didn't think of for which no such simple solution exists. Edited by Pfaeff
0

Share this post


Link to post
Share on other sites
Sounds like you need guaranteed order of delivery, in which case UDP is the wrong tool for the job unless you want to basically reinvent TCP on top of it (which IMHO is [i]usually[/i] a waste of time especially if you're new to networking).

I really suggest you look at TCP first. It's much easier to get a good model going that isn't open to all kinds of bugs and exploits due to dropped packets and such. And frankly it works fine and is plenty fast - many "Action Oriented" games use TCP for their network model with no real problems.

Once you're comfortable with basic networking you can look into reliable UDP models, but I don't recommend starting there.


This forum's FAQ has a lot of great material on this kind of thing, by the way; if you haven't browsed through there yet you really ought to.
0

Share this post


Link to post
Share on other sites
[quote]The problem I have is the following:[list]
[*]Let's say a player with 10 life drinks a potion at t0 and gains 10 additional life
[*]That player gets hit for -10 life at t1
[*]The first packet gets lost for one client and is resent some time later. For him the player will get hit and die, while for all other players he will be alive.
[/list]
[/quote]
Make a drinking animation that lasts 1 second, where health is only restored after that one second. It will cover the latency and hint player that they are vulnerable.

[quote]The first packet gets lost for one client and is resent some time later.[/quote]

"The packet ain't lost, it's restin'."


Each action, message, command, etc... has a timestamp of sorts.

Some actions, especially ones which are frequent, can be sent as "unreliable". For movement, they would arrive with following timestamps: 1,2,4,3,7,8,9,10. 3 would be discarded, since we already received 4. Packets 5 and 6 are pinnin' for the fjords, but since we received 7 and later, we don't care.

Now here's a catch - what about message 11? Was it sent? Was it lost? What about 12, 13, ....?

And what if now send an action message, such as picking up something - am I in range or not?
0

Share this post


Link to post
Share on other sites
[quote name='ApochPiQ' timestamp='1336505918' post='4938468']
Sounds like you need guaranteed order of delivery, in which case UDP is the wrong tool for the job unless you want to basically reinvent TCP on top of it (which IMHO is [i]usually[/i] a waste of time especially if you're new to networking).

I really suggest you look at TCP first. It's much easier to get a good model going that isn't open to all kinds of bugs and exploits due to dropped packets and such. And frankly it works fine and is plenty fast - many "Action Oriented" games use TCP for their network model with no real problems.

Once you're comfortable with basic networking you can look into reliable UDP models, but I don't recommend starting there.


This forum's FAQ has a lot of great material on this kind of thing, by the way; if you haven't browsed through there yet you really ought to.
[/quote]
I already did that, but when I was finished with the system based on TCP, I decided to try out UDP.

[quote name='Antheus' timestamp='1336575055' post='4938680']
[quote]The problem I have is the following:[list]
[*]Let's say a player with 10 life drinks a potion at t0 and gains 10 additional life
[*]That player gets hit for -10 life at t1
[*]The first packet gets lost for one client and is resent some time later. For him the player will get hit and die, while for all other players he will be alive.
[/list]
[/quote]
Make a drinking animation that lasts 1 second, where health is only restored after that one second. It will cover the latency and hint player that they are vulnerable.

[quote]The first packet gets lost for one client and is resent some time later.[/quote]

"The packet ain't lost, it's restin'."


Each action, message, command, etc... has a timestamp of sorts.

Some actions, especially ones which are frequent, can be sent as "unreliable". For movement, they would arrive with following timestamps: 1,2,4,3,7,8,9,10. 3 would be discarded, since we already received 4. Packets 5 and 6 are pinnin' for the fjords, but since we received 7 and later, we don't care.

Now here's a catch - what about message 11? Was it sent? Was it lost? What about 12, 13, ....?

And what if now send an action message, such as picking up something - am I in range or not?
[/quote]
My current implementation supports unreliable messages and I plan on using them as you suggested. If the received message has an older "timestamp" as the most recently received message, the new one is simply discarded.

I think the problem of packet ordering is fundamental for every game and that is why I asked for methods to deal with it. Of course there are games in which such problems are not so much apparent and there are games where those problems can be circumvented using clever design of gameplay as described in my first post or in the example of Antheus. But there might be cases in which that won't work (none that I can think of atm though). If these cases are rare and isolated, a simple stop-and-wait strategy could work. Other cases might require some resynchronisation with the server, but I am not sure if more sophisticated methods may be required for my needs.
0

Share this post


Link to post
Share on other sites
To implement ordering guarantees to an UDP datagram stream, store a running "packet number" counter in each sent datagram. When receiving datagrams, you can examine the packet numbers to detect out of order receives. When you receive a datagram out of order, you generally have two choices:
- Queue up the datagram and wait for the earlier datagrams before processing the first datagram you received out of order. (This is what TCP does, and it causes head-of-line blocking and incurs additional latency)
- Immediately process the datagram and choose to discard the older datagrams in case they will be received in the future. This is called "latest data guarantee" messaging, because this method does not guarantee that all datagrams will be processed by the receiver, but that at least the most recent/newest version of the data will be seen by the receiver.

Another problem you will need to solve with UDP is accidental datagram duplication caused by the network. UDP does not guarantee that if you send one datagram, that the other end would receive at most one datagram, but instead, the datagram may get duplicated along the way, e.g. due to resends. When you have these unique packet number counters attached to datagrams, you can easily detect duplicate datagrams and discard them.

I have implemented an UDP-based game networking library, perhaps that is of help for reference: [url="http://clb.demon.fi/knet/_kristalli_u_d_p.html"]kNet over UDP documentation[/url], source code that implements [url="https://github.com/juj/kNet/blob/stable/src/UDPMessageConnection.cpp"]kNet over UDP[/url].
1

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