What is wrong with my pathfinding code?

:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By Cobra!
:warning: Old Version Published before Godot 3 was released.

I’m having a problem with my pathfinding.

I’m trying to use the Navigation and NavigationMesh to do my pathfinding, but I’m running into some problems.

The AI that is doing the pathfinding is just running off on one direction and doesn’t stop.

Here’s the level I’m testing on, with the NavMesh highlighted:

Upon printing it for debugging, the coordinates are way off, like I suspected:

The first 3 vectors are the path nodes
The bottom Vector3 is the actual position of the player, which the AI is supposed to be chasing.

Here’s my code:

#AI.gd

onready var currentTarget = get_node(target)
var previousTarget
var currentDirection = Vector3()
export(float) var turnSpeed = 1
var enemySpotted = false

var navMesh
var followPath = Vector3Array()
var currentPathNode = 0
const PATH_COOLER = 0.3
onready var pathTimer = PATH_COOLER

export(float) var minDistance = 3.5
export(float) var maxDistance = 50
var diff
var dist

func AILogic(delta):
	dist = get_translation().distance_to(currentTarget.get_translation())
	if enemySpotted: # If the enemySpotted flag is true
		if currentTarget.dead() or dist > maxDistance:# If the target is dead or too far away.
			if !previousTarget:
				resetTargets() # Reset the targets
				enemySpotted = false # Set the flag of "enemySpotted" to false, returning the AI to it's ordinar state.
			else:
				currentTarget = previousTarget
				previousTarget = null
			followPath = Vector3Array()
			currentPathNode = 0
		elif dist > minDistance: #and it isn't too close tae it
			if navMesh:
				FollowTargetPath(currentTarget.get_global_transform().origin, delta, enemySpotted)
				#translate(FollowTarget(currentTarget.get_global_transform().origin, delta, enemySpotted))
			else:
				navMesh = get_tree().get_root().get_node("Level").navMesh
		else: # If the AI IS close enough to the player.
			followPath = Vector3Array()
			currentPathNode = 0
			turn_to(currentTarget.get_global_transform().origin, turnSpeed / 2, delta)
			fightingLogic(delta) # Go to the fightingLogic method, which takes care of the fighting mechanics.


#This is where the following logic happens, it basically slowly turns to the target, and walks forward untill it's too close tae it, where it returns (0,0,0) to let the function
# calling it know that it's too close to the target, for it to change target if it's not going after the enemy.
func FollowTarget(target, delta, isEnemy):
	if get_translation().distance_to(target) > minDistance:
		turn_to(target, turnSpeed, delta)
		if abs(velocity.z) < topSpeed:
			velocity.z -= _acceleration * delta
			if isEnemy:
				nextAnim = wapen + "Rinnin"
			else:
				nextAnim = wapen + "Walkin"
	else:
		if !enemySpotted:
			changeAnim("Staundin 4", wapen + "Staundin")
		return Vector3(0, 0, 0)
	translate(velocity)
	return velocity

func FollowTargetPath(target, delta, isEnemy):
	dist = get_translation().distance_to(currentTarget.get_translation())
	if followPath.size():
		if currentPathNode < followPath.size() and pathTimer > 0:
			var targetFollow = FollowTarget(followPath[currentPathNode], delta, isEnemy)
			if targetFollow.length() == 0:
				currentPathNode += 1
			else:
				translate(targetFollow)
			pathTimer -= delta
		else:
			translate(FollowTarget(target, delta, isEnemy))
			followPath = Vector3Array()
			currentPathNode = 0
			pathTimer = PATH_COOLER
	else:
		followPath = navMesh.get_simple_path(get_translation(), target, false)
		for i in followPath:
			print(i)
		print(target)
-----
#LevelMain.gd (Root Script)

export(NodePath) var navigationMesh
onready var navMesh = get_node(navigationMesh) setget , getNavMesh

func getNavMesh():
	if navMesh extends Navigation:
		return navMesh
	else:
		return 0

What am I doing wrong?

Did you draw the path in 3D to see if it’s actually wrong or not?

Zylann | 2017-02-06 20:08

I don’t actually know how to draw in 3D, people make it seem like that’s an impossibility. If I find out how, I’d try it, but seeing as the coordinates seem to be way off like they are, I don’t know what good it would do.

Cobra! | 2017-02-06 20:42

Instance TestCubes at all the points? Or use ImmediateGeometry: http://docs.godotengine.org/en/stable/classes/class_immediategeometry.html?highlight=Immediate

Zylann | 2017-02-06 20:43

Well, I’m trying to add code to instance a test cube, but I’m getting a lot of errors in my code, such as:

Invalid call. Nonexistent function 'instance' in base 'GDNativeClass'.

Here’s the code I’m trying to use:

func instanceCube(position):
	var testCube = TestCube
	var tempTestCube = testCube.instance()
	testCube.set_translation(position)
	add_child(testCube)

Cobra! | 2017-02-06 23:17

TestCube is a class, not a scene, so it must be instanced using new:

func instanceCube(position):
    var tempTestCube = TestCube.new()
    testCube.set_translation(position)
    add_child(testCube)

Zylann | 2017-02-07 09:36

Okay, i’ve done that, and I’m getting weird results.

The cubes seem to be behind the AI and follows them around…


What do I do now?

Cobra! | 2017-02-07 18:30

Is “set_translation” for local positions? If so, I think that’s the problem. Is there a way to set the global translation?

Cobra! | 2017-02-08 12:44

Oh yeah… :facepalm: if your path is in global space (I assume it is?) you want to make it visible in global space too, so if you use ImmediateGeometry or TestCube to see it, you have to instance them under the root of the world, not as child of the character (which is why it “follows” them). It could be related to your problem in fact^^

Zylann | 2017-02-08 16:15

It could, yeah.

Well, I modified the code like so:

func instanceCube(position):
var testCube = TestCube.new()
testCube.set_translation(position)
get_tree().get_root().add_child(testCube)

and that seemed to work, because the cube aren’t following the AI any more, although like I expected, they are near the centre of the scene and are staying there:

I’m kind of stuck now. Is there a way to make the path use local coordinates instead? Or make the script generate a proper path for the AI to follow?

Cobra! | 2017-02-08 19:19

Well if your AI can’t tell its character to move to a specific world position, then it would be hard to make it move in the first place. You should be able to move the root node of your character, which is usually child of a world-space node (or a node positionned at (0,0)), so moving the character root is like moving in the space it is placed on (the world, then).

Does the path make sense when you look at it? I see grey boxes but it’s messy^^"

Try first with only one AI, which tries to run in your direction. Simple, one target position.

If it works, then use pathfinding to reach multiple points, one at a time, building on top of the same logic. If you have problems there, use what I said to show the path, see if anything is wrong, and adjust your logic.

If it works, then use multiple AIs :slight_smile:

Zylann | 2017-02-08 19:26

Unfortunately no, the box patterns make no sense to me either, they appear there for every AI, even ones nowhere near that part of the map…

The AI does normally follow the player just fine without pathfinding, using my “Follow target” method on the Pastebin, but it’s only when I use it for Pathfinding where it has no idea where it’s going…

Also, I am moving the root node of the character…

Cobra! | 2017-02-08 20:30

As I said, try with only one AI and make sure what you see with debug code is right (without following the path yet), and try to fix it until you get the result you expect.

Zylann | 2017-02-08 20:48

I have been only testing it with one AI, and I have no idea how to fix it. All I’m doing is getting a path from navigation and storing the vectors into the AI script, and getting the AI to follow them one at a time. I don’t what I can do TO fix it…

Cobra! | 2017-02-08 22:54

