Dynamic NPC Actions

The true cornerstone of a project such as this will be dynamic and human like actions. I have spent the last two weeks thinking of a system that would allow the development and evolution of dynamic actions, searching the internet, writing down ideas, and finally come up with a design I feel confident enough to post about. I am writing this down for my benefit as well as anyone who is curious, so the train of thought it going to be random and probably hard to understand. For that I apologize, I will have more solid implementation details ready when I have a working system written.

I started by defining what I would be given, and what I would need to produce, and I decided to start with nothing but basic preprogrammed controllers attached to the actor’s to control everything about it. Rotation, position, scale, etc. For an npc, he would have controllers on all his bone joints, for an example. These controllers will have a predefined range of accepted values and know how to move around those ranges. What I wanted to end up with was a high level action, something that will ultimately be composed of hundreds of controller movements over time. And I needed a nice system to wrap up all this data into a structure the npc can store and build off of.

To start off, picture a flat plain of controllers. Each controller knows what it can do, but there are no existing actions yet so this npc is stupid as a brick. During training, actions will start simple, something along the lines of, ‘bend index finger’ works. The npc would look at its action graph and see only the flat plain of controllers, so then its asks each controller if it can accomplish the task of moving the finger’s x position by 1. The controller(s) that respond will have already been defined as able to do this so the npc builds a new action that connects directly with the controllers found previously. Now if the game asks to bend a finger, this action will say ‘I can do that’ and use the correct controller to chance the finger’s position. Its worth noting how the action knows it can do this, so I will explain that a bit. Each action has a function that reads the actor’s current state and determines if it has actions or controllers in its collection to handle that state in any way. If it does, it says yes.

So as the npc adds more and more actions it builds it’s web of linked actions, the process looks a lot like building a neural network. Actions have many actions linked to it, and many actions linked to. I cannot go to much farther without showing you the action class definition so here you go:

class Action
{
Action();
Action( Action* next );

bool validStart( Actor* );
bool validEnd( Actor* );

void AddNext( Action* );
void RemoveNext( Action* );

private:

std::set<Action*> actionList;  // Each entry in this action array represents a start state.
// What about actions that have many independant start actions?
};

When designing this class I thought it was going to be some monster from hell, but after I thought about it, added some recursion, and trimmed it down I think it ended up rather nice. Its simple and works well. Each action will hold links to one or more actions. Each action link represents a valid start state, so when validStart is called the class should call each of it’s start states validState functions and return the OR of their return. This design is very recursive, a next link could be another action or a controller at the very basic level. Therefore chains of actions will form in neural network fashion with proper training. When the npc wants to change his state (execute an action) he simple needs to figure out what state he wants to be in, call validEnd( endState ) on each of his higher level actions that match his start state and if one matches, execute the action.

Only problem here is the tremendous overhead of using the brain. Take an example actor with just three levels of actions, when the game asks to do an action on the third level that action asks for valid start on all level 2 actions linked to it, and in turn those level 2 actions call valid state for all level 1 actions linked to it, which in turn call validstart for all controllers that are linked with it. We could be looking at thosands of function calls with a simple 4 or 5 level npc. And the growth is
exponential.
For now we will just have to deal with it since I believe this to be the best way to describe dynamic actions however in the future tremendous effort will be required to optimize this code.

I will be working on integrating this design into my demo project so if my explanation is way off I will have sample code sometime soon.