Adapting Pathfinding with Potential Energy

Introduction

Virtual or animated characters in computer games have been around for nearly as long as computer games themselves. They are more commonly known as non-player characters (NPCs) or computer controlled characters and are typically the most visible manifestation of game artificial intelligence (AI). The term “game AI” is used to refer to many aspects of a computer game, such as decision making, path-finding, collision detection, animation systems and audio cues. Game AI can be organized according to a number of different tasks, namely low-level movement, decision making, tactical decision making and strategic decision making (Millington & Funge, 2009; Thurau, 2006; Tozour, 2002a).

The most essential requirement of an NPC is to move through the game environment. Early computer games primarily made use of only movement algorithms and had very little, if any, high-level decision making abilities; for instance, the first arcade videogame to include an animated computer opponent was 1974’s Shark Jaws (Byl, 2004). In this game the NPC took the form of a shark which preyed on the human player’s avatar, a scuba diver, by swimming directly towards it. In addition to limited high-level decision making, many early games took place in small and relatively simple environments that were designed specifically for their zombie-like NPC inhabitants. For example, the Pac-man game world had no dead ends, so the movement decisions of the ghosts only needed to be taken when they reached a junction. As computer games have increased in complexity and changed from 2D to 3D environments a need for more sophisticated abilities has developed. NPCs in today’s computer games should not get trapped behind in-game objects such as vehicles or buildings; they should take terrain into account and take suitable routes to desired locations.

NPC behavior in modern commercial computer games is frequently achieved through a combination of fundamental techniques: movement algorithms, finite state machines (FSMs), pre-programmed scripts and pathfinding. These techniques have produced remarkable character behavior; however, they all need to be programmed to include every situation an NPC may encounter. They lack the ability to adapt and generalize to unforeseen situations; this means that they tend to produce lifeless characters that are prone to repetitive and predictable behavior. Furthermore, this results in diminished enjoyment for the human player as they are able to exploit repetitive behavior, poor decision making and NPC errors to achieve game objectives. If games are to maintain high-levels of entertainment for the human player they need overcome these deficiencies through NPCs that are more believable and responsive to the player.

The work presented in this chapter pursues approaches to enhancing NPC behavior in computer games that will produce characters that are more believable, challenging and responsive to the human player. This aim can be achieved in a variety of ways, such as through offline learning (Funge, 2004). Offline learning occurs before a game is release or while a game is not being played. It can produce more believable behavior for NPCs; however, it still encounters similar limitations to current FSM and scripting techniques. This is illustrated by McGlinchey (2003), who states that humans may act differently in identical situations, but his offline learning system is always completely deterministic. In addition, Laird (2001) found that games developers were impressed by his offline behavior modeling system, but would invariably ask, “Does it anticipate the human player’s actions?” (Laird, 2001). Consequently, NPCs that learn offline are susceptible to repetitive behavior and are not responsive to the human player’s actions.