How can a game handle all characters at once?

Question

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?

Answer 1

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).

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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 10⁹ clock cycles per second. If we calculate 60 timesteps per second, that leaves 10⁹ / 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.

Answer 8

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.