Ich habe versucht herauszufinden, wie man so etwas wie die Wegfindung in Starcraft 2 implementiert. Ich suche nicht nach all den ausgefeilten Funktionen wie Beflockung, Warteschlangen usw. Tatsächlich gefällt mir, wie in Starcraft 1 die Einheiten sich gegenseitig stören würden andere. Aber ich möchte einen besseren Wegfinder als den in Starcraft 1 verwendeten.
Aus den Google-Suchanfragen, die ich durchgeführt habe, haben die verschiedenen Antworten etwas mit A * über einem Navigationsnetz und / oder mit einer Art "Sichtbarkeitsdiagramm" zu tun. Aber ich habe etwas widersprüchliche oder unklare Antworten bekommen, was ich tun soll.
Eine Sache, über die ich gelesen habe, hat etwas damit zu tun, A * über den Eckpunkten eines Dreiecksnetzes (dem Navigationsnetz) zu machen. Und dann irgendwie "den Weg begradigen", was ich nicht kann. Aber das garantiert keine Optimalität, oder?
Eine andere Frage, die ich hatte, ist, wie die Wegfindung von Starcraft 2 mit der Tatsache umgeht, dass die Einheiten Scheiben mit einem endlichen Radius und keine Punkte sind, wenn es um Ecken geht. Und wie man mit dynamischen Hindernissen wie Leerlaufeinheiten oder sogar anderen beweglichen Einheiten umgeht.
Ich bin auf der Suche nach detaillierten Erklärungen und nicht nach den allgemeinen Übersichten auf Super-High-Level-Ebene, die für Suchergebnisse typisch sind.
Wenn es darauf ankommt, habe ich mir bereits Amits Notizen zur Pfadfindung angesehen . Ich habe von Computational Geometry: Algorithms and Applications gehört, aber nicht gelesen . In einem Blogbeitrag über eine AI-Navigationspräsentation auf der GDC 2011 wurde erwähnt, dass Starcraft 2 eine eingeschränkte Delaunay-Triangulation für ein Navmesh verwendet. Obwohl der Blog-Beitrag die Steuerung von Boids und die "Horizontanalyse" erwähnt, wird nicht genau erwähnt, wie die Kernpfadfindung auf dem Navmesh erfolgt.
quelle
Antworten:
Wenn Sie Starcraft 2 installiert haben, öffnen Sie den Karteneditor und schalten Sie die Pfadfindung um . Sie können sehen, wie das Navigationsnetz aufgebaut ist, wenn Sie Gebäude und andere Hindernisse platzieren.
Sollte kein Problem sein - Starcraft 1s Wegfindung war albern. Dieser Blog-Beitrag eines Programmierers spricht darüber.
Es geht darum, die KI nicht mehr als optimal dumm zu machen . Ihre Einheiten haben eine Zick-Zack-Bewegung zwischen den Knoten, wenn Sie nicht ein wenig glätten.
Wenn Sie eine Pfadplanung durchführen , haben Sie eine Verfeinerungsphase, in der Sie sich ansehen, durch welche Knoten Ihre Einheit gehen muss, um zum Ziel zu gelangen, und dann beginnen Sie, überschüssige Knoten in der Mitte des Pfades zu entfernen, die wir nicht benötigen Folgen Sie, dh wir können ohne statische Kollisionen direkt von Knoten A zu Knoten C über B gehen, also ignorieren Sie B vollständig.
Dies führt dazu, dass der Weg gerade wird.
Wenn Sie eine solide Erklärung wünschen, wird dies bereits in Büchern ausführlich behandelt (sogar mit funktionierendem Spielcode). Wenn Sie also etwas Geld zum Brennen haben, lesen Sie Programming Game AI By Example und / oder Artificial Intelligence for Games . Beide diskutieren diese Themen ausführlich.
quelle