I'm approaching the point in my MUD where I'd like to start implementing some NPCs. I don't have any AI experience. I've googled a bit and searched the forums here, but a lot of the discussions I've found are at a high level, discussing advanced AI topics. I'll keep perusing, but in lieu of a forum FAQ, can someone point me to some good resources for some MUD NPC AI design?Simple is fine, almost preferred, as I'm just beginning to plan my NPC implementation, and as I said I'm a bit of an AI noob. What I have kicking around in my head right now is to have an XML template that all NPC types will rely upon that defines their probabilities for actions in and out of combat. Maybe something like this: When the NPC is created, I will load these probabilities in, and based on events and its environment, they will change. For example, if the monsters hit points drop to 20%, its retreat probability will move up to 50%. Perhaps I'll even add an attribute to those combat/nonCombat elements for frequency, which will be a minimum time in milliseconds for how frequently the monster takes an action, with a random deviation to make it look good. Anyway, these are all just rough ideas, but does it sound like I'm on an appropriate path? Are there some good resources for about this level of thinking/design?

Most MUDs have virtually no NPC AI anyway, so resources on them are limited.

My suggestion would be for you to think about what exactly you mean by 'AI'. It seems like you have combat decision making on the list, along with some sort of random chat behaviour, and some wandering behaviour. You also have a state machine, denoting a state of combat and one of non-combat, and certain activities only occur within one of the two states. You want to modify activity behaviours based on context, which implies that perhaps you have a fixed list of possible activities which contexts can be assumed to know about, and that the contexts know how to appropriately modify such activities.

So, let's expand from there. Might you want more than just those 2 states? Maybe there would be a state for when the NPC is grouped with someone else, or one for when they are sleeping, or... whatever. Consider each of the exclusive states an NPC might be in. Then consider how you decide which state they are in at any given time - if it's just a case of combat or not-combat, this might be simple enough.

Then think about these activities. Is there a standard list of activities to choose from? Are they all one-shot commands? If some take time to execute, how will you handle that? How will you modify the probabilities based on context? For example, when your hit points drop to 20%, what exactly do you do to those activity probabilities? Simply saying you'll raise the retreat% to 50% is not enough: what if it was already 60%? What if there was no retreat% at all? What do you do about the other percentages to make them still sum up to 100%? What if your hit points have dropped to 20% but some Berserk spell is cast on the NPC, which normally lowers their Retreat%?

I'm afraid I don't have any simple answers for you. I've been thinking about how to improve MUD NPC AI for a while and not come up with much of use. If it just comes down to a few randomly chosen attacks or utterances then it's not worth spending much time on, because few people will see the subtlety. I think truly interesting AI would come about more as a result of either NPC planning (deciding what they want and then executing actions to bring them closer to that), or perhaps cooperation (calling for help, grouping up, healing each other), and so on.

PS. Forget the XML template for now. The file format you store this stuff in is not relevant to AI as such. What is relevant is what you do with the information once it's loaded. But do try and use XML in a sensible way: a separate tag for each attack type doesn't make sense, for example. More reasonable would be an <action> tag with retreat/slash/heal as the value of an attribute

Thank you for your response, Kylotan.

I suppose my question deals more with design, rather than AI. I'm concerned with at this point more with the AI mechanics rather than the actual NPC logic at this point. The two topics are related, to be sure, but I want to flesh out my implementation before I start working into the details.

So, on the topic of design, Is the simple probability acting state machine concept that I've presented solid? And what is a good way to implement the delay in actions? I'd imagine keeping a thread per NPC is a bit inefficient. Maybe I'll have one thread that maintains all NPCs, sleeping for a 10th of a second and subtracting the time since the last loop from each monster's "waiting" value, and the ones that go below zero act then and reset that value? That, too, might be a bit unruly, especially if there are hundreds of NPCs in the world.

As for the specifics:

Quote:
So, let's expand from there. Might you want more than just those 2 states? Maybe there would be a state for when the NPC is grouped with someone else, or one for when they are sleeping, or... whatever. Consider each of the exclusive states an NPC might be in. Then consider how you decide which state they are in at any given time - if it's just a case of combat or not-combat, this might be simple enough.

The XML I posted I just pulled out of the air. I'll likely have more states than combat an not, such as bartering for shop keepers, or reactions to pick pocketing.

Quote:
More reasonable would be an <action> tag with retreat/slash/heal as the value of an attribute

