Games typically precomputed much of the pathfinding information and assumed a non-destructible world. The whole thing in the article about recomputing the blocked/non-blocked state is a thing many games with pathfinding simply didn't do at runtime at all.

They usually pathfinding on a larger granularity with more of the world aligned to a larger grid. Since asteroids are so organically shaped and freely movable in this case, it necessitates a finer pathfinding grid. It looks like they're roughly 6-8 pixels here. In an older game, it could easily be 16 or more. Pathfinding cost scales quadratically as the grid gets finer.

Also, while CPU speeds have increased, RAM access rates have not kept up. It's quite hard to actually keep the CPU busy and not have it stalled waiting for memory very often. "Data-oriented design" is a whole little subfield dedicated to dealing with this problem.

Hey, I'm the developer of the game in the blog post. What takes several milliseconds is the number of world queries that need to be made to detect blocking objects and also object proximity. This is why I went with a quad tree to try to speed that part of things up.

Once those queries have been made the actual search is very fast. The problem then is that those queries need to be made again due to the dynamic nature of the game world.

You probably realized its absurd to have 50000 square nodes in your pathfinding graph and instead divided the area into 50 convex polygons (if that). Convex polygons being the basic shape because you can go directly from every point within to every other point within.

I'm guessing it might be multiple paths for multiple NPCs. But not sure.

And if you were performance conscious, you certainly would not do lots of pathfinding from scratch on every frame.