• Advertisement
Sign in to follow this  

Spreading tasks over multiple frames

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

In real-time games, there is a common problem of performing computational tasks that only need to run once in a while but cannot be finished within one frame without causing a lag.

Some examples are: pathfinding, updating the movement graph, looping over and updating all entities, various AI routines.

These tasks must be spread over multiple frames to avoid sudden jerks in the frame rate.

I have used the method in "Programming Game AI by Example" to do this for pathfinding. It works, but pathfinding is only one problem to fix.

I would like to know if someone has found clever ways of doing this in general, where there is a fixed amount of CPU time to allocate between multiple tasks.

Also, what is the correct term to use for this technique?

Thank you.

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by captain_crunch
I would like to know if someone has found clever ways of doing this in general, where there is a fixed amount of CPU time to allocate between multiple tasks.

For tasks that can be done easily in parallel (like pathfinding), thread pools. More often than not your cores are being underutilized, so no reason to spread out a task if it can be done sooner.

For other kinds of tasks, you'll have to come up with a solution on a case-by-case basis since each problem is different. If your computation has a large loop, for example, then in might be possible to refactor the code so that it does one iteration per frame. Or you can split a computation into pieces and do one piece per frame. Or you can do a combination of both. If the loop is really small but does a lot of iterations, you can get away with doing multiple iterations per frame but keeping track of the duration so that it doesn't exceed a certain time. It really depends.

Share this post


Link to post
Share on other sites
Even with parallelization, tasks may take longer than one frame to finish, so spreading them out is still necessary.

I think a general solution is a good idea. There must be a central place to keep track of how much CPU time is left.
A class called TaskManager could take care of this.
Another class called Task would somehow encapsulate the code to be run, and would have a method CycleOnce(). TaskManager then maintains a list of tasks.

something like:

TaskManager.Update()
while time_left > 0 do

tasks[i].CycleOnce()

loop

Of course the hard part is fitting the code for each problem into the CycleOnce() method.


Share this post


Link to post
Share on other sites
You'll have to store where you left your code. As for pathfinding, you can pause the loop when you run out of time. Pathfinding works with a couple of lists that have a set of current nodes to evaluate, nodes that are already done, etc. Keep those lists in the memory so you can catch up next time. The only problem with pathfinding in particular is that these temporary lists can be pretty big.

Updating and doing AI is easier. First, you can put the "AI update" inside an entities update. Then update a limited number of entities each cycle.

i = task.previousLoopIndex (maybe that is somewhere you can store inside a more general class such as Zipster suggested?)

while task.notRunOutTime do
if i>= entityList.count then i:=0;
entityList[i].update;
task.previousLoopIndex = i++

Be aware that the entity count may change in the meanwhile (stuff got removed or added).


Maybe not the answer you was looking for...but... why not using multi-threading? It surely isn't the most friendly and easy manner to do stuff, but it is specifically meant for such things. You can execute the whole thing at once, but inside a lower priority (background) thread.

The "only" difficulty is to isolate tasks from the main-thread. Problem with many AI functions is that you need positions/stuff from other entities that can be updated at the same time by the main-thread. To prevent this you could:
1.- Create a "query" struct. This struct contains all the info you'll need to accomplish a task. AI related structs could look like this:
* start/end position (for pathfinding)
* enemy positions (for pathfinding, checking sight, tactics, etc.)
* your health/condition status
Construct this thread in the main thread, so you don't have to grab variables inside the other thread anymore. Only work with local, thread-safe stuff.

2.- Insert the query in a "request list". Use a mutex/critical section to protect this list as it can be altered by 2 threads. Lock it, insert, unlock. Then let the other thread lock it, check if there is a new query, grab it, unlock.

3.- Execute the query.
4.- When it's done, create a result struct (target, what to do, list of path nodes, etc.), and insert it in a similar "result" list (also thread-safe).
5.- Let the main thread check for new results, then pass them to the requesting entity (you can store a pointer or callback address for this).

