Add multi-threading support

[roy-t]

Use cases

• Compute one path without stalling the game loop (ordering a unit)
• Compute a large number of paths in succession (ordering a squad, all AIs, etc..

I'd like to make this approach compatible with a typical Game Loop. Meaning that you should be able to check every frame if a given path query was completed. Maybe we can use a producer/consumer like scheme.

Another option is to use the async/await pattern. I think that would work great for computing a single path, but I'm not sure if its the best fit for a Game Loop. For complex environments it might take more than one frame to compute a path and this shouldn't stall paths.

Challenges

• How to make sure the cell costs are not changed while calculating a path without locking (copy the array?)

[chrisschwartzdev]

Hey! I've been searching around for simple AStar libraries and have decided to go forward with using this one for now. It looks very promising, but multi-threading support would make this a lot more appealing. I was just wondering how far along multi-threading support is, or if there's any rough timeline. Thanks, I appreciate it!

[roy-t]

Hey @BassaForte,

Unfortunately there has been no progress. I'm switching jobs and doing some work on the side so I haven't had much time.

But I've thought about it a fair bit. So far my conclusions:

• Doing an individual path search multi-threaded is nearly impossible with A*. So far all my attempts have made it slower instead of faster, even for very long paths.
• The way to go would be to create a wrapper in which you can queue path queries which will be executed on the thread pool. But there are some gotcha's:
  • What if someone modifies the grid after a path query was queued, what if someone modifies it during the computation of the path (that would lead to bad things). Probably best to only guarantee that the path was valid/shortest for the moment you queued the query.
  • How to do the callbacks when a query is done? Putting the results in a ConcurrentQueue? Callbacks? Events? Observables? I have not yet figured out which approach is the best for the usage scenarios.

Can I ask, what are you using this library for? It will give me a better idea on who to tailor the implementation to.

Depending on your feedback and the time I have the coming days I might create a PR request with minimal prototype for you to test. No promises :).

[chrisschwartzdev]

@roy-t Thanks for replying! It's cool, I can totally understand that you haven't had much time. I was just wondering is all :) There are some interesting points in your conclusions.

Since you asked: in my application, the grids would be mostly static. I've been working on a 2D top-down MMORPG game (in Unity) where the players can move freely, but NPCs and monsters use path-finding to move around randomly (within a limited distance of their spawn point) and follow players to attack them. For my grid data, I'm exporting collide-able tiles for the server to read and use for path-finding and player movement verification. Since the tiles are being exported from Unity, the general use for the path-finding is that the grid will be static. The only instance that I could see them not being static is if I decide to add some randomized dungeons (which is something I'd love to do at some point).

If it helps any further, my plan is to have the game world be a relatively large size. The world itself is already split up into regions, for the purpose of the interest areas for players and which entities they should receive updates for. It'd likely be too much for the server to generate paths within a giant grid of about 1280x1280, so perhaps I would have one grid per 40x40 region.

Sorry if that was a bit much to read. Thanks for your time and I appreciate the help!

[bradzoob]

This is a fabulous lib, thanks! have been using it for a while.

Yeah it's not deterministic so won't work in parallel for a single job as far as i'm aware (i'm not educated to know otherwise, but intuitively it's a brute force operation and as such needs to be domain aware, hence parallelism is traditionally off the cards, but maybe Compute handles these things with magic now?), BUT you can use an interpolation of broad graph values for long path determination, breaking each chunks cell entry/exit path finder into it's own thread/process and manage it via a queue, while not perfect this is pretty much the only solution I know of / could come up with for large graphs (which is virtually ALL graphs in 2018 lol). You could then set multiple LOD scales of your graphs depending on the range required (i only need 2).

I already multithread queue this lib for navigating entry/exit points in chunks, but obviously not calculating all cells multithreaded but just dispatching each in-chunk path request to a thread as needed (when path within a chunk is required), hence can only use about 64x64 cells for minimal frame impact as this lib is computationally heavy compared to straight 2d unweighted A*, although it may be my poor understanding of .NET/Unity that is leading to the speed issues, benchmarks provided in earlier versions of this lib i couldn't even get close to (5x the computational cost), I did have to hack Unity to use 4.6.NET though, so it could be that, now it's native so maybe I should revisit the benchmarking and maybe start using the proper parallel jobs architecture :)

In any case you'd still need to use chunk / cell navigation on anything over 512x512 (mine is 16384x16384xN heights, if you want to maintain realtime tick and can't afford units to be idle while waiting for a single gigantic path array.

I'd love it if you implemented a Multi-threaded architecture with path completion callbacks that provide the ID of the request so that the calling method can map it back to the original action as I'm certain it would be far better than mine. I'm still trying to figure out this beast known as the GC and what it truly wants. :P

Happily using this lib to drive river pathing on terrain. There's obviously some issues with the range available for the broad check, as I'm limited to 64x64 cells at any scale, which leads to angular paths that don't look natural, but I've been tricking it with various simplex "bubbles" to wind the paths a bit, but every now and again i come back here to see if any performance breakthroughs have been made so i can wrench just a little bit more performance out which would allow me to increase that cell range and get more natural winding of rivers as they descend into the sea :)

[roy-t]

Hey brradzoob,

Thanks for your praise :D

sorry to hear that your running into speed issues. I gave this somethought and I think the more you change the weights the more the worse the A* prediction is, thus the worse runtime you have. Try to have most cells weighted at 1.0 for the best performance.

Btw what do you mean by this library not being deterministic? There is no randomness involved so you should get exactly the same path every time.

Btw 16384 is gigantic :D, I never thought the library would be used for such large maps. Maybe in your case you're better of with a graph based A* algorithm. Use it on pre-computed entry and exit paths for chunks. Then only use grid based search inside chunks.

Btw for generating rivers check out the blog and Twitter of Amit Patel: https://twitter.com/redblobgames

[bradzoob]

Sorry my bad, i went into an optimization frenzy straight after this post, and i gained a lot of performance with pathing, basically lopped 70% execution time off (editor attachment/unity2018.2/IL2CPP). It's still not great but it's at least buying tickets to the ball park of great :)

Oh, i've read heaps of his older stuff back in the day on various gamedev things, one of my fav reads was: http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/

But i see he's doing fresh new things!

hah, i was going to mention I'm intending to shift your A-Star to AI duties where i can queue/thread and it's not time sensitive but for pre-compute game init phase i'll use a DAG (+some winding trickery), and that's what Amet was illustrating in this very article I first read many years ago. This is a bizarre twist of fate, i've returned home to understand the lessons of former masters :P Thanks!

[bradzoob]

Deterministic: I mean it's iterative, you can't run the search in parallel per query because the results feed back into the subsequent query, so a path point isn't known until it's discovered, so not really appropriate for GPU calculations which is about brute parallelism except where you need to run thousands of them over very small domains, as I've seen done with compute shaders, but presumably you'd be unable to do the same over a larger domain because as the domain grows the usefulness of parallelism provided by the GPU is lost.

Yeah 16384 seems large, but I wasn't happy with games like Rimworld using 400x tiles as a benchmark for "huge", which i understand to be about the reasonable extent a fast A* can be frequently run before exponentially losing performance, so 16384 seemed a nice number to challenge :) 16384 isn't really even that large though. I was going to make it unlimited but wanted to keep the initial scope finite while figuring out how to do river pathing for performance over large areas, then figure out how to cordon off parts of the map for pre-rendering, because river chunks need to be connected you can't pre-determine them over infinite distance etc. Might use some sort of broad cellular network for this in the future, so that rivers exist in determined geometric regions and when first discovered will generate the node network required within that region.