Image Courtesy of Dan Vavra (http://games.tiscali.cz/tema/umela-inteligence-ve-hrach-1-zapomente-na-inteligenci-56421)
In our recent GAM111 class, we have been implementing pathfinding systems into our first-person shooter in-class project. The first person shooter we have made uses basic enemies which will approach the player and attack them, similar to games such as Dead Rising (Capcom, 2006). pathfinding – the ability for computer agents to navigate a 3D space – is a complicated undertaking in which AI agents must account for obstacles and find a suitable path to reach their destination. Most modern games take pathfinding to an extreme, implementing complicated cover systems and movement dynamics in order to challenge their players. There are two types of pathfinding systems that are most prevalent in the industry: Node-based and Navigation Mesh-based systems.
Spatial graph pathfinding is the oldest and most obsolete method of pathfinding in games. Spatial graph pathfinding relies on a network of points for which the agent can navigate through, like a spider traversing its web. Like almost all pathfinding algorithms, spatial graph pathfinding uses the A* algorithm (pronounced “A-Star”) algorithm, a heuristic means of calculating the fastest path to a destination. The algorithm will spread itself out over the spatial graphs until one hits the destination. Games such as Oblivion (Bethesda, 2007), Bioshock: Infinite (Irrational Games, 2013) and The Bureau: XCOM Declassified (2K Games, 2013) all used spatial graph pathfinding solutions for their artificial intelligence. While popular, spatial graphs can impose navigation issues depending on their implementation. Spatial-graph paths normally make it difficult for agents to navigate realistically, if the network of paths isn’t completely straight. In Paul Tozour’s example (below), an agent which is navigating along a branch in the network will adhere exclusively to that branch, sometimes zig-zagging from node-to-node on the way to its destination. Additionally, basic implementations of spatial graph pathfinding don’t support path correction around obstacles. As before, these issues depend on the implementation. Bioshock: Infinite used a combination of navigation meshes and spatial graphs. The spatial graphs support the basic movement, and the navigation meshes allowed for path correction.
Navigation meshes are the most prevalent pathfinding systems in games. A navigation mesh – contrasted to a spatial graph implementation – is an entire mesh which an agent can move within. NavMeshes support a more natural area of movement and enable more realistic pathfinding solutions. A NavMesh will calculate the area of walkable terrain that the agent supports, and will divide it into a series of polygons. Comparatively, spatial graph meshes and navigation meshes use the same amounts of computing overhead and memory, and as such are a good choices for artificial intelligence solutions. As is the case with Bioshock: Infinite, the two methods can be combined, but for the ability to place cover/interaction points for agents to use(below).
Despite the benefits, there will never be a perfect pathfinding solution. Sophisticated artificial intelligence must always balance realism and resource overhead meaning there will always be compromises. Navigation meshes present the most versatile solution to pathfinding, particularly as games such as Halo 2 & 3, the Metroid Prime trilogy, and the Jak and Daxter trilogy all rely on navigation meshes to great effect. On the other hand, 2D games may benefit from a spatial graph implementation. When building systems for artificial intelligence, developers must ask themselves what the best method for their implementation of artificial intelligence is, how realistic their simulations need to be, and how their AI solutions will utilise them.
Irrational Games (2014). Bioshock: Infinite [Computer Software]. Massachusetts, USA
Capcom (2006). Dead Rising [Computer Software]. Osaka, Japan
2K (2013). The Bureau: XCOM Declassified [Computer Software]. Canberra, Australia
Pinter, M. (2005). Gamasutra – Toward More Realistic Pathfinding. Gamasutra.com. Retrieved 4 July 2016, from http://www.gamasutra.com/view/feature/131505/toward_more_realistic_pathfinding.php?print=1
Tozour, P. (2008). Fixing Pathfinding Once and For All. ai-blog.net. Retrieved 14 July 2016, from https://web.archive.org/web/20150816054029/http://www.ai-blog.net/archives/000152.html