godot: Navigation2D#get_simple_path doesn't behave properly when using per-tile navigation polygons

Hello! I’m using 3.5 alpha and the problem is still here.

Sorry i use google translate

There are fewer problems in calculating the path around holes. But there are still problems with finding direct or shortest paths. I think the problem is that the algorithm uses astar on a graph of triangles and stops when it finds the first match on the minimum number of transitions.

It is necessary that when finding the first path, the algorithm remembers the result as the minimum of those found, and continues searching in other branches until they exceed its length. If the length is exceeded, discard the search branch. If a shorter length is found, update the saved result.

I found that the algorithm uses costs derived from the distances from the input point of the polygon to the edge of the next polygon. This is a very rough estimate and can often be wrong. (You can see it on the picture)

I really love Godot and want to help the development. I’m sorry I didn’t understand the build system. I hope my advice is helpful.

PS: I figured out how to run the build it. I found the code where the path is calculated (nav_map.cpp:82). Yes, the approximate path length used to discard “long” paths is incorrectly calculated here. I’ll try to fix it, hope I can)

@clayjohn I don’t think usability tag is the right one - you can set up the navigation in editor just fine. Issue is about method $Navigation2D.get_simple_path() (when using TileMap as source of your navigation poly) returning silly routes:

Note that every tile is 100% covered with NavigationPolygon without overlaping - i checked polys in .tscn file, my first thought was some float creeping to the neighboring cell, but no. Also note that edges of paths are exactly on edges of tiles.

Fun thing is, it doesnt work as one would expect even in Godot 3.0.6 - but it works sligtly better (bends are not so sharp):

Sorry if this isn’t right, but I was following the GDC tutorial on using simple_path and I was getting some odd behaviour, too. After some digging I found this post, but also an old pathfinding demo on github that hadn’t been updated for three years… However I managed to get the demo working, and compared and the pathing behaviour was much more as expected. I still can’t figure out why though, allthough they both do use different methods.

Here’s a gif of the results of the gdc tutorial pathfinding:

https://media.giphy.com/media/JnusvvxCd1w9w9kWfA/giphy.gif

Here’s a gif of the modified older demo:

https://media.giphy.com/media/JszpjWCBSdHyPjirOy/giphy.gif

As you can hopefully see, in the gdc version, the characted moves first up or down then left or right whereas the old modified version, shows the path as being the same as the gdc one, but moves diagonally as you’d expect.

Here is a copy of the the codes from the modified older demo:

From the main ‘game’ node:

extends Node2D

export var tile_d : Vector2 = Vector2(32, 32)

onready var nav_2d : Navigation2D = $Navigation2D
onready var line_2d : Line2D = $Line2D
onready var character : KinematicBody2D = $player
onready var cursor: Sprite = $Cursor

func _unhandled_input(event: InputEvent) -> void:
		
	if event is InputEventMouseButton:
		
		if event.pressed and event.button_index == BUTTON_LEFT:
			
			character.path_target = get_global_mouse_position()
			var new_path : = nav_2d.get_simple_path(character.global_position, get_global_mouse_position(), false)
			line_2d.points = new_path
			character.points = new_path

from the player script:

extends KinematicBody2D

export var speed = 100
var points : = PoolVector2Array() setget set_points
var path_target : = Vector2() setget set_path_target

const eps = 1.5

onready var line_2d : Line2D = get_node("../Line2D")
onready var map : TileMap = get_node("../Navigation2D/TileMap")

func _ready():
	pass
	
func _physics_process(delta):
	if points.size() > 0:
		points = get_node("../Navigation2D").get_simple_path(self.global_position, path_target, false)
		line_2d.points = points
		if points.size() > 1:
			var distance = points[1] - global_position
			var direction = distance.normalized()
			if distance.length() > eps or points.size() > 2:
				position += direction * speed * delta
			else:
				position += Vector2(0, 0)

func set_points(value: PoolVector2Array) -> void:
	points = value
	if value.size() == 0:
		return
	set_process(true)
	
func set_path_target(value: Vector2) -> void:
	path_target = value

here is a link to the unmodified github repo: https://github.com/FEDE0D/godot-pathfinding2d-demo

and the GDC code is available in the video tutorial: https://www.youtube.com/watch?v=0fPOt0Jw52s

Godot 3.1.1, Windows 7 64-bit

Happens for me too. If I make the optimize argument false, it looks like it uses simplified, Manhattan distances. Though looking at source code, I find only good old square root, hmm…

Another idea that maybe it optimizes away tiles and uses different-sized navmeshes instead (is fine), which are then just followed center to center instead without smoothing (not fine).

Related: https://github.com/godotengine/godot/issues/17885 https://github.com/godotengine/godot/issues/19011 https://github.com/godotengine/godot/pull/28640

I wanted to use the algorithm described by the user jb-dev on the page Navigation Meshes and Pathfinding on gamedev.net I took the base picture from one question on stackoverflow

