Improving Performance of my Unity3D HTN-Planner (CUHP) with Multithreading

By adding some simple features, I have greatly increased the performance of my C# Hierarchical Task Network (HTN) Planner for use in Unity3D (CUHP). I previously explained how my Unity3D task planner works. To recap, it is a simple task planner written in C# for use in Unity3D, suitable for a wide range of video game genres (e.g. visual novels, adventure games, strategy games, shooter games). It can be used for NPC behavior, but also for story generation or even level generation! Feel free to experiment with it! I might also provide more (open source code) examples of the wide variety of applications of the planner in the future.

With this new blog post I show you how the performance of my planner is greatly improved by adding multithreading and functionality to cancel planning. In the previous version of my HTN-planner, the game could easily freeze up, resulting in a terrible user experience. Now with multithreading, the planner is run on a separate thread, so that the game continues to run on the main thread without freezing up. I will briefly explain multithreading in the next sextion, and follow this with some code examples. Furthermore, I provide a section about the cancel plan functionality and another section in which I explain some of my future steps.

The updated source code of my planner is available here: C# Unity3D HTN-planner (CUHP) on sourceforge.

Multithreading

I will not go into a lot of detail about multithreading, it is a complex subject and there are a lot of good sources available on the internet if you want to know more about it. That said, multithreading is "simply" the ability to execute a program on multiple threads. This is especially useful when a lot of calculations need to be done in a single method. With multithreading you can start the method with the heavy calculations on a new thread, while the main update method of your game continues to run on the main thread. This prevents the game from freezing up because now the update method does not need to wait until the heavy calculations are done.

Unity3D also provides thread-like behavior with coroutines. However, I choose threads over coroutines because threads are more flexible.

Multithreading is important for my Unity3D HTN-planner, because in some cases the planner takes a very long time to finish planning (up to several minutes). An example case is when there are a lot of applicable HTN-methods to the provided planning problem, but the planner is still unable to find a valid plan. Therefore, with multithreading, the planning can be run on a separate thread while the game continues to run on the main thread. This of course creates a new problem in some games, namely, if the NPC behavior is fully dependant on the plan generated by the planner. This could be solved in several ways, for example: by planning in advance, by adapting your planning algorithm (e.g. decrease number of HTN-methods), or by providing backup behavior for the NPC while it waits on the planner to finish.

Thanks to Mike Talbot of WhyDoIDoIt.com I found a simple way of using multithreading in Unity3D: Mike's "Loom" class. I have added this class to my CUHP project, renamed it to ThreadManager.cs and made a few minor changes.

I have added multithreading to the previously presented cleaning robot example. I have adapted my planner interface script (PlannerInterface.cs) such that when the user clicks the "Clean"-button on the GUI, a new thread starts in which the HTN-planner will run. The following code snippet shows the "SearchPlanAndSend"-method, in which the planner is started on a new thread. When a plan is found, it is automatically sent to the cleaning robot's task queue. I believe the code is very easy to understand. However, feel free to ask questions if anything is unclear.

private void SearchPlanAndSend()
{
    this.doneSearching = false;
    this.searchSuccessful = false;
    if (GetComponent<WorldModelManager>())
    {
        State initialState = GetComponent<WorldModelManager>().GetWorldStateCopy();
        if (initialState.ContainsVar("at"))
        {
            initialState.Add("checked", initialState.GetStateOfVar("at")[0]);
        }
        List<List<string>> goalTasks = new List<List<string>>();
        goalTasks.Add(new List<string>(new string[1] { "CleanRooms" }));

        ThreadManager.RunAsync(() =>
        {
            List<string> plan = planner.SolvePlanningProblem(initialState, goalTasks);

            ThreadManager.QueueOnMainThread(() =>
            {
                this.doneSearching = true;

                if (plan != null)
                    this.searchSuccessful = SendPlanToRobot(plan);
                else
                    Debug.Log("no plan found");
            });
        });
    }
}

The next section is about the cancel planning functionality.

Cancel Searching for Plan

The cancelling of searching for a plan (i.e. cancel planning) simply means that the planner is commanded to stop planning. I enabled this with a simple boolean "cancelSearch" in my HTN-planner code, which makes the planner stop instantly.

It is (for example) useful to cancel planning when the world state (or game state) changes so much that the plan currently being searched for will probably not be applicable to the current situation anymore. The plan will then most likely not produce the desired result anymore. Then after cancelling, you can issue the planner to find a new plan based on the new world state.

I provide no code sample of the cancel functionality because it is very straightforward. Just read through the code available on sourceforge and look for the "Cancel"-button in the "OnGUI"-method of the file RobotGUI.cs. This cancel button is a new addition to the cleaning robot example to showcase how to cancel planning.

