How do I change the pathfinding algorithm of a Navigationagent (2d in my case but 3d as well)?

[starck]

Godot Version

V 4.7.2

Question

Hello ! I’m trying to make a pathfinding algorithm on the principle of A* but that would work for car (so instead of rotating on itself, the object would turn like a car) which I think I have somewhat nailed.

But I don’t understand how to change the pathfinding algorithm in the navigation Agent and I can’t find any help on how to do that anywhere (maybe I’m a bad looker, but I’ve looked at countless Youtube videos, Reddit post and forum posts and none answer my question).

i’ve tried pocking around the NavigationPathQuerryParameters but

Thank you for your help!

[Marabo]

Although NavigationAgent2D and NavigationAgent3D use an A* algorithm internally for pathfinding, the built-in godot classes AStar2D and AStar3D are their own separate thing. I use AStar3D to navigate through doors between rooms, but you can use it to navigate through any points you decide to set up in your AStar2D.
My drone has no NavigationAgent3D node, and pathfinds entirely using godot’s built-in AStar3D and my drone’s physics-based movement function. I believe it should work with your car.

1. When the level is generated, it creates a AStar3D inside the level script and populates the points and connections according to the rooms and doors in the level. The only points it needs are the doors in each Area3D room, which I named NavNodes and placed manually in the editor, but you can use whatever you need instead, for example a series of points along a race track, or a grid of points on the floor.

class_name Level
extends Node3D

var nav_astar:AStar3D
var nav_nodes:Array[NavNode]
var areas:Array[Area3D]

func _build_nav(nav:Node) -> AStar3D:
	var astar:= AStar3D.new()
	
	for child in nav.get_children():
		if child is NavNode:
			nav_nodes.append(child)
		if child is Area3D:
			areas.append(child)
	
	for i in nav_nodes.size():
		var nav_node:NavNode = nav_nodes[i]
		
		astar.add_point(i, nav_node.global_position)
		
	for i in nav_nodes.size():
		for j in range(i + 1, nav_nodes.size()):
			var node_a:NavNode = nav_nodes[i]
			var node_b:NavNode = nav_nodes[j]
			
			if _nav_nodes_share_area(node_a, node_b):
				astar.connect_points(i, j)
	
	return astar

2. When the drone enters a state that requires it to move to another room, it builds a path using the level’s AStar3D, according to the starting area it’s in and the destination area, and stores it in path: PackedVector3Array. Its current path point is stored in path_index: int

var path: PackedVector3Array
var path_index: int = 0

func _build_path(destination_area:NavArea, starting_area:NavArea) -> void:
	var start_id := _get_closest_connection(starting_area, global_position)
	var destination_id := _get_closest_destination(start_id, destination_area)

	path = GameState.level.nav_astar.get_point_path(start_id, destination_id)
	path_index = 0

In your case, you could simply use the point in the AStar2D that is closest to your car as the starting point with AStar2D.get_closest_point(), and then find the point that is closest to your destination in the same way.

3. The drone tries to approach the first point in the path it built. It does so using it’s physics-based movement method. All the method does is apply a force on the drone’s RigidBody3D to move it in that direction until it’s close enough. Since it has inertia, it can end up moving in a curve-like motion, or overshoot it’s target, then corrects itself.
   Use whatever movement is appropriate for your car, e.g.: accelerate forwards, and apply a force to make your car turn in the direction of the point

func _move_toward(target: Vector3, _delta: float) -> void:
	var direction: Vector3 = global_position.direction_to(target)

	if direction.length_squared() < 0.001:
		return

	# Desired velocity
	var target_velocity :Vector3 = direction * max_speed

	# Difference between desired and current velocity
	var velocity_difference :Vector3 = target_velocity - linear_velocity
	
	# Only accelerate if below desired velocity
	var force :Vector3 = velocity_difference * move_force

	apply_central_force(force)

4. When it eventually arrives close enough to the point, it increments path_index by 1 and sets its new movement target as the next point in the path:

		var target:Vector3 = npc.path[npc.path_index]

		npc._move_toward(target, delta)

		if npc.global_position.distance_squared_to(target) < 0.25:
			npc.path_index += 1

This continues until the drone reaches the last point in the path, in which case it goes back to being idle and starts wandering freely in the new area.

		if npc.path_index >= npc.path.size():
			npc.wander_zone = GameState.level.get_area_at_position(npc.global_position)
			npc.state_machine.change_state("idle")
			return

