31
\$\begingroup\$

This question is just to gain knowledge about how a game can handle so many characters at once. I am new to gaming so I beg your pardon in advance.

Example

I am creating a tower defense game in which there are 15 tower slots where towers are built and each tower ejects projectile at a certain rate; lets say that every second, 2 projectiles are created by each of the towers and there are enemies marching on the battlefield, lets say 70 (each with 10 types of attributes like HP, mana, etc., which will change as they move around the battlefield).

Summary

Tower Count = 15
Projectiles Created By Each Tower Per Second = 2
Total Number of Projectiles Created Per Second = 30
Units in Battlefield Count = 70

Now, does the game handle those 30 projectiles and 70 units by handling them on 100 different threads (which is too much for a PC) or 1 thread that moves all of them, reduces their value, etc. (which will be kind of slow, I think)?

I do not have a clue about this so can anyone guide me on how this will work out?

\$\endgroup\$
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – MichaelHouse Apr 17 '16 at 17:40
  • \$\begingroup\$ Adding onto the other answers... an example of some massive games. Skyrim had most of it's game logic update on a single thread. The way it manages this so well is that distant NPCs (NPCs who are miles away) are approximated according to their schedule. Most MMOs update game logic on a single thread, BUT each portion of a map exists on a different thread or server rack. \$\endgroup\$ – moonshineTheleocat Apr 18 '16 at 19:56
77
\$\begingroup\$

Now how does the game handle those 30 Projectile and 70 units by handling them on 100 different threads

No, never do that. Never create a new thread per resource, this doesn't scale in networking, neither does it in updating entities. (Anyone remember the times when you had one thread for reading per socket in java?)

1 thread that moves all of them reduces their value etc?

Yes, for starters, this is the way to go. The "big engines" split some work between threads, but this is not needed to start a simple game like a tower-defense game. There's probably even more work to do every tick which you'll also do in this one thread. Oh yeah, and the rendering of course.

(which will be kind of slow i think)

Well... What is your definition of slow? For 100 entities, it shouldn't take more than half a millisecond, probably even less, depending on your code-quality and the language you're working with. And even if it takes two full milliseconds, it's still good enough to hit the 60 tps (ticks per seconds, not talking about frames in this case).

\$\endgroup\$
  • 34
    \$\begingroup\$ More like half a microsecond, unless you're doing something weird. But most importantly, splitting the work over multiple threads is going to make everything worse, not better. Not to mention that multithreading is extremely hard. \$\endgroup\$ – Luaan Apr 15 '16 at 10:59
  • 13
    \$\begingroup\$ +1 Most modern game engines are rendering thousands or even tens of thousands of polygons in real time, which is far more intensive than tracking the movement of a mere 100 objects in memory. \$\endgroup\$ – phyrfox Apr 15 '16 at 17:25
  • 1
    \$\begingroup\$ "A simple game like a tower defense game." Hmm... have you ever played Defense Grid: The Awakening, or its sequel? \$\endgroup\$ – Mason Wheeler Apr 15 '16 at 19:31
  • 4
    \$\begingroup\$ "Never create a new thread per resource, this doesn't scale in networking..." ahem some very scalable architectures do precisely this! \$\endgroup\$ – NPSF3000 Apr 16 '16 at 4:57
  • 2
    \$\begingroup\$ @BarafuAlbino: That a weird thing to say. There are plenty of valid reasons to create more threads than cores available. It's a complexity / performance / etc trade-off like any other design decision. \$\endgroup\$ – Dietrich Epp Apr 17 '16 at 5:00
39
\$\begingroup\$

Rule number one of multithreading is: Don't use it unless you need to parallelize on multiple CPU cores for performance or responsiveness. A requirement "x and y should happen simultaneously from the users point of view" is not yet sufficient reason to use multithreading.

Why?

Multithreading is hard. You have no control over when each thread gets executed which can result in all kinds of impossible to reproduce problems ("race conditions"). There are methods to avoid this (synchronization locks, critical sections), but these come with their own set of problems ("deadlocks").

