Just about every game has Non-Player Characters, from the aliens in Galaga to the government agents in Half-Life. As game technology has progressed, players have expected more and more intelligent NPC's.

One of the newer technologies to garner interest has been the automaton approach, in which NPC's are treated as free, functioning (but still somewhat limited) individuals within their own environment. They have goals and resources, and set about ways to achieve those goals. Interactions can be managed using a messaging system (e.g., an NPC wants to buy some food, and sends a "buy food" request to a shopkeeper. When the shopkeeper next gets updated, s/he processes the request and sends a response to NPC1). This sounds wonderful; a fairly small amount of programming should result in lots of NPC's wandering around, doing their own thing.

Unfortunately, there is one major flaw in this concept: processing time. If each NPC is basically a computer-controlled player and is updated in real time, a mere dozen or so could easily drag on the system to the point of making the game unplayable for that lone human player. If they're not updated in real time, NPC's will react in extreme slow motion.

So the issue with automaton NPC's is one of management. Is there a way to control numerous NPC's, without requiring unnecessary drag on the system? I believe so.

Let's look at the various ways in which the game can update the status of NPC's.

1. Update the NPCs in rotation.

This creates a "slow motion" effect, though, as it would often take long periods of time for two NPCs to interact. Example: NPC1 sends a "cost" request to NPC2; NPC2 sends a "price" response to NPC1; NPC1 sends a "buy-for-X" message to NPC2; NPC2 updates its inventory and sends a "here's-your-item" message to NPC1; NPC1 updates its inventory. Thus, a simple 5-second business transaction drags out into a 5-stage process!

The only way to expedite this is to make the game cheat a little. Thus, if the NPC wants to move, let the NPC move in 20-foot steps. Unfortunately, these steps would have to be calibrated just right, and would generate silly results on machines with different processing power.

2. Divide the NPCs up into two groups; some are to be updated, others are not.

This has two drawbacks: 1) more work is required to classify all of the NPCs, and 2) it will seem strange to the player that some NPCs are blocks of wood while others have a high degree of interaction. The disparity obviously wouldn't be that drastic at first glance, but it would still be jarring.

This is workable, however.

3. Write the NPCs such that they don't have to be visibly updated. E.g., NPCs can't move.

However, this would restrict the NPCs so drastically that the game would have to cheat to let them do anything worthwhile, and this defeats the purpose of creating "smart" NPCs.

4. Only update NPCs that are close to the player.

This creates a disparity when the player visits an NPC, leaves, travels all over the map, then comes back much later to find out that the NPC hasn't done much at all even though a lot of time has passed. This might be acceptable with a refinement, though:

4a. Update NPC's with a frequency based on their distance from the player.

NPCs close to the player are updated frequently, whereas NPCs farther from the player are updated less frequently, but are allowed to cheat somewhat. The results would be imprecise, but seems to me to be the best of all possible worlds.

Of course, we still have to figure out exactly how we're going to structure a game so that the NPC's have their freedom. But that's worth another article at least....