How to do a thread-safe 3D Pathfinding?

Archive
1
:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By Skipperro

Hi,

I’m building a simple 3D scene with following structure:

Scene
–Player
–Enemies
----BadGuy1
----BadGuy2
----BadGuy3
–Navigation
----NavMesh

I want to use Navigation.get_simple_path() to provide the BadGuys a route to the player through a map. Initially I simply put a timer for each BadGuy to call Navigation every 2 seconds, but it lead to mini freeze every 2 seconds, as it takes more than 100ms to process.

I quickly realized, that I need to calculate path on a thread and send the results to BadGuys. I’ve done that and performance is now great without any annoying stuttering.
But since I’ve made this change I keep getting random crashes and hangs with 100% CPU Load. I thought, that I made some not thread-safe operation so I spent days trying to fix this using mutex, call_deffered() functions, many individual threads, one AI-Overlord thread, but nothing makes my game stable.

Are there some examples of how to properly call get_simple_path() on Navigation Node from a Thread and send results back to another Node? I’m stuck!

2
:bust_in_silhouette: Reply From: Zylann

I think this should be something you can use in a thread, but I can’t confirm that.
However, Navigation is a node, and the scene tree API is known to not be thread-safe. So it boils down to a few questions:

  • Is the navigation modified during the game?
  • Is the search algorithm using non-thread-safe APIs? (engine side)
  • Is the threaded code YOU wrote accessing nodes from its thread?

If you are accessing nodes from your thread, change that. Make sure the thread logic is isolated, and use call_deferred or Mutex to push the result back to the main thread.

If the problem still occurs, the first two could be the subject of a Github issue because that’s a legit use case, I don’t see why you shouldnt be allowed to use threads here, despite the fact it’s the API of a node.

Another question I’d have, is why is it taking 100ms? This is quite a long time, is your navigation mesh really complex?

Navigation Node is not modified in any way. It’s used only to run get_ simple_ path() function.
To update BadGuy path I call this from a thread:
call_ deferred(“update_path”, newpath)
so it updates on the main thread with the data from thread.

I don’t know what you mean with “search algorithm”.

Map is pretty simple, but it takes over 100ms because I have to calculate path for not one but for many BadGuys.

Can a thread create a duplicate() of the Navigation Node to store it locally, to be 100% sure, that it did’t read anything from the active node tree?

P.S. Your height-map terrain plugin is awesome!

Skipperro | 2019-07-29 13:28

I guess you are then running all pathfindings in the same thread then?

What I mean by “search algorithm” is basically pathfinding, what the engine does.

Note that changing the position of navigation occluders could do modifications.

I’m not sure if Navigation still works if duplicated outside the tree… but IMO you should not need to do this, get_simple_path() must be thread-safe because otherwise it becomes a hassle. You could reproduce this in a simple project to show your problem, and post a Gitgub issue explaining what you need.

Zylann | 2019-07-29 13:55

Yes, currently I’m running all pathfinding on one dedicated thread, but I’ve done many variants of this including one where each BadGuy started his own pathfinding thread. It was even worse, since by having more BadGuys than CPU cores it started to take computing power from the main thread and added overhead from the threads themselves.I couldn’t find the way to let only few of them calculate and force others to wait their turn. But this is other, design-related topic.

My current project is way to big for posting, but if I don’t find a solution I will recreate it on a small scale and post as issue.

Skipperro | 2019-07-29 14:12

3
:bust_in_silhouette: Reply From: twinpixel

Instead of getting the paths of all baddies every 2 seconds you could try to get one path for each baddie every 10 ms or so. One baddie after the other. Then you could probably run the pathfinding in the main thread?

Did you try that?

Yes, this could be the way to go and I thought about it. I could do it this way, you are right, but I don’t want to do this unless I really have to.

Even if one pathfinding will take only 5 ms and I will iterate through BadGuys updating only one per frame, at 60 FPS (max 16 ms per frame) I will need 1/3 of the frametime to do pathfinding. Right now my game on highest settings need 10 ms to render each frame. Adding extra 5 ms will push me uncomfortably close to the limit, if I want to have minimum of 60 FPS.

There is also efficiency aspect. This is a perfect use case for all those extra CPU cores, that are laying around doing nothing. Why put more work on the one core that does rendering, when the rest is wasted?

Skipperro | 2019-07-30 14:41