Im working on a game in the same vein: Archapolis, a city builder with real time traffic simulation and interior views of your citizens homes (which you can customize/build yourself if you want), so you can watch them live their lives. I'd like the player to have a more hands on approach to managing the city as well.
I created a path finding algorithm that can simultaneously path hundreds of thousands of units to random destinations at a comfortable frame rate (or around 100-200K like in the video using one CPU core). Units can choose from any of the shortest paths between two points (there are many in a grid), and from those paths, can also choose the path that matches any preferences they have.
I’m confused. The game says 55 fps, but it looks like 4? Is it just computing positions at a lower rate while rendering at 55?
Anyway, from my experience with Songs of Syx, which also has large scale pathfinding, I’d like to encourage you to find a way to spread it (and other calculations) around. When you reach larger city sizes, the game becomes noticably slower on some ticks. Still smooth, but when your guys are moving at 4x speed, and everyone suddenly slows down to 2x speed (presumably because calculations take so long that running at 4x isn’t possible any more), it’s very jarring.
Right now the units are moving in tile-sized increments. I'll be implementing floating point movement soon. I move the map around while the units are moving and you'll see its not at 4 FPS.
I think with any quasi-infinite growth game, you are going to run into a problem of it slowing down, eventually. That's what inspired me to create this algorithm. I wanted a game that could scale, and traditionally path finding is a CPU intensive task.
The video I linked is out of date, I'll be making a new one soon.
Now: building the path finding graph is now stored in a vector (i.e. array) instead of an unordered_map (and still has constant time access/find). This cut CPU cycles by 66% since a vector doesnt use linked list/pointers/store a hash, and reduced RAM requirements by 75%. Then I parallelized that part of the code base.
So for my 6 core machine, I can find all the all-pairs, all-possible shortest paths in a 50 x 50 grid of roads in 10 seconds. This is about 13 square miles of city if each block is the size of a Manhattan block. I'll be working around this time by implementing a planning mode so it only updates as needed.
Currently I can close edges (i.e. an individual road between two intersections), but right now I would have to rebuild the path finding graph each time the graph changes. I was thinking of this problem too, cause it would be really cool to temporarily close a road down for repairs/construction. I think there is a way to make it work without needing to rebuild! Just havent had time to look into it.
The way I did it in Citybound is to assume that the graph constantly changes anyways (also because the player can add/remove roads quite rapidly) and route the cars more like packets on the internet than with static A*-ish algorithms.
That way, road nodes can propagate changes locally.
Interesting, I assumed the roads were not going to change frequently (but rather, in bursts). So I used that premises to develop my algo. To enforce this behavior (on a code level), I will be adding a "planning" mode, where roads can be placed freely/frequently. Once the user sends the plan off to be constructed, then the graph will update. I may go one step further and have construction (i.e. graph updating) only happen at night, and give the user something else to do while its updating.
That being said, if they have a modern machine, then there will be no need for this at all (just need to figure out the avg user CPU GHz & core count). It takes 10 seconds for my algo to find the all pairs/all possible shortest paths between two nodes on my machine for 10,000 nodes, which by that point is a HUGE city.
The reason I did not go with A* is because it doesn't scale to 100K+ units and it always chooses the same path.
Here's a tech demo of what I've been working on: https://www.youtube.com/watch?v=7q0l87hwmkI
I created a path finding algorithm that can simultaneously path hundreds of thousands of units to random destinations at a comfortable frame rate (or around 100-200K like in the video using one CPU core). Units can choose from any of the shortest paths between two points (there are many in a grid), and from those paths, can also choose the path that matches any preferences they have.
Very early stages of development still!