Multithreading

[NON]

Hello
I'm doing a project to get some experience about multithreading (which I know very little about). For this I'm making a game that will play a bit like Dwarf Fortress. I'm thinking this should be a good type of game for this. I've seen discussions about using multithreading for DF and how it would benefit that game, since it tends to become really slow with lots of creatures moving around.

I have some basic stuff set up in a common single thread already (game loop, rendering actors, some utility functions, etc). The first draft will just be a benchmark demo, probably not even handling user input. I want to see what the limit is for map size and number of actors moving around with pathfinding, and how far I can push that limit with more effective algorithms and (hopefully) by using multithreading.

I do have a clear idea of a game I want to make from this though. I think what I have in mind would be an awesome game, so I'm excited about that too, and I don't intend to stop at just a technical demo. Of course I'm not going for something so huge as DF(!), this would be a much simpler game. Hopefully it can be a fun challenge.

Anyway,
I came here to ask for some advice about multithreading. In a game similar to DF, what would be good to put in separate threads? My first idea was "pathfinding of course", it's one of the most CPU-intense parts for sure. But can it be run in parallel with the rest of the game? It doesn't seem so - you calculate this before a creature moves. I guess when the time comes for calculating paths for all creatures, you could calculate as many paths as possible in parallel though. I'm also looking at bidirectional A* pathfinding - wouldn't that benefit from running in two threads? One thread would search from the origin and the other from the goal.

Would be interesting to hear your ideas. What could/should be put in separate threads? Would there be a lot to gain from all this?

[Cfyz]

I think there are ways to make pathfinding works asynchronous. In general, you'll just have to make it possible for creature to start moving without full path available. For example, the background task may update creature's path at some intervals, i. e. creature will start in some general direction and then correct its way once or twice. Most likely it wont get too far by the time calculation is done (so error will be negligible) but this might increase responsiveness greatly and scale pretty well.

As for parallel A* I think this specific case will not benefit much. The reason is in such game there will be not one huge task but whole lots of small ones. If tasks do not sleep/wait much, there is no benefit in using more threads than number of CPU cores because all cores will be fully loaded with work anyway. It might seem that task may be calculated two times faster by dividing the work between two cores, yet actually this will also cut the number of simultaneously calculated tasks in half. On a large amount of CPU-bound tasks parallelizing will not help because average processing time will stay the same.

[NON]

Okay I really need to study up more on the basic principles of multithreading/core. I was totally lost at the second paragraph of your reply.

How about handling user input, user interface and rendering in a separate thread than the game logic? That way pressing keys should feel responsive even if the game logic slows down? It would also free *some* load from thread/core that handles game logic? But maybe that's not how it works at all

[miki151]

I would let the creatures calculate their moves in parallel if they are far enough from each other. Once they are calculated, execute them in the right order. You would have to synchronize it like in the readers-writers problem: http://en.wikipedia.org/wiki/Readers%E2%80%93writers_problem

The biggest slow down of pathfinding is when there is no actual path, because all (?) algorithms will have to exhaust the whole area. To solve this you have to maintain what areas are disjoint, which can also be parallellized.

[Eben]

Okay I really need to study up more on the basic principles of multithreading/core. I was totally lost at the second paragraph of your reply.

How about handling user input, user interface and rendering in a separate thread than the game logic? That way pressing keys should feel responsive even if the game logic slows down? It would also free *some* load from thread/core that handles game logic? But maybe that's not how it works at all

What language / engine / libraries are you using? That will make a huge difference to your approach since it will change the complexity of implementation. Handling user interface things should already be multithreaded if you're using a modern GUI library.

Usually multithreading is good for doing things that need to be done semi-simultaneously, like responding to user input multiple ways (ie updating a GUI and running logic code at the same time) and when doing a task that can crunch on a lot of data without interacting with other threads.

If you're trying to learn multithreading, doing it in a game is a very bad idea. Make your game without it and then try to add it if there are parts where it makes sense to. That way you know that your multithreading is causing whatever issues come up since it will have worked before you did that part. And there will be things that come up, multithreading is extremely difficult to do well and hard to debug.

[NON]

I'm using C++11 with SDL 1.2.

So, not exactly a modern GUI library.

[Numeron]

I use some multithreading in my engine, and am intending to implement more as time goes on, so I might be able to offer some advice on how it can be done for other roguelikes. Hold onto your hats, wall of text incoming.

This is what you want to do.

How about handling user input, user interface and rendering in a separate thread than the game logic? That way pressing keys should feel responsive even if the game logic slows down? It would also free *some* load from thread/core that handles game logic? But maybe that's not how it works at all

