5.2 – Hybrid (BT + Utility) Architecture

5.2.0 – The Idea

At certain point when I was implementing stuff, I started to realize that all kinds of AI systems could probably give very similar results, if not identical. It was just a matter of how hard it would be to design, tune, and debug, And that drew a clear line between different systems. Behavior tree and FSM were highly regarded for their nature of simplicity–they would give you exactly what you designed, but they were too mechanical, and could grow to be unnecessarily complex. Utility and planners were great to show off some organic features, they were simple too, in system wise, but they were hard to design and even harder to tune.

So there was some interesting balance between system complexity and design complexity. After all, the purpose of computing and artificial intelligence was to make all our life easier.

So far I have only been thinking from the system’s perspective. I tried to figure out the potential and strength of certain systems. But in really, it was usually the other way around. Game came first, then system could be developed. The next phase of this project would be focusing on re-engineering.

5.2.1 – The design

Behavior tree is driven precisely by design. This is its strength and limitation. On one hand, it is intuitive and easy to tune. One the other hand, it is not subject to changes in the environment and not good at handling unexpected situations. This is because decisions are rarely binary. In a lot of cases, the priority of behaviors cannot be clearly defined. Sure, you can walk around the problem with a more sophisticated tree, but is that really necessary?

So the primary problem with behavior trees is that the order of behaviors are preset and cannot be changed in run-time. There are a couple of ways to change it. One is using a utility system in the selector to score each child, and re-order them based on the priority.

5.2.2 – The utility behavior

Essentially, only the leaf child need to be scored–they are actions and conditions. The composites just need to propagate the scores from their children to their upper level. The Behavior class needs to be extended to support the scoring:

UtilityBehavior.h:

void addConsideration(Consideration* _consideration)
{
	m_Considerations.push_back(_consideration);
}
inline virtual float getScore(Blackboard* _blackboard)
{
	float finalScore = 1.f;
	if (m_Considerations.size() > 0)
	{
		for (Consideration* c : m_Considerations)
		{
			finalScore *= c->getScore(_blackboard);
		}
	}
	return finalScore;
}

5.2.3 – The utility selector

The onUpdate() of selector needs to be modified to calculate the score of individual child, reorder them, and pick the one with the highest priority.

UtilitySelector.h

virtual Status onUpdate(Blackboard* _blackboard) override
{
	if (m_Utility.size() == 0)
	{
		// Query for child utility values
		for (auto it = m_Children.begin(); it != m_Children.end(); it++)
			m_Utility[it] = (*it)->getScore(_blackboard);

		// Sort children from highest to lowest
		std::vector<std::pair<Behaviors::iterator, float>> sortedChildren;
		for (auto it = m_Utility.begin(); it != m_Utility.end(); it++)
			sortedChildren.push_back(*it);
		sort(sortedChildren.begin(), sortedChildren.end(), [=]
			(std::pair<Behaviors::iterator, float>& a,
			std::pair<Behaviors::iterator, float>& b) 
			{ return a.second > b.second; });

		// Set current to the highest
		m_CurrentChildInSorted = m_SortedChildren.begin();
	}
	// Search in utility order until a child behavior says its running
	for (;;)
	{
		m_CurrentChild = m_CurrentChildInSorted->first;
		Status status = (*m_CurrentChild)->tick(_blackboard);
		if (status != Status::BH_FAILURE)
		{
			if (status == Status::BH_SUCCESS) m_Utility.clear();
			return status;
		}
		if (++m_CurrentChildInSorted == m_SortedChildren.end())
		{ 
			m_Utility.clear();
			return Status::BH_FAILURE;
		}
	}
}

You May Also Like

Leave a Reply

Your email address will not be published. Required fields are marked *

The AI Project