It simulates two stretched threads, by the length of which we can calculate the cost of transitions to each next polygon. But to implement it, I will have to do a flat sweep for each sequence of polygons. This is necessary because Godot has only one implementation of pathfinding - for 3D space. Pathfinding in 2D just wraps it and provides the same interfase but with Vector2 instead Vector3. The algorithm will produce the correct result, but it is not optimal. Each polygon needs to be rotated in 3D space. To do this, needed to allocate memory and perform trigonometric operations.

In this case, it is necessary to keep in memory two threads of the path (left-red and right-green) with theirs turning points. I’m sorry, but it looks like I can’t do it.

This needs to be re-tested in the latest 3.x branch (what will be Godot 3.5) due to the navigation server backport that was just merged. It would also be nice to get testing done in master and 3.4 for completeness.

Still valid in 3.2.4 beta3

I think (I don’t really understand that pathfinding code, it’s more guessing) the problem is Navigation2d::_navpoly_link as it seems to only link edges and that in combination with the simple path and the mecanism of finding the path through the polygons leads to the weird paths.

To demonstrate that this problem is not related to the tilemap itself, I updated my example (below). Maybe someone with some deeper understanding of the pathfinding can come and fix this. I assume it could be done with just fixing the _navpoly_link method to extend the linking to vertices and not only edges. I feel uncomfortable and lost in writing a solution.

Three notes on my new example:

1. The green line is the path returned, by get_simple_path
2. The orange/red line is the direct path between the current position and the destination.
3. If you hold space, the tank will not stop.

New Example Project: bug_#28235.zip

The point is however, that in the GDC version the path is calculated as in our demo, what you see with this “odd path”, but since you recalculate it every physics tick, you get the “better” path. Keep in mind, that the pathfinding is an expensive algorithm (running linear), so I expect, you found yourself with lowered FPS. The path you saw is as wrong as the other.

I can confirm that this error persists in a freshly build version of master branch.

so #22047 does not fixed this

I can confirm that this error persists in a freshly build version of master branch. My tests so far (I used the provided minimal example as starting point): Project at the bottom

1. With a fully covered Tile you get really weird paths (3 segments)

2. @nettocavalcanti Path without overlapping takes ~3sec to be generated and are not much better (5 segments):

3. Overlapping is not better: (96 segments)

4. A Navigation Polygon with ~30 Verticies is not performance friendly:

5. Updated test project: tests.zip

I hope this helps a bit. I still struggle to get into that pathfinding code.

EDIT: Path optimisation made not better nor worse

Well, I think this is the same problem @HaSa1002 .

I removed all links to the desired tile and overlaped the junction between the two tiles. But the get_simple_path() method returns an empty array.

I tried your solution, but still not working:

I think this is some kind of bug when the engine tries to link a NavPoly to another.

@giviz In one jam game I used this workaround, which smoothes the path after A* (Theta*-ish):

func _update_navigation_path(start_position, end_position):
	# get_simple_path is part of the Navigation2D class
	# it returns a PoolVector2Array of points that lead you from the
	# start_position to the end_position
	path = get_simple_path(start_position, end_position, false)
	# The first point is always the start_position
	# We don't need it in this example as it corresponds to the character's position
	
	if path.size() > 1:
		
		var lastPoint = path[-1]
		var cellSize = 64
		lastPoint.x = floor(lastPoint.x / 64) * 64
		path[-1]

		var space_state = get_world_2d().direct_space_state
		
		var i = 0
		while i < path.size():
			var size = path.size()
			
			for j in range(i+1, size):
				var result = space_state.intersect_ray(path[i], path[size - j - 1], [ player ] )
				if result.empty():
					for k in range(i+1, size - j - 1):
						path.remove(i+1)
					break
			
			i += 1
		
		$Line2D.points = path
		
		path.remove(0)
		followPath = true
	
	return path.size() > 1

@git2013vb It uses distances for weights. Yes, some games require custom weights (so e.g. swamp is less preferred than road), but a lot of games don’t.

If it is crucial don’t use tile-based navigation and prefer to create a polygon which is then added as instance. (See my weird looking screenshot above)

So I looked into the algorithmn and found various possible reasons for the misbehaviour:

1. The algo runs per polygon (I assume one polygon for each tile, though I haven’t looked into that)
2. Once it founds that the dest point is not inside the polygon it tests which neighbour poly is nearest to that point and saves a point in the on the edge both share
3. It’s a total mess and hard to read and understand (What is USE_ENTRY_POINT?)

One word on 1 and 2: I don’t know if it would break something (I assume it does) and is even possible, but what is about batching the navigation polygons together first and see then what happens?

My somewhat unrelated question, why we use a map there to store the polygons? Do they need to be sorted? And how are they sorted? As I implied with point 3, I don’t really get how it works and it blows my mind regulary when I try.

@ka0s420 The path is as wrong as the other, because the debug navigation shows exactly the same wrong path as in the calc and run method. The reason is the path seams “better”, because you recalculate the path every time and the first points is a bit special and differently set

@ka0s420 if i get it, you are finding new path every physics tick - not by finding one at the beginning and then following it. Nice.