Step One: Separate your UI and Game into two distinct projects and set them up so that each portion can run with its own thread. Basically like a server and client. To save you a lot of trouble down the road they shouldn't even be able to reference each other, but I have a 'Base' project which defines some common data structures that both can use (like World/Level/Tile etc), and an 'Application' project which is able to kick them both off. The UI client receives everything it needs to know from messages sent to it, and in turn sends commands which the server waits for, and when available acts out a turn and sends more update messages. This is how my latest 7DRL Hellspace works and its a great first step because adding networking and running the server on a remote computer is very easy to implement from here. If the server is laggy, the client can still render and play the nice animations and whatever else.

Step two: You should start to think about how the turn-based nature of roguelikes isn't well suited for synchronous execution. Every actor takes its turn in a distinct queue, and you can't let actors further down the queue take their turn at the same time as the current because earlier actor's actions might effect later ones. You can't even guarantee the actors further down the queue will even be alive by their turn! So you'll have to decide exactly how (if at all) you want your game to work time-wise. Will it be real-time? Will every actor take their turn at once, with a post processing phase to resolve conflicts? This also might be a good time to note that dual core computers are very common at the moment, meaning adding more threads than the two from step one will not nessecarily improve things for a lot of people.

Step Three: This is the step I'm up to. I want to have easily un-pluggable queue types so that I can work with both a single threaded traditional roguelike queue but also swap it out for a different multi-threaded real-time queue if I want to make that kind of game. There's lots to read about real-time game design, but essentially on each game 'tick' all the actors can decide what to do next at once before time is advanced. To facilitate this, I'm separating the level structure into chunks (ala minecraft), and to perform an operation inside a chunk it needs to be locked first. To perform multi-chunk operations, they're locked in order of their Ids to ensure there's no deadlocks. I intend chunks to be large-ish because my previous efforts to synchronise at finer levels of detail have been fraught with enourmous levels of complexity and a horrendous amount of deadlocks. When it comes to threading, if you can't completely and undeniably separate the systems (as with the client/server) then you have to very very clearly isloate the area of the system you want without getting confused by the details.

The biggest slow down of pathfinding is when there is no actual path, because all (?) algorithms will have to exhaust the whole area. To solve this you have to maintain what areas are disjoint, which can also be parallellized.

My engine also has multi-threaded pathfinding: when a path is requested, the requesting thread will idle while two runner threads calculate the same path at once. One source to goal and the other goal to source - the first one to find a complete path kills the other and returns. This fixes the problem you describe when a monster in an open desert can't get into a small hut - One thread searches out the entire desert looking for a way in, but the search from the hut outwards will very quickly find there's no path. I don't know how well this will work out with my implementation of step 3.

[Eben]

Numeron's post lays out a pretty much perfect plan.

I did multi-threaded FOV and found that while it greatly sped up raycasting, shadowcasting single threaded is still much faster and gives quite nice results.

One thing that's important conceptually is allowing things to "short out" if they're taking too long. So for example if the monster AI on its own thread is out of time (the game is now asking for a move decision) it's nice if your algorithm can turn out a partial or fallback answer rather than making the rest of the system wait. In a game it can be as simple as "um, I don't know what to do yet! move me one square in a random direction I guess"

[NON]

[...]

Thanks for your wall of text

I'm still curious about the benefits of running UI in a separate thread for a single player game though. The questions I asked in the part that you quoted, would you say "yes" to them? Or is it not so much worth it if you know you will never deal with networking issues?

My engine also has multi-threaded pathfinding: when a path is requested, the requesting thread will idle while two runner threads calculate the same path at once. One source to goal and the other goal to source - the first one to find a complete path kills the other and returns. This fixes the problem you describe when a monster in an open desert can't get into a small hut - One thread searches out the entire desert looking for a way in, but the search from the hut outwards will very quickly find there's no path. I don't know how well this will work out with my implementation of step 3.

This is especially interesting to me. But wouldn't it be even more effective if these two threads combined their effort, instead of just using the "winner"? It seems to me that you ought to stop when the two paths meet each other (or when one of them discovers that it's impossible). I'm talking about this (scroll down to "Bidirectional search"):
http://theory.stanford.edu/~amitp/GameProgramming/Variations.html

So for example if the monster AI on its own thread is out of time (the game is now asking for a move decision) it's nice if your algorithm can turn out a partial or fallback answer rather than making the rest of the system wait. In a game it can be as simple as "um, I don't know what to do yet! move me one square in a random direction I guess"

Ouch, then you'd get different gameplay depending on the performance of your computer. Dumber AI (easier game) on a slower computer. I wouldn't want to have it like that.

[Eben]

So for example if the monster AI on its own thread is out of time (the game is now asking for a move decision) it's nice if your algorithm can turn out a partial or fallback answer rather than making the rest of the system wait. In a game it can be as simple as "um, I don't know what to do yet! move me one square in a random direction I guess"

Ouch, then you'd get different gameplay depending on the performance of your computer. Dumber AI (easier game) on a slower computer. I wouldn't want to have it like that.

