AStar#get_point_path() / AStar#_solve() not thread-safe

[jan-krueger]

Godot version: 3.0.2

OS/device including version: Windows 10 64bit

Issue description:

0:00:04:0405 - Condition ' p_elem->_root ' is true.

Type:Error Description:
Time: 0:00:04:0405
C Error: Condition ' p_elem->_root ' is true.
C Source: core\self_list.h:46 C
Function: SelfList::List::add

Error in the external console

ERROR: SelfList::List::add: ERROR:
SelfList::List::add: Condition ' p_elem->_root '
is true. Condition ' p_elem->_root ' is true. At: At:
core\self_list.h:46 core\self_list.h:46

This seems to be caused by calling AStar#get_point_path() (GDScript) which calls AStar#_solve. I am lacking the C++ skills to debug what is going on and unfortunately, the assertions aren't commented nor do they emit a more helpful message which makes all of this kinda difficult to understand for a beginner.

After further testing, it turns out either AStar#get_point_path() or AStar#_solve() are not thread-safe, I think the latter one. I execute AStar#get_point_path() on another thread to avoid stuttering. This works just fine with only one thread but adding more than one causes the error. I tested this by adding a Mutex to lock down the method call.

Steps to reproduce:
Call AStar#get_point_path() in several threads

Minimal reproduction project:

I essentially call queueNavigation to add a new job and processQueue gets called to process all the jobs.

https://gist.github.com/sweetcode/0d61c20d26d32e15a49281eba1d6a08e

[alimalkhalifa]

Another permutation of this found

I first encountered this while trying to use AStar#get_point_path() in a thread, but this error had persisted after taking it off. After reading MortimerMcMire's comment on #8691 I modified my code to check for duplicate connections and disabled bidirectional connecting:

if not point2 in astar.get_point_connections(point1):
    astar.connect_points(point1, point2, false)

Suggestion

Add automatic checking in AStar#connect_points(p1,p2,b) so as to not double connect, and make it bidirectional aware.

Also would be nice to have a more descriptive error!

[jan-krueger]

Thank you, this actually resolved the issue for me.

[Ploppy3]

So the solution is to disabled bidirectional connections?

[alimalkhalifa]

@Ploppy3 basically you need to avoid duplicate connections. So you can either build your map by radiating outwards and never connect backwards and keep bidirectional active, or you can do what I did and move about in whatever way but always check if a connection exists before making one (with or without bidirection, but easier without).

[alimalkhalifa]

@akien-mga would it be desirable to make all AStar::connect_points check to see if a connection already exists or is it deemed an edge case, and we should leave that check in user-land? Its kind of situational in that there are methods of building the graph/map without iterating backwards in some use-cases, in which case a check would slow down unnecessarily. That said, AStar fails if it has double connected points. Maybe a compromise is to add a flag to the call which disables the check?

[Eman2022]

came here after hours of sifting through code in a thread to find that get_point_path is just not working inside a thread. This really bums me out, I have no desire whatsoever to re-write my connection code, outside of this my Astar class is working perfectly. This is still an issue in godot 3.2.2

[smix8]

Old issue that should be closed for the original issue because the AStar classes no longer use this SelfList.

That AStar classes are at their very core not thread-safe is part of the documentation.

Making them fully thread-safe would require a major rework proposal because it is not only their Point struct and temp data that is a problem but also how they allow random changes to the graph while threads would still op on the graph resulting in corrupted results or random crashes.