Non-Player Character AI in RPG Elements

     One of the most important parts of my RPG game engine is non-playable characters, also known as NPCs. Interacting with these characters is one of the most important parts of the game, and the more realistic these characters behave the more believable the virtual world becomes.

     I want to design a system for describing behavior that is at first simplistic but can gracefully extend to include more advanced behaviors. Initially I want to be able to describe a behavior of a couple random or sequential actions. For example, a character that paces around randomly and then occasionally jumps. Designing a system to handle this simple behavior is trivial, but it may not extend well when I want to implement more complicated behaviors. For example, I want to eventually add tasks and goal oriented actions. These actions will not describe a sequence of individual actions but require the character to choose a sequence of actions to achieve a described goal.

     I plan to solve this by using having an action queue. The queue is populated with the current action and the next actions the character plans to preform. Some actions correspond directly to an atomic physical action like preforming an animation or moving. Other actions are made up of many atomic actions generated dynamically. When the first action in a characters queue is one of these more complicated actions it break this action down into its atomic actions. So the solution is a queue of actions where an action can be an atomic action or a more abstract complex action.

     I have so far come up with a four types of complex actions. The first is a simple sequence of actions the character preforms in order. The second is a weighted set of actions preformed in a random order with preferences to a particular action based on the weights. The third is a goal oriented action were all that is described is a goal and the character must generate a set of atomic actions that will allow it to complete the goal, it must also re-evaluate its decision at each step to consider changes in the world that invalidate the plan. The last type of action is a utility oriented action, this type of action is the most abstract since it only specifies some need that they character must satisfy, such as satisfying its hunger, and this action can be composed of many goal-oriented actions.

     Each one of these action types gets progressively more abstract and requires the character, rather than the game designed, to do more of the decision making. Well it is possible for the character to have complete information about the world this would not be the most realistic. A possible extension I have thought about for this system is to have the character build up its own model of the world which includes imperfect and erroneous information about the world. Characters would then benefit by interacting with each other to learn and complete goals. While this would be an interesting experiential I anticipate that this feature is still a long way off.

     In the meantime I have implemented the first parts of this description in my game engine. I have atomic actions, sequences and weighted sets working. Since each level of action gets progressively more abstract it is necessary to describe some lower level actions before the higher level ones can use them.

     In the near future I intend to start writing some goal oriented actions, specifically related to moving a character from one map to another. I talked about how I am able to build a graph of my maps based their connections. My characters will plan a route from a point on one map to a point on another map first by calculating a least cost path through this map graph, then as they arrive at each map they will calculate a path from the entrance door to the exit door, making this a two tiered search technique. There is one issue I still need to resolve, currently the map graph does not show which doors in a map are unreachable from other doors. If a character plans to enter a map through one door and exit through another but there is no way to reach the exit door the search algorithm will fail. This problem is made more complicated by the fact that objects in the world could possibly move and block the path after it has planned its route.

The diagram shows that a character can not simply find a solution by considering what maps are connected, it must also know what connections are reachable from each other

     There is one other component of NPC behavior that I plan to implement, which is how the player interacts with the them. In some of the original RPG games NPCs would respond with a single message every time the player talked to them. This style has persisted in many newer games but a few recent games, like those in the elders scrolls series, have come up with much better ways of handling these interactions. In games like Morrowind, the player is presented with a list of questions that they can ask an NPC, and the NPCs responses vary based on how much they like the player. This may seem like a large amount of dialogue that the designer must write but much of it is shared between characters. Some conversation topics are global, which means every NPC can be asked this topic and gives the same response, the responses can then be customized based on the attributes of the NPC and the topic can be qualified to be only ask-able of specific NPCs. My plan is to implement a conversation system that is similar to this but I also hope to develop ways of generating some simple conversation topics to reduce the amount of work required by the designer. Another problem I realize with this system is that eventually the list of topics will grow to be large, and I will eventually need to develop a way to search it quickly and intuitively.

     I believe that NPC behavior and interaction will be one of the most interesting features going forward with my project. I also believe it will be a very challenging process with the potential for many exciting innovations. Despite the challenge, I am confident that by simulating more realistic NPCs my virtual worlds will seem more alive.