• 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

Flow Control, Prioritizing Data for Packets, and Thread Communication

3 posts in this topic

I'm designing a top-down twitchy space shooter a la Subspace/Continuum, and am in the process of doing research to plan my server architecture (built in C# with lidgren-gen3, communicating to a Unity Web Client for the game client -- very slick stuff). I'm primarily basing it off of the FPS model, with UDP packets sent at regular intervals to players (20-30 Hz). I have a number of questions regarding these packets.

In particular, I studied [url="http://www.gdcvault.com/play/1014345/I-Shot-You-First-Networking"]David Aldridge's Halo Reach GDC talk[/url], where he talks about flow control and the server model, and I want to adopt something a little simpler to begin with. My simpler system goes a little something like this:

- Sends control information to the server
- Control information is immediately realized locally
- Other entities in the world are Interpolate based on past received state unless new state contradicts (dead reckoning, etc.)
- (Possible expansion: Receive other players' control input and use that for prediction)

- Receives control information from clients and modifies the world accordingly
- Each tick creates a new immutable state from the last, to avoid errors caused by update order
- Dispatches delta-compressed state updates to each client regularly (based on their last acknowledged received state)
- If bandwidth allows, dispatches events to justify change in state (weapon fired, bomb exploded, etc.)
- (Possible expansion: Distribute other players' control input to clients for prediction)

I plan on running at least two threads. These will be:

1 Communication thread:
- Handles sending data, and dispatching received data to wherever it needs to go

1..n Arena threads:
- Simulate a single arena's world model and state, receiving information from a communication thread

The arena threads might be multiple threads to manage different sectors of an arena, but let's assume that one arena is one thread.

There's the relevant details, now we're getting to my question. The Halo Reach server paradigm has a Flow Controller, which tells the game logic manager "I have this much room for a packet to send to player X, how would you like to fill it?" then the game logic manager prioritizes state updates and events, and returns a packing of that packet space based on what information is most important and relevant for player X. If I'm understanding that incorrectly, stop me here.

This is complicated with threads, since I'm guessing all of my communication will be through C# lockless queues. Receiving messages and telling the Arena thread about them is fine. The problem is, how do I say the following things (let's pretend this is a chat log between the Flow Controller and the Arena thread):


<Flow_Controller>: Arena thread, here's a packet for you of size N, time to fill it.
(i.e. How do I tell the Arena thread that it's time to send out messages, OR should the Arena thread constantly be sending out messages by priority?)


<Arena_Thread>: Flow controller, remember that low-priority state update I sent you a minute ago that you haven't sent over the network yet? Well, it isn't relevant now, so forget about it.
(i.e. Once a state update is already in the queue, how can the Arena thread invalidate it so it won't be sent out?)


<Arena_Thread>: Flow controller, remember that low-priority state update I sent you a minute ago that you haven't sent over the network yet? Well, here's a new state update about that same entity that's now really important, so forget about the original update and send this one.
(i.e. A state update that was previously enqueued as very low priority message is now really important and should be sent out ASAP.)


There's two ways of approaching this, as I see it:

1) 20-30 times a second, the Flow Controller tells the Arena thread that it's time to send a packet, and we can send x bytes for player X, and y bytes for player Y, etc. Once the Arena thread gets that message, it pauses simulating, picks the best messages to send to each player based on those size restrictions, enqueues them for the Flow Controller, and goes back to simulating.
[b]Problem:[/b] There will be a delay between when the Flow Controller asks for the packet, and the Arena thread gets around to filling it. The Arena thread also has to stop for a period of time (that grows with each connected player).

2) The Arena thread is constantly, asynchronously outputting messages with priorities, maintaining, updating, and deleting old messages to that at any time the Flow Controller wants it, there's a nice up-to-date list of messages to send out with correct priorities based on the current (or very recent) world state.
[b]Problem: [/b]Standard mutual exclusion nightmare. How does the Arena thread constantly update and maintain this list while the Flow controller is reading it and consuming messages it sent out? This sounds like a lot of locks, and performance compromise. The Arena thread will also have to maintain one of these lists for each player.

So, am I completely off-track here? I really like the idea of prioritizing messages and selecting the highest-priority messages to send to each player based on bandwidth. I'd like to implement it if possible, but if this sounds completely crazy, I guess I could just try the Quake3/Valve model. Any ideas on how to do this packet-packing problem with inter-thread communication would be quite wonderful. Thanks!

Share this post

Link to post
Share on other sites
I think you're better of with the arena thread just simulating, period. It then emits the state of all objects after each simulation step. Some separate entity is responsible for keeping clients up to date. This entity inspects the known data about the game, and about the client, and sends the appropriate messages in packets.
You can model this using real messages -- arena sends "entity 3 changed property 12 to value 77.4" -- or you can save RAM by sharing a pointer into an entity object, and just taking that property value out of the object when time comes to send it. Which option you choose depends on implementation strategy, how much you feel you need to lock, etc.
If you go full messaging, you could even hoist the "send data to clients" work into another process/node, for some additional bit of robustness and scalability, but in practice, that gain is not super big.

Share this post

Link to post
Share on other sites
Okay, that's a good way to look at it. So the way I envision the system working is this:

Each game tick, the Arena thread creates a new world state by applying rules on the current immutable world state, without modifying that original world state. After the new world state is created, it's locked and read-only. The Arena thread emits that read-only timestamped world state. Also, the Arena thread, in a separate channel, produces a stream of events (this bomb exploded, that ship fired a laser) to justify changes in the world state.

Periodically (20-30Hz), the Flow Controller takes the most recent world state (discarding any old states it missed), determines the relevance and priority of each state update to send for each client, and packs some of that client's outgoing packet with the highest-priority world state changes (or the entire world state, delta-compressed, if there are enough changes). The Flow Controller also picks as many events as it can take, also prioritized, and stuffs them into the outgoing packet as well. It sends off that packet as well, and moves on to the next client in a round-robin fashion. The Flow Controller always sends the most recent state info to each client. So if we have 4 clients A-D, A and B might get tick 122, then C gets tick 123, then D and A get tick 124, B and C get tick 125, etc.

Does that sound like a good way to approach it, then? I envision the Arena thread with two output queues, a state queue and an event queue. The Flow Controller will just burn through everything but the most recent state queue whenever it wants to send out state info, but will try to send out as many events as it can. Events, of course, will time out if the Flow Controller couldn't send them out soon enough for them to actually be relevant.

Since the states in the state queue will be immutable, I can just pass references out. I'll have to figure out how many old world states save and keep around, but that's a minor question.

Share this post

Link to post
Share on other sites
You can have multiple msg/event queue with different 'quantum' of priorities (highest gets priority to be sent before lower ones considered - some even absolute 'always send immediately') Anything put into Queue X is assumed equal in priority so just get pulled from linearly.
Some transitory information (ie- position updates) graduate to a higher priority (esacalate) when they havent been sent for some time threshold
(that is the data set (ie- SHIP1234.posx & .posy) not a particular times instance of it - latest instance of course would go out)

This requires you to have to maintain the current 'update' state (last confirmed sent) for all the data sets and the last sent values
(if you are doing delta compression you do this anyway). Bandwitdh per client session is controlled obviously (with throttling now possible when external things begin to choke or that client seesion is experiencing network conniptions)

That may be alot of processing that might best be moved to an intermediary thread(we seem to have lot more cores these days) or seperate session server (bige scalability) that determines the outbound content and the network thread is pure send/recv.

Lockeless FIFO buffers can be used between these threads to avoid the usual lock hell.

Queue Quantums you might want:

Absolute - always sent immediately
High - events usually sent every time
Low - msgs can wait but will be bumped up if too longa wait
Advisory - gets sent if nothing else goes (usually for keep alives and game irrelevant extras)

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