Saving and resuming position while iterating over a container

Question

Background:

I'm in the process of writing a relatively simple behavior tree driven AI system for a game that I'm working on. Basically, the behavior tree is made up of individual gameplay tasks (move, attack, etc.) as well as composite tasks that iterate over sub-tasks in a variety of ways. Each gameplay task is a leaf and will return a status (success, failure, or running).

For example, a sequence composite task iterates over its sub-tasks in sequential order. If all of the sub-tasks in the sequence return Status.SUCCESS, the sequence will also succeed. If any of the sub-tasks in the sequence return Status.FAILURE, the sequence will end early and fail. Finally, if any of the sub-tasks return Status.RUNNING, the sequence needs to store its position, return Status.RUNNING this frame, and re-tick the same sub-task again next frame.

I had no issue getting my behavior tree to work correctly within a single frame of execution at first by recursively calling Tick() down the tree. This works basically like a depth-first traversal. But I've been having some issues finding a clean way of dealing with storing and resuming from nodes that return Status.RUNNING.

I probably can't post all the code needed to compile and run this without making a mess of this question but here's the basic flow of the program:

• The main game Engine loop calls Update() on all entities/components each frame.

• The AIController, an AI player of the game, will act according to the tree of Task objects that compose its BehaviorTree. When the AIController is updated each frame it calls Update(AIController ai) on its internal BehaviorTree object and passes itself in as an argument.

• The BehaviorTree encapsulates a tree structure of Task nodes. Each Task represents some kind of action that the AI player will perform (move, wait, attack, etc.). A CompositeTask is a task that controls the execution flow of any number of sub-tasks - in other words, a branch. When the BehaviorTree is updated each frame, it simply calls Tick(AIController ai) on the root Task node.

• Occasionally a CompositeTask will tick a sub-task that returns Status.RUNNIGN. This means that the sub-task requires more time than a single frame to perform some action and is requesting to be ticked again during the next Engine update/frame/loop. When a sub-task returns a running status, the composite that ticked it will also return a running status and execution will then back out of the entire behvaior tree. During the next frame of the game, the behavior tree should immediately skip back to the task that returned Status.RUNNING in the previous frame and resume where it left off.

All the code samples below are functional and in both cases my sequencer is behaving as intended when populated with some simple test tasks. I recognize that I'm being a bit loose with the permissions - a lot of things are public that probably shouldn't be but it makes it easier to test and debug in my current engine and I'll buckle down on that a little later. I'm a self-taught programmer who hasn't worked with many large or experienced teams yet and I'm still quite new to C# as a language, so I'm more than happy to receive any critiques or advice on how I can generally improve!

First Attempt:

This was my first attempt at handling real time tasks (for example, automated character movement over time). If a task can be performed with a single frame/update/tick it will either return Status.SUCCESS or Status.FAILURE, the tree will continue being traversed, and as many nodes will be ticked as possible. However, whenever a task node returns Status.RUNNING we need to store that task somehow, back out of the tree traversal, and resume from node next time.

Because each composite task calls Tick() on its sub-tasks, it seems like the state of the tree at any given time is tied to the function call stack. I can't just store the running tasks in a list outside of my behavior tree, because despite being easy to tick them again next frame I would be losing the bigger picture of their place in the tree and wouldn't know where to go next.

I 'solved' this by creating a reference to a task in each of my composites. When one of a composite's sub-tasks returns Status.RUNNING a reference to that task is stored in Task savedTask then the composite also returns Status.RUNNING. Next time the composite is ticked it checks if a task has been saved. If so, the savedTask is reference compared to the current subtask iteration and the foreach loop will jump ahead until we find a match.

This is the behavior tree class which only really serves to encapsulate everything:

/*
*   AI behavior tree encapsulation.
*/
public class BehaviorTree {
    public Task root;

    public void Update( AIController ai ) {
        if( root != null ) {
            root.Tick ( ai );
        }
    }
}

Here a simple abstract base class for all of the task nodes in my behavior tree:

/*
*   Base class for representing various behaviors in an AI behavior tree.
*/
public abstract class Task {
    public enum Status {
        SUCCESS = 0,
        FAILURE = 1,
        RUNNING
    }

    public abstract Status Tick( AIController ai );
}

This is the abstract base class for all my composite tasks:

/*
*   Abstract base class for composite tasks.
*   A composite task is the root of a subtree of tasks.
*   As such they contain a list of children 'subtasks', that they
*   iterate over and update in a variety of ways. (Sequencing, selecting, parallel updating, etc.)
*   In other words, they serve as control structures within a behavior tree.
*/
using System.Collections.Generic;

public abstract class CompositeTask : Task {
    protected Task savedTask;
    public List<Task> subtasks = new List<Task>();
}

Here's my first shot at programming my sequence composite task node:

/*
*   Ticks subtasks in list order until it one of its subtasks FAILS.
*   As a result, the subtasks towards the beginning of the list are pre-requisites.
*   Subtasks that are found later in the list are skipped if a previous task fails.
*   When a task returns RUNNING it's saved for the next tick, when it will be immediately skipped to.
*   Performs the inverse behavior of a Selector composite task!
*/
public class Sequencer : CompositeTask {
    public override Status Tick ( AIController ai )
    {
        foreach( Task subtask in subtasks )
        {
            //If a task returned Status.RUNNING last tick, skip ahead to the running task..
            if( savedTask != null ){
                if( subtask != savedTask ){
                    continue;
                }
            }

            Status subtaskStatus = subtask.Tick( ai );
            switch( subtaskStatus ){
                case Status.SUCCESS: 
                    savedTask = null; //Make sure task isn't saved next tick..
                    break; //Break switch and move on to next subtask tick..
                case Status.FAILURE:
                    savedTask = null; 
                    return subtaskStatus; //Back out early when any subtask fails.. 
                case Status.RUNNING:
                    savedTask = subtask; //We need to save running tasks so we can pick up where we left off!
                    return subtaskStatus; //Back out early and resume/retick running task time!
            }
        }
        return Status.SUCCESS;
    }
}

