Pseudo-non-deterministic AI

RPG-wise, everybody talks about non-linear gameplay, on the other hand, branched game stories are very expensive and do not really add to the entertainment value of the game for the first play.

So I am currently thinking about simulating non-deterministic NPCs. This would work thus: A couple of NPCs with the same role (e.g. peasants) would appear in the game, but their AI would only be assigned when the user interacts with the NPCs, in exactly the order the user approaches them.

So, for the user it seems that he randomly picks an NPC to talk to, and that NPC happens to have all the details on the next quest.

For the game, the NPC the player talked to was assigned the personality / dialog / etc that was required to set the player up with a certain quest.

Look to FSM or fuzzy FSM (FuSM) first (easiest to implement). You can then have logic that may assign a particular state pattern for a particular NPC based on when the user approaches them.