Blog for James Ford at GarageGames.com

Behavior Trees in TGB Experiment

James Ford — 2008-09-28T04:37:57+00:00

If you are interested in game AI and haven't heard of behavior trees you might want to check out AIGameDev.com. In short they are the new, sexier finite state machines, basically a good way of laying out behaviors for your game agents in a nice modular and reusable way.

I felt like messing around with them and maybe a few other AI techniques for some experience, and ended up with this...

Some "monster" agents getting hunted down by a "hero" agent.

To give you an idea what it looks like to put together a behavior tree in script...
Note that there's more code behind the scenes doing work of course, in fact some in C++.

function FighterBehaviorTree::create( %agent )
{
   %tree = new BehaviorTree()
   {
      class = "FighterBehaviorTree";
      agent = %agent; 
   };
      
   %root = SelectorBehavior::create();
   %tree.add( %root );        

   // Eat some Food
   %beh = %root.add( SequenceBehavior::create() );
      %beh.add( Condition::create( "HungryCondition", false, true ) );                  
      %beh.add( ChatBehavior::create( "I'm hungry..." ) );      
      %sel = %beh.add( SelectorBehavior::create() );
         %beh = %sel.add( SequenceBehavior::create() );      
            %beh.add( Condition::create( "HasFoodCondition", false, true ) );         
            %beh.add( ChatBehavior::create( "Eating some food!" ) );
            %beh.add( LeafBehavior::create( "EatFoodBehavior" ) );
            %beh.add( WaitBehavior::create( 2000 ) );
         %beh = %sel.add( SequenceBehavior::create() );
            %beh.add( Condition::create( "HasFoodCondition", false, false ) );        
            %beh.add( ChatBehavior::create( "Going to buy food!" ) ); 
            %beh.add( MoveToPositionBehavior::create( $TavernPos, 0.1 ) );
            %beh.add( LeafBehavior::create( "BuyFoodBehavior" ) );
   
   // Kill a Monster
   %beh = %root.add( SequenceBehavior::create() );
      %beh.add( Condition::create( "MonstersNearbyCondition", true, true ) );
         %sel = %beh.add( SelectorBehavior::create( "FightOrFleeSelector" ) );
            %beh = %sel.add( SequenceBehavior::create() );               
               %beh.add( ChatBehavior::create( "Hunting a Monster!" ) );               
               %par = %beh.add( ParallelBehavior::create() );          
                  %par.add( LeafBehavior::create( "TargetClosestEnemyBehavior" ) );
                  %par.add( FollowTargetBehavior::create( 15 ) );        
                  %beh = %par.add( LoopBehavior::create( "FOREVER" ) );                  
                     %beh = %beh.add( SequenceBehavior::create() );
                        %beh.add( LeafBehavior::create( "ChooseWeaponBehavior" ) );
                        %beh.add( ChatBehavior::create( "Attacking!" ) );
                        %beh.add( LeafBehavior::create( "AttackTargetBehavior" ) );
                        %beh.add( WaitBehavior::create( 1000 ) );               
   
   // Rest at Inn
   %beh = %root.add( SequenceBehavior::create() );
      %beh.add( Condition::create( "TiredCondition", false ) );
      %beh.add( Condition::create( "MonstersNearbyCondition", true, false ) );
      %beh.add( MoveToPositionBehavior::create( $InnPos, 0.1 ) );
      %beh.add( LeafBehavior::create( "SleepBehavior" ) );
      
   // Wander
   %seq = %root.add( SequenceBehavior::create() );   
      %seq.add( Condition::create( "MonstersNearbyCondition", true, false ) );
      %beh = %seq.add( TimerBehavior::create( 3000 ) );
         %beh.add( LeafBehavior::create( "WanderBehavior" ) );   
      %seq.add( WaitBehavior::create( 1500 ) );

   return %tree;
}

So that looks fairly organized, maybe even a little "tree" like right? Still, creating them could be easier. So I've been working on an editor to help out.

Looking at the FighterBehaviorTree in game

So I'd say my review of behavior trees is "thumbs up". Once you have the framework in place, putting together a new tree consisting of a few sequences and selectors is a breeze.

Still I'm not doing anything very complex with these yet. Some more complex things I'd still like to try...
* building behavior trees dynamically, perhaps under the direction of a planner

And lots of stuff to add to the editor
* substituting one behavior for another ( correctly transferring over children )
* show the execution path in the tree editor
* Saving assembled trees to a managed script file

Of course there's plenty of other ai topics I'd like to look into
* fuzzy logic ( possibly used in a SelectorBehavior )
* a system for working and permanent memory of agents
* etc ad infinitum

