I am in the design stages of a game with a general idea of how I'm going to implement things as far as game mechanics. One of the things I'm stumped on so far is NPC movement... I plan to have them constantly milling about or a "randomized" patrol path, where if they encounter something hostile, they go attack it (a guard type NPC). I planned to use threads and sort of handle their own actions there, but I realized quickly that this might be costly as far as resources if there are a lot of NPCs in an area. Then, I considered constant polling of each NPC and their actions, but I realized that also might be resource intensive. Any ideas as to how to implement this kind of behavior where each NPC has to be able to move and react independently of another NPC without threads or constant polling of every single NPC, or ideas on how to optimize this behavior?

Quote:Original post by Captain P
It's very common to update every game object that needs to run some logic every frame. Let's face it: it needs to happen somehow... and unless you'll need a great amoung of NPC's in your game, I wouldn't worry too much about it. If it becomes a bottleneck, you could optimize it by running the full logic for NPC's in close proximity to the player, while running some faster, but less accurate, logic for NPC's outside the players view - or even stop updating them at all. Of course, this depends on the game you wish to create. And of course, you're working with limited resources, so not everything may be possible (100.000 AI-driven NPC's, each interacting with each other? Uhh...).

As for running around, you could give each NPC a target, and have them move towards that target, and when they arrive, decide a random new target for them. Some games use nodegraphs for this, so NPC's know where they can move (this also allows you to let them do pathfinding when they need to get to a specific point), but that depends on the needs of your game of course.

First I'd like to thank you for your input, it is insightful. If anyone else has any other ideas I'd love to hear them.

I assume that you mean run the logic for every single frame for the NPC logic? Wouldn't that be somewhat inefficient as far as far as resources go?

For example, the NPC checking if theres anything within its range to attack, or once a target is acquired, checking if the target is still in its range, and according to the rate of fire of the NPC, attack that target?

It just seems like a lot of checks, especially for the rate of fire portion, maybe its a bowman or something like that on a tower who fires four times a second, what if there are like say, ten of them, but with different rates of fire for some reason. This is why I initially came up with the idea of threads, where I could just cause the thread to sleep or wait for the duration of the downtime between shots. But thats ALOT of threads.

Once again, thank you.

You could use a discrete event system. This is where you have a time-ordered queue of events to process and you process events but only the ones that are due at the current time. These events create other events that will push themselves into your queue at the correct time.

This has the benefit that only one thing needs to be checked for a frame where you have 100+ NPCs walking.

You have to tie this to the animation so you set up a linear animation that will render at the right spot as time goes by. Your collision system needs to add events onto this queue so your walking NPC will hit things or spot enemys... but this can be handled however your collision system works.

You have to implement your algorithms to they don't need to constantly poll. Designing a system like this isn't always straightforward. You could look at the course notes for the paper I did last semester and some of the links we were given.

If you need this system this is how to do it. My guess is that designing around a system like this is annoying (no polling etc.) and many don't do it.

Threads are an extremely fragile solution because you're giving up control to the OS's scheduler and throwing determinacy out the window, unless you're doing lots of synchronization to ensure that this processing all happens in a coordinated manner. Multithreaded systems are also notoriously difficult to debug, and in any case the only way a multithreaded system could outperform a single threaded one is on a system that can physically execute more than one thread at a time. Even then, modern PCs never really have the capacity to execute more than four threads simultaneously, with most limited to one or two.

If you want to distribute work across multiple frames to avoid excessive work each frame, you're better off writing your own scheduling system so that you have full control over the processes and avoid multithreading issues. At the simplest level, AI tasks could be staggered so that only some fraction of the entities run their AI each frame, and every other frame they continue doing what they were already doing. At the other end of the complexity spectrum, you could use an event system like umbrae described, allowing your NPCs to request proximity queries and then processing the query and returning the results at some time in the future determined by your scheduling system.