I read your post twice and I am not sure about the recursive O(n) algorithm. However, you seem to know what youa re talking about so I cannot really comment (I do not personally know what it is).
For a generalized way of implementing very believable entity movement is to simulate a processor for each entity. Each entity has its own instruction pointer, and with the instruction pointer comes an 'operation code'. Then, you get to invent your own instruction set! The operation code typically holds:
A floating point scalar
An opcode identifier
An entity pointer
An integer
A vector
so you have:
struct OPCODE
{
int OPCode;
Vector OPVector;
float OPFloat;
int OPInt;
Entity *OPEntPptr;
}
This seems like a total hack at first, but this is mroe or less how it is done professionally. Think about it, whenever you want to do *anything* with any unit in the world, it must involve one of those datatypes. If not, then you simply dont' use it! For example, you may want to attack an enemy, that requires various things
a) knowing what the entity is (entity pointer)
b) knowing WHERE the entity is (vector)
c) how fast to move towards target persecond (float)
you would then need to enumerate the types of operations:
Code:
enum
{
Attack=0,
Move,
Idle,
Patrol,
NumOfInstructions
}
Each physical entity will own these things to make this work:
Code:
class ENTITY
{
public:
void Update();
static OPCODE instructions[NumOfInstructions]; //all that is needed is to set the OPCode identifier
//with these, which are typically held in either your enum or in #defines of a file
int instructionpointer(0);
int fetch(1); //true / false, tells the simulated process whether or not to fetch a new instruction
OPCODE instruction; //the actual instruction owned by each entity
}
then in your handy dandy update function, you do something like this:
Code:
if(fetch) //do we need a new instruction yet?
//i.e have we accomplished what we previously wanted to do,
//or, have we quit trying to do what we previously wanted to do?
{
this->instruction = ENTITY::instructions[instructionpointer];
//init values specific to scenario, i.e player position, or new target
fetch = 0;
}
switch(instruction.OPCode)
{
case Attack:
{
//run your program attack code until you kill target or give up
break;
}
case Move:
{
//do stuff
break;
}
case Idle:
{
//DONT do stuff :)
break;
}
}
etc etc. I've made several syntax mistakes but its hard to show how this works. When you get it right, it works perfectly. You are starting to go down a road where you manually must check EVERY SPECIFIC condition in the world ALL of the time and things wont happen automatically. Obviously the next instruction pointer you want the program to do is decided upon algorithmically in each of those switch statements. You can have 10,000 possible actions, and depending on the outcome of each action you can branch off to potentially any other action, which is also a basis in neural nets and simulated human response.
and just an example
Code:
case Attack:
{
if(EntityIsDead(instruction.OPEntity))
{
instructionpointer = Patrol; //or you can decide to idle, depending on random numbers
fetch = 1; //tell engine to update my instruction set
}
else
{
//Calculate attack angles to player, you could even add MORE opcodes such that there is a specific
//'calculate pitch and yaw' instruction added to your instruction set, otherwise, you are in attack mode
//so continue attacking
}
break;
}
The very nice thing about this type of implementation is that your recursive 0(n) algorithm can be encapsulated, but more effectively utilized, using this setup. Now if only I could get the whole grammar thing right