With the rise and success of digital games over the past few decades, path planning algorithms have become an important aspect in modern game development for all types of genres. Indirectly-controlled playable characters as well as non-player characters have to find their way through the game's environment to reach their goal destinations. Modern gaming hardware and new algorithms enable the simulation of large crowds with thousands of individual characters. Still, the task of generating feasible and believable paths in a time- and storage-efficient way is a big challenge in this emerging and exciting research field. In this chapter, the authors describe classical algorithms and data structures, as well as recent approaches that enable the simulation of new and immersive features related to path planning and crowd simulation in modern games. The authors discuss the pros and cons of such algorithms, give an overview of current research questions and show why graph-based methods will soon be replaced by novel approaches that work on a surface-based representation of the environment.
TopIntroduction
Over the past decade, educational games have received increasing attention. By now, a large body of research has been carried out to determine how the principles behind engaging digital games can be utilized to improve learning. In general, this is an open research question with new methods still being developed, e.g. (Jeuring, van Rooij, & Pronost, 2014). It has been shown for particular cases that engaging virtual environments can yield a higher motivation and better learning results for students (Murray, Bogost, Mateas, & Nitsche, 2006; Ketelhut, Dede, Clarke, Nelson, & Bowman, 2007; Ketelhut, 2007; Gee, 2007; Schmitz, Specht, & Klemke, 2012).
A key requirement to achieve a high level of engagement and thus better learning results is the game being immersive. Immersion can be achieved in many ways, among which are the technological aspects of a game. Modern computer hardware and smarter algorithms have radically changed and shaped the overall appearance of digital games in general and educational games in particular. Technological aspects of games such as graphics, modeling or physics simulation have received much attention, and this led to a wide range of novel techniques to generate visually convincing and believable pictures, character models, and animations.
By contrast, the paths traversed by virtual characters1 are often not visually convincing. Many educational games do not let their virtual characters move around autonomously. This is due to the fact that moving characters might not be necessary to achieve the learning goals. Furthermore, the computation of realistic and visually convincing paths is difficult and might even ruin a user’s immersion when done in a cheap way. However, many educational games try to simulate a realistic virtual 3D environment to better match recent advances in entertainment games. An example of such a game is The River City Project (2002 - 2007). The game has been successfully used by teachers and students in the U.S., and results indicate that using virtual environments in education “might act as a catalyst for change in student’s self-efficacy and learning processes” (Ketelhut, 2007). The River City Project simulates a virtual city from the late 19th century with buildings and different terrain, and the residents of the city are displayed as virtual 3D non-player characters. These, however, seem stationary and do not autonomously move around the city in a realistic way. We believe that state-of-the-art path planning and crowd simulation methods can improve such games with respect to the users’ immersion and overall learning experiences.
Many games that do support moving characters rely on predetermined or scripted paths. In such games, a designer can manually create believable paths that are of high quality. While this does not ruin a user’s immersion, it also limits the flexibility and design possibilities of a game. By contrast, games that are more flexible and allow unpredictable interactions among characters rely on algorithms to handle path planning.
In this chapter, we will discuss such algorithms. We focus on path planning for single virtual characters and large virtual crowds. The latter have become increasingly important in simulation software for mass events and evacuation training, e.g. (SportEvac, 2014), which could be used in school education to increase the students’ awareness of potential dangers during such events.
The overall goal in this research field is to compute visually convincing and natural paths for a large number of characters in real-time to improve the user’s immersion. We will discuss how this field and the methods used have changed over the past few decades, and give an overview of state-of-the-art techniques and open research problems.
We will start with discussing different ways to represent traversable space in a virtual environment. A classical approach is to use a grid or waypoint-graph representation. Path planning is then done using a graph-based search algorithm. We will explain why a graph representation is not adequate for many challenging path planning and crowd simulation problems.