Ich glaub das hat was mit der Zeitkomplexität des Algorithmus es zu tun. Da müsste auch die verwendete heuristic mit Einflüssen jnd auch die Anzahl der nodes. Und es gibt natürlich auch worst case scenarien. Bzw bei einem algo der ein optimales Ergebnis (immer den besten weg findet) auch dazu führen dass erst fast das gesamte Spielfeld durchsucht wird bevor der optimalste weg gefunden wurde. Heuristiken helfen zwar dass es da nicht alszu sehr ausartet aber passiert halt.
Da stellt sich jetzt aber die Frage ob hier nicht rum optimiert wird bevor überhaupt ein konkretes Problem auftritt. Werden mehrere Einheiten zusammen bewegt so kann reicht es aus den Weg ein einziges mal zu berechnen. Ob jetzt hier Worstcase Szenarien auftreten können hängt ganz stark von dem Graphen ab. Ist die Welt eher offen findet A* ziemlich direkt den kürzesten Weg. Man kann sich jetzt hier unglaublich viel Arbeit machen und nach irgendwelchen tollen anderen Lösungen suchen, oder man setzt das ganze einfach mal um und guckt ob es zu einem Problem führt.
Oft arbeitet man bei der Wegfindung auf verschiedenen Ebenen. Das bedeutet ich suche zunächst einen Weg in einem recht groben Graphen. Hier werden zum Beispiel nur statische Objekte der Umgebung berücksichtigt. Der Weg den ich hier finde könnte dann theoretisch weiter unterteilt werden. Als Beispiel suchst du den kürzesten Weg durch eine Stadt bei der alle Häuser betretbar sind. Zuerst möchtest du nur einen groben Weg mit Straßen und Häusern durch die du gehst. Danach guckst du wie du dich durch die Häuser selbst bewegen kannst. Danach guckst du wie du dich durch einen einzelnen Raum bewegen kannst. Das kann an sich alles noch mit der statischen Welt berechnet werden. Die dynamischen Objekte könnten dann im letzten Schritt oder sogar erst bei der Durchführung der Bewegung betrachtet werden. Durch so einen Ansatz kann es mir jetzt natürlich passieren dass ein Weg nicht mehr zu 100% optimal ist, wobei man sich vorher fragen sollte was am Ende das eigentliche Ziel ist. In einem Spiel geht es darum dass sich Einheiten plausibel und nicht dass sich diese unschlagbar intelligent und effizient verhalten. Sollte das alles nicht reichen dann kannst du die gefundenen Wege theoretisch auch noch irgendwo zwischen speichern.
tldr: A* ist nicht ineffizient. Du kannst mehrere Einheiten zusammenfassen um einen Weg nicht doppelt berechnen zu müssen. Du kannst die Wegfindung auf verschiedenen Genauigkeitsebenen berechnen. Du kannst gefundene Wege cachen.