Asynchronous behaviour for NPC in C# game

Question

This question is related to this one (Using C# 5 async to wait for something that executes over a number of game frames).

Context

When Miguel de Icaza first presented C# 5 async framework for games at Alt-Dev-Conf 2012, I really loved the idea of using async and await to handle "scripts" (so to speak, because they are in c#, and in my case, compiled---just in time but compiled anyway) in games.

Upcoming Paradox3D game engine seems to rely on the async framework to handle scripts too, but from my point of view, there is a real gap between the idea and the implementation.

In the linked related question, someone uses await to make a NPC perform a sequence of instructions while the rest of the game is still running.

Idea

I want to go a step further and allow a NPC to perform several actions at the same time, while expressing those actions in a sequential manner. Something along the lines of:

class NonPlayableCharacter 
{
    void Perform()
    {
        Task walking = Walk(destination); // Start walking
        Task sleeping = FallAsleep(1000); // Start sleeping but still walks
        Task speaking = Speak("I'm a sleepwalker"); // Start speaking
        await walking; // Wait till we stop moving.
        await sleeping; // Wait till we wake up.
        await speaking; // Wait till silence falls
    }
}

To do so, I used Jon Skeet's as-wonderful-as-ever answer from the related question.

Implementation

My toy implementation consists of two files, NPC.cs and Game.cs NPC.cs:

using System;
using System.Threading.Tasks;

namespace asyncFramework
{
    public class NPC
    {
        public NPC (int id)
        {
            this.id = id;

        }

        public async void Perform ()
        {
                    Task babbling = Speak("I have a superpower...");
            await Speak ("\t\t\t...I can talk while talking!");
            await babbling; 
            done = true;
        }

        public bool Done { get { return done; } }

        protected async Task Speak (string message)
        {
            int previousLetters = 0;
            double letters = 0.0;
            while (letters < message.Length) {
                double ellapsedTime = await Game.Frame;
                letters += ellapsedTime * LETTERS_PER_MILLISECOND;
                if (letters - previousLetters > 1.0) {
                    System.Console.Out.WriteLine ("[" + this.id.ToString () + "]" + message.Substring (0, (int)Math.Floor (Math.Min (letters, message.Length))));
                    previousLetters = (int)Math.Floor (letters);
                }
            }
        }

        private int id;
        private bool done = false;
        private readonly double LETTERS_PER_MILLISECOND = 0.002 * Game.Rand.Next(1, 10);
    }
}

Game.cs:

using System;
using System.Collections.Generic;
using System.Threading.Tasks;

namespace asyncFramework
{
    class Game
    {
        static public Random Rand { 
            get { return rand; }
        }

        static public Task<double> Frame {
            get { return frame.Task; }
        }

        public static void Update (double ellapsedTime)
        {
            TaskCompletionSource<double> previousFrame = frame; // save the previous "frame"
            frame = new TaskCompletionSource<double> (); // create the new one
            previousFrame.SetResult (ellapsedTime); // consume the old one
        }

        public static void Main (string[] args)
        {
            int NPC_NUMBER = 10; // number of NPCs 10 is ok, 10000 is ko
            DateTime currentTime = DateTime.Now; // Measure current time
            List<NPC> npcs = new List<NPC> (); // our list of npcs
            for (int i = 0; i < NPC_NUMBER; ++i) { 
                NPC npc = new NPC (i); // a new npc
                npcs.Add (npc); 
                npc.Perform (); // trigger the npc actions
            }
            while (true) { // main loop
                DateTime oldTime = currentTime;
                currentTime = DateTime.Now;
                double ellapsedMilliseconds = currentTime.Subtract(oldTime).TotalMilliseconds; // compute ellapsedmilliseconds
                bool allDone = true;
                Game.Update (ellapsedMilliseconds); // generate a new frame
                for (int i = 0; i < NPC_NUMBER; ++i) {
                    allDone &= npcs [i].Done; // if one NPC is not done, allDone is false
                }
                if (allDone) // leave the main loop when all are done.
                    break;
            }
            System.Console.Out.WriteLine ("That's all folks!"); // show after main loop
        }

        private static TaskCompletionSource<double> frame = new TaskCompletionSource<double> ();
        private static Random rand = new Random ();
    }
}

This is quite a straightforward implementation!

Problem

However, it doesn't seem to work as expected.

More precisely, with NPC_NUMBER at 10, 100 or 1000, I have no problem. But at 10,000 or above, the program doesn't complete anymore, it write "speaking" lines for a while, then nothing more gets on Console. While I'm not thinking of having 10,000 NPCs in my game at once, they also won't writeline silly dialogs, but also move, animate, load textures and so on. So I'd like to know what is wrong with my implementation and if I have any chance of fixing it.

I must precise that the code is running under Mono. Also, the "problematic" value could be different at your place, it can be a computer specific thing. If the problem can't seem to be reproduced under .Net, I will try it under Windows.

EDIT

In .Net, it runs up to 1000000, although it requires time to initialise, it may be a Mono specific problem. Debugguer data tell me that there are indeed NPCs that aren't done. No info as to why yet, sadly.

EDIT 2

Under Monodevelop, launching the application without a debugger seems to correct the problem. No idea as to why however...

End word

I realise this is a really, really lengthy question, and I hope you will take the time to read it, I'd really like to understand what I did wrong.

Thank you very much in advance.

Answer 1

There is one important point about TaskCompletionSource.SetResult: the continuation callback triggered by SetResult is normally synchronous.

This is especially true for a single-threaded application with no synchronization context object installed on its main thread, like yours. I could not spot any true asynchronicity in your sample app, anything that would cause a thread switch, e.g. await Task.Delay(). Essentially, your use of TaskCompletionSource.SetResult is similar to synchronously firing game loop events (which are handled with await Game.Frame).

The fact that SetResult may (and usually does) complete synchronously is often overlooked, but it may cause implicit recursion, stack overflow and deadlocks. I just happened to answer a related question, if you're interested in more details.

That said, I could not spot any recursion in your app, either. It's hard to tell what's confusing Mono here. For the sake of experiment, try doing periodic garbage collection, see if that helps:

Game.Update(ellapsedMilliseconds); // generate a new frame
GC.Collect(0, GCCollectionMode.Optimized, true);

Updated, try to introduce the actual concurrency here and see if this changes anything. The easiest way would be to change the Speak method like this (note await Task.Yield()):

protected async Task Speak(string message)
{
    int previousLetters = 0;
    double letters = 0.0;
    while (letters < message.Length)
    {
        double ellapsedTime = await Game.Frame;

        await Task.Yield();
        Console.WriteLine("Speak on thread:  " + System.Threading.Thread.CurrentThread.ManagedThreadId);

        letters += ellapsedTime * LETTERS_PER_MILLISECOND;
        if (letters - previousLetters > 1.0)
        {
            System.Console.Out.WriteLine("[" + this.id.ToString() + "]" + message.Substring(0, (int)Math.Floor(Math.Min(letters, message.Length))));
            previousLetters = (int)Math.Floor(letters);
        }
    }
}

Answer 2

Not sure if this is related, but this line stood out to me:

allDone &= npcs [i].Done; // if one NPC is not done, allDone is false

I would recommend awaiting on your Perform method. Since you want all NPCs to run asynchronously, add their Perform Task to a list and use Task.WaitAll(...) for completion.

In turn you could do something like this:

var scriptList = new List<Task>(npcs.Count);

for (int i = 0; i < NPC_NUMBER; ++i) 
{
  var scriptTask = npcs[i].Perform();
  scriptList.Add(scriptTask);

  scriptTask.Start();
}

Task.WaitAll(scriptList.ToArray());

Just some food for thought.

I've used the await/async keywords with the Mono Task library without issue, so I would not be so quick to jump to blame Mono.