Wegfindung und Kollisionsvermeidung auf Mobilgeräten

Derzeit entwickle ich ein Diablo-ähnliches Spiel für die mobile Plattform (iphone5 +).

Eine einfache A * -Suche findet den Pfad, aber die Vermeidung von Kollisionen muss noch berücksichtigt werden.

Es werden ungefähr 50 Monster gleichzeitig aktiv sein, daher ist die Leistung sehr wichtig.

Ich habe einige Methoden gefunden, die funktionieren könnten.

1. NavMesh + RVO

   Die Neufassung / Umleitungsbibliothek funktioniert gut pathfinding, aber die Crowd-Simulation erreicht schnell das Limit (mehr als 5 ms für 30 Agenten).

   Eine andere Bibliothek RVO2 scheint in Ordnung zu sein (weniger als 2 ms für 50 Agenten), aber die Bibliothek hat einige Lizenzprobleme.

2. Strömungsfelder + Physik-Engine

   Viele RTS-Spiele verwenden diese Methode, aber es scheint, dass eine Physik-Engine erforderlich ist, um Kollisionen aufzulösen. Wenn viele Agenten kein gemeinsames Ziel haben, kostet diese Methode möglicherweise mehr als die herkömmliche A * -Pfadfindung.

3. Lenkverhalten + Physik-Engine

   Das Lenkverhalten enthält viele Konzepte, von denen ich denke, dass simple avoidance behaviorsie funktionieren könnten (biegen Sie einfach nach links / rechts ab, wenn sich etwas vor Ihnen befindet), aber die Methode erfordert immer noch eine Physik-Engine, um zusammenzuarbeiten.

Ich bin mir immer noch nicht sicher, welche ich verwenden soll. Vielleicht gibt es andere Methoden zur Pfadfindung und Kollisionsvermeidung.

PS Halo:Spartan Strikeverwendet Havok AI (basierend auf RVO?), Aber ich habe in diesem Spiel nicht viele Feinde gesehen, daher frage ich mich, ob die erste Methode (NavMesh + RVO) auf mobilen Plattformen gut funktioniert.

Dies ist eine ziemlich interessante Frage, und ich werde versuchen, mit dem beizutragen, was ich kann.

Zunächst denke ich, dass Sie die Grenzen für das Spiel, das Sie erstellen möchten, klar definieren und diese Fragen definieren müssen (einige wurden möglicherweise bereits beantwortet).

• Wie weit ist das Monster Aggro?
• Wie viele Monster gleichzeitig ist dein Ziel?
• Wie ist dein Terrain organisiert? Ist es gekachelt?
• Wie viel Kollisionsvermeidung möchten Sie?

Zu zitieren eine Antwort von hier ab , wie Wegfindung in starcraft erfolgt 2:

Starcraft II verwendet eine eingeschränkte Delaunay-Triangulation des Kartengeländes und der Gebäude, um ein Navmesh zu erstellen. Ein * mit einem Trichterfilter wird verwendet, um entlang dieses Netzes unter Berücksichtigung der Einheitsradien zu verlaufen. Darüber hinaus werden lokale Lenkungs- und Kollisionsvermeidungsschichten hinzugefügt, einschließlich einer kooperativen Funktion "Leerlaufeinheiten aus dem Weg schieben", bei der es in bestimmten Fällen möglich ist, eine Einheit zu verschieben, anstatt sie zu umgehen. Darüber hinaus werden parallel bewegte Einheiten zur Kollisionsvermeidung ignoriert, da garantiert werden kann, dass sie sich nicht gegenseitig beeinflussen. [...] SC2 verwendet sechs Lenkkräfte: Folgen, Beflocken, Gruppieren, Trennen, Vermeiden und Ankommen.

Kehren Sie also zu Ihren drei Aussagen zurück:

1. NavMesh + RVO -> Wenn Lizenzprobleme vorliegen , ist dies keine Option. Es könnte jedoch die einfachste Implementierung sein.
2. Flow Fields + Physics Engine -> Es hängt ehrlich davon ab, aber es scheint in einer semidynamischen Umgebung wirklich rechenintensiv zu sein, wie Sie es möchten
3. Lenkverhalten + Physik-Engine -> Lenkverhalten scheint mir der richtige Weg zu sein. Auf diese Weise können Sie einige hübsche Herdenverhalten für Ihr Spiel definieren, zum Beispiel abhängig vom Monstertyp. Und es passt gut zur Mob-Nummer. Allerdings würde ich mich zur Kollisionserkennung von der Physik fernhalten. Ein einfaches Vermeidungsverhalten ist ausreichend, um die Geschwindigkeit zu verringern oder zu erhöhen, zu drehen usw.

In einigen Hinweisen zum Lenkverhalten können Sie mit den gewünschten Bereichen so viele Lenkkräfte definieren, wie Sie benötigen. Sie benötigen mindestens 3 für Beflockung / Anziehung / Abstoßung, aber mehr sind wahrscheinlich interessant.

Versuchen Sie dann, eine Bibliothek zu finden, die Lenkverhalten ausführt, um festzustellen, ob es Ihren Anforderungen entspricht ( so ? Ich kenne keine wirklich, aber es existiert).

Wenn die Bibliothek nicht Ihren Anforderungen entspricht, können Sie Spaß haben! Es gibt jedoch genügend Ressourcen und Algorithmen, um das Beflockungsverhalten selbst zu implementieren. Beispiel 1 Beispiel 2

Wenn Sie sich für die Implementierung entscheiden, sollten Sie wissen, dass einige nette Optimierungen erforderlich sind, da der Umfang Ihres Agenten beispielsweise durch seine Position in der Herde verringert wird. Es sollte sowieso in einigen Algorithmen enthalten sein.

Nun, das ist das Beste meines Wissens, ich bin mir sowieso nicht sicher

Wenn die feindlichen Pfade nicht sehr dynamisch sind (Dynamisch wäre, dass jedes Paar Agenten verschiedene Ziele angreift und die Pfade zu diesen Zielen alle paar Frames aktualisiert werden müssen).

Dann würde ich eine Kombination aus Strömungsfeldern und Lenkverhalten durchführen, wenn die Leistung Ihr Hauptanliegen ist. Es gibt einige kompliziertere Themen wie die Aufteilung des Speicherplatzes Ihrer Agenten, sodass es einfacher ist, Nachbarn zu finden, aber es ist die beste Wahl für die Leistung. (Entfernen Sie Ihre A * -Suche und verwenden Sie Flussfelder, um Ihre Agenten zu leiten.)

Diese beiden Algorithmen zusammen werden im Allgemeinen als die am besten optimierte Lösung für Szenen mit hoher Agentendichte und wenig dynamischem Pfad angesehen.

Ich würde Physik vermeiden, egal welche Option Sie haben, da sie schwer werden kann.

Kollisionen zwischen Agenten können fast ausschließlich durch Lenkverhalten behandelt werden, und Flussfelder reduzieren das Gewicht von 50 Agenten, die Pfade berechnen. Beachten Sie jedoch, dass Flussfelder immer teurer werden, je größer Ihre Kartengröße und je kleiner Ihre Rastergröße ist und je dynamischer Ihre Zielauswahl sein muss.