The tag change you pointed out is definitely a good idea, especially since I declare commands in XML as well. If I go to the more general "action" tag, what do I do about parameters? Perhaps I'll just stick them on the action tag as attributes just the same? So maybe we turn "slash" into a more general "attack" command, complete with targeted body parts (I probably won't go that far, but it's a good sample case):

<action type="slash" target="leg">attack</action>

If I do that, though, is there any sense in putting the "attack" in the body of the element, rather than just as another attribute? I always go back and forth on XML, whether to use all nested values or all attributes. Perhaps someone can give a compelling reason to use both, as above?

Quote:
I'm afraid I don't have any simple answers for you. I've been thinking about how to improve MUD NPC AI for a while and not come up with much of use. If it just comes down to a few randomly chosen attacks or utterances then it's not worth spending much time on, because few people will see the subtlety. I think truly interesting AI would come about more as a result of either NPC planning (deciding what they want and then executing actions to bring them closer to that), or perhaps cooperation (calling for help, grouping up, healing each other), and so on.

I'm afraid I don't really plan on taking the AI much further than the typical bot. I just want them to attack those they are hostile toward, present a few personality traits (emotes and sayings), serve as shop keepers, and be able to respond to simple questions by picking out key words. Perhaps in the future I'll take it to a greater degree, and hearing some examples as to what that might entail would be helpful, but for now i want to keep it simple.

Quote:
Then think about these activities. Is there a standard list of activities to choose from?

I'm not sure about that. Perhaps I'll group them, in maybe a many to many table with a "type", attack or support, and I will link them to NPC types?

Quote:
Are they all one-shot commands?

For now, yes.

Quote:
If some take time to execute, how will you handle that?

Round time is already implemented. If the creatures randomly modified wait time comes up before its round time is up, it will simply wait until the round time expires.

Quote:
How will you modify the probabilities based on context? For example, when your hit points drop to 20%, what exactly do you do to those activity probabilities? Simply saying you'll raise the retreat% to 50% is not enough: what if it was already 60%? What if there was no retreat% at all? What do you do about the other percentages to make them still sum up to 100%? What if your hit points have dropped to 20% but some Berserk spell is cast on the NPC, which normally lowers their Retreat%?

The question of how the probabilities change based on events is very compelling. Perhaps I'll just have a handful of personality types, and I will modify some base reaction types from there? For example, there might be a cowardly creature type, which will increase its retreat thresholds by 30% when the monster reaches 40% health, rather than 20%. The 30% will be applied to retreat, and the other values will be adjusted equally to bring the totals to 100%.

Perhaps all attacks will be lumped together under a root "attack" node, having a parent probability for simply attacking, and the children with have a probability set of their own for which attack to execute. This would allow me to adjust the retreat and attack ratios on a general basis, regardless of the number of attacks the creature has available to it. So cowardly creatures at 40% health become 30% more likely to retreat, 30% less likely to attack, and have the same probability for support commands, whereas an aggressive character is just as likely to retreat, 20% more likely to attack, and 20% less likely to use support commands.

There sure is a lot to think about, in terms of both design and logic. Logic is fun, but design concerns me more at this stage.

Thank you again, Kylotan.

Quote: Original post by CyberSlag5k
Is the simple probability acting state machine concept that I've presented solid? And what is a good way to implement the delay in actions? I'd imagine keeping a thread per NPC is a bit inefficient. Maybe I'll have one thread that maintains all NPCs, sleeping for a 10th of a second and subtracting the time since the last loop from each monster's "waiting" value, and the ones that go below zero act then and reset that value? That, too, might be a bit unruly, especially if there are hundreds of NPCs in the world.

Yes, a simple state machine is fine, and yes, periodically picking a weighted random choice is ok too.

You don't want a thread per NPC. In fact you should steer clear of threads altogether. They're far too easy to get wrong. The system you describe sounds like it would become a nightmare to manage, with contention over shared data, the potential for deadlocks, etc. Just say no.

Your typical MUD will have a traditional heartbeat/pulse system: you have an update loop that runs several times a second, and every X updates (ie. every few seconds, typically), you update all NPCs. It's that simple. A more flexible system if you want updates at different periods is to have a priority queue of future updates. When you create an NPC, place an 'update me' message on the priority queue scheduled for X seconds in the future. During your periodic update you pull anything off the queue that is scheduled to execute now, check the NPC is refers to is still around, and then do it. In the case of NPC AI, this will typically do your AI and then schedule the next update.