Yes, but if your algorithms run slow enough that threading speeds them up in a way noticeable to the player then you're already getting a somewhat different experience on a different computer with or without the threading. The real question (for all game choices really) is how much it matters to the player. Maybe you'd have different difficulty levels with different system requirements... I know some 4x games I have to put the AI on a much easier mode on my laptop than on my desktop to make it playable at a reasonable speed.

[reaver]

You might want to take a look at OpenMP (http://openmp.org/openmp-faq.html#WhatIs) for a different kind of parallelism.

[Numeron]

Thanks for your wall of text

I'm still curious about the benefits of running UI in a separate thread for a single player game though. The questions I asked in the part that you quoted, would you say "yes" to them? Or is it not so much worth it if you know you will never deal with networking issues?

Your welcome! Incidentally, an easy intro into step 3 is implementing threads for the analysis (like line of sight calcs) and decision making phase of the game tick since all those functions should be read-only you don't need to worry about the threads stepping on each others toes.

As to your question, honestly, I don't think just the separation of UI and game is better performance wise for single player so far but I haven't fully tested it and haven't run into any performance problems either way. The thing is, no game stuff can really update on the front end until the message is sent to the server, the server takes the action, and the result is returned. So in a way I have two threads doing the procedural work of one since the server has to idle while input is taken care of on the client, and the client just waits for updates from the server while the server works (except of course it never really just waits, it keeps on rendering etc but you get the idea) Dividing it up then will certainly smooth out your rendering but can arguably make everything else slower thanks to the communication overhead. In order to proceed into step 3 however and get the performance boost from threaded game logic you have to cleanly separate out the UI so all your core data structures aren't constantly locked up by your front trying to get display info.

My engine also has multi-threaded pathfinding: when a path is requested, the requesting thread will idle while two runner threads calculate the same path at once. One source to goal and the other goal to source - the first one to find a complete path kills the other and returns. This fixes the problem you describe when a monster in an open desert can't get into a small hut - One thread searches out the entire desert looking for a way in, but the search from the hut outwards will very quickly find there's no path. I don't know how well this will work out with my implementation of step 3.

This is especially interesting to me. But wouldn't it be even more effective if these two threads combined their effort, instead of just using the "winner"? It seems to me that you ought to stop when the two paths meet each other (or when one of them discovers that it's impossible). I'm talking about this (scroll down to "Bidirectional search"):
http://theory.stanford.edu/~amitp/GameProgramming/Variations.html

That... is really interesting, and I'm kicking myself I never thought of it. I'll probably add further investigation onto my list of things to do It would probably be faster to use one thread and I guess keep two node lists, alternating between them when expanding the heads. Communication overhead is often overlooked, and can sometimes slow things down more than the concurrent operations save, but who knows.

Then again, I'm super happy with my change-over as the other benefits, like offering remote servers to play on (even for singleplayer) and eventually offering multiplayer are great (once I figure out how it would even work in a roguelike). Also the separation of the UI has allowed much easier implementation of animations and other neat front end effects since the rendering and so on doesn't have to just stop when the game is updating (not that it takes long enough to notice anyway). If you've played any of my recent games, you'll see I have a lot of that kind of thing.

[miki151]

My engine also has multi-threaded pathfinding: when a path is requested, the requesting thread will idle while two runner threads calculate the same path at once. One source to goal and the other goal to source - the first one to find a complete path kills the other and returns. This fixes the problem you describe when a monster in an open desert can't get into a small hut - One thread searches out the entire desert looking for a way in, but the search from the hut outwards will very quickly find there's no path. I don't know how well this will work out with my implementation of step 3.

Brilliant, thanks!

[requerent]

You shouldn't thread separate processes, you increase the amount of extra work you have to do by orders of magnitude (mutex and sync) AND increase your overhead AND under-utilize threads AND your application won't scale.

The Thread Pool Pattern will serve you best. When you have groups of like data that are being processed by the same set of instructions, you can just loop through, queueing each one as a job. The Thread Pool will assign each one to the available threads as soon as one is available. In this way, you're always distributing the load over multiple threads. You could even offload processes to the GPU if you're ambitious. After that particular set of instructions finishes with the data, you can run another set of instructions to determine what to do next, offloading each job to the queue for threading. Data is always in synch, threads are always utilized, and you score extra bonus points if you optimize for data/instruction cache misses.

Do pathfinding calculations for ALL monsters at the same time. Then do decision-making for each at the same time... etc. etc. etc. It's a little quirky in a turn-based game, since you may want to change paths so that they are non-blocking, but if your game is engineered/designed well, then it's easy to deal with.


Oh- also, try and schedule jobs according to the cache line size. Say you're processing 4 ints of data each loop per entity, unroll it so that each thread processes the data for 16 at once (64 bytes)-- this lines up with the typical size of a cache line and is a simple way to improve performance.