I recently posted the following, explaining some of my ideas about Agent AI:
I think there are two seperate sorts of plot here.
One emerges from NPC interactions. This is the kind of story that happens in everyday life - i.e. sweeping epic story arcs are going to be rather rare while the more mundane "someone stole my phone but I never found out who, so I bought a new one" are going to be rather more common.
The other is were the plot is pregenerated (or generated on the fly from prewritten chunks or complicated rules) and some mechanism attempts to force or entice the player to enter it. These tend to be much more story like - things you'd read in books or see in films. A great wizard looking to guide a young champion, managing to overthrow a kingdom ... that sort of thing.
I see no reason why both can't be put to work in a game. I've already done some work on the second method which I don't really intend to revisit until I'm implementing it in my game. I'm happy with it for now, limited as it is.
The first method - interesting situations developing from NPCs - well, I've had a few thoughts about how this could be done, recently. I'll just run through the idea quickly here.
In Ultima Online there was a log file. You could open the log file and see, say, the last 100 notable events that had occured. It might read:
Mary says "Hello"
Jack says "You stole my armour!"
Jack attacks Mary
The guards are called
Jack is killed
Mary says "Newb"
The Ghost of Jack says "ooOOOOoooooOOooo"
This log file was unique to what your character saw. Maybe you can guess where I'm going with this :D
Each NPC is given a log file that's modelled as a queue and takes in event data types. I would define events as:
event (e.g. "It's Dinner Time")
actor event (e.g. "YOU have left the city of Murag")
actor event actor (e.g. "PETE attacks JEFF")
Next you decide what in your world counts as an event. You might have dusk, dawn, seeing characters, characters talking, characters stealing, characters dying etc.
Eveything the NPC saw (or heard?) would then be pushed into it's personal event queue (potenitally removing the oldest event). So you have a list of events and we'll call this list "current events".
Along with this "current events" list the NPC will also have long term events. These are different for each NPC and can be generated randomly. Long term events include such things as:
NPC_X is immediate family
I am a werewolf
I hate bad people
Now you have these two [i]knowledge bases[/i]. If you've done some University AI you've probably covered expert systems. Well that's where I'm going. For an expert system you need a knowledge base, a rule set and an inference engine.
The rule set should be different for each character but generally similar rules will apply to certain NPCs. Guards will have certain rules, as will peasants, criminals and the like.
Rules are generally if-then statements.
if (NPC1 attack NPC2) and is_immediate_family(NPC1) then
You have to be careful with such rules. Imagine if NPC2 here, is also immediate family! Rules may modify the rule base, current knowledge might get promoted to long term knowledge - this should also be done through rules such as
1. if (NPC1 killed NPC2) and is_immediate_family(NPC2) then
AddLongTermKnowledge(NPC1 killed family)
2. if(see(NPC1) and killed_family(NPC1))
From simply rules like these quite complicated behaviour can be built up - and it's quite emergent!
(You would have to have a amazing amount of rules to get a "kindly wizard adopts an orphan boy because he knows he has a special gift that will come in useful to overthrow the evil kingdom that he's foreseen coming".)
The last thing you need is an inference engine which is pretty easy to write (as in there's plently of literature out there) but you probably want to write it in such a way that it can be queried over a number of frames (as in frame per second) depending on the drain on the CPU. Each NPC on screen (at minimum) is going to have to queried semi-regularly)
I think once you've got the rules done then interesting things will start happening. Possible there should be global rules too.
if guard attacks criminal it's okay
if NPC does some illegal he's a criminal
I intend to create the above system but not any time soon. (I'm still working on the graphics bit of my game) I think versions could work with extremely basic rule sets too.
Also the "current events" list might want events to be prioritzed. Leaving a city might be quite low - forgotten quickly. Someone becoming a criminal might be quite high takes a while to forget.
I posted it a Gamedev.net and the post can be found here.