Comment by munificent

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.