Sign in to follow this  

NPC Movement

This topic is 3813 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 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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Sure, you process the AI every frame. You have to update them like any other game object? The AI just dictates how or where the entity is moving, or their action, for the update. So, yes, you'd likely run it every game cycle, or at least every update cycle (I haven't seen a lot of games that don't update per cycle).

AI would be run incrementally like everything else in your game loop. Meaning, you wouldn't stop up and wait for the NPC to walk from point A to point B, you'd interpolate it based on time to move a couple pixels each game cycle toward it's destination.

Checks are made to decide where it's moving, or if it should stop this cycle and begin an attack, etc etc.

I think you're thinking too deeply on it ;) Implement it, run it, if it seems slow or kills performance, then post back asking for optimization advice!


Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Or you could use timers. Have one timer for Render(), and another slower timer for updating NPC AI. Maybe only once per second is enough for far-away NPCs.

Share this post


Link to post
Share on other sites

This topic is 3813 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