Pathfinding is certainly worth a background thread. No worries about speed, or having too many entities looking for a way at the same time. And the beautiful thing is, even if it takes 0.5 seconds (loooongg), it can be considered as normal human behavior.

Rick

Share this post


Link to post
Share on other sites
I had not thought of having threads running in the background behind the main loop. That is new to me...
But if the thread runs on its own across multiple frames, how do you prevent it from slowing down the game and hurting the frame rate? Maybe "it just works"?

Share this post


Link to post
Share on other sites
I'm no expert so I can't tell you the fine details, but basically this is what happens on a single-core system:

- Main thread has a relative high priority (Windows has lowest, low, normal, high and highest). When above normal, it will be called before anything else.

- Whenever the high priority thread(s) is idle (doing nothing), lower priority threads have a chance to run. Idle happens when calling sleep(between 2 cycles for example), but also when streaming something from the harddisk, or waiting for hardware (videocard) returns. A lot more than you think probably.

Keep in mind that systems with multiple cores can truly run both threads parallel. How that exactly works... Let's say its pretty brilliant.


The background thread itself won't really hurt the main-thread performance. The trick is not to block the main-thread. Don't wait until the background is done, just go on. Instead of:

// block until getPath has a result
myCharacter.pathToFollow = pathfinder.getPath( A to B );

You'll do something like this:

struct pathQuery;
pathQuery.parameters = (A to B, some more details)
pathQuery.callback = gotPathfindResult( );
pathQuery.callerHandle = myCharacter

pathRequestList.add_threadsafe( pathQuery ); // Insert, and continue
...do something else


< Each cycle, check if your result is already there >
if pathRequestList.count > 0
result = pathRequestList[0];
result.callback( result.callerHandle );

Compare it with writing a letter with a question to some company. Instead of waiting in front of your mailbox, you'll continue watching TV, sleeping, working, drinking beer, whatever. Each morning you check your mailbox. You can't take actions as long as you don't have your reply, but there is plenty of other stuff you can do.

In game-terms, this "wait" time is usually a matter of microseconds, so you won't really notice anyway. What would you do if the navigation system isn't answering immediatly? Exactly, you just sit down in your car, listen some music, already drive into some direction maybe. The same thing can be done with AI.

Rick

Share this post


Link to post
Share on other sites
While priorities are a nice thing at first glance (and they truly are so on modern multi-core CPUs), you must be aware that they can prevent your application from scaling down properly. Or put differently, they can totally screw up on a low-end machine.

You will usually have a main thread and a number of worker threads equal to the number of cores in the machine. This will make sure that you take maximum advantage of parallelism. There may be a tiny scheduling overhead for having N+1 threads running on only N cores, but this is neglegible, and often enough one thread will block anyway, so you're rather running something like N+0.1 threads.
Some people even go as far as spawning half a dozen extra threads which are controlled by an IOCP. This may cause a very small scheduling overhead in the worst case, but will guarantee that the CPU is always used as long as there are tasks, even if several workers block for some reason. On the average, you will have one thread per core (or maybe 1.05 threads, whatever).

Now, here comes the problem with priorities. A thread with lower priority will run only if no thread with a higher priority is ready to run. Which means that as long as high priority threads are running, your low priority thread gets zero CPU time. Zero.

That is generally a good thing, because this way your important tasks are done as fast as possible, and the non important ones can run in the background when the CPU wouldn't be doing anything. And modern CPUs with their many cores and superb speeds are never loaded more than 25-30% anyway! Hopefully?

However, if your program happens to run on a computer which is not all that supreme (somewhat older, and maybe with only a single core), it may happen that the CPU is indeed 100% busy with running the render loop and doing the other high priority things.

Normally (without priorities), the background thread (AI or such) would make things even worse by getting an equal time share. Which will cause a jerky feeling in the game. This is not nice, but the point is, it will still work. It will not work perfectly, but it will do to the best of the CPU's ability.

Now, with a lower priority background thread, you have no AI at all. The low priority thread will not get a single time slice, ever. Except, if by pure coincidence there is a huge stall in the main thread and the worker threads at the same time, so maybe once every 5-10 seconds.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement