Game AI - Behavior Trees

How do you make a robust AI/scripting system for a game?

1) For all NPC's/environment/entities do you give them a SEPARATE single behavior tree (etc. patrolBehavior, allyBehavior, vendorBehavior, doorBehavior)? If there are 500 units on the screen, should I do a full pass on the tree (going from root -> node/action) or should I do 1-node progress for all the units?

2) I am doing the AI logic in the update() function... but I heard some games have their separate AI thread, any ideas?

3) I'm wondering how to divide my game into sections/chapters... do I use a simple variable (EVENT="Mission 3") to denote how for the player's been, and make it all linear? And then utilize variable in the trees above?

1. each NPC/Agent has its own behavior tree. The tree is updated and it 'knows' where to continue, so the efficiency is usually quite good.
2. AIs can be updated in the main thread, it can also be updated in a separated thead. it depends and up to you.
3. it depends and up to you.

behaviac is a really excellent one.

behaviac supports the behavior tree, finite state machine and hierarchical task network. Behaviors can be designed and debugged in the designer, exported and executed by the game.

The C++ version is suitable for the client and server side.

and, it is open sourced!