AI Rework – Level 2 Tree

Okay, now we get to the fun stuff! And by fun I of course mean “densely technical and hard-to-follow”.

With creature’s wandering randomly until they invariably died horribly, I wanted my next focus to be giving them the ability to move towards things. This means a lot more than just having a MoveToPlant() routine, though: they first have to be able to find a plant in the world.

I could probably have implemented this as a simple black-box method that takes a creature and returns the nearest edible tree, but I wanted to test out my understanding of behavior trees. Additionally, implementing this as a behavior tree opens up the possibility of alternate methods for finding an edible plant in the future: checking memory, other senses, or may be even finding and asking other creaures where food may be found.

So anyways, this was the result:

You'll have to imagine your own funny comment, I got nuttin.

You’ll have to imagine your own funny comment, I got nuttin.

… and the code looks summit like this:

new Sequence(
	new SortLocalTrees(parent),
	new RepeatUntilFail(
		new Sequence(
			new GetNextTree(),
			new Inverter(
				new Sequence(
					new IsTreeEdibleSize(),
					new IsTreeInMapBounds(),
					new Inverter(new IsTreeBehindFence())
					new StoreClosestEdibleTree()
				)
			)
		)
	),
	new CheckClosestEdibleTree()
)

A bit more complex than last time! But don’t worry, it’s the same basic concepts. Let’s run through it:

SortLocalTrees

SortLocalTrees() is a fairly simple routine, and is called once when the root sequence starts up. It gathers up all the trees in the local area, puts them into a List, and sorts them by distance. It doesn’t actually *do* anything with items in the list: just sorts them.

If SortLocalTrees() fails (say, because there are no trees in the area), the parent Sequence fails, and the entire FindClosestEdibleTree() routine Fails. Back in the main AI, this causes the creature to fall back to Wandering. If SortLocalTrees() succeeds, however, it moves on to…

RepeatUntilFail()

A curious node: this one will keep on repeating so long as it’s child succeeds. It is actually incapable of failing: if the child fails, this routine succeeds, if it succeeds it just keeps going.

This can actually be something of a liability: it’s why we need the CheckClosestEdibleTree() routine at the end, so that if there are no edible trees in the area, the routine doesn’t return a misleading success.

It also has the potential to get caught in an infinite loop: simply tie it to a routine that never fails.

GetNextTree()

GetNextTree will get the next tree from the local tree list, succeeding when it returns a new tree, and failing if it’s at the end of the list. The Tree itself is stored in the creature’s “NextTree” field, so future routines can access it.

Combined with the RepeatUntilFail() above, this means that the behavior tree will go through the local tree list one by one, continually pulling out a new one and performing the following sequence on it. Since we sorted the list earlier, it will do so in order from the closest to the furthest.

Inverter()

A simple NOT gate. If the child fails, the inverter succeeds. If the child succeeds, the inverter fails. The reason for this will become apparent in a moment.

IsTreeEdible(), IsTreeInmapBounds(), IsTreeBehindFence()

Succeeds if the tree is edible/in map bounds/behind a fence, fails if it’s not. The inverter on BehindFence is there because we want the find to succeed if it’s not behind a fence.

StoreClosestEdibleTree

Copies the NextTree variable into the ClosestEdibleTree variable, so that later routines (like MoveTo() and Eat()) can target it.

CheckClosestEdibleTree()

As mentioned above, this ensures the routine as a whole fails if the RepeatUntilFail() Succeeded without filling out ClosestEdibleTree.

So, Here is where the entire routine finally comes together:

– The list is sorted, and GetNextTree() pulls out the closest tree.
– IsTreeEdible() Fails: this tree is not edible: maybe it’s too high for the creature to reach.
– The Sequence above it fails, so the Inverter above that succeeds. Thus, the entire GetNextTree() Sequence succeeds, and RepeatUntilFail() starts it over.
– GetNextTree pulls out the second closest tree.
– IsTreeEdible Succeeds this time. We have found an edible tree!
– For the sake of clarity, the tree is also in the map bounds and not behind a fence, so they succeed too.
– The Sequence stores the current tree in the “ClosestEdibleTree” variable, and succeeds.
– The Inverter get’s a Successful “tree found and stored” signal, and turns it into a Failure().
– This Fail() feeds up the tree to the RepeatUntilFail(), which in turn turns it back into a Success().
– When RepeatUntilFail() succeeds, it advances on to the final check: CheckClosestEdibleTree().
– If there’s something in this variable, it means the whole routine succeeded. If there’s not, it means the routine went through every local tree and didn’t find a single edible one.
– And with that, the FindClosestEdibleTree() routine succeeds. Future routines can now make use of the ClosestEdibleTree variable with impunity.

Now, I freely admit implementing a single-frame routine like this as ordinary code would have been a heck of a lot simpler. A sort(), a foreach() loop, the same checks as above and break when the checks passed. It could even be encompassed in a behavior tree wrapper, to succeed or fail depending on what it returned.

But the goal here wasn’t to program something efficiently, but to learn how to use behavior trees. And I think I’m getting the feel for them: it’s becoming easier for me to think my way through them and identify the problems I’m having when I test them.

The big advantage to Behavior Trees though is that, unlike code, they can be data driven, are inherently extensible, and most importantly can span multiple frames. Non-indicative example: it would be a matter of moments to change this to have creatures wait a frame between getting each new tree, reducing the per-frame computation and making it possible to actually see creatures weighing their options when they make decisions.

They can also be manipulated on the fly and even stored genetically, but I’m not sure how far down this rabbit hole I want to go. A simple system that manipulates behavior via emphasising or disregarding certain emotions or leaves of the tree is likely to be a lot more intuitive and communicative than genetic behavior trees.

I’m rambling and can’t think of a good segue to end the post on, so I’ll cut it short here.

Next time: And Suddenly There Was Gameplay Changes. Seriously: a completely new behavior and several major change to existing ones, none of which I was planning to implement. I just sorta happened. Stay tuned!

Advertisements
  1. #1 by Michael on October 21, 2014 - 2:31 am

    Wow. I just want to thank you for writing this incredibly informative and inspiring post. After reading this, I truly feel that I understand how behavioral trees work. Great job.

  2. #2 by Nolan on October 21, 2014 - 1:51 pm

    Can we get a glimpse of what a carnivore’s tree might look like? I really hate seeing carnivores just… sitting there and starving.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: