Jump to content
  • Advertisement
3dmodelerguy

C# Doing AStar Pathing Finding In Threads

Recommended Posts

I will keep the idea of having each thread has access to its own grid to be able to parallelize the path finding if needed however the solution of locking the grid seems to be work well for me now so just going to stick with that until it becomes a problem.

The more common use case it going to be having many seekers and targets at the same time so I think I would rather stick with one path finding solution if possible instead of trying to implement different algorithms for different use case (seems like that could get really complicated) and A* seems like the more generally use path finding solution (and the first one that I found a good video explaining the algorithm that actually made sense to me).

Share this post


Link to post
Share on other sites
Advertisement
14 minutes ago, 3dmodelerguy said:

(seems like that could get really complicated) and A* seems like the more generally use path finding solution

No, it's the opposite of both - Dijkstra is the same algorithm just without the heuristic, so simpler, (older,) and just one line of code to change. Dijkstra is also more general as it works on any graph (i use it for meshes where A* would make no sense because no heuristic can be used to approximate geodesic distance over curved surface).

But just to let you know. I assume you would require a pretty large number of seekers with the same target to beat A*.

Share this post


Link to post
Share on other sites

Another strategy is simply allot some time each frame for path-finding. Run the jobs in parallel at that time but wait for all path-finding jobs to complete before continuing. No locking necessary. Time cost would roughly be that of the slowest job. That will be cheaper than running all your path-finding jobs one after the other in the frame, but different to running them in the background (which requires a snapshot of map data). You would have to benchmark to see how long your jobs are taking to work out the best way.

Actually, when I think of path-finding, I don't see how locking is useful at all. If you've locked the map against writing, then you can't be doing any updates in that time, so you might as well just be doing your path-finding. And if all you're doing is path-finding then you don't need to lock the map. The real issue is not locking the map and preventing it from being changed, but recognizing that it may be changed, and that your path-finding result may be incorrect by the time it is executed or during it's execution.

Once you accept that the map may change then it doesn't matter that a path-finding job produce an incorrect result. Because a failed navigation can simply trigger a fresh path-finding job.

Share this post


Link to post
Share on other sites
On 8/30/2019 at 7:58 AM, DeadStack said:

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.

As a former professor of CS focusing on AI, I would tell a student to implement this exact solution.  I would then state that the information for the independently created paths should be copied back into the main map.

One of the "gotchas" for an implementation like this would be states that would alter the pathways.  Colliding with other members, or changes in the state of the map, such as doors opening or closing, "cave-ins" or other map restructuring are among the issues you would need to deal with when copying map chunks to the individual entities to pathfind through.  To solve that quandary, you would need some type of alert, callback, or other signaling method from the main thread to your pathfinding threads that will alert the pathfinding threads of possible map changes.

A number of other things to think about exist, but DeadStack's solution is where you should start.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!