Determining what action an NPC will take, when it is partially random but influenced by preferences?

Question

I want to make characters in a game perform actions that are partially random but also influenced by preferences. For instance, if a character feels angry they have a higher chance of yelling than telling a joke. So I'm thinking about how to determine which action the character will take. Here are the ideas that have come to me.

Solution #1: Iterate over every possible action. For each action do a random roll, then add the preference value to that random number. The action with the highest value is the one the character takes.

Solution #2: Assign a range of numbers to an action, with more likely actions having a wider range. So, if the random roll returns anywhere from 1-5, the character will tell a joke. If it returns 6-75, they will yell. And so on.

Solution #3: Group all the actions and make a branching tree. Will they take a friendly action or a hostile action? The random roll (with preference values added) says hostile. Will they make a physical attack or verbal? The random roll says verbal. Keep going down the line until you reach the action.

Solution #1 is the simplest, but hardly efficient. I think Solution #3 is a little more complicated, but isn't it more efficient?

Does anyone have any more insight into this particular problem? Is #3 the best solution? Is there a better solution?

Answer 1

If you're going to go with options 1 or 2, look into buckets of random results - see Randomness without Replacement. If you go with a tree action, you can still use some of the same concepts to determine which branch of the tree to go down; however, you'd have a bit more determinism built in, as your options will restrict as you traverse down the tree.

If I recall correctly, Neverwinter Nights, which had a fairly nice scripting engine for its NPCs, would use a random probability to determine some of the actions their NPCs would take in certain states, but the states themselves were more driven by the script for that NPC (more of a state machine than a tree, but the concepts are similar). For example, if the NPC was walking, there was a chance they would stop, maybe laugh, etc. - but if they were attacked, they would switch to combat and stay there.

In other words, it all depends on what your actions are, and how you want the character to behave.

Answer 2

Markov chain, influenced by real user actions.

From wikipedia:

A Markov chain is a discrete random process with the property that the next state depends only on the current state.

Answer 3

#1 and #2 are simple but probably won't scale well to more complicated behaviors. Behavior trees (#3) seem to be the preferred system in many games nowadays. You can find some presentations and notes on AiGameDev.com, e.g. http://aigamedev.com/open/coverage/paris09-report/#session3 and http://aigamedev.com/open/coverage/gdc10-slides-highlights/#session2 (the first one from Crytek is quite good)

You probably don't need to worry about "efficiency" here in the sense of CPU usage, since this is very unlikely be a major bottleneck in your game. Reducing the amount of programmer/designer time needed to tweak the behavior is much more important.