In some cases of the cleaning robot example, the planner is unable to find a valid plan and gets stuck. I left this in for people who like a challenge. Experiment with the program to see when it gets stuck and try to improve my cleaning robot example so that the planner does not get stuck anymore. Good luck!

Future Work

I want to keep my future work section short this time with stating only the following: I plan to work next on a turn-based strategy game example in which my HTN-planner is used. And after that I want to work on a real-time strategy game example in which my HTN-planner is used. Feel free to ask questions though!

You are encouraged to use the CUHP-system, and expand and improve on it, as long as you share alike under the same (or a similar) open-source license.

CUHP: Simple C# Task Planner for Unity3D

Artificial intelligence is a growing field, especially in the games industry. The need for realistic and intelligent behavior in games is increasing. In my previous post I presented a new planner written in C#, a so-called hierarchical task network (HTN) planner. I know of several (scientific) examples where HTN-planners are used in real-time strategy games (e.g. Total Annihilation, Warcraft) or first-person shooters (e.g. Killzone 2, Arma, Unreal Tournament). I now show how my planner can be used in video games, or more specifically, video games made with Unity3D.

In the next section I talk about how my HTN-planner works with Unity3D, after that I show an example, and finally, I talk about what direction I have in mind for the future of my HTN-planner.

The C# Unity3D HTN-Planner

I present you, the C# Unity3D HTN-planner (CUHP), a hierarchical task network (HTN) planner written in C# for use in Unity3D. The planner is downloadable as a Unity asset-file and as a Unity3D project. If you want to know how HTN-planners work, I would suggest you read my previous blog post first.

The HTN-planner takes as input a planning problem and a planning domain. The planning problem contains a knowledge representation of the current state of the world and one or more goal tasks. The planning domain contains HTN-operators and methods which represent actions an agent or an NPC can take in the world.

An interface with the HTN-planner is needed to use the CUHP-system in a game environment. It can be really simple, and can be part of another script if desired. The following code is an example of such a planner interface:

private HTNPlanner planner = new HTNPlanner(typeof(Domain), new Domain().GetMethodsDict(), typeof(Domain));

private List<string> GetPlan ()
{
    if (GetComponent<WorldModelManager>())
    {
        State initialState = GetComponent<WorldModelManager>().GetWorldStateCopy();
        List<List<string>> goalTasks = new List<List<string>>();
        goalTasks.Add(new List<string>(new string[1] { "SolveProblem" }));

        return planner.SolvePlanningProblem(initialState, goalTasks);
    }
    return null;
}

First a new HTN-planner is declared and the planning domain is given as parameters. Here, a method called "GetPlan" is made to provide a way to use the HTN-planner. It can be customized to fit specific needs. The method gets the initial state from another script (WorldModelManager) and creates a new goal task called "SolveProblem". Finally, it calls the "SolvePlanningProblem"-method of the HTN-planner, providing the initial world state and goal tasks as parameters, and then returns the plan found by the planner. The next section shows an example in which a plan is actually executed.

The Cleaning Robot Example

I made two simple examples in Unity3D, a swap object example and a cleaning robot example. The latter is the most interesting, it is a virtual environment consisting of several linked rooms which together form a building. A cleaning robot resides in this building and it can be commanded to clean dirty rooms. The user can simply click on a room to make it dirty (or clean), and by doing this, a planning problem is created. Then, when any number of rooms are made dirty, the planner can be started (with a button) to solve the planning problem and produce a plan for the cleaning robot to execute. When a feasible plan is found, the robot will execute it and clean all dirty rooms in the building.

The following picture shows the virtual environment of the cleaning robot example:

The world is abstract and basic because the focus is on planning. The tiles represent rooms, the sphere represents the cleaning robot. When the user clicks on the "Clean"-button, the HTN-planner seeks a plan and sends it to the robot for execution. The robot converts a plan of actions into an action queue and executes the actions one-by-one. If the robot is still busy and receives a new plan, it clears its action queue and fills it with new actions, but it always finishes its current action. This simple example can be easily extended into a more complex game situation.

As mentioned in my previous blog post, the HTN-planner is not perfect at backtracking yet. The user can create some planning problems in the cleaning robot example for which no feasible plan can be found. This should not be too hard to fix and I might do that soon.

Future Work

I have a few ideas in mind about the future of this CUHP-system:

• HTN planning for strategy games. I want to make a more advanced game example to show the power of my HTN-planner, for example, I want to apply it to a real-time strategy game.
• Extending the Unity3D Editor. I want to extend the Unity Editor GUI for easy integration of the planner with a game, and to provide a more efficient way of designing artificial intelligence when making a game.
• Unity Asset Store. I am considering making the planner available in the Unity Asset Store.

I plan to work on these points in the future, and will write about it when I made progress.

You are encouraged to use the CUHP-system, and expand and improve on it, as long as you share alike under the same (or a similar) open-source license.