Task Scheduler - suggest improvements

I'm currently using a TaskScheduler to spread expensive AI tasks across multiple frames. It's working reasonably well, but this pretty simple algorithm has 2 major issues.

Code (CSharp):

1.  
2. private Queue<Task> PlannedTasks = new Queue<Task>();
3. System.Diagnostics.Stopwatch watch;
4. private readonly long TimeAllowedPerFrame= 1; // Milliseconds
5.  
6. void Update()
7. {
8.     watch = System.Diagnostics.Stopwatch.StartNew();
9.     while (watch.ElapsedMilliseconds < TimeAllowedPerFrame && PlannedTasks.Count > 0 )
10.     {
11.         PlannedTasks.Dequeue().Activate();
12.     }
13.     watch.Stop();
14.  }

1. It treats all frames as equivalent.
   We know this isn't true. Some frames have animations/particles/physics/etc that make the frame take longer to process, but my code will take the same chunk of time no-matter-what.
   
   I'd really like to be able to vary the Time available per frame for tasks depending on how long the frame is taking to complete.
   
   
2. It treats all Tasks as equivalent
   If a task so big that it's eating up 10 milliseconds, I have to break it into smaller tasks until the chunks are easily handled. This works on my machine, but someone else may be using a slower device and the breakdown may no longer be good enough.
   
   Also; say task A uses 99.9% of TimeAllowedPerFrame and the next task B is large as well; it has to complete the entire task B even though it takes me well over the time allowed.
   
   I'd like to be able to halt/resume a Task so that I can split tasks depending on the actual situation rather than attempting to predict ahead of time.

I have a few ideas on these problems but nothing I'm entirely happy with; can anyone make some suggestions? Would love to hear from people who've tackled this topic before as well.

 

This is what threading is usually used for (even single core systems support threading as a multi-tasking setup... you are not limited to the number of threads == the number of cores you have. Only that the number of threads actually executing code simultaneously is limited to the number of cores... though it's more complicated than that). I mean heck, in .Net 4 MS upgraded their threading library and now refers to the idea as 'tasks', rather than 'threads'.

There is also thread prioritizing, but there is contention about its use since it hinges on the OS implementing it, and the implementation can sometimes be more expensive than just sticking with 'normal' prioritizing.

Another thing you must consider. Offsetting a task until the framerate is in some tolerant range might NEVER happen. The frame rate might just be bad on a machine... and if some AI bot waits for the framerate to get good... it ends up never doing anything. Really weird exploit in your game "underclock your machine to beat level 10, the enemies never attack if the framerate is too low".

 

lordofduct is right, and i'd like to put extra emphasis on his last point.

You'll find out that your scheduling system initialy intended to manage a good FPS must in fact spent more time at lower FPS else the game systems relying on it won't run well then.

You need to calculate how much time you want to spend in there at 60 FPS for example, and then scale that time based on real FPS.

At higher FPS you can indeed run less tasks per frame and be fine with it.

At lower FPS, you must loose a few more to have your game hold up. At 20 FPS, each frame is 50ms long, if you allow 5 extra ms -which is huge- you're still above 18 FPS and that FPS difference isn't very noticeable, however like it's been said your AIs not reacting would likely be noticeable. (i had that very scheduling issue with vegetation in the game i'm working on, it didn't refresh fast enough at low fps causing a poor user experience until we scaled the scheduler allocated time per frame and all has been fine since)

 

Threading isn't currently possible as the AI is running many instances of Physics.Raycast, NavMeshCalculate, etc... Eventually some of the more generic portions my be Thread safe but this very much tied to the Pathfinding/LoS checking.

Also, my project is turn based, so it's not likely that it will wait for long for frame rate to improve AND it's just as easy to give a minimum of 1 millisecond to make sure it always gets SOME time to process.

Currently I'm working out the number of milliseconds for 60 fps but I had hoped to have something with a bit more flexibility.

 

OK, so if you need to allow accessing the main thread.

I wouldn't break into a task manager for a given 'task' like "AI calculations". Because this would require your AI logic to constantly have blocking breaks in it to ensure it doesn't do too much work. You can't just stop work mid code unless that code has logic built into it to do so (C# is just far too high level).

Rather instead have a thread, and the a task queue to perform simple operations back on the main thread.

So first off, before getting to the load balancing... I'll bring up a simple tool for thread hopping that I really like. Personally I have my own implementation, but this 3rd party tool packages it up very nicely (and it's free!):
https://www.assetstore.unity3d.com/en/#!/content/15717