Usually games which deal with such a low number of objects as just a few hundred (yes, this isn't that much in game development) usually process them in a serial manner each logic-tick using a common for loop.

Even the relatively weaker smartphone CPUs can perform billions of instructions per second. That means even when the updating logic of your objects is complex and takes about 1000 instructions per object and tick, and you are aiming for a generous 100 ticks per second, you have enough CPU capacity for tens of thousands of objects. Yes, this is a grossly oversimplified back-of-the-envelope calculation, but it gives you an idea.

Also, common wisdom in game development is that the game logics are very rarely the bottleneck of a game. The performance-critical part is almost always the graphics. Yes, even for 2d games.

\$\endgroup\$
  • 1
    \$\begingroup\$ "Rule number one of multithreading is: Don't use it unless you need to parallelize on multiple CPU cores for performance or responsiveness." Might be true for game development (but I even doubt that). When working with real time systems the primary reason to add threads is to to meet deadlines, and for logical simplicity. \$\endgroup\$ – Sam Apr 15 '16 at 13:50
  • 6
    \$\begingroup\$ @Sam Meeting deadlines in real-time systems is a case where you need multithreading for responsiveness. But even there the logical simplicity you seemingly reach through threading is often treacherous, because it creates hidden complexity in form of deadlocks, race conditions and resource starvation. \$\endgroup\$ – Philipp Apr 15 '16 at 13:55
  • \$\begingroup\$ Unfortunately, many times I've seen the game logic bog down the whole game if there are pathfinding problems. \$\endgroup\$ – Loren Pechtel Apr 18 '16 at 3:38
  • 1
    \$\begingroup\$ @LorenPechtel I've seen this too. But usually it was solveable by not doing unnecessary path calculations (like recalculating every single path on every single tick), caching frequently-requested paths, using multi-tiered path finding and using more appropriate pathfinding algorithms. This is something where a skilled programmer can usually find a lot of optimization potential. \$\endgroup\$ – Philipp Apr 18 '16 at 7:01
  • 1
    \$\begingroup\$ @LorenPechtel For example in a tower defense game, you could use the fact that there are typically only a handful of destination points. So you could run Dijkstra's algorithm for each destination to compute a direction map which guides all the units. Even in a dynamic environment where you have to recompute these maps every frame, this should still be affordable. \$\endgroup\$ – CodesInChaos Apr 18 '16 at 8:57
26
\$\begingroup\$

The other answers have handled the threading and power of modern computers. To address the bigger question though, what you are trying to do here is avoid "n squared" situations.

For example if you have 1000 projectiles and 1000 enemies the naive solution is to just check them all against each other.

This means you end up with p*e = 1,000*1,000 = 1,000,000 different checks! This is O(n^2).

On the other hand if you organize your data better you can avoid a lot of that.

For example if you list on each square of the grid what enemies are in that square then you can loop through your 1000 projectiles and just check the square on the grid. Now you just need to check each projectile against the square, this is O(n). Instead of a million checks each frame you only need a thousand.

Thinking about organizing your data and processing it efficiently due to that organisation is the biggest single optimization you can ever make.

\$\endgroup\$
  • 1
    \$\begingroup\$ As an alternative to storing the entire grid in memory just to track a few elements, you could also use b-trees, one for each axis, to quickly search through possible candidates for collisions, etc. Some engines even do this for you "automatically"; you specify hit regions, and ask for a list of collisions, and the library gives it to you. This is one of many reasons why developers should be using an engine instead of writing from scratch (when possible, of course). \$\endgroup\$ – phyrfox Apr 15 '16 at 21:27
  • \$\begingroup\$ @phyrfox Certainly, there are any number of different ways to do it - depending on your use-case which is better will vary substantially. \$\endgroup\$ – Tim B Apr 16 '16 at 9:34
17
\$\begingroup\$

Do not create threads per resource/object but per section of your program logic. For example:

  1. Thread to update units and projectiles - logic thread
  2. Thread for rendering the screen - GUI thread
  3. Thread for network (eg. multiplayer) - IO thread

The advantage of this is that your GUI (eg. buttons) does not necessarily get stuck if your logic is slow. User can still pause and save the game. It's also good for preparing your game for multiplayer, now that you separate the graphic from the logic.

\$\endgroup\$
  • 1
    \$\begingroup\$ For a beginner I wouldn't recommend using separate graphic and logic threads, since unless you copy the required data, rendering the game state requires read access to the game state, so you can't modify the game state while drawing it. \$\endgroup\$ – CodesInChaos Apr 18 '16 at 9:03
  • 1
    \$\begingroup\$ Not drawing too often (eg. more than 50 times per second) is kinda important and this question was about performance. Dividing program is the simplest thing to do for a real performance benefit. It's truth this requires some knowledge about threads, but acquiring that knowledge is worthwhile. \$\endgroup\$ – Tomáš Zato - Reinstate Monica Apr 18 '16 at 9:17
  • \$\begingroup\$ Dividing a Program into multiple Threads is kind of the hardest thing for a programmer to do. Most really annoying bugs stem from multi-threading and it is a giant amount of hassle and most of the time just not worth it - First rule: Check if you have a performance problem, THEN optimize. And optimize right where the bottleneck is. Maybe a single external thread for a certain complex algorithm. But even then you have to think how your game logic will advance when this algorithm takes 3 seconds to finish... \$\endgroup\$ – Falco Apr 18 '16 at 15:09
  • \$\begingroup\$ @Falco You're overseeing the long term advantages of this model - both for the project and the programmer experience. Your claim that it's hardest think can't really be addressed, that's just an opinion. To me GUI design is much more terrifying. All evolved languages (C++, Java) have pretty clear multithreading models. And if you're really not sure, you can use actor model which doesn't suffer from beginner multithreading bugs. You know there's a reason why most applications are designed as I proposed, but feel free to argue about it further. \$\endgroup\$ – Tomáš Zato - Reinstate Monica Apr 18 '16 at 16:56
4
\$\begingroup\$

Even Space Invaders managed dozens of interacting objects. Whereas decoding one frame of HD H264 video involves hundreds of millions of arithmetic operations. You have a lot of processing power available.

That said, you can still make it slow if you waste it. The problem is not so much the number of objects as the number of collision tests performed; the simple approach of checking each object against each other object squares the number of calculations required. Testing 1001 objects for collisions this way would require a million comparisons. Often this is addressed by e.g. not checking projectiles for collision with each other.

\$\endgroup\$
  • 2
    \$\begingroup\$ I'm not sure Space Invaders is the best comparison to make. The reason it starts out slow and speeds up as you kill enemies isn't because it was designed that way, but because the hardware couldn't handle rendering that many enemies at once. en.wikipedia.org/wiki/Space_Invaders#Hardware \$\endgroup\$ – Mike Kellogg Apr 15 '16 at 14:11
  • \$\begingroup\$ What about, each object maintains a list of all objects that are close enough that it might collide with them in the next second, updated once a second or each time they change direction? \$\endgroup\$ – Random832 Apr 15 '16 at 15:18
  • \$\begingroup\$ Depends on what you're modelling. Space partitioning solutions are another common approach: partition the world into regions (e.g. BSP which you may have to do anyway for rendering purposes, or quadtree), then you can only collide with objects in the same region. \$\endgroup\$ – pjc50 Apr 15 '16 at 15:30
3
\$\begingroup\$

I am going to disagree with some of the other answers here. Separate logic threads are not only a good idea, but hugely beneficial to processing speed - if your logic is easily separable.

Your question is a good example of logic that is probably separable if you can add some additional logic on top of it. For example, you could run several hit detection threads either by locking the threads to specific regions of space, or mutexing the objects involved.

You probably do NOT want one thread for every possible collision, just because that is likely to bog down the scheduler; there is also a cost associated with creating and destroying threads. Better to make some number of threads around the system's cores (or utilize a metric like the old #cores * 2 + 4), then reuse them when their process finishes.

Not all logic is easily separable, though. Sometimes your operations can reach across all game data at once, which would make threading useless (in fact, harmful, because you would need to add checks to avoid threading issues). Further, if multiple stages of logic are highly dependent on each other occurring in specific orders, you will have to control the execution of threads in such a way as to ensure that does not give order-dependent results. However, that issue isn't eliminated by not using threads, threads just exacerbate it.

Most games don't do this simply because it is more complex than the average game developer is willing/able to handle for what is usually not the bottleneck in the first place. The vast majority of games are GPU-limited, not CPU-limited. While improving the CPU speed can help overall, it's usually not the focus.

That said, physics engines often employ multiple threads, and I can name several games I think that would have benefited from multiple logic threads (the Paradox RTS games like HOI3 and such, for example).

I do agree with other posts that you probably would have no need to employ threads in this specific example, even if it could be beneficial. Threading should be reserved to cases where you have excessive CPU load that cannot be optimized down via other methods. It is a huge undertaking and will affect the fundamental structure of an engine; it isn't something you can tack on after the fact.

\$\endgroup\$
2
\$\begingroup\$

I think the other answers miss an important part of the question by focusing too much on the threading part of the question.

A computer doesn't handle all objects in a game at once at all. It handles them in sequence.

A computer game progresses in discrete time-steps. Depending on the game and the speed of the PC, these steps are usually either 30 or 60 steps per second, or as many/few steps as the PC can calculate.

In one such step, a computer calculates what each of the game objects will do during that step and updates them accordingly, one after another. It could even do so in parallel, using threads to be faster, but as we'll soon see speed is not a concern at all.

An average CPU should be 2 GHz or faster, that means 109 clock cycles per second. If we calculate 60 timesteps per second, that leaves 109 / 60 clock cycles = 16,666,666 clock cycles per time step. With 70 units, we still have about 2,400,000 clock cycles per unit left. If we had to optimize, we might be able to update each unit in as little as 240 cycles, depending on the complexity of the game logic. As you can see, our computer is about 10,000 times faster than it needs to be for this task.

\$\endgroup\$
0
\$\begingroup\$

Disclaimer: My all time favourite type of game is text-based and I write this as a long time programmer of an old MUD.

I think an important question you need to ask yourself is this: Do you even need threads? I understand that a graphical game probably has more use of MTs but I think it also depends on the mechanics of the game. (It might also be worth considering that with GPUs, CPUs and all the other resources we have today are far more powerful which makes your concerns of resources as problematic as it might seem to you; indeed 100 objects is virtually zero). It also depends on how you define 'all characters at once'. Do you mean at the exact same time? You won't have that as Peter rightfully points out so all at once is irrelevant in the literal sense; it only appears this way.

Assuming you will go with threads: You definitely should not consider 100 threads (and I am not even going to get into whether it is too much for your CPU or not; I refer only to the complications and the practicality of it).

But remember this: multiple-threading is not easy (as Philipp points out) and has many problems. Others have much more experience (by a lot) than I do with MT but I would say they too would suggest the same thing (even though they would be more capable than I would be - especially without practise on my part).

Some argue that they disagree that threads aren't beneficial and some argue that each object should have a thread. But (and again this is all text but even if you consider more than one thread you need not - and should not - consider it for each object) as Philipp points out games tend to iterate through the lists. But yet it isn't only (as he suggests although I realise he is only responding to your parameters of so few objects) for so few objects. In the MUD I am a programmer for we have the following (and this isn't all the activity that happens in real-time so keep that in mind too):

(The number of instances do vary of course - higher and lower)

Mobiles (NPC i.e. non player character): 2614; prototypes: 1360 Objects: 4457; prototypes: 2281 Rooms: 7983; prototypes: 7983. Each room has its own instance usually but we also have dynamic rooms which is to say rooms within a room; or rooms inside a mobile e.g. the stomach of a dragon; or rooms in objects e.g. you enter a magical object). Keep in mind that these dynamic rooms exist per object/room/mobile that actually has them defined. Yes this is very much like World of Warcraft's (I don't play it but a friend had me play it when I had a Windows machine, for a while) idea of instances except we had it long before World of Warcraft even existed.

Scripts: 868 (currently) (oddly enough our statistics command doesn't show how many prototypes we have so I will be adding that). All of these are held in areas/zones and we have 103 of those. We also have special procedures that proc at different times. We also have other events. Then we also have connected sockets. Mobiles move around, do different activities (besides combat), have interactions with players, and so on. (So do other types of entities).

How do we handle all this without any delay?

  • sockets: select(), queues (input, output, events, other things), buffers (input, output, other things), etc. These are polled 10 times a second.

  • characters, objects, rooms, combat, everything: all in a central loop on different pulses.

We also (my implementation based on discussion between the founder/other programmer and myself) have extensive linked list tracking and pointer validity testing and we have more than enough free resources should we actually have a need for it. All of this (except we have expanded the world) existed years ago when there was less RAM, CPU power, hard disk space, etc. And indeed even then we had no problems. In the loops described (scripts cause this as do area resets/repopulations as do other things) monsters, objects (items), and other things are being created, freed, and so on. Connections are also accepted, polled, and everything else you would expect.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.