Okay, a bit of an update, it turns out that it does form a path if I’m at the botton half of the map (Although the AI seems to have a lot of trouble following it, but it gets stuck on the first point… On the top half, the path just doesn’t go past a certain point, despite there being a navmesh in the area…

I’m completely stuck, what do I do?

I have no idea how any of this works, so I’d have no hope to ever fix this by myself, I need outside help. That’s why I’m here.

Cobra! | 2017-02-08 23:33

Unfortunately I’m not much experienced on the 3D part yet, that’s why I’m suggesting to do things as slowly and surely as possible, by doing steps separately: first, get a path and draw it to make sure it looks the way you expect (I still see an unshaded cube soup in your screenshot, I’m not sure it’s exactly what you want?), and then follow that path (be it a hardcoded one or one coming from pathfinding). That’s how I would go myself if I were to learn the same stuff as you. Unfortunately I don’t have enough time yet so I can mainly give you directions.
You can also have a look at the 3D pathfinding demo found in the official examples, to see how it follows paths.

Zylann | 2017-02-08 23:44

Okay, thanks anyway.

Cobra! | 2017-02-09 16:42

:bust_in_silhouette: Reply From: Gokudomatic2

I made a working bot that can use navmesh. You can check my code if you want:

also available in the asset library if you prefer:
https://godotengine.org/asset-library/asset/52

Sorry, which script is it?

Cobra! | 2017-02-07 17:49

Are there any tutorials on how to implement the addon if I chose to use it?

Cobra! | 2017-02-07 18:27

You don’t see any file? Strange. What do you see in this link :
https://github.com/gokudomatic/eco-fps-walker/blob/master/README.md

Gokudomatic2 | 2017-02-07 22:08

This is interesting.

Is there any chance at all that you can provide a tutorial on how to do this yourself or how to implement the addon?

Cobra! | 2017-02-08 12:54

There is a chance but, short answer, not anytime soon. I asked the guy behind GameFromScratch to make one with my help. He’s interested but he’s waiting for v3.0. As for me, I don’t have the energy nor the time to write a proper tutorial, and even less to record a video. Other projects are waiting :wink:
I can only recommend you to read the readme from my repo (especially the “usage” section) and see the samples.

Gokudomatic2 | 2017-02-08 20:07

Okay, thanks anyway. Would I be allowed to use this addon in commercial games?

Cobra! | 2017-02-08 22:55

Yes. Such information are found in the MIT licence file in the github repo. You’ll see it’s a very permissive licence.

Gokudomatic2 | 2017-02-09 07:08

:bust_in_silhouette: Reply From: Cobra!

I figured it out!

It turns out it wasn’t my code that was the problem, it was the navmesh itself!

In the first screenshot, I showed the navmesh in the editor, but the centre of that mesh was at the corner:

So what I did was go to Blender, selected the navMesh in the file and applied the transform (Space > Search “Apply Object Transform”), which makes the centre of the area the centre of the mesh.

After rearranging the code a little bit, it worked!

My code as of right now, I just need to fix some minor issues with the movement of the AI themselves, but this works, and you guys have my full permission to use this for your own games. Assuming anyone here actually develops 3D games and needs an easy pathfinding code:

#AI.gd
var velocity = Vector3()
export(int) var topSpeed = 5
export(int) var acceleration = 1
onready var _topSpeed = topSpeed
onready var _acceleration = acceleration
onready var decceleration = acceleration / 2

onready var currentTarget = get_node(target)
var previousTarget
var currentDirection = Vector3()
export(float) var turnSpeed = 1
var enemySpotted = false

var navMesh
var followPath = Vector3Array()
var currentPathNode = 0
const PATH_COOLER = 0.3
onready var pathTimer = PATH_COOLER

func FollowTargetPath(target, delta, isEnemy):
	if followPath.size():
		if currentPathNode < followPath.size() and pathTimer > 0:
			dist = get_translation().distance_to(followPath[currentPathNode])
			if dist < minDistance:
				currentPathNode += 1
				print(currentPathNode)
			else:
				translate(FollowTarget(followPath[currentPathNode], delta, isEnemy))
			pathTimer -= delta
		else:
			#translate(FollowTarget(target, delta, isEnemy))
			followPath = Vector3Array()
			currentPathNode = 0
			pathTimer = PATH_COOLER
	else:
		followPath = navMesh.get_simple_path(get_translation(), target, true)

#This is where the following logic happens, it basically slowly turns to the target, and walks forward until it's too close to it, where it returns (0,0,0) to let the function
# calling it know that it's too close to the target, for it to change target if it's not going after the enemy.
func FollowTarget(target, delta, isEnemy):
	dist = get_translation().distance_to(getTargetPosition())
	if dist > minDistance:
		turn_to(target, turnSpeed, delta)
		if abs(velocity.z) < _topSpeed:
			velocity.z -= _acceleration * delta
			if isEnemy:
				nextAnim = wapen + "Running"
			else:
				nextAnim = wapen + "Walking"
	else:
		if !enemySpotted:
			changeAnim("Staundin 4", wapen + "Staundin")
		return Vector3(0, 0, 0)
	return velocity
----------
#LevelMain.gd (Where the Navmesh is):

export(NodePath) var navigationMesh
onready var navMesh = get_node(navigationMesh) setget , getNavMesh

func getNavMesh():
	return navMesh

func getPath(start, end):
	var begin = navMesh.get_closest_point(start)
	var p = navMesh.get_simple_path(begin, end, false)
	return Array(p)

If you can’t be bothered, however, you can try Gokudomatic2’s eco-FPS-walker, linked in the other answer to this question by (I assume) the author themself.