Copy LinkCopied!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 only: GPS services also use these algorithms to find an efficient route 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 really good 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.

Copy LinkCopied!Pathfinding uses in games

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

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

Copy LinkCopied!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. There again, it's useful for grid-based games.

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

• The NavigationRegion2D and NavigationRegion3D nodes are used to define regions of your game levels where you want to allow AI navigation.
• The NavigationAgent2D and NavigationAgent3D nodes are used to define the properties of the AI that will navigate the regions.

These nodes allow AI-controlled entities named "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.