This allows you to run a coroutine on a background thread that then returns back to the main thread with a simple yield statement like 'yield return Ninja.JumpToUnity'.

You can quickly jump from a thread to the main thread to calculate that raycast, then jump back to the thread and use it for stuff.

NOW, load balancing.

What you can then do is expand on the concept by implementing the same things from ThreadNinja yourself (kind of like how I did). But this time instead of yield a 'JumpToUnity' token... you have a 'JumpToUnityWhenResourcesAvailable' token instead. You can include a 'tolerance' value with said token.

Then your threaded coroutine manager thinger would be tracking whatever tolerance you're concerned with. You could do something like where it has an Update call ordered to be first, and a LastUpdate call. Then it calculates the time differential, and if everything is kosher it does the 'jumptounity' and processes what is necessary.

Now in your 'threaded coroutine' you ONLY calculate the one or 2 time calls that are required to be unity thread safe. But then go back to the background thread to do all the heavy lifting.

Code (csharp):

1.  
2. yield return new JumpToUnityWhenResourcesAvailable(1); //for 1 millisecond
3. var result = Physics.Raycast(ray, out hit);
4. yield return CustomThreadNinja.JumpBack;
5.  
6. if(result) //do stuff
7.  

I still warn though... this isn't exactly the best way to deal with what you need to do when it comes to load balancing.


... I could come up with other methods that could be far better at it. Like a method queue that in your background thread you queued up raycasts and other jobs. Then some task pump went through the queued up options as it can while your threads block/wait for the queue to get through its requests.

Then your task queue only allows X number of operations to occur per frame (only 50 raycasts per frame, and the sort). So your thread just waits for the queue to get to its request.

This though requires quite a bit more design than the threadninja option.

 

I've decided to stick with 'Software Threads': you can find the example in Artificial Intelligence for Games by Millington [chapter 9 Execution Management]


This allows me to interrupt Tasks longer tasks easily. The code is becoming more modular as well as it moves out of large AI Manager/Actor/Evaluation classes and into smaller classes that implement my TaskInterface.

I would still REALLY like to see how much time I have left in a frame to do work so I can modify how many milliseconds I can realistically use and still maintain a specific framerate.

This is the updated Scheduler

Code (CSharp):

1.  
2. void Update()
3. {
4.  
5.     watch = System.Diagnostics.Stopwatch.StartNew();
6.     while (watch.ElapsedMilliseconds < QuittingTimeMilliseconds && PlannedTasks.Count > 0 )
7.     {
8.         MillisecondsLeftToRun = QuittingTimeMilliseconds - watch.ElapsedMilliseconds;
9.  
10.        if (CurrentActiveTask == null)
11.            CurrentActiveTask = PlannedTasks.Dequeue();
12.  
13.        CurrentActiveTask.Activate(MillisecondsLeftToRun);
14.  
15.       if (CurrentActiveTask.Status == TaskStatusTracker.TaskStatus.Finished)
16.           CurrentActiveTask = null;
17.  
18.    }
19.  
20.    watch.Stop();
21.  
22. }

this is an example Task

Code (CSharp):

1. public void Activate(double p_millisecondsLeft)
2. {
3.     status = TaskStatusTracker.TaskStatus.Running;
4.  
5.    watch = Stopwatch.StartNew();
6.    timeCount = 0;
7.    SomeTypeofLoop( ChecktoSeeifLoopingShouldStop&& timeCount < p_millisecondsLeft)
8.    {
9.        // Do task work in loop usually
10.  
11.       timeCount = watch.ElapsedMilliseconds;
12.    }
13.  
14.    if (timeCount < p_millisecondsLeft)
15.        status = TaskStatusTracker.TaskStatus.Finished ;
16.    else
17.        status = TaskStatusTracker.TaskStatus.Holding;
18. }