My Programming Cheatsheet

James Ford — 2008-07-28T18:45:43+00:00

//---------------------------
// Programming Notes
//---------------------------

These are my "programming notes", a txt tile I keep on my desktop for things I looked up one to many times and decided to write down.

const F32*
means the F32 is const, you can't change its value but you can change the pointer
const *F32
means the pointer is const, you cannot change the pointer, but you can change the F32

Rotate vector by an angle ( in 3D this is rotating around the z axis )
x' = cos(theta)*x - sin(theta)*y
y' = sin(theta)*x + cos(theta)*y

EndMission / EndGame script function flowchart
loadmission() -> endmission()
destroyserver() -> endmission()
endMission() -> onmissionended() -> endgame() -> resetmission()
GameConnection::onDeath() -> cycleGame() -> onCycleExec() -> endgame()

How to get a sequence name by its index.
const char* seqName = mShape->getName( thread->sequence->nameIndex );

How to set a conditional breakpoint using string comparisions.
if ( dStrcmp( seqName, "chew" ) == 0 )
{
int t = 0; // set breakpoint here
}

This is how you get a nodes name:
S32 nodeNameIdx = mShapeInstance->getShape()->nodes[cast.node].nameIndex;
const UTF8 *nodeName = mShapeInstance->getShape()->getName( nodeNameIdx );

To regenerate intellisense:
Close VStudio, delete .ncb and .suo files in the solution folder, reopen and build project.

description of Player::getTransform MatrixF columns
column0 = rightvec
column1 = forwardVec
column2 = upVec
column3 = position

Calculate Size of a Terrain Block
squaresize x texelsPerMeter = terrain length ( or width )

UP is POSITIVE Z
Higher objects have a more POSITIVE z position

qSort itemA - itemB is ASCENDING - lowest val is element0
itemB - itemA is DESCENDING - highest val is element0

To post a url link with and give it a different visible name.
{url=VisibleName}www.url.com{/url}
But use square brackets.

PI = 180 Degrees

