C# - How can I improve method override performance in a Behaviour Tree?

Question

I’m using a custom-built behaviour tree that utilizes abstract/virtual method overrides to control the AI of a large number (1000+) of in-game creatures. This component is critical to the performance of the game, and I am looking for ways to reduce its CPU usage. Note: due to the nature of the game, an ecosystem simulator, I cannot simply stop simulating the AI for creatures that are out of sight.

The tree itself relies on the abstract base class Routine, which provides state information about the node and the overridable abstract On_Act() method, which is where each derived routine implements the logic it should follow to decide whether or not to succeed or fail.

public abstract class Routine
{
    /// ...

    /// <summary>
    /// Override to specify the routines logic.
    /// </summary>
    /// <param name="entity"></param>
    /// <param name="world"></param>
    protected abstract void On_Act(Entity entity, World.World world, ref List<Routine> routineTree);

    public virtual void Act(Entity entity, World.World world, ref List<Routine> currentTree)
    {
        currentTree.Add(this);
        On_Act(entity, world, ref currentTree);
    }

    /// ...

}

A good example of an implementation would be the WalkToLocation class, which causes an entity to attempt to walk to a given location, succeed if it reaches the target location, and fail if it becomes incapacitated on the way there.

public class WalkToLocation : Routine
{
    public Func<Vector3> TargetLocation { get; set; }

    public WalkToLocation(Func<Vector3> TargetLocation)
    {
        this.TargetLocation = TargetLocation;
    }

    protected override void On_Act(Entity entity, World.World world, ref List<Routine> routineTree)
    {
        IMobile creature = entity as IMobile;
        if (entity != null)
        {
            if (!creature.CapableOfMovement)
            {
                this.Fail();
                return;
            }

            Vector3 targetLocation = world.MapBoundaries.ClampPosition(TargetLocation());

            bool moveToResult;
            moveToResult = creature.WalkTowards(targetLocation, world);


            if (moveToResult == true)
            {
                this.Succeed();
                return;
            }
        }
        else
        {
            throw new ArgumentException("\"entity\" needs to implement IMobile");
        }
    }
}

And finally, it’s called from a Decorator class (a derived class of Routine) that pulls multiple routines together. Here, “scavenge” instructs an entity to walk over to an edible entity and eat it. (It also overrides the child sequences success if the food source becomes null)...

public class Scavenge : Decorator
{
    Creature parent;

    public Scavenge(Creature parent)
    {
        this.parent = parent;

        Child =
            new Sequence(
                new WalkToEntity(() => (Entity)parent.Context.OptimalFoodSource).Reportable(),
                new Eat(() => parent.Context.OptimalFoodSource).Reportable()
            );

    }

    protected override void On_Act(SpeciesALRE.World.Entity entity, SpeciesALRE.World.World world, ref List<Routine> routineTree)
    {
        if (Child.IsRunning())
        {
            Child.Act(entity, world, ref routineTree);
        }

        if (Child.HasFailed())
        {
            this.Fail();
            return;
        }
        else if (Child.HasSucceeded())
        {
            if (parent.Context.ClosestCorpse == null)
                this.Fail();
            else
                this.Succeed();
            return;
        }
    }
}

This all works well enough. From a performance standpoint, though, it’s proved unexpectedly awful. I spend more than half my CPU time inside the behaviour tree, and from what I can tell from the profiler, a significant chunk of that time is spent on overhead. In particular, methods like “Act” and “On_Act” on their own seem like they should cost barely anything, but every time they’re called I see a percentage of CPU time vanish without being accounted for by child methods.

I’m hoping someone with a better understanding of abstract/virtual methods than I can shed some light on where and why I’m incurring so much overhead, and how I can adjust the program to run faster, before I start folding sequences and selectors into single routines to reduce the depth of the tree, which rather defeats the point of having a Behaviour Tree in the first place.

Answer 1

Your CPU is going to try to run your code as fast as possible. Unless it is bound by other constraints (e.g. it's waiting for I/O or other resources) it'll run at 100%, or very close, until it is finished. See this article:

In computer science, a computer is CPU-bound (or compute-bound) when the time for it to complete a task is determined principally by the speed of the central processor: processor utilization is high, perhaps at 100% usage for many seconds or minutes. Interrupts generated by peripherals may be processed slowly, or indefinitely delayed.

So you do not seem to observing any measurements that in and of themselves indicate there is a performance problem.

If you wish to improve the performance, I doubt the "tree" is the issue. You probably have some subroutines that are expensive, e.g. searching for the nearest other creature, or detecting environmental obstacles. For these problems, there are some solutions that help, e.g. binary space partition or other data structures. If you want to find out more about those, start another question.