Change this logic to whatever fits the need of your car AI.
e.g.: if your car is trying to reach the player, when the car reaches the last point in the path and the player was not in range, build a new path to the player and start moving along the path.

[starck]

Thank you for your reply, it helps a lot !

sorry for the slow reply, I wanted to really understand your reply. I’ll try to discard navAgent, although it’s a new can of worm I have to open, I’m sure I’ll get better results =) but I’m surprised that you can’t change the pathfinding algorithm considering there is a drop down menu (that gives the very helpful single option to use A*) in the inspector :

there’s also a PATHFINDING ALGORITHM enum in the NavigationPathQueryParameters2D class NavigationPathQueryParameters2D — Godot Engine (stable) documentation in English

Maybe it was a projet that got discarded ¯\_(ツ)_/¯

[Marabo]

I’m sorry if my answer was confusing. I forgot about that drop-down selection and I thought you were trying to use AStar2D alongside NavigationAgent. Even though there’s a drop-down selection, it uses an A* algorithm by default and can’t be changed. It seems like they might have intended to add more than one algorithm in the future? NavigationAgent2D/3D does use an A* algorithm internally, but it’s separate from the AStar2D and AStar3D classes. I’ll edit my answer to change the wording a bit.

Also, after reading my answer again, I realise now that it sounds like I was saying there is no way to use NavigationAgent for your project, but that is not what I meant. I neglected to mention that it would also be perfectly possible to use a NavigationAgent2D for your project instead of AStar2D, depending on what you need. I simply wanted to use my own project as an emphasis that they are two separate things, and to give you something concrete to compare your own project.

If you wish to use NavigationAgent2D instead, since it already uses A*, you can follow the same principle of navigating towards each point individually.
Personally, I decided not to use NavigationAgent because it can’t really handle flying or swimming movement, and is mostly restricted to moving along the floor.
Since I only needed my drone to be able fly through doors while I let it handle its movement on its own inside rooms, it was simpler to use AStar3D. But NavigationAgent might or might not be the more appropriate solution for you.

In either case, the principle is the same; create a point map/navmesh, set a target, create a path to that target, and move towards each point in order until the final position is reached. Recalculate a new path as needed, either when you reach the destination, or when the target has moved.

Without going into too much detail, it would look a bit like this:

Add a NavigationRegion to your level, and bake the navigation mesh according to your level geometry. This can be done in the editor, or using NavigationRegion2D.bake_navigation_mesh().
By default, your level geometry has to be children of the NavigationRegion, but this can be changed in geometry_source_geometry_mode to use groups instead

Add a NavigationAgent2D to your car. It will automatically use the navigation mesh you created with NavigationRegion, unless you created more than one, in which case you need to tell it which one to use with NavigationAgent2D.set_navigation_map()

Set the car’s target (e.g.: a finish line, or another vehicle which your car is trying to ram into, etc.) in NavigationAgent2D.target_position. This automatically creates a new navigation path inside NavigationServer.

Every frame, call NavigationAgent2D.get_next_path_position(). This returns a Vector3 coordinate which you can plug into your car’s movement function.
e.g.: my_car.move_to(navigationagent.get_next_path_position())
When your car is within the distance set in path_desired_distance, the next path position will automatically be updated the next time your call get_next_path_position().

Then check if NavigationAgent2D.is_navigation_finished() to see if your car has reached the last point in the path.

One thing of note is to not set NavigationAgent2D.target_position every frame, especially if you have many NavigationAgents, since it recalculates the path every time you do, which is costly. If you’re trying to follow a moving target, you can set a timer and update the target_position only as often as you need, each second or so for example, or alternatively you can check if the moving target has moved away far enough from target_position.

[starck]

Yes, this is what I’ve been using, but I can’t control the path, it will always be a line from the car to the destination (assuming there are no obstacles) regardless of the car orientation. This is not what I want, I want the orientation of the car to be a factor in the pathfinding algorithm.

Car can’t 360 on themselves, but if I ignore that and tell the car to move like a car in the vague direction of the object, it messes the logic of the pathfinding agent.

having the pathfinding agent use the car orientation to make the car behave like a car and not a tank is the goal.

[Marabo]

Do you mind sharing your car’s movement script?