Pathfind 1M agents to unique destinations in my video game

Hacker News

Share card

Pathfind 1M agents to unique destinations in my video game

Try it out here: https://yesbox.itch.io/archapolis Or video: https://www.youtube.com/watch?v=x0HCnQqF5K4 Hi HN I've been working on a city builder game for the last seven months. The first bar I wanted to pass was creating an efficient and more realistic path finding engine. Finally, version 0.1.0 of my game Archapolis is released! This is a toy/tech demo, but any and all feedback is really important to me, hence I'm releasing it now (for free). I'd also like to get an idea how well my code runs on a variety of machines, so if you feel like testing it out, I would love to hear from you and your results! I'll talk a bit about the path finding code here: - It will find all possible shortest paths between two points in nearly the same time as Dijkstra's, and store them efficiently in a (C++) vector (i.e. array) (max possible paths is the binomial coefficient formula) - An agent can access/find a path in constant time (just like a hash table) using some arithmetic (since the vector index is the "key"). - The game will generate the all pairs all possible shortest paths once you place a unit down, and update each time the road network changes. - The path finding algorithm can also utilize preference weights (e.g. beauty, tourism, commercial, cultural neighborhood...) stored in roads. An agent that has a preference will take the shortest path from all possible shortest paths that match their preference. - In the download, these are colored roads for now, so units that match the road color will prefer those roads. - Its multi-threaded. On my machine, finding / storing all pairs all shortest possible paths in a 50 x 50 grid (with 9,800 nodes) takes 17 seconds (with six cores) and needs 2.5 GB of RAM. This is an extreme stress test. If using Manhattan block sizes, this is around 13 square miles of city, or roughly nine Cities: Skylines tiles. - In game, roads will be planned first, then placed all at once so only one update is needed. - I'm really happy with the results. Not only will units utilize all shortest paths between two points, the preference weights gives personality to each unit, so part of my unit AI is already done! - One other note: the one way roads are faster roads (less "weight"), though the agents will still move the same speed over them. They just create faster/shorter paths for testing the algo.