New Pathfinding Algorithm

Hacker News

Share card

New Pathfinding Algorithm

Hello HN, I am creating a city builder video game and wanted to figure out a way to efficiently and realistically path hundreds of thousands of agents around the game world, with path preferences that the agents can utilize (such as wanting to walk through china town on their way to their destination) If you're not aware, algorithms like Dijkstra and A* will only return one shortest path between two points, which is not very realistic when you're walking around e.g. Manhattan, NYC and have a binomial coefficient number of possible paths to choose from. The other limitation is that these algorithms wont factor in path preferences (might not be entirely true for A*). So I created an algorithm that can cache all possible shortest paths between two points in N space (so all node pairs cached is N^2 space). Additionally, I figured out a way to store the data in a (C++) vector and maintain constant find/access time, since hash tables have a lot of memory overhead. I wrote up an introduction article (with video proof at the end, though it's my first YouTube video so bear with me ha ha) that will be followed by a technical one when I have time. If you have any tips on how I can put the algorithm through the ringer, and how I could create a white paper if successful, I would greatly appreciate it! I don't have any academic connections so I'm not sure who I could reach out to professionally. Link: https://www.yesboxstudios.com/2022/04/27/all-nck-shortest-paths-in-near-optimal-time-and-space-complexity-introduction/