Sign in to follow this  

Redesign of my game

This topic is 2650 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have now decided that my game should allow the user to browse the game world while the game is updating for one game day to the next.

Inorder to do this i will need threads.

I would like to code this myself not use a library

Are there any open source, multi-threaded projects i could browse through to see how it is done?

Share this post


Link to post
Share on other sites
IMO, you'll have far better luck looking at -- then implementing some simple threading examples, rather than trying to reverse-engineer what the threading is trying to accomplish in a large current project.

Spawning a thread to calculate a new world state is very easy. The real headache is in allowing other threads to safely read or write that data while the first thread is updating it. If you don't use a library that manages thread safety for you, then you'll need a deep understanding of concurrency issues to do it yourself. Some values can safely be read while other threads are writing them without locking. Most though will require you to use some type of semaphore based control structure, or one of its derivatives, such as a critical section/mutex.

Share this post


Link to post
Share on other sites
Quote:
Original post by gameplayprogammer
I have now decided that my game should allow the user to browse the game world while the game is updating for one game day to the next.

Inorder to do this i will need threads.


No, I bet you won't really. Just continue to interleave update() and render() calls as you normally do for your game loop, and add conditional logic to the sub-tasks of update() that do the appropriate things at end-of-day. There's a lot of such work to do? Then stagger it.

Share this post


Link to post
Share on other sites
@jonathanjansson: Yeah it does, i will have about 1000 different entities in this game, all who could be doing things like buying/selling resources from each other.

@Echkard: I am thinking of using QT or Boost for the multi-threading. I think QT as i will be using the QT designer, gui and widgets. I am happy to use a library to manage thread safety if you know of any.

@Zahlman: 1000 different entities, still think its possible. I have detailed my problem below.

At the moment using one thread there is this long wait as all the entities do their update. You can not browse as the UI has to wait till the AI is finished to process clicks.

My idea was that while the game is in updating state, the human can browse the world but not be able to complete any tasks. So a user can click on any entity and see its info screen while it is doing its end-of-day update.

Share this post


Link to post
Share on other sites
Gameplay, let's assume your game is running on a single core cpu for a minute. In that case, whether you have one entity or one million, Zahlman's non-threaded approach will be FASTER overall than using threads. Flipping that statement on its head, if your game will run fast enough on a uniprocessor, then you don't "need" threads.

Regarding thread safety, you can find thread-safe collection classes. The problem here is that the locking granularity is so coarse that, for your intended use (two threads with massive amounts of shared state) you'll probably wind up with so much contention that it'll underperform or barely outperform the single-threaded solution.

