HTN planner prototype

I’ve been working on Paragon bots for some time now, and up until now, it was mostly about making it work, having bots play the game at all. Now, when the dust has settled and the bots do indeed play the game, it’s time to start thinking about bots that can use their abilities in an advanced manner, chaining their own abilities and cooperating ability triggering with their friends. This calls for some kind of planning, and I’ve wanted to implement a generic Hierarchical Task Network (HTN) planner for UE4 for a long time now. Well, here’s my use-case :D

Since I’ve never implemented an HTN before I’ve figured I can put together a quick prototype that will allow me to get this unique, intimate understanding you can only get by doing the thing yourself. This post is a kind of a record of the process.

To refresh my memory on HTNs I’ve reached for an article I remembered had a really clear explanation of the concept (namely this one).

An HTN planner implementation consists of two parts: planning domain, and the planner itself. There’s also “world state”, but I’m considering it a part of the domain since the domain used determines the validity of the world state representation.

Following the naming convention used in the article we have:

In short, an HTN Domain is build of Primitive and Compound Tasks. Compound tasks are build of Methods. Methods are build of Primitive and Compound Tasks.

The world state is a simple “facts” lookup with additional info on how to modify and check the stored facts:

As mentioned, the second part of and HTN planner implementation is the actual planner itself.

Up until now, I’ve listed only the properties of the declared classes. With this we can (almost) build a planning domain. I’ve just taken advantage of python syntactic sugar to make planning domain look nicer once defined:

With these we can build a test domain:

Of course, this wouldn’t compile. There’s a bunch of functions used here I haven’t defined (or even declared!) yet. This is partly how I work. I lay out the high-to-mid level code, and then just fill in the blanks. Let’s fill in the blanks now. First the part I always, always, always build along with any system I implement, and so should you, the debugging/validation code:

And last but not least (by far) the code that does the actual work. Here comes the functional part of the classes declared above:

The code doesn’t require much explanation, provided you’ve read the article mentioned earlier. There’s not much I can add other than the actual implementation (which I do).

The whole code in proper order can be found on the github. And we can test it like so:

which generates the following output:

Of course, this is the most basic implementation of an HTN planner and it doesn’t handle the more exotic cases. But it’s enough for me to start a proper C++ implementation in UE4 sources.

Sharing toys

It’s kinda funny to think I’ve gone live with my blog and then not posted anything after the very first post. I’m working on an interesting one, I promise, but in the meantime, I wanted to share a tiny toy I’ve made while investigating new tech. The new tech is Processing.js and I’m looking into it since I’ve already used regular Processing a bit in the past, and it’s an easy way to implement dirty prototypes with simple 2d graphics, and have it work in the browser without any changes to the code! I know suspect there better alternatives, but this one’s good enough :D

The following toy is a dead simple avoidance implementation, written from scratch in Processing, and done solely for the purposes of refreshing my Processing skills. Had fun implementing it nonetheless.

Here’s a link to the sources of this toy on github. Feel free to take a look, even though there’s a lot more educational value in trying to implement something like this from scratch rather than reading someone else’s code (especially mine! ;) ).