Various AI Techniques

[Shando]

Hi all,

I have now completed initial testing for Blackboards (http://en.wikipedia.org/wiki/Blackboard_system), Behaviour Trees (http://en.wikipedia.org/wiki/Behavior_Trees_(Artificial_Intelligence,_Robotics_and_Control)), Decision Trees (http://en.wikipedia.org/wiki/Decision_tree) and Finite State Machines (http://en.wikipedia.org/wiki/Finite-state_machine) in Skyline

The link below points to a folder on my OneDrive account that contains the generic scripts for each of these AI types:

http://1drv.ms/1JPcXlP

The Main Script I used for testing is this:

Code: Select all

sky.include "decisiontree.lua";
sky.include "decisionbranch.lua";
sky.include "evaluators.lua";
sky.include "blackboard.lua";
sky.include "actions.lua";
sky.include "behaviortree.lua";
sky.include "behaviortreenode.lua";
sky.include "finitestatemachine.lua";
sky.include "finitestate.lua";
sky.include "finitestatetransition.lua";

myLogicType = 0;

function onInit ( objID )
   -- Set up the Blackboard
   gBlackboard = { };

   bb_Initialise ( );

   bb_Set ( 1, "enemyid", 2 );
   bb_Set ( 1, "health", 100 );
   bb_Set ( 1, "maxhealth", 100 );
   bb_Set ( 1, "ammo", 33 );
   bb_Set ( 1, "maxammo", 100 );
   bb_Set ( 1, "target", 2 );
   bb_Set ( 1, "height", 1.7 );
   bb_Set ( 1, "heightstand", 1.7 );
   bb_Set ( 1, "heightcrouch", 1.0 );
   bb_Set ( 1, "ismoving", false );
   bb_Set ( 1, "isfalling", false );
   bb_Set ( 1, "maxspeed", 10.0 );
   bb_Set ( 1, "maxspeedstand", 10.0 );
   bb_Set ( 1, "maxspeedcrouch", 5.0 );
   -- TODO: The next line is Skyline specific
   -- bb_Set ( 1, "velocity", newType.vec3 ( 0.0, 0.0, 0.0 ) );
   bb_Set ( 1, "animstatecurrent", "idle" );
   bb_Set ( 1, "animstatenew", "" );
   -- TODO: The next line is Skyline specific
   --bb_Set ( 1, "bestfleeposition", newType.vec3 ( 0.0, 0.0, 0.0 ) );
   bb_Set ( 1, "moveendtime", 0 );
   bb_Set ( 1, "team", 1 );

   bb_Set ( 2, "health", 50 );
   bb_Set ( 2, "team", 2 );

   objID = 1;
   enemy = 2;

   myActions = act_actions ( objID );

   --myLogic = decisionTree ( objID );
   --myLogicType = 0;

   --myLogic = behaviourTree ( objID );
   --myLogicType = 1;

   myLogic = finiteStateMachine ( objID );
   myLogicType = 2;

   animStateNew = "";
end

-- |------------------------------------------------------------------------------
-- | Update: called every frame
-- |------------------------------------------------------------------------------
function onUpdate ( dt )
   if ( myLogicType == 0 ) then
      myLogic:DT_Update ( dt );
   elseif ( myLogicType == 1 ) then
      myLogic:BT_Update ( dt );
   elseif ( myLogicType == 2 ) then
      myLogic:FSM_Update ( dt );
   end

   tmpBool, animStateNew = bb_Get ( objID, "animationstatenew" );
 
   local tmpBool1, tmpState = bb_Get ( objID, "animationstatecurrent" );
 
   if ( tmpState ~= animStateNew ) then
-- TODO: The next line is Skyline specific
--   anim.playAnimation ( objID, animStateNew, 30, 1);
      bb_Set ( objID, "animationstatecurrent", animStateNew );
   end
end

function decisionTree ( objID )
   -- *******************
   -- DECISION TREE START
   -- *******************
   -- Set up the Decision Tree
   local tree = dtNew ( );

   local isAliveBranch = dbNew ( );
   local criticalBranch = dbNew ( );
   local moveFleeBranch = dbNew ( );
   local enemyBranch = dbNew ( );
   local ammoBranch = dbNew ( );
   local shootBranch = dbNew ( );
   local moveRandomBranch = dbNew ( );
   local randomBranch = dbNew ( );

   isAliveBranch:DB_AddChild ( criticalBranch );
   isAliveBranch:DB_AddChild ( myActions.ACT_DieAction ( objID ) );
   isAliveBranch:DB_SetEvaluator ( function ( )
         if Evaluators_IsNotAlive ( objID ) then
            return 2;
         end
      
         return 1;
      end
   );

   criticalBranch:DB_AddChild ( moveFleeBranch );
   criticalBranch:DB_AddChild ( enemyBranch );
   criticalBranch:DB_SetEvaluator ( function ( )
         if Evaluators_HasCriticalHealth ( objID ) then
            return 1;
         end
      
         return 2;
      end
   );
    
   moveFleeBranch:DB_AddChild ( myActions.ACT_MoveAction ( objID ) );
   moveFleeBranch:DB_AddChild ( myActions.ACT_FleeAction ( objID ) );
   moveFleeBranch:DB_SetEvaluator ( function ( )
         if Evaluators_HasMovePosition ( objID ) then
            return 1;
         end
      
         return 2;
      end
   );

   enemyBranch:DB_AddChild ( ammoBranch );
   enemyBranch:DB_AddChild ( moveRandomBranch );
   enemyBranch:DB_SetEvaluator ( function ( )
         if Evaluators_HasEnemy ( objID ) then
            return 1;
         end
      
         return 2;
      end
   );
    
   ammoBranch:DB_AddChild ( shootBranch );
   ammoBranch:DB_AddChild ( myActions.ACT_ReloadAction ( objID ) );
   ammoBranch:DB_SetEvaluator ( function ( )
         if Evaluators_HasAmmo ( objID ) then
            return 1;
         end
      
         return 2;
      end
   );

   shootBranch:DB_AddChild ( myActions.ACT_ShootAction ( objID ) );
   shootBranch:DB_AddChild ( myActions.ACT_PursueAction ( objID ) );
   shootBranch:DB_SetEvaluator ( function ( )
         if Evaluators_CanShootAgent ( objID ) then
            return 1;
         end
      
         return 2;
      end
   );

   moveRandomBranch:DB_AddChild ( myActions.ACT_MoveAction ( objID ) );
   moveRandomBranch:DB_AddChild ( randomBranch );
   moveRandomBranch:DB_SetEvaluator ( function ( )
         if Evaluators_HasMovePosition ( objID ) then
            return 1;
         end
      
         return 2;
      end
   );

   randomBranch:DB_AddChild ( myActions.ACT_RandomMoveAction ( objID ) );
   randomBranch:DB_AddChild ( myActions.ACT_IdleAction ( objID ) );
   randomBranch:DB_SetEvaluator ( function ( )
         if Evaluators_Random ( objID ) then
            return 1;
         end
      
         return 2;
      end
   );

   tree:DT_SetBranch ( isAliveBranch );

   return tree;
   -- *******************
   --  DECISION TREE END
   -- *******************
end

function behaviourTree ( objID )
   -- *******************
   -- BEHAVIOR TREE START
   -- *******************
   local tree = btNew ( objID );
   local node;
   local child;

   node = tree.BT_CreateSelector ( );
   tree.bt_node_ = node;

   -- die action
   child = tree.BT_CreateSequence ( );
   node:BTN_AddChild ( child );
   node = child;

   child = tree.BT_CreateCondition ( "is not alive", Evaluators_IsNotAlive );
   node:BTN_AddChild ( child );
   node = child;

   node = node:BTN_GetParent ( );
   child = tree.BT_CreateAction ( "die", myActions.ACT_DieAction ( objID ) );
   node:BTN_AddChild ( child );
   node = child;

   -- flee action
   node = node:BTN_GetParent ( );
   node = node:BTN_GetParent ( );
   child = tree.BT_CreateSequence ( );
   node:BTN_AddChild ( child );
   node = child;

   child = tree.BT_CreateCondition ( "has critical health", Evaluators_HasCriticalHealth);
   node:BTN_AddChild ( child );

   child = tree.BT_CreateAction ( "flee", myActions.ACT_FleeAction ( objID ) );
   node:BTN_AddChild ( child );

   -- reload/shoot/move/pursue actions
   node = node:BTN_GetParent ( );
   child = tree.BT_CreateSequence ( );
   node:BTN_AddChild ( child );
   node = child;

   child = tree.BT_CreateCondition ( "has enemy", Evaluators_HasEnemy );
   node:BTN_AddChild ( child );

   child = tree.BT_CreateSelector ( );
   node:BTN_AddChild ( child );
   node = child;

   -- reload action
   child = tree.BT_CreateSequence ( );
   node:BTN_AddChild ( child );
   node = child;

   child = tree.BT_CreateCondition ( "has no ammo", Evaluators_HasNoAmmo );
   node:BTN_AddChild ( child );

   child = tree.BT_CreateAction ( "reload", myActions.ACT_ReloadAction ( objID ) );
   node:BTN_AddChild ( child );

   -- shoot action
   node = node:BTN_GetParent ( );
   child = tree.BT_CreateSequence ( );
   node:BTN_AddChild ( child );
   node = child;

   child = tree.BT_CreateCondition ( "can shoot enemy", Evaluators_CanShootAgent );
   node:BTN_AddChild ( child );

   child = tree.BT_CreateAction ( "shoot", myActions.ACT_ShootAction ( objID ) );
   node:BTN_AddChild ( child );

   -- pursue action
   node = node:BTN_GetParent ( );
   child = tree.BT_CreateAction ( "pursue", myActions.ACT_PursueAction ( objID ) );
   node:BTN_AddChild ( child );

   -- move action
   node = node:BTN_GetParent ( );
   node = node:BTN_GetParent ( );
   child = tree.BT_CreateSequence ( );
   node:BTN_AddChild ( child );
   node = child;

   child = tree.BT_CreateCondition ( "has move position", Evaluators_HasMovePosition );
   node:BTN_AddChild ( child );

   child = tree.BT_CreateAction ( "move to position", myActions.ACT_MoveAction ( objID ) );
   node:BTN_AddChild ( child );

   -- random action
   node = node:BTN_GetParent ( );
   child = tree.BT_CreateSequence ( );
   node:BTN_AddChild ( child );
   node = child;

   child = tree.BT_CreateCondition ( "50/50 chance", Evaluators_Random );
   node:BTN_AddChild ( child );

   child = tree.BT_CreateAction ( "random move", myActions.ACT_RandomMoveAction ( objID ) );
   node:BTN_AddChild ( child );

   -- idle action
   node = node:BTN_GetParent ( );
   child = tree.BT_CreateAction ( "idle", myActions.ACT_IdleAction ( objID ) );
   node:BTN_AddChild ( child );
   node = child;

   return tree;
   -- *******************
   --  BEHAVIOR TREE END
   -- *******************
end

function finiteStateMachine ( objID )
   -- *******************
   --     FSM START
   -- *******************
   local fsm = fsmNew ( objID );

   fsm:FSM_AddState ( "die", myActions.ACT_DieAction ( objID ) );
   fsm:FSM_AddState ( "flee", myActions.ACT_FleeAction ( objID ) );
   fsm:FSM_AddState ( "idle", myActions.ACT_IdleAction ( objID ) );
   fsm:FSM_AddState ( "move", myActions.ACT_MoveAction ( objID ) );
   fsm:FSM_AddState ( "pursue", myActions.ACT_PursueAction ( objID ) );
   fsm:FSM_AddState ( "randomMove", myActions.ACT_RandomMoveAction ( objID ) );
   fsm:FSM_AddState ( "reload", myActions.ACT_ReloadAction ( objID ) );
   fsm:FSM_AddState ( "shoot", myActions.ACT_ShootAction ( objID ) );

   -- idle action
   fsm:FSM_AddTransition ( "idle", "die", Evaluators_IsNotAlive );
   fsm:FSM_AddTransition ( "idle", "flee", Evaluators_HasCriticalHealth );
   fsm:FSM_AddTransition ( "idle", "reload", Evaluators_HasNoAmmo );
   fsm:FSM_AddTransition ( "idle", "shoot", Evaluators_CanShootAgent );
   fsm:FSM_AddTransition ( "idle", "pursue", Evaluators_HasEnemy );
   fsm:FSM_AddTransition ( "idle", "randomMove", Evaluators_Random );
   fsm:FSM_AddTransition ( "idle", "idle", Evaluators_True );

   -- move action
   fsm:FSM_AddTransition ( "move", "die", Evaluators_IsNotAlive );
   fsm:FSM_AddTransition ( "move", "flee", Evaluators_HasCriticalHealth );
   fsm:FSM_AddTransition ( "move", "reload", Evaluators_HasNoAmmo );
   fsm:FSM_AddTransition ( "move", "shoot", Evaluators_CanShootAgent );
   fsm:FSM_AddTransition ( "move", "pursue", Evaluators_HasEnemy );
   fsm:FSM_AddTransition ( "move", "move", Evaluators_HasMovePosition );
   fsm:FSM_AddTransition ( "move", "randomMove", Evaluators_Random );
   fsm:FSM_AddTransition ( "move", "idle", Evaluators_True );

   -- random move action
   fsm:FSM_AddTransition ( "randomMove", "die", Evaluators_IsNotAlive );
   fsm:FSM_AddTransition ( "randomMove", "move", Evaluators_True );

   -- shoot action
   fsm:FSM_AddTransition ( "shoot", "die", Evaluators_IsNotAlive );
   fsm:FSM_AddTransition ( "shoot", "flee", Evaluators_HasCriticalHealth );
   fsm:FSM_AddTransition ( "shoot", "reload", Evaluators_HasNoAmmo );
   fsm:FSM_AddTransition ( "shoot", "shoot", Evaluators_CanShootAgent );
   fsm:FSM_AddTransition ( "shoot", "pursue", Evaluators_HasEnemy );
   fsm:FSM_AddTransition ( "shoot", "randomMove", Evaluators_Random );
   fsm:FSM_AddTransition ( "shoot", "idle", Evaluators_True );

   -- flee action
   fsm:FSM_AddTransition ( "flee", "die", Evaluators_IsNotAlive );
   fsm:FSM_AddTransition ( "flee", "move", Evaluators_True );

   -- die action

   -- pursue action
   fsm:FSM_AddTransition ( "pursue", "die", Evaluators_IsNotAlive );
   fsm:FSM_AddTransition ( "pursue", "flee", Evaluators_HasCriticalHealth );
   fsm:FSM_AddTransition ( "pursue", "shoot", Evaluators_CanShootAgent );
   fsm:FSM_AddTransition ( "pursue", "idle", Evaluators_True );

   -- reload action
   fsm:FSM_AddTransition ( "reload", "die", Evaluators_IsNotAlive );
   fsm:FSM_AddTransition ( "reload", "shoot", Evaluators_CanShootAgent );
   fsm:FSM_AddTransition ( "reload", "pursue", Evaluators_HasEnemy );
   fsm:FSM_AddTransition ( "reload", "randomMove", Evaluators_Random );
   fsm:FSM_AddTransition ( "reload", "idle", Evaluators_True );

   fsm:FSM_SetState ( "idle" );

   return fsm;
   -- *******************
   --      FSM END
   -- *******************
end

function globalFn ( callID, tTmp )
  local tmpStr = tTmp.tStr;
  local tmpTeam = tTmp.team;
  local tmpPos = tTmp.position;
  local tmpEnemyID = tTmp.enemy;

  local tmpBool, tmpT = bb_Get ( objID, "team" );
 
  if ( tmpTeam == tmpT ) then   
    if ( tmpStr == "RetreatPosition" ) then
-- TODO: Do stuff here based on the incoming message
    elseif ( tmpStr == "PositionUpdate" ) then
-- TODO: Do stuff here based on the incoming message   
    elseif ( tmpStr == "EnemySelection" ) then
-- TODO: Do stuff here based on the incoming message
    end
  else
-- TODO: Non "Team" messages get handled here
  end
end


The Main Script should be fairly easy to understand, but feel free to give me a shout if you don't understand something (there are also a couple of other things I was trying still in the code such as the Messaging).

I apologise in advance for the fact that not everything is commented as well as it should be

Finally, most of the code is taken from a fantastic book called "Learning Game AI Programming with Lua" by David Young. I have, however, spent many hours extracting the bits I needed and changing the code so that it worked in Skyline.

The original code is issued under the following licence:

Copyright (c) 2013 David Young dayoung@goliathdesigns.com

This software is provided 'as-is', without any express or implied
warranty. In no event will the authors be held liable for any damages
arising from the use of this software.

Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it
freely, subject to the following restrictions:

1. The origin of this software must not be misrepresented; you must not
claim that you wrote the original software. If you use this software
in a product, an acknowledgment in the product documentation would be
appreciated but is not required.

2. Altered source versions must be plainly marked as such, and must not be
misrepresented as being the original software.

3. This notice may not be removed or altered from any source
distribution.

I have contacted David and told him what I was doing, and he didn't seem to have any issues, BUT, as with all these things, if you do provide any form of source code please include the above.

Shando

[SolarPortal]

holy crap! Well done Shando! That is a complete library lol.
Looking through the code is quite impressive, but we would love to see an example of it running though.
It is quite a read through for us also lol.

This is a good set lua of scripts to include with skyline if you allowed it, but an example or tech demo would be required for the end users.

When reading through, i take it you are supposed to control what the entities and physics does for each state or evaluator in the "evaluators.lua" script file, as this is the only location i see with skyline library API. Or am i missing something?

This is quite an achievement m8.

Advancements with the next release of skyline:
I think this will be great to advance with the dynamic properties and a custom AI Editor Plugin.
That would make this a complete system. The editor plugin itself could even be sold on the store lol.

With Dynamic Scripts, for example where you have:

Code: Select all

 
function onInit ( objID )
-- code before

    bb_Set ( 1, "health", 100 );

-- code after
end


You would use this instead:

Code: Select all

 
--[[Prop|float]] customhealth = 100;

function onInit ( objID )
-- code before

    bb_Set ( 1, "health", tonumber(entity.getDynamicProperty("customhealth")));

-- code after
end


That would make it a reusable script for the health value, where one character may have 100 health and another has 1000. All without tweaking the code. Replicate this across the lot and this 1 script could be reused over and over without opening a script editor for the users.

[Shando]

Hi SP,

I will get around to creating a complete demo of the various techniques (and maybe a UI to go with it ??)

Basically, you have to create an "Initialize", a "CleanUp" and an "Update" function for each "Action". These go in the "actions.lua" file. These are used to actually set up and affect the entity for each relevant "Action".

You also have to create the various "Evaluator" functions which go in the "evaluators.lua" file. These are used to determine if an entity can "do something" (eg: whether an entity has any ammo determines whether it can "Shoot" or if it needs to "Reload" ).

Finally, you create the actual technique that sets up the Tree (or FSM) by directly referring to the created "Actions" and "Evaluators" (as shown in my Main Script).

I'll see if I can put together a quick demo over the weekend (if I can find the time).

Shando

[SolarPortal]

this makes sense. Looking forward to seeing this in action

[StarFire]

Wow Shando that is one heck of a library, great work m8

Looking forward to seeing it running. Not sure if there is going to be much performance hit but if there is the option it could be turned into a C++ lib and integrated into Skylines core code base.

Again well done!

[epsilonion]

Hi shando if you still have the files can you please re-link please, I am interested in working out how it all works in skyline.

If you want I could put them on my server and link to them there so it doesnt expire so that future users can download them

[SolarPortal]

put them on the store, thats what its there for

[Shando]

Hi All,

Just uploaded to Store for the SPECIAL PRICE of 0.00 Well, there is no demo etc. so can't really charge anything for it!

If anyone needs any help, just let me know either here, or via pm and I'll try to help ( PS: haven't looked at this for over a year, so may take me a little while to work things out )

Shando