This worked fine, but it felt a bit messy and brute-force. So I thought about other possible ways to do it. Thinking back to some of the C++ code that I've written, using something like an iterator came to mind. After a little research I found that IEnumerator seems to be more-or-less the same idea in C#...

Second Attempt:

So, going back to the drawing board, I tried rewriting my code to make use of enumerators. Now, instead of storing a reference to a task, my composite now stores an IEnumerator reference. I've used foreach loops and IEnumerable objects many times before in C#, but this is the first time I've ever needed to deal with IEnumerators alone. Honestly, I went for a kind of 'lazy' approach to calling subtasks.GetEnumerator() instead of doing so in the constructor because I figured that tasks might be added and removed dynamically at various points in time. I added some small convenience functions for controlling my IEnumerator to prevent cluttering my code in other places.

Here are the changes to my CompositeTask abstract base class:

using System.Collections;
using System.Collections.Generic;

public abstract class CompositeTask : Task {
    public IEnumerator position;
    public List<Task> subtasks = new List<Task>();

    /*
    * Move to the first subtask in the list.
    */
    protected void FirstSubtask(){
        if(position == null){ //Lazy enumerator retrieval..
            position = subtasks.GetEnumerator();
        }

        position.Reset();
        position.MoveNext();
    }

    /*
    * Try to move to next subtask in list, return true if it can.
    * If it can't move or is at the end of the list, it resets to the first subtask and returns false.
    */
    protected bool NextSubtask(){
        if(position == null){ //Lazy enumerator retrieval..
            position = subtasks.GetEnumerator();
        }

        if( position.MoveNext() ){
            return true;
        }
        else{
            FirstSubtask();
            return false;
        }
    }
}

Here's my new sequencer code using IEnumerators. It works as it should, but honestly I suspect this code is kind of bad! The basic idea was to store an enumerator that always references one of the sub-tasks. If a sub-task is succeeds, the enumerator moves to the next one and we tick it immediately. If a sub-task fails, the enumerator is moved to the beginning. And finally, if a sub-task returns Status.RUNNING we don't touch the enumerator and we just back out. Next time the composite is ticked, it will tick whichever subtask is referenced by the enumerator.

Here's the altered Sequencer composite task that I rewrote using IEnumerators:

public class Sequencer : CompositeTask {
    public override Status Tick ( AIController ai )
    {
        if(position == null){ //Lazy enumerator retrieval..
            FirstSubtask();
        }

        Task subtask = (Task)position.Current;
        Status subStatus = subtask.Tick(ai);
        switch( subStatus ){
            case Status.SUCCESS:
                if( NextSubtask() ){
                    Tick(ai);
                }
                else{
                    FirstSubtask();
                }
                break;
            case Status.FAILURE:
                FirstSubtask();
                break;
        }
        return subStatus;
    }
}

Conclusion

Anyway, that's about it. Both of these "sequencer" composite tasks work correctly now, but I'm not convinced that the code couldn't be a lot better in both examples. The first code is just a brute-force reference comparison of the saved task against the current sub-task, but it's relatively clean and simple. The second code is based on iterators/enumerators and feels like it's on the verge of being the right path, but it's also a bit messy and it probably shows my lack of experience in certain areas. I'm alright with that, as I'm here to learn and improve! After all, I don't have many opportunities for code review!

My main questions are:

• What is the best way to approach this overall issue (essentially saving and resuming from a certain iteration of a loop or place in a tree traversal)?

• What are the pros and cons of the strategies used both of my attempts?

• How can I improve the code in my enumerator example?

• Are there other strategies for solving this problem that I should be aware of?

• From this example, how can my programming and software design be improved overall?

Answer 1

Your situation

Sometimes the best way to solve a problem is to avoid it. Why not make Status a property on Task rather than a return value? Then you can just check the status of each sub-task before ticking, and skip it if its status is SUCCESS

In General

Most of the time, a simple foreach iteration over an IEnumerable<T> is what you want for iterative logic. But in some cases- and tree-related algorithms are an area this often occurs- a different data structure will serve you better. In this case, I'd suggest storing your children in a Stack. Then your loop can look like:

    while(subTasks.Any())
    {
        var next = subtasks.Pop();
        Status subtaskStatus = next.Tick( ai );
        switch( subtaskStatus ){
            case Status.SUCCESS: 
                break; //Break switch and move on to next subtask tick..
            case Status.FAILURE:
                return subtaskStatus; //Back out early when any subtask fails.. 
            case Status.RUNNING:
                subtasks.Push(next); //Push it back onto the stack so it'll be first in line next time
                return subtaskStatus; //Back out early and resume/retick running task time!
        }
    }

As a side note, if you do have cause to use IEnumerator and IEnumerable, you should pretty much always use the generic versions, in the same way that you'd always choose to use a List<Task> to hold tasks rather than a List<object>

Etc.

For more general comments, your code is mostly good stylistically. Naming conventions, actual names, and so on, are good ("Sequencer" is possibly a little iffy, but I can't be sure without knowing exactly what it does differently from other potential CompositeTask implementations)

Two ways in which your code doesn't follow standard C# conventions is your use of all-uppercase for enum values, and having opening braces on the same line. Both of these are a matter of preference, but it's usually a good idea to follow language conventions.