So I was following this tutorial series:

While this working well in the beginning, when I attempted to implement thread, is broken. The code for generating the path would never finish.

When I only had 1 seeker and 1 target, it worked fine, but having 2 or more seekers target the same target and it breaks. I tested it with 2 seeker following 2 different target where the paths would not cross and everything worked fine. The only thing that makes sense is that in the threads that are running at the same time are trying to modify the same node in the grid causing bad things.

I though it was weird that the path generation was modifying the node that the main grid stores directly, if this common?

How would I be able top handle generating multiple paths at the same time using thread for this kind of setup?

2 hours ago, 3dmodelerguy said:

I though it was weird that the path generation was modifying the node that the main grid stores directly, if this common?

I'd guess that's not uncommon for simple pathfinding implementations. I've implemented pathfinding that way at times when there didn't seem to be need for a more sophisticated approach.

Are you in fact storing pathfinding state directly in the grid, with only a single state (e.g. G, H, and F) per cell? (I assume you wrote the code or are at least familiar with it, and therefore know the answer to this question.)

Quote

How would I be able top handle generating multiple paths at the same time using thread for this kind of setup?

I don't know if you've finished the tutorial series yet, but maybe that will be touched on there. You could also search for e.g. 'multithreaded a star' or 'multithreaded pathfinding'. Or, maybe someone who's implemented multithreaded pathfinding will offer some suggestions.

I haven't implemented multithreaded pathfinding myself. Although some fairly obvious ideas spring to mind, I'll refrain from commenting, as I suspect it's a well-explored problem with generally accepted solutions. I'm guessing some searching might lead you to said solutions, but if you get stuck you can always post back here.

As far as if I am sure the grid is directly being modified with path finding state, I am pretty sure that it is (if I understand how C# deals with values properly). While I did write the code I am using myself, the linked here is from the author and this code for the most part is the same. When path finding, these are the lines that get the nodes from the main grid:

https://github.com/SebLague/Pathfinding/blob/master/Episode 10 - threading/Assets/Scripts/Pathfinding.cs#L24-L25

https://github.com/SebLague/Pathfinding/blob/master/Episode 10 - threading/Assets/Scripts/Pathfinding.cs#L45

If you take a look at those methods, these are what they are doing:

https://github.com/SebLague/Pathfinding/blob/master/Episode 10 - threading/Assets/Scripts/Grid.cs#L123-L153

Based on the code, I believe those method are returning references in which case when they are modified here:

https://github.com/SebLague/Pathfinding/blob/master/Episode 10 - threading/Assets/Scripts/Pathfinding.cs#L52-L54

The instances being stored in the grid are being updated.

As far at the multi-threading, he does go into it however it does not work for me like it does for him. I deviated a little in the implementation but nothing that I would think would cause an issue with multi-threading (mostly changes so that the implementation only focuses on 2D support, not worrying about any 3D stuff).

I was able to prevent the issue by using locks in the path finding code and while that does provide the benefit of having the path finding code run outside the main Unity thread, the paths are still being generated serially in those threads which is not ideal so trying to see how I might be able to get the path finding processes to also run in parallel or each other.

4 minutes ago, 3dmodelerguy said:

As far at the multi-threading, he does go into it however it does not work for me like it does for him.

If you're interested in pursuing it further, maybe you could link to the video/tutorial/whatever where he talks about multithreading. It might be interesting to see what approach he recommends (and it might help in determining why it isn't working for you).

@Zakwayda This is the specific video on multi-threading:

Without digging into the tutorial further myself I can't comment directly on the implementation. However, I looked through the comments on the video and saw some mention of potential threading issues, including thread-safety issues related to modifying the state of the grid concurrently (the problem you seem to be running into).

I don't want to mischaracterize the tutorial at all, but you might look through the comments yourself if you're curious, as it seems at least possible (again, not saying this is the case!) that the implementation presented in the video isn't actually thread-safe and only works in the video demonstration due to circumstance.

In any case, in principle at least it doesn't seem viable to execute multiple searches at the same time if you're only maintaining a single state for each grid cell.

Copy the map chunks around the pathfinding entities. And give each pathfinding job it's own data. Run each job asynchronously. The entities can each grab the completed knowledge as it completes.

Generally,

I've avoided multi-threading w/ A* in the past as I viewed it as an effort whose performance trade-offs wouldn't justify the inherit complexities of introducing threading/locking into my pathfinding code. Though, to be fair, I've never personally profiled/implemented it. Just due to the amount of synching/locking/sharing of state of the threads needed to divvy up a single map between xx threads discouraged me, as I feared the performance would be quite lack-luster.

I could see multi-threading of A* working at a higher level (theoretically, maybe not in any practical scenario), e.g. I have six maps that are autonomous from one-another, and need to compute the best path for each simultaneously. And each thread would get their own map.

If you're looking for general ways to improve your single threaded performance there are some optimizations that can be had with A*, namely JumpPoint searching which effectively attempts to remove a lot of intermediate nodes from your OpenList

p.s. I could be totally wrong about multithreading w/ A*, and life, uh, found way ? but either way, give jumpoint searching a peek

@markypooch Unfortunately having the grid be uniform in cost is not something I can do so it would seem like jump point searching would not be practical.

Moving this code into its own thread does not seem like it is causing any measurable performance difference from my crude benchmarking as the code that is running is the same as if it was running in the main thread (expect that it is running within a lock block so there is the minor overhead for that). The real benefit that I was looking for in the the main Unity thread is no longer being blocked while the A* is running so even if I have a spike where I need to but path for like 30, 40, 50 agents (which might happen), the game itself will not lag (maybe the paths for those agent wont be immediate but that is much better than the game lagging while the path are being generated).

I have not implemented MT pathfinding either, but why not just have a copy of non static data per thread? (similar to DeadStacks suggestion). 

On 8/29/2019 at 10:15 PM, 3dmodelerguy said:

but having 2 or more seekers target the same target

If you have many seekers but just one target (or vice versa) you could do just one (Dijkstra) search from the target and break after all seekers have been found. (In case you had not thought about this - did not watch the tuorials)