architecture - How to manage all the NPC/AI objects on the server?

I'm writing a simple MMO, and currently have the the server-client architecture in place for multiple users to see each other and be able to move around together...now its time to add enemies.

Was wondering if anyone had links to articles that discussed how to best handle the hundreds of NPC objects that need to be managed in the world. I've done some searching and couldn't find much info about how this is typically done.

The two methods of structuring the implementation I can think of:

1. Holding all the instantiated NPC objects in a list, and having an NPC Thread loop through them sequentially and see if each has any logic that needs to be processed and perform necessary actions. I'm not sure if the performance of this design would be sufficient?


2. Event based system. Create a method in the NPC class that processes AI/Logic on it, have this method be called when an associated event is signaled, either on a timer for non interacted AI functionality (such as wandering), or signal the event externally from the packet handler (player moving nearby, or player attacking within range).

Is either of these approaches the correct way? What other methods of doing this exist?

Answer

As always, architecture depends on your requirements. How many mobs are you going to have? How complex is their AI? What does it react to? How often does it change its state? Answer these questions, and you'll have a much better understanding of what you want and how to get that.

Generally, you'd want to have at least some kind of event system. AI is usually defined in terms of events: "When A happens, do B"; and if you don't have events in actual code, you'd have to somehow translate these definitions.

In my experience, you can get away with a simple loop implementation when you have few and really simple mobs (contrary to what the other answer seems to suggest). For example, in our current game we have hundreds of small instances with each having 10 mobs at most. And these mobs are dead-stupid; AI of 99% of them can be described in one sentence: "Am I attacking anyone? If not, attack closest player." In this case a simple loop is more than enough - twice a second we check for a new target (and a few other things for the rare "smart" mobs), and that does it.

However, when you have more and/or smarter mobs, naive approach stops working. For AI to react to some stimulus, you'd have to write code that detects it inside your AI loop. For example: suppose your mob should do something "when hit by a player". With a loop approach, there's no easy way to determine the mob was hit. When the AI is running, you can check that mob's health diminished since last tick, or that the mob is currently targeted by someone. But you cannot detect actual hits without resorting to hacks, like saving each hit info somewhere for AI to access it later.

Secondly, a naive loop always runs, no matter what happens. When you have lots of mobs, you want the AI to run as fast as possible.. and the fastest code is the code that never runs at all. If you have mobs that are not active, you want them to not run AI, or only run it sporadically (as in, wandering mob AI should only run when it decides where to go next).

With event-based approach, you can have you other subsystems send AI events whenever convenient, eliminating problem of "detecting hits". Of course, some events would still require detecting code: most notorious example is the "approach" event. And when you don't run your AI routine in a loop when nothing happens, you gain performance.

You can also use a hybrid approach. Instead of handling AI events immediately, you can stuff them into some kind of queue. Then, when AI routine runs (in a loop), it removes events from this queue and handles them one by one. With this architecture, AI performance might be a bit slower, but it is more predictable; also, you can guarantee that all AI runs on a single thread (which might be tricky otherwise). This kind of loop can also be easily throttled by skipping some events (for example, each AI iteration only handles three most recent events, discarding the rest). Or events might be prioritized, and less-important ones discarded if AI is found to be lagging.

Overall, the "loop with events queue" approach is probably the most flexible. But I want to reiterate: don't just choose it blindly as "the best". Think about your requirements first, and some simpler approach may turn out to be better.