To get around this, you really need to not just try to 'plug in' some library, but get a basic understanding of concurrency issues -- why threads sometimes need to lock data when accessing it, the times when they can safely read shared data without locking it. This will also teach you how to structure your data (no pun so that either fine-grain locking is possible, or that coarse-grained locking doesn't kill your concurrency.

So don't try to look at a large threaded project. Start with any small threading example that uses the basic synchronization structures. When you know what a semaphore/mutex/critical section is and how to protect data with them, all the above will be clear to you.

Share this post


Link to post
Share on other sites
Quote:
Original post by gameplayprogammer
At the moment using one thread there is this long wait as all the entities do their update. You can not browse as the UI has to wait till the AI is finished to process clicks.

This is actually a really good argument for spawning a worker thread. However, as indicated by another reply to this post, browsing through the source code for an entire game is really overcomplicating things. As a matter of fact, learning how to make your game multi-threaded can be achieved in 20 minutes by simply reading the relevant API documentation for your operating system (eg. MSDN for Windows).

Share this post


Link to post
Share on other sites
Quote:
Original post by Dragonion
Quote:
Original post by gameplayprogammer
At the moment using one thread there is this long wait as all the entities do their update. You can not browse as the UI has to wait till the AI is finished to process clicks.

This is actually a really good argument for spawning a worker thread.
No it isn't. It's a really good argument for not shutting down your message pump. A worker thread that goes off and does its own independent task is one thing. A thread that shares massive amounts of state with the main thread (as this one will) is another thing entirely.

Quote:
learning how to make your game multi-threaded can be achieved in 20 minutes by simply reading the relevant API documentation for your operating system (eg. MSDN for Windows).
You can learn to spawn a thread easily. Learning about thread safety, synchronization, and how to avoid deadlock and race issues takes a lot longer.


Share this post


Link to post
Share on other sites
Quote:
Original post by Echkard
No it isn't. It's a really good argument for not shutting down your message pump. A worker thread that goes off and does its own independent task is one thing. A thread that shares massive amounts of state with the main thread (as this one will) is another thing entirely.


Exactly how do you conclude that the two threads will share "massive amounts of state" from "My idea was that while the game is in updating state, the human can browse the world but not be able to complete any tasks. So a user can click on any entity and see its info screen while it is doing its end-of-day update." ? If anything, it sounds to me that the updating process is indeed not dependent of this viewing he is trying to accomplish.

Quote:
Original post by Echkard
You can learn to spawn a thread easily. Learning about thread safety, synchronization, and how to avoid deadlock and race issues takes a lot longer.


Ok, 25 minutes then if you want to include the section about synchronizing with a critical object. Thread safety, race issues and deadlocks? Exactly how is this relevant to such a relatively simple task he is talking about?

Share this post


Link to post
Share on other sites
Quote:
Original post by DragonionExactly how do you conclude that the two threads will share "massive amounts of state" from "My idea was that while the game is in updating state, the human can browse the world but not be able to complete any tasks. So a user can click on any entity and see its info screen while it is doing its end-of-day update." ? If anything, it sounds to me that the updating process is indeed not dependent of this viewing he is trying to accomplish.
The OP stated the user would be able to browse the world while the game is updating world state. A classic reader-writer scenario. The mere fact that we don't have two writers doesn't eliminate all contention.

Quote:
Ok, 25 minutes then if you want to include the section about synchronizing with a critical object. Thread safety, race issues and deadlocks? Exactly how is this relevant to such a relatively simple task he is talking about?
With all due respect, if you say that, I don't believe you've written a multithreaded program that shared large amounts of state. Not one that didn't crash, at least :)

If you really don't know how a thread can cause synchronization issues and program crashes even when only one thread is writing while the other reads, I can dig up some references for so. As one simple example, imagine reading the position of an object where its x coordinate has been updated, but not its y coordinate, putting it in a position where it can't possibly be. Or a collection deque, where a new entry has been added, but the pointers not yet updated.

You can say "oh, just throw a critical section around it", but a critical section means single-threading. When two threads share massive amounts of states, you can actually wind up with worse performance than a single-threaded solution if you use such coarse-grain locking.

Share this post


Link to post
Share on other sites
Quote:
Original post by Echkard
Quote:
Original post by DragonionExactly how do you conclude that the two threads will share "massive amounts of state" from "My idea was that while the game is in updating state, the human can browse the world but not be able to complete any tasks. So a user can click on any entity and see its info screen while it is doing its end-of-day update." ? If anything, it sounds to me that the updating process is indeed not dependent of this viewing he is trying to accomplish.
The OP stated the user would be able to browse the world while the game is updating world state. A classic reader-writer scenario. The mere fact that we don't have two writers doesn't eliminate all contention.

Quote:
Ok, 25 minutes then if you want to include the section about synchronizing with a critical object. Thread safety, race issues and deadlocks? Exactly how is this relevant to such a relatively simple task he is talking about?
With all due respect, if you say that, I don't believe you've written a multithreaded program that shared large amounts of state. Not one that didn't crash, at least :)

If you really don't know how a thread can cause synchronization issues and program crashes even when only one thread is writing while the other reads, I can dig up some references for so. As one simple example, imagine reading the position of an object where its x coordinate has been updated, but not its y coordinate, putting it in a position where it can't possibly be. Or a collection deque, where a new entry has been added, but the pointers not yet updated.

You can say "oh, just throw a critical section around it", but a critical section means single-threading. When two threads share massive amounts of states, you can actually wind up with worse performance than a single-threaded solution if you use such coarse-grain locking. There are fine-grained solutions for any reader-writer pattern, but they require at least a minimal understanding of concurrency issues.


Share this post


Link to post
Share on other sites
Quote:
Original post by Echkard
The OP stated the user would be able to browse the world while the game is updating world state. A classic reader-writer scenario. The mere fact that we don't have two writers doesn't eliminate all contention.

So you are suggesting that all data has to be updated before anything can be read? Say we have "a classic reader-writer scenario" where the position of 10 3D objects is repeatedly being updated by one thread and another thread is displaying these on the screen. Then let's say the update thread has reach index 5 when the OS switches to the display thread. At this point only half the objects are properly updated, but -remaining rational- what is the worst outcome of this situation? Half the objects are being drawn one frame out of place would be my intuitive answer. Long ago I actually did try to synchronize the data in a similar scenario where everything was updated before drawn. And, trust me, this is not a very efficient solution.

Quote:
Original post by Echkard
With all due respect, if you say that, I don't believe you've written a multithreaded program that shared large amounts of state. Not one that didn't crash, at least :)

I have. And it didn't crash either. Do you have a past in database programming? Because, you know, parallel programming with a low level language is quite different.

Quote:
Original post by Echkard
If you really don't know how a thread can cause synchronization issues and program crashes even when only one thread is writing while the other reads, I can dig up some references for so. As one simple example, imagine reading the position of an object where its x coordinate has been updated, but not its y coordinate, putting it in a position where it can't possibly be.

So <x1,y1> is a valid position in your world, but moving it to position <x2,y1> makes your program crash? I am beginning to understand why you are experiencing deadlocks and other critical problems in your programs ;P

Quote:
Original post by Echkard
Or a collection deque, where a new entry has been added, but the pointers not yet updated.

Yes, having the possibility of referencing a null-pointer would certainly be a situation where it would make sense to implement some kind of synchronization.

Quote:
Original post by Echkard
You can say "oh, just throw a critical section around it", but a critical section means single-threading. When two threads share massive amounts of states, you can actually wind up with worse performance than a single-threaded solution if you use such coarse-grain locking.

I am personally not a big a fan of using critical sections for synchronization since they can indeed affect performance in an undesirable way. Nevertheless, critical sections are actually used for multi-threading. I believe you mean they can not be used for multi-process synchronization (http://msdn.microsoft.com/en-us/library/ms682530%28VS.85%29.aspx).

[Edited by - Dragonion on September 8, 2010 12:29:16 PM]

Share this post


Link to post
Share on other sites
Quote:
what is the worst outcome of this situation? Half the objects are being drawn one frame out of place would be my intuitive answer.So <x1,y1> is a valid position in your world, but moving it to position <x2,y1> makes your program crash? I am beginning to understand why you are experiencing deadlocks and other critical problems in your programs ;P
I'm not going to get into this e-Peen shaking contest with you, but to explain why your intuition is wrong here, consider either of the two situations below:

(a) The coordinate of the entity are stored as double-precision floats, or a 64-bit integer. In this case, updating even a single coordinate is not atomic, and a reader can see an indeterminate value that has no relationship whatsoever to any past value. For floats, it can very easily be a value far outside the allowed range of values, or even a NaN value that will throw an exception.

(b) The coordinates are stored as a tuple (x,y) or (x,y,z) of 32-bit values. Each value is updated atomically. Now consider the case where your entity is teleported from (a1, b1) to (a2,b2). The first value is updated giving a position of (a2,b1), then the thread is preempted. Your reader now sees a value that never existed in a previous frame, and is likely very far from both the proper old and new positions.

Further, I am very sure that updating the world state in the OP's game involves more than "moving 10 objects around". The objects themselves very likely change state, new objects are added to collections, and old objects removed from them.

If you read my earlier post, you'll see the statement that, among other things, learning about concurrency will teach the programmer when they can "safely read values while they're being written". If you try to lock everything, every time, you are indeed going to have poor performance. That's why its important to understand exactly when readers and writers don't conflict, and implement the least amount of concurrency control required.

Quote:
Yes, having the possibility of referencing a null-pointer would certainly be a situation where it would make sense to implement some kind of synchronization.
And this is a very common case when using collection classes. If you don't use a thread safe collection class or implement your own thread safety, expect crashes. If you use the class's own coarse-grained locking, expect major contention issues if your threads share large amount of state.

Quote:
Nevertheless, critical sections are actually used for multi-threading. I believe you mean they can not be used for multi-process synchronization (http://msdn.microsoft.com/en-us/library/ms682530%28VS.85%29.aspx).
No, I didn't mean that at all. You've misinterpreted both your link and my comments. Critical sections most certainly are used for synchronization, but like any such object, will cause contention if not properly used. BTW, a mutex and a critical section are, in concurrent programming terms, the same object -- they're both special types of binary semaphores, one designed for interprocess use, the other for intraprocess.

Share this post


Link to post
Share on other sites
"(a) The coordinate of the entity are stored as double-precision floats, or a 64-bit integer. In this case, updating even a single coordinate is not atomic, and a reader can see an indeterminate value that has no relationship whatsoever to any past value. For floats, it can very easily be a value far outside the allowed range of values, or even a NaN value that will throw an exception."

This could -theoretically- be an issue, so if the program is running on a 32-bit system using 64-bit floats, synchronization could rightfully be considered.

"(b) The coordinates are stored as a tuple (x,y) or (x,y,z) of 32-bit values. Each value is updated atomically. Now consider the case where your entity is teleported from (a1, b1) to (a2,b2). The first value is updated giving a position of (a2,b1), then the thread is preempted. Your reader now sees a value that never existed in a previous frame, and is likely very far from both the proper old and new positions."

Extremely unlikely, but yes; this could yield a single frame lasting a few milliseconds with a displaced object -- something I would prefer if the alternative meant a significant decrease in performance because of synchronization, though. And even if I chose to synchronize, a simple volatile variable would likely be sufficient for this operation.

"Further, I am very sure that updating the world state in the OP's game involves more than "moving 10 objects around""

It should have been obvious that this was an example without any relation to the OP's problem.

"The objects themselves very likely change state, new objects are added to collections, and old objects removed from them."

How can you conclude it's very likely the objects will change state? And even if they did, who says it would cause any problems? You could point to your comments above, but this statement is nevertheless speculation.

"No, I didn't mean that at all. You've misinterpreted both your link and my comments. Critical sections most certainly are used for synchronization, but like any such object, will cause contention if not properly used"

No, I didn't misinterpret anything: I replied to your comment "but a critical section means single-threading" with "Nevertheless, critical sections are actually used for multi-threading".

Listen, neither of us have seen the source code and I'm pretty sure we would both have chosen a different approach all together, so, with all due respect, I won't comment any further.

[Edited by - Dragonion on September 8, 2010 3:58:02 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Dragonion
How can you conclude it's very likely the objects will change state?
Unless the OP is trying to recreate the 1975 version of "Pong", I think his game is going to have more than static objects whose count and state can't change in any way. In fact, given he's considering threads to handle the updating, it's a rather safe bet that updating world state is more complex than simply moving a few objects to new positions.

Quote:
And even if they did, who says it would cause any problems?
You're not reading the posts. I said the OP needs to understand concurrency well enough to know what will and won't cause problems.

Quote:
No, I didn't misinterpret anything: I replied to your comment "but a critical section means single-threading" with "Nevertheless, critical sections are actually used for multi-threading".


No, you didn't understand. A critical section *does* mean the code in that section is single-threaded. Two threads that share so much state that the bulk of their work is protected by a critical section are essentially running single-threaded. This is why the extreme coarse-grained locking of many thread-safe collection classes creates high contention. It's also why Zahlman's suggestion to simply interleave in message pump calls is probably a better solution than threading for the OP.

In any case, given the absurdity of the statement that a person with no knowledge of concurrency can convert a complex state-sharing program to multithreading in "20 minutes" without issue, I think trying to pound any more sense here is effort lost.

Share this post


Link to post
Share on other sites

This topic is 2650 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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