Quote: The XML I posted I just pulled out of the air. I'll likely have more states than combat an not, such as bartering for shop keepers, or reactions to pick pocketing.

Pulled out of the air or not, it's important to enumerate all these. Going from combat to non-combat is as simple as checking to see if anybody's fighting you. But how do you check for a bartering state? And when does an NPC know to stop reacting to pick-pocketing? What if a street urchin picks your pocket while you're battling a greater demon? You need a clear system for deciding and initiating state changes.

Quote: The tag change you pointed out is definitely a good idea, especially since I declare commands in XML as well. If I go to the more general "action" tag, what do I do about parameters? Perhaps I'll just stick them on the action tag as attributes just the same?

Yes, that is what I'd do.

Quote: If I do that, though, is there any sense in putting the "attack" in the body of the element, rather than just as another attribute?

No. In 99% of cases, you don't need anything inside the XML tags when using them for plain data exchange. This is another reason why XML is a bit of a crap data format, but hey, it works.

Quote: I just want them to attack those they are hostile toward, present a few personality traits (emotes and sayings), serve as shop keepers, and be able to respond to simple questions by picking out key words.

Ok, but you'll be best served by splitting these out into separate systems rather than combining them under 'AI'. Most shopkeepers handle shopping as instantaneous actions, for example, so that can stand totally separately. Just put a check in to see if they're too busy to answer a buyer/seller's request and you're done, for the most part. The same could arguably be said for keyword conversations.

Hostility towards characters is an interesting one. Most old MUDs just had an 'AGGRESSIVE' flag stating they'd be aggressive towards anybody. That may suffice, but you might want to extend it somewhat. You might have a 0-100 score instead where 0 means they will never initiate combat, and 1-100 are various degrees of aggression, 1 meaning they will only fight you if they are almost certainly guaranteed to win, and 100 meaning they will fight you no matter what.

You might also want to implement some sort of memory where NPCs remember previous PCs that attacked them, and are hostile to them automatically.

Other nice ideas could revolve around concepts like territory and hunger. Some creatures may wander, but might only be aggressive if near their home, or if they have children to protect. Other creatures may kill only to eat, and without going the whole way to modelling an ecology, you could make them only aggressive at certain times of day for example to simulate this.

Quote: Perhaps I'll just have a handful of personality types, and I will modify some base reaction types from there? For example, there might be a cowardly creature type, which will increase its retreat thresholds by 30% when the monster reaches 40% health, rather than 20%. The 30% will be applied to retreat, and the other values will be adjusted equally to bring the totals to 100%.

It sounds reasonable. But perhaps it's worth abandoning the explicit percentages and instead just treat it as a weighted system. Then you don't have to worry about making everything add up to 100 each time. You can temporarily double or half the chance of a certain activity based on some event without needing to rebalance the whole set of things.

Quote: Perhaps all attacks will be lumped together under a root "attack" node, having a parent probability for simply attacking, and the children with have a probability set of their own for which attack to execute. This would allow me to adjust the retreat and attack ratios on a general basis, regardless of the number of attacks the creature has available to it.

This also sounds reasonable. It becomes easier if each system in itself has simple rules to decide whether it's off or on, and let sub-systems handle the details. Trying to balance many different concerns at once is awkward.

Quote:
Your typical MUD will have a traditional heartbeat/pulse system: you have an update loop that runs several times a second, and every X updates (ie. every few seconds, typically), you update all NPCs.

I'm not sure how this is different from what I had suggested.

Quote:
A more flexible system if you want updates at different periods is to have a priority queue of future updates. When you create an NPC, place an 'update me' message on the priority queue scheduled for X seconds in the future. During your periodic update you pull anything off the queue that is scheduled to execute now, check the NPC is refers to is still around, and then do it. In the case of NPC AI, this will typically do your AI and then schedule the next update.

I like this, it seems more efficient as I'm not looking at every NPC object multiple times per second. Would I have to store the list of pending actions by execution time? Does a particular data object lend itself to this? Maybe I'll just have to write my own self-sorting dictionary.

Quote:
Ok, but you'll be best served by splitting these out into separate systems rather than combining them under 'AI'. Most shopkeepers handle shopping as instantaneous actions, for example, so that can stand totally separately. Just put a check in to see if they're too busy to answer a buyer/seller's request and you're done, for the most part. The same could arguably be said for keyword conversations.

