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

[Jeto143]

Godot version:

3.1.stable.official

OS/device including version:

Windows 10 (10.0.17134 Build 17134), but happens on other systems too.

Issue description:

When adding NavigationPolygonInstances that entirely cover tiles of a tileset, then covering a Tilemap with said tiles, using Navigation2D and its get_simple_path method produces unwanted behavior (unoptimal paths that include more points than needed):
https://i.imgur.com/yn4hegV.gif
https://streamable.com/47nzc

The actual result should instead be the same as what happens when covering the whole navigable area with a single NavigationPolygonInstance:
https://streamable.com/exk7u

Steps to reproduce:

Note that these steps can be reproduced either with the 3.1's new tileset editor, or using the old-fashioned way (scene converted to tileset).

1. Create a tileset resource with one single tile (to keep things simple).
2. Add a NavigationPolygonInstance covering exactly that whole tile.
3. Create a scene with a Navigation2D node that includes a TileMap node referencing that tileset. Cover the tilemap with the tile.
4. Add a sprite node that will serve as the moving object and place it somewhere on the map.
5. Use get_simple_path (with optimize to true) to compute a path between the sprite and a position far away (ideally, diagonally).
6. The resulted path will contain unwanted steps, even though there is no obstacle and the whole area is supposed to be navigable.

Minimal reproduction project:

weird_pathfinding.zip

Notes:

• This was initially posted as a question here and someone agreed it looked like a bug (even remade his own minimal projects to find out it behaved slightly differently in 3.0.6).
• If you take KidsCanCode's recent YouTube tutorial (that you can download from here) and simply fill the "holes" on the tilemap with the given tile, it will occur as well (that's actually what I did for the streamable.com links above). I talked a bit with KidsCanCode on Discord and he thought that seemed suspicious.
• I'm still very much a Godot beginner, so sorry if I missed anything obvious.

[kondelik]

@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):

[starry-abyss]

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:
#17885
#19011
#28640

[nettocavalcanti]

I've started learning godot (3.1) last week to make a tiled-board-game-test (descent journey into darkness - just for learning purpose) and got stuck on the same problem.

Basically I made a Navigation2D (star shaped) on each tile, but when I use get_simple_path() it just give me some weird path (clearly not the simple one).

On the image below, the "right way" to find the path is to go left/down (diagonally on the last 2 tiles), but it make a little "detour" on the left tile before arrives where I want.

I tried to enlarge navigation lines, but still got this problem.

Sorry for my bad english. I posted it only to help.

[HaSa1002]

Maybe unrelated, but: I experience issues with this node, when I am entering a Vector which has integer values (i.e. (390|120). The Navigation Node will not return anything (an empty Array). You can workaround this, when you add a really small Vector (I use 0.001).

[nettocavalcanti]

Hello HaSa1002, I tried to place a non-integer value on a Vector2 in get_simple_path param, but still get the same wrong path.

[HaSa1002]

Yeah, I meant I experience issues with getting any path (get_simple_path return an empty array) and therefore I described a nonsense workaround.

[nettocavalcanti]

Oh, now I understood... Anyway, I'll try this approach with the nearby NavyPolys to see if I get something else.

Thanks for the tip!

[nettocavalcanti]

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.

[nettocavalcanti]

Ok, I think I found a work around...

I have to make my NavPoly have no angle joint. Like make a tile's edge touch the other tile's edge, without any kind of angle.

I really think its a problem with some method to check the connection of the polygons.

Hope it helps others like me.

[HaSa1002]

Does anybody knows anything about the get_simple_path method? I am giving this a trial now, but this method is huge and I am new to the Godotcode. Maybe I head over to irc

[HaSa1002]

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

[nettocavalcanti]

Yes! This is exactly my problem. Even when I used my previous "solution" (avoiding corners between diagonals), I still get the weird path:

Thank you for helping example @HaSa1002 !!

Hope someone can help on finding and fixing this bug.

[kondelik]

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

so #22047 does not fixed this

[nettocavalcanti]

Well, @SPLITE at least for this particular case it seems not fixed... With the NavigationPolygonInstance like a "star"...

[HaSa1002]

@nettocavalcanti That is not completly right. The error even persists on the fully covered Tiles

[nettocavalcanti]

Yes, you're right. Forgot what @HaSa1002 posted before... Sorry.

[ka0s420]

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

[kondelik]

@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.

[HaSa1002]

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.

[ka0s420]

@SPLITE yes, that's right. At first the old demo had it so that it recalculated the path repeatedly, but also that the target would change aas you moved the mouse around. I made it so you click and it caches the target.

@HaSa1002 yeah it's definitly not ideal to do this. Not sure why it was this way in the demo, or why the paths behave so differently. Definitely wouldn't use it in anything where the pathfinding overhead was critical like an rts. But for a turn based tactics style game or something like that it would work. Not sure why you think the path is as wrong as the other?

[HaSa1002]

@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

[HaSa1002]

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.

[HaSa1002]

I now tested with one polygon having some structure in it.

The side effect, despite of working, is that it's faster.

[HaSa1002]

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

[girng]

Dang, running into this issue after following KidsCanCode and GDQuest's tutorials. I'm having the same issue in the answer here. It makes movement very wonky for hack n slash/point and click movement.

[git2013vb]

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)

