Pathfinding

Pathfinding algorithms are a family of algorithms that aim to find an efficient path between two points, avoiding obstacles along the way. They are used to make AIs navigate around game levels, although not exclusively: GPS services also use these algorithms to find efficient routes to your destination.

Godot provides the most widely used pathfinding algorithm in games and many other domains: AStar. It's a flexible and efficient algorithm that's excellent at finding the optimal path between two points.

The engine both provides it as a class you can use to build and traverse your maps manually and uses it as part of its navigation system, which finds efficient geometric paths on navigation meshes.

Pathfinding uses in games

In games, we use pathfinding algorithms to make AIs navigate around complex game worlds. For example:

• In strategy games, units find the shortest path to a target location, accounting for paths blocked by obstacles.
• In RPG games, NPCs find their way to the player or to quest locations.
• In point-and-click adventure games, the player moves their character around the game world by clicking on the screen.
• In simulation games, vehicles drive automatically around the game world.

Pathfinding tools in Godot

As mentioned above, Godot uses the AStar algorithm for pathfinding. The engine provides two classes to use it directly:

• AStar2D for 2D games. It's particularly useful for grid-based games, regardless of the grid type (square, hexagonal, etc.).
• AStar3D for 3D games. Similarly, it's useful for grid-based games.

The engine also provides a more advanced pathfinding system called "navigation" that uses AStar internally:

• The NavigationRegion2DNavigationRegion2D and NavigationRegion3DNavigationRegion3D nodes define regions of your game levels where you want to allow AI navigation.
• The NavigationAgent2DNavigationAgent2D and NavigationAgent3DNavigationAgent3D nodes define the properties of the AI that will navigate the regions.

These nodes allow AI-controlled entities called "agents" to find the shortest path between two points in the navigation regions. They can also avoid obstacles and other agents almost automatically. It's a powerful system with many features and settings.