Pathfinding and Boids

Michael Holm

One of the core elements of any game is the AI system, the simulation of intelligence. And one of the core systems of any AI system is the ability of a 'Non Player Character' - a NPC to find its way on a game level. The pathfinder needs to find the 'optimal' path from one location to another in a 3D world, and needs to do that fast.

A Playstation2 running at 60 frames pr. sec. has around 5Mhz processing power for each frame, in which it needs to run a full cycle of any of the processes needed to simulate a seemingly living game world, from NPCs evaluating scripts, to audio subsystems, bullet collisions, player/world collision, light simulation, character skeleton deformation and rendering. And one small part of all that is path finding.

Therefore a pathfinder has to be very efficient, and find a path from any point in a 3D world to any other point, in as few clock cycles as possible. We have implemented a pathfinder that'll do that in as few as an average 100.000 cycles on a PC, and will give a short introduction to the principles and optimization involved in achieving this goal.

Once a path has been found, a NPC starts walking the planned path, and will, in most games, do that very directly. Most NPCs will walk on the path, following it exactly as it's layed out. This creates problems, if two or more NPCs are following the same path, possibly in opposite directions, where they will overlap in space, with little or no regards to other NPCs on the level. This makes NPCs look blind and dumb, and can have a heavy impact on the game-experience, for the player. A Boid is an entity that will try to detect intersections with other boids, and avoid them in a seemingly intelligent way. Each NPC has been given a cane, with which he probes the world around him, detects intersections and tries to respond naturally to the environment.