So things like emotes, movement, and combat would be handled using a "real time" update scheme, but others will be strictly event based? That sounds good to me.

Quote:
Hostility towards characters is an interesting one. Most old MUDs just had an 'AGGRESSIVE' flag stating they'd be aggressive towards anybody. That may suffice, but you might want to extend it somewhat. You might have a 0-100 score instead where 0 means they will never initiate combat, and 1-100 are various degrees of aggression, 1 meaning they will only fight you if they are almost certainly guaranteed to win, and 100 meaning they will fight you no matter what.

You might also want to implement some sort of memory where NPCs remember previous PCs that attacked them, and are hostile to them automatically.

Other nice ideas could revolve around concepts like territory and hunger. Some creatures may wander, but might only be aggressive if near their home, or if they have children to protect. Other creatures may kill only to eat, and without going the whole way to modelling an ecology, you could make them only aggressive at certain times of day for example to simulate this.

There are some really interesting concepts here. I particularly like that aggressiveness factor idea. I had considered tracking NPC hostility, but for mobs I don't think it's worth it, and I'm not sure I'll even allow the player to attack the friendly NPCs. It's a good feature to have, but it may be beyond my intended scope. We'll see.

Quote:
It sounds reasonable. But perhaps it's worth abandoning the explicit percentages and instead just treat it as a weighted system. Then you don't have to worry about making everything add up to 100 each time. You can temporarily double or half the chance of a certain activity based on some event without needing to rebalance the whole set of things.

So if they were weighted values, to determine their probability I would just divide by the sum of all values? So if the monster had a value of 60 for attack, 20 for retreat, and 40 for support, it would have a 50% (60/120) chance to attack, a 16% (20/120) chance to retreat, and a 33% (40/120) chance to use a support ability? Then when the monster reaches its "threshold", bump its retreat factor up to 60, moving its retreat percentage up and everything else down automatically. I like that.

Thanks, Kylotan. This really helps.

Quote: Original post by CyberSlag5k

Quote:
Your typical MUD will have a traditional heartbeat/pulse system: you have an update loop that runs several times a second, and every X updates (ie. every few seconds, typically), you update all NPCs.

I'm not sure how this is different from what I had suggested.

"Maybe I'll have one thread that maintains all NPCs": that differs in requiring a separate thread, or at least implying its existence. The typical MUD is a single process, single-threaded program. NPC updates, networking, input handling, etc, all happens sequentially.

Quote: I like this, it seems more efficient as I'm not looking at every NPC object multiple times per second. Would I have to store the list of pending actions by execution time? Does a particular data object lend itself to this? Maybe I'll just have to write my own self-sorting dictionary.

Store them how you like, really. The typical implementation is a priority queue, which is usually implemented as a binary heap. Any more specific advice will depend on the language you're using. In C++ I'd probably just perform a sorted insert into a std::deque and optimise later if needed. (Why not a std::priority_queue? Because you can't iterate over them.)

Quote: I had considered tracking NPC hostility, but for mobs I don't think it's worth it, and I'm not sure I'll even allow the player to attack the friendly NPCs.

Fair enough, just bear in mind that most MUDs have had the ability for an NPC to remember its PC enemies for well over a decade now. I don't know if you're trying to compete on features or not, so I just thought I'd point that out.

Quote: So if they were weighted values, to determine their probability I would just divide by the sum of all values?

Exactly.

Quote: The typical MUD is a single process, single-threaded program. NPC updates, networking, input handling, etc, all happens sequentially.

Ah, I see. Why is it better to perform everything in sequence? My server will be running on a dual-core box, so I thought that putting significant amounts of work on different thread would lead to faster response time.

Quote: Original post by CyberSlag5k

Quote: The typical MUD is a single process, single-threaded program. NPC updates, networking, input handling, etc, all happens sequentially.

Ah, I see. Why is it better to perform everything in sequence? My server will be running on a dual-core box, so I thought that putting significant amounts of work on different thread would lead to faster response time.

I would guess it's because the code would be much easier to write, debug and maintain. But if you have experience with multi-threaded programs, locking and semaphores and such, go for it.

Yes, because writing correct multi-threaded code is actually really difficult, especially in languages like C++ that have no real support for it.

But anyway, the chance of you maxing out even one core with the requirements of a typical MUD are something like 1%, so trying to optimise for speed and concurrency is just overkill. It wasn't all that long ago that Realms of Despair was handling 400 concurrent users on a Cyrix 300MHz machine, for example.