sin(x) = len(opposite) / (len(hypotenuse)

cos(x) = len(adjacent) / len(hypotenuse)

tan(x) = len(opposite) / len(adjacent)

Be the Dinosaur - AI Postmortem

James Ford — 2008-05-24T02:12:39+00:00

Be The Dinosaur
AI Postmortem

This was originally going to be a blog post but it got way, way too long. For the complete pdf doc, click here. The rest of this post contains no information not in the full version. Go ahead and click it.

Introduction

Be The Dinosaur (BtD) is a museum exhibit featuring an interactive simulation in which the visitor takes first-person control of a dinosaur in the late Cretaceous period. The exhibit may contain 1 - 32 machines together on the same network. Currently the two playable dinosaurs are the Triceratops (trike) and Tyrannosaurus rex (trex). Visitors will interact with each other in the simulation and with AI controlled dinos (DinoAgents). The most important activities are finding food, water, and defending yourself from other dinos.

This project is produced by Eureka Exhibits and developed by us at Sickhead. The Sickhead team consists of Tom Spilman, Russell Fincher, Ross Pawley, and James Ford (me). We began work on this project October 1st; 2000+ svn commits and 7 months later we emerge having finished the first project phase.

The focus of this paper, however, is the ai in BtD. Serious work on the AI began ~February 25, 2008. This paper reflects work done from then until May 19, 2008. This means approximately 2.5 months of full time work by an individual (me) was done for the BtD AI as it is now.

Reasons for this Paper

Spend some time reflecting on what we have done, and what to do next.
Let the community know what we are up to here at Sickhead.
Give something back to the community; there might be something useful for you in here.

AI Development Cycle

The first BtD museum exhibit opened on Feb.3, 2008. At that time there was no dinosaur AI except for a random wander behavior which did not perform pathfinding or obstacle avoidance. Since multiple players were not always available and not reliable for "modeling correct dinosaur behavior", improvements to the AI were a high priority for both improving the educational value and overall visitor experience.

After completing work on other core issues I began working exclusively on the AI around February 25th. The simulation was already on exhibit and the museum was promised on-going improvements throughout the duration of the exhibit. Also, visiting publicists and agents from other museums would be visiting and we needed to maximize the chance of booking future exhibits. If you are getting worried, we did make all deadlines, a good impression, and everyone was happy. At this time the exhibit has moved to the Louisville Science Center in Kentucky and we are in preparation for beginning a second BtD contract, which will include more AI improvements.

Since the simulation was already on exhibit when real work on the AI began it was important to implement features that would make the biggest different in gameplay first. We did not have an allocated amount of time for a design phase or time to develop a complex architecture. I also had very little AI programming experience. This should set the tone for you, and I thought it worthwhile to mention that time constrains played a large role in the AI development.

Resources and Acknowledgements

The most valuable resource turned out to be ImmersiveAI provided by Gavin Bunney.
www.garagegames.com/blogs/64167/12423

The book Programming Game AI by Example by Mat Buckland.
www.ai-junkie.com/books/toc_pgaibe.html

And the AI Game Programming Wisdom series of books.
www.aiwisdom.com

Thank you Gavin for making iAI available to the public, and excellent work! We had to make a decision early on whether to make our own architecture from scratch or try integrating an ai resource. We looked at GOAP (goal oriented action planning used in F.E.A.R.) and would have loved to implement it in Torque, but we just didn't have the time. iAI turned out to be a perfect starting framework for A* pathfinding and goal-based behaviors.

Also very useful and often consulted was the book Programming Game AI by Example, thanks Mat Buckland for writing the most practical, and best overview, ai book ever. In particular, the steering behavior code formed the basis of our SteeringManager class.

The AI Game Programming Wisdom books were also excellent for providing general education of contemporary ai techniques. Obviously not all the papers could apply to this project, and in fact source code from only one or two papers made it into BtD. Some of the more tantalizing ideas and techniques we just did not have time to mess with. However, I consider myself a much better educated ai programmer for having read them and that will help solve any problem.

BtD AI Architecture Overview

Brief list of components:

Steering Behaviors for managing short range movements and obstacle avoidance.
Procedural node generation based on empirical testing and A* pathfinding.
A prioritized goal architecture for defining dino behaviors.
A DinoAgent class completely separate from the Player class, which can be attached and detached.
A DinoAgentManager class to handle updating agents, propagating sound events, and other operations that affect all or multiple DinoAgents.

Brief list of DinoAgent behaviors:

All Dinos:

Find and drink water.
Prefer to remain near their pack.
Interact with friendly dinos (eg. vocalization).
Respond appropriately to overly aggressive "friendly" dinos.

Trike:

Find and eat edible plants.
Use a variety of tactics while in combat ( eg. charge, defend, flee ).

Trex:

Find and eat dino carcasses.
Hunt and kill prey dinos using a variety of tactics ( eg. stalk, charge, circle, flee ).

A few AI topics covered in the pdf:

Interesting techniques...

Integrating dynamic and static obstacle avoidance ... what didn't work, what else didn't, and what did
Precomputing paths to solve problems ... finding the closest water or plants to a dinos position
Handling goal failure and avoiding goals ... don't repeat the same mistake

Areas for BtD AI to improve...

Making Dino AIs more responsive to the player ... more interaction options, re-prioritizing interaction goals
Improvements to handling goal failure ... better failure tests, more custom code in goal-fail callbacks
Improvements to the goal architecture ... goal subclassing, dynamic goal priority ...

---

The rest you can read in the PDF. Also our client put a few videos on YouTube.

Enjoy!

TGB 1.5.1 Tutorial Pack In Development

James Ford — 2007-09-07T00:16:28+00:00

TGB is a powerful engine which, once learned, can be used to create near-anything. The catch is, the learning curve remains steep, and many a would-be developer gives up in frustration. The tutorials that ship with TGB are excellent, but do not provide as complete an education as newcomers often hope for.

I hope to change this for every TGB-noob.

The TGB tutorial pack will consist of 5 complete and working classic games, made with the latest version of TGB 1.5.1, making heavy use of behaviors, and using script only. These games may be taken for educational value only or used as a framework for your own classic-style game. The whole pack will be available for purchase at a very reasonable price.

Games Included:
Pong, Asteroids, Tetris, Pacman, Bomberman.

Although its hard to outline the specific topics covered in each tutorial everyone already knows these games, and each one has its own challenges, most with more than one solution. In these cases I will try to outline my first approach and if I decided to change it, why.

Specific Topics:
Behaviors: these are used for controlling the player, AI objects, defining oncollision results, and pretty much everying.
Tilemaps: These are used in Tetris, Pacman, and Bomberman (and every 2D game) over and over.
Physics and Collision: When to use it, and when not to.

Current Progress:
Pong: 90% ... An optional amount of fine tuning and writting the tutorial.
Asteroids: 50% ... Rigidbody collisions working, adding bullets and particle effects.
Tetris: 50% ... Decided to change method of representing pieces so a bit of rework to do.
Pacman: 70% ... Player and ghost movement working + powerups and ghost respawing.
Bomberman: 50% Working with 1.3 but needs "behaviorization" and cleaning of spagetti code.

Expect screenshots soon.

I expect a couple months of work before its ready, but I'll keep you posted!