Log In  

Hi everybody!

It's been some time since I posted around here, and worked with Pico8 in general. Was a tough summer. But I come back with a second wind, partly because of the arrival of my PocketC.H.I.P.

Last Friday I started a project while I was on a train, to test out the device and how comfortable was to actually code with it. And I decided to post here some updates about the development of said project. So, without further ado:


Behavior Trees

Most of you probably know about them, and have worked with them. For those which do not, I'll provide a quick explanation. Please correct me if I'm wrong, as I'm by no means an expert in this matter.

The Behavior Tree is a model widely used in the videogame industry to create goal-oriented plans using small, self-contained, behaviors. They came out in a conference about Halo 2 AI systems, and since then they've been used in lots of different projects, even outside of the domain of videogames (robotics, etc).

A behavior tree(BT) works by going through its nodes, from the root towards the leaves, computing these nodes according to certain rules.

The possible outcome of a node Tick() function is either Success, Failure or Running (usually). Each node computes its Tick() function analyzing the outcome of its own children.

e.g: The Inverter node's Tick() will return Success if its unique child returns Failure, and Failure if it returns Success.

So, in each Tick() (usually inside an Update() function), the tree will be computed and only some behaviors will activate, creating a composed, more complex, behavior.

If you're interested in reading more about them, here are a few nice links to articles and posts:
Gamasutra Article
Introduction To Behavior Trees
Another introduction




I had a few objectives in mind when I started my implementation, tried to focus my project on them. Namely:

1) Each BT should be able to take a form of serialized data as model, and built itself with that given data. This is because code-driven trees (when you have to call a function yourself to create each node, add them, etc) it's extremely cumbersome, and more importantly, a token eater. There are interesting code-driven models out there (like this one: https://github.com/codecapers/Fluent-Behaviour-Tree), but a data driven approach it's way more realistic.

2) Debug. Debug. Debug. Being able to visualize the real tree was really important for me, as I said I'm no expert and prone to make silly mistakes.

>Basic structure

I started with the second one. First thing was actually build the trees (with mock methods, totally code-driven), draw them, etc... When I was confident that everything important was visible, I started to implement the basic nodes that made up most trees: Selector and Sequence. I also created two nodes, Success and Failure, for testing purposes.

They work like this:
Parent: A
Children: B, C, D

If A is a Sequence Node, it will return Success only if all childs, in order, Succeed. If any Fails, the remaining child nodes won't compute. e.g:

Sequence( "AreEnemiesAround", "EnterCombatMode", "TargetClosestEnemy")

This sequence will fail if there are no enemies, or if you can't enter combat mode, or if for whatever reason you can't target the closest enemy.

If A is a Selector Node, it will check if child, in order, and return the status of the first child that doesn't fail. That means either Success or Running will be selected. Once it selects one child, the rest aren't computed in that tick.

Imagine a Selector node, entered if a npc is hungry on a survival game:
Selector("Eat", "Cook", "Hunt", "CraftBow")

If our npc has cooked food, she will be able to Eat.
Else she will have to cook something she owns.
Else, if she doesn't carry anything, she will have to hunt.
Else, if she can't hunt because she lacks weapons, she will have to craft a bow. Etc...

>Visual Representation

I wrote a recursive draw function that goes through each node and draw it, in a different color according to its state:
green for Success, red for Failure, and yellow for Running. If the node is not reached by the calculations of that given Tick, it's color won't be updated, and usually will show Yellow as default color.

This was one of my first tries:

Here both the Root node and its two children were Sequence nodes, and its children, the leaves, were either success or failure nodes.
You can see how the first sequence returns Success (as its two children did too), but the second sequence fails because the first child (the third leaf) its a Failure Node.
The fourth leaf is not evaluated, and hence its left as it is, with yellow color.

-- To be continued ---

bt behavior-trees ai
P#28792 2016-09-19 08:01 ( Edited 2016-10-14 10:26)

:: More
About | Contact | Updates | Terms of Use
Follow Lexaloffle:        
Generated 2018-10-17 05:38 | 0.237s | 1835k | Q:9