Path finding is a tricky problem. I developed my own algorithm[0] for a city builder game (Metropolis 1998) I'm working on. I needed an efficient solution to finding _all_ shortest paths between two points, and after a few weeks of trudging through the mud, I ended up with a good one.
The algorithm can handle 100,000+ units path finding to their own unique destinations at 60 FPS. [edit: on a single CPU core]. The graph is processed once, and stores all possible paths (using near minimum storage)
Additionally, I can have additional preference weights in the graph so units can use paths that match their preferences.
Note: The video[0] no longer represents the look of my game, as I've moved on to isometric[1].
The algorithm can handle 100,000+ units path finding to their own unique destinations at 60 FPS. [edit: on a single CPU core]. The graph is processed once, and stores all possible paths (using near minimum storage)
Additionally, I can have additional preference weights in the graph so units can use paths that match their preferences.
Note: The video[0] no longer represents the look of my game, as I've moved on to isometric[1].
[0] https://www.youtube.com/watch?v=7q0l87hwmkI
[1] https://twitter.com/YesboxStudios