Adapting Pathfinding with Potential Energy

Adapting Pathfinding with Potential Energy

Thomas Hartley (University of Wolverhampton, UK)
DOI: 10.4018/978-1-4666-1634-9.ch002


Movement through a computer game environment is an essential requirement of non-player characters (NPCs) in today’s computer games. Local movement is typically reactive and based on the current state of the game and the NPC. Long-range movement is concerned with determining a short and appropriate route from one location in the game environment to another. A desired destination is typically not known in advance. Therefore, techniques are needed to determine a route while a game is being played. This problem is known as pathfinding or path planning. Traditionally, pathfinding systems have focused on determining the shortest path between locations; however, many computer games are beginning to incorporate terrain and strategic reasoning (also known as tactical location analysis) into the pathfinding process. This chapter describes an approach to strategic and tactical pathfinding that learns in-game from an NPC’s experience of executing previously generated paths. The experience is used to adapt future pathfinding and therefore allows NPCs to avoid (or be attracted to) areas of the game world. Hence NPCs can improve their chance of success and encourage the human player to adapt their behavior.
Chapter Preview


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.

Complete Chapter List

Search this Book: