Adapting Pathfinding with Potential Energy

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.