Multi-Threaded / Parallel Pathfinding

I’m working with Roblox pathfinding… still. All seems pretty alright. However, I’m looking to improve the performance of many NPCs at once calculating paths many times a second.

I learned that some speculated ideas, involve multi-threading. Currently, I use a coroutine per an NPC to control the functionality of that NPC. (Their pathfinding part anyway). This provides the illusion that I’m multi-threading when in reality I am really not. Each NPC, in real time, is taking turns calculating a path. (If I understand this all correctly).

Parallel Luau allows for the emulation of true multi-threading, thanks to Roblox. So how would I implement this with NPCs?

Thanks to Thread Safety, I can’t calculate paths in parallel, nor use functions such as MoveTo() to move the NPC along the path. (Likely for good reason)

So what do I do? I read that Roblox is over time working on gradually moving their functions over into a ‘parallel’ compatible state?
Am I not understanding this correctly? Am I not supposed to run calculations on a path in parallel and I’m just not understanding?

Anyone bold enough in the understanding of multi-threading or parallel luau, feel free to respond. Or completely correct my understanding on everything.

Actors! They are a subclass of Model, meaning that you can just plop the NPC bodyparts and humanoids into them. Each NPC will be its own Actor, and any subsequent scripts inside them are eligible to be multithreaded.

Before all that though, there is a very important decision you should make when doing any multithreading stuff; how will data flow?

They both have pros and cons:

  • If you have each thread run in serial independently, it can avoid any bottleneck associated with returning data (via Events), but all the processed data will be isolated and inaccessible between actors. If you plan on using modules to process data, this also means bloating up your memory since each thread will clone the entire module for itself.
  • On the other hand, if you have the processed data returned to a single collection point, all the data will be available and you can easily do whatever you want with it, at the cost of performance impacts from sending data.

Here’s a screenshot from one of my projects that uses multithreading; you can see the various steps and also bottlenecks to performance attributed to Parallel Luau.

Note that the bottleneck stuff mentioned above is based on the premise that Events are the only way to exchange data between serial and parallel, which it currently is. Roblox is still working on a type of shared memory system between the different threads, which should hopefully be miles better than throwing around events. But for now you have to stick with Events.

The reality is, Parallel Luau is still an emergent feature that lacks a lot of basic necessities. It needs time to mature. A lot of functions and methods in the Roblox Engine are still not threadsafe, and in that case, there’s nothing you can do but wait.

In addition, multithreading is really only designed to tackle a few specific challenges and is not meant to be used everywhere nor on everything. It is good at repetitive tasks like millions of math calculations since they’re all done individually regardless, but is counterintuitive for things like calculating physics (since everything interacts with everything else and it would be a disaster to cross the thread boundary countless times each frame).
In your case, pathfinding does sound applicable to me since it’s nothing more than just an algorithm, and the reason why it isn’t threadsafe could just be because Roblox hasn’t enabled it yet.

5 Likes

For testing purposes, right now I have a Main script that firstly requires a NPC module (a class) that returns enemy instances and their methods to control them. A loop that then spawns them.

Will I be able to control all of the NPCs like that via one module script and still have each NPC run in parallel? Or does each NPC need their own Actor and script to control them?

It depends; look back at the two paradigms I explained in my previous post. The one on the left where each thread will individually run in serial, if applied to your scenario, would mandate the one-Actor-each approach since the data has to be used within the Actor script itself. But if you use the one on the right where the threads will return the data to a central processing point then you don’t really need to, since the data can go anywhere and it’s not locked within the threads.

1 Like

Alright, I think this makes sense, I guess I have no choice though but to wait on Roblox. Appreciate the help!

This topic was automatically closed 14 days after the last reply. New replies are no longer allowed.