Behavior Tree / AI

BlitzMax Forums/BlitzMax Programming/Behavior Tree / AI

Scaremonger

(Posted 2013) [#1]

MERRY CHRISTMAS TO ALL

A couple of years ago, the AI (using a FSM) of a game I was developing became so large and unwieldy that I ultimately gave up on it.

Recently I started trying different approaches and during some research found this article about AI in Halo 2 which took me in a totally different direction. Further research gave me some information on Behavior trees but nothing much to build upon so I started from scratch. My design goals were simple: It had to fit into existing code, not be reliant on other libraries and be reusable.

My Behavior Tree is implemented as a linked tree of Nodes called Controls and Traits. Controls decide on which child should be executed and Traits are the Leaf nodes that implement a Behavior or Action for your sprite or character.

Take the following code; it shows a simple AI that moves a sprite to a screen location and when it arrives, chooses a new destination:

Example1-Simple

SuperStrict
'# BEHAVIOR TREE / Simple Sprite Movement
'# (c) Copyright, Si Dunford, ITSpeedway.net, Dec 2013
'#

Include "..\bhtree_main.bmx"
Graphics( 800, 600 )

'# Build Behavior tree
TSprite.buildTree()

'# Create Some Sprites
For Local n% = 1 To 10
	New TSprite.Create()
Next

'# GAME LOOP
Local sprite:TSprite
Repeat
	Cls	
	'If KeyHit( KEY_SPACE ) Then DebugStop
	For sprite = EachIn TSprite.list
		sprite.update()
	Next
	For sprite = EachIn TSprite.list
		sprite.draw()
	Next
	Flip
Until KeyHit( KEY_ESCAPE )

'############################################################
Type TSprite
Global list:TList = CreateList()
Global tree:BHTree	'# Behaviour Tree
Field ax#, ay#		'# Actual Position
Field dx#, dy#		'# Actual Position
	'------------------------------------------------------------
	Method Create:TSprite()
		ListAddLast( list, Self )
		ax=Rand( 0, GraphicsWidth() )
		ay=Rand( 0, GraphicsHeight() )
		dx=Rand( 0, GraphicsWidth() )
		dy=Rand( 0, GraphicsHeight() )
	Return Self
	End Method
	'------------------------------------------------------------
	Method draw()
		DrawOval( ax,ay,15,15 )
	End Method
	'------------------------------------------------------------
	Method update()
		tree.update( Self )
	End Method
	'============================================================
	Function buildtree()
	Local root:Control
		'# Create the root node (Must be a control)
		root = New Selector
		root.addchild( New Movement )
		root.addchild( New ChooseDestination )
		'# Create the tree
		tree = New BHTree.Create( root )
	End Function
End Type

'############################################################
Type ChooseDestination Extends Trait
	'------------------------------------------------------------
	Method update%( obj:Object )
	Local sprite:TSprite = TSprite( obj )
		sprite.dx=Rand( 0, GraphicsWidth() )
		sprite.dy=Rand( 0, GraphicsHeight() )
	Return STATUS_SUCCESS '# Always successful
	End Method	
End Type

'############################################################
Type Movement Extends trait
	'------------------------------------------------------------
	Method update%( obj:Object )
	Local sprite:TSprite = TSprite( obj )
	Local angle#         = ATan2( sprite.dy - sprite.ay , sprite.dx - sprite.ax ) + 90
	Local distance#      = Sqr( (Float(sprite.ax) - Float(sprite.dx) ) ^ 2 + (Float(sprite.ay) - Float(sprite.dy) ) ^ 2 )
		sprite.ax :+ Cos( angle - 90 ) 
		sprite.ay :+ Sin( angle - 90 ) 
		'# If we are there, Continue Processing Tree
		If distance < 1 Then Return STATUS_FAILURE '# Process next Behavior
	Return STATUS_SUCCESS '# Stop processing behaviors
	End Method
End Type

Whilst this example is very simple (and probably easier to implement with a FSM), you have to remember that the tree can be easily expanded to thousands of decisions without having to manually maintain a state.

The Behavior tree in the example is created by using a standard "Selector" Control as a root node and two custom Traits as children of that node (Movement and ChooseDestination).

I have currently implemented the following standard Control nodes:
* Selector - Executes each child until one is successful and only fails if all children fail.
* Randomiser - Executes a single random child node.
* Sequence - Executes each child until one fails. Succeeds if all children succeed.

It also supports bitvector based node execution, which means that large portions of the Behaviour Tree can be enabled / disabled based on a single system game state.

My Code is in BETA at the moment and I hope to have it up on SourceForge shortly.

I'd be interested in hearing your thoughts on this.

Cheers,
Si...

Scaremonger

(Posted 2013) [#2]

V1.00 Released on SourceForge

Whats new!
* Three new Controls: Singular, RoundRobin and RequireNone
* Three new Traits: Enabler, Disabler and Decision
* TreeBuilder that allows Behavior trees to be created from a definition file (No more code changes when tweeking your AI).
* Added Enable/Disable ability to all traits & controls
* Started a Wiki
* Can be used standalone or compiled as a module.

Controls
* Selector - Executes each child until one is successful and only fails if all children fail.
* Randomiser - Executes a single random child node.
* Sequence - Executes each child until one fails. Succeeds if all children succeed.
* Singular NEW
* RoundRobin NEW Selects the next child in order
* RequireNone NEW Parses all children and returns success when all children fail, or fail when any one succeeds.

Traits:
* Enabler NEW - Enables a list of nodes
* Disabler NEW - Disables a list of nodes
* Decision NEW - Allows a decision point to be included

Examples
* Example1-Simple.bmx
* Example2-TreeBuilder.bmx NEW