In my understanding what is missing about the whole process to determine the correct path is the weight of each possible solution. The weight have to be find by relate the distance between the target and the current position compared with the weight between the start and the current position. I didn't see the it anywhere in code. So the process will find the first one possible way, and because it start from left the probability the it show the left side first is very high. The approach is not complete in my opinion. Also it seems more complicate because the polygon are not regular four side polygons (square shape) but seems sometime the process make 3 side polygons(triangle shape) in its formula (But I'm not sure 100% about this) :)

[starry-abyss]

@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.

[git2013vb]

<..snip..> weights <...snip...>
I was not referred to that "weighs" rather a "costs"
http://theory.stanford.edu/~amitp/GameProgramming/
https://www.youtube.com/watch?v=-L-WgKMFuhE

[starry-abyss]

I understand, I implemented A* on the grid before, it's not that complicated.
Non-uniform costs are an extra feature, not a requirement. In the simple implementation to know the cost, call a function each time, which will return the distance between two cells.

[git2013vb]

Honestly I didn't full check how it was implemented in godot. The code is a bit complicate and people need time to investigate.

[giviz]

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)

That seems to be the best approach indeed. I guess there is no simple solution to extract the polygon auto compiled from the tilemaps and reassign it to a NavigationPolygonInstance, it has to be re-created from scratch ?

That would mean to create a polygon the size of the map, and crop into it thousand of small polygons (one for each 1/25 of a tile that can be blocked). Or maybe reduce it to only take into consideration what's in and around the viewport.

The auto compilation from the tilemaps is really fast to load in comparison to my tests with a lot of small polygons. With too many polygons (2500 sub tiles to block) it wont even load.

[KoBeWi]

Still valid in 3.2.4 beta3

[starry-abyss]

I think it's just not a valid A* over grid implementation, as A* over grid should prioritize direct lines (by measuring the distance towards the goal). It probably just picks up routes at random instead.

[aaronfranke]

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.

[nklbdev]

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)

[nklbdev]

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.

[Kushal-Dev94]

If you guys find a workaround for this, pls let me know.

[smix8]

#61266 might fix some of the tileset issues mentioned here.

Even with this fix expect a lot of navigation tile edge merge issues at the moment in 3.5 as the NavigationServer2D lacks some critical fixes not backported from Godot 4.0.

e.g. NavigationPolygon resources that would merge perfectly in Godot 4.0 refuse to merge in Godot 3.5 because the merge code is overly strict on angle, proximity and edge length.

[akien-mga]

Fixed by #61996.

[nklbdev]

It's wonderful! I'll be testing it out today or tomorrow!

[nklbdev]

@smix8, I read your message. I understand.
I compiled the latest version of the 3.x branch (6ecdef84cf36ba9268ccc19b78210b039098eb52) and the bug is still here

[smix8]

@nklbdev
Could you be so kind and create a dedicated new issue for this (old) bug with a small test project. I know this 2D bug is old and I have my suspicions what could cause it for 2D. In this issue we have actually a ton of bugs mixed together (e.g. wrong navpoly, old pathfinding, ....) which makes it hard to keep track of and the majority of the other bugs are fixed now or also have their own dedicated issues open.

[nklbdev]

@smix8, thanks for the tip, i just created a new related issue!