You can do a lot of shortcuts with the pathing, because you are doing a lot of pathing on a graph that doesn't change much from frame-to-frame.

Exactly. The only time you should be calculating paths is after the player places new roads. Repeatedly calculating paths on a fixed graph is a huge waste of time!

It’s even easier than that since each agent only needs to plans a path once, when they start their trip. After that they are simply following a cached path, removing road segments from it as they go. Most games will simply not recalculate those paths when you change the network, because it causes a lag spike every time the player makes a change, and because most routes wouldn’t end up changing. Better to just have cars ignore roads that didn’t exist when they departed, and have them vanish if they need to take a road that has since been deleted.

My graph is changing a lot, my whole environment from walls to objects is destructable and contains complex logic like access controlled doors.

Maybe your game doesn't change much. Lack of good pathfinding is what's constricting that the most. If good pathfinding existed, games in general could become more dynamic.

You could look into whether good-enough approximations exist?

Especially if the moving entities in your game aren't supposed to be omniscient. They could gradually learn about what good enough paths are.

I suspect pre-generation caching, game design, multi-core, SIMD versions of algs, etc. have evolved a lot.

Real-world performance isn't that determined by the form of the time-complexity.

>Simple fact is, pathfinding is a performance bottleneck that hasn't been solved yet.

But we got thousand times faster CPUs than at Sim City 2000 times.

And they have multiple cores. And if that is not enough there are GPUs with even more compute.

and better algorithms

But that still doesn't change the fact that path finding must necessarily occupy a larger and larger fraction of the cpu time as the player builds a larger and larger city. Each path becomes longer, there are more paths to plan, etc. In order to maintain an acceptable frame rate in a large city on the minimum spec computer at the time of release, Cities: Skylines has a fixed limit of 16k moving vehicles. This caps the time spent path finding as well as maximum frame time because once the vehicle limit is hit, agents start teleporting rather than being forced to traverse the map.

> no hardware acceleration exists

I'm picturing an alternate history where in addition to dedicated graphics cards, we also start building dedicated common algorithm cards - NVidia and AMD duking it out over whose hardware-accelerated sorting implementation performs best, Phoronix benchmarking how each companies' Linux drivers handle A* etc :)

GPUs are that card given the GPGPU craze in days past.

You're not wrong, but the idea of a sort of alt-history of various acceleration cards really tickled me :)

Between Dwarf Fortress and Factorio's ability to simulate huge numbers of agents, I'm not convinced.