Strategien für den Umgang mit Menschenmengen an Engpässen

Ich habe kürzlich meine Spiel-Engine von Lenkverhalten auf impulsbasierte Bewegung mit der richtigen zeitbasierten Kollisionsauflösung umgestellt. Dies hat so viele Probleme gelöst (kein Tunneln mehr, yay) und die Simulation viel stabiler gemacht. Mit der Stabilität ist jedoch ein neues Problem verbunden.

Die drei Bälle begannen ihre Reise in der Nähe des unteren Bildrandes. Ihr Ziel war, wo der rosa Ball aufgehört hat. Unterwegs stecken die roten und grünen Kugeln an der Drosselstelle in der Wand fest.

Früher konnte ich mich auf Gleitkommafehler und die allgemeine Instabilität des Lenkverhaltens verlassen, damit sich die grünen und roten Kugeln gegenseitig drängeln, bis sie den Drosselpunkt erreicht haben. Bei richtiger Kollisionsauflösung heben sich die auf die Kugeln einwirkenden Kräfte gegenseitig auf, was dazu führt, dass die Kugeln vollkommen ruhig bleiben.

Welche Methoden werden üblicherweise verwendet, um solche Situationen zu lösen? Vielleicht würde eine Art Prioritätswarteschlangensystem funktionieren, obwohl ich sehe, dass es komplex wird, wenn ich die Priorität zwischen mehr als zwei Objekten festlegen muss.

collision-resolution Fibbles
quelle

Ich bin auch enttäuscht von der Steuerung des Crowd Managements. Könnten Sie bitte ein paar Links zu "impulsbasierter Bewegung" in die Frage einfügen?

Kromster

Ein Impuls ist nur Kraft * Zeit. Ich wollte damit sagen, dass ich zu einem physikalisch basierten Modell übergegangen war, bei dem die kontinuierliche und nicht die diskrete Kollisionserkennung verwendet wurde. Lenkverhalten respektieren Dinge wie Newtons Bewegungsgesetze nicht wirklich, sie wurden entwickelt, um Vogelschwärme nachzuahmen, anstatt eine physikalische Simulation zu sein. Ich habe eigentlich keine Gamedev-Links für Bewegung, es ist wirklich nur Highschool-Physik. Christer Ericsons Buch Real Time Collision Detection ist jedoch so ziemlich das Spiel, das für die kontinuierliche Kollisionserkennung entwickelt wurde.

Fibbles

Antworten:

Weisen Sie jedem beweglichen Objekt einen eindeutigen Index zu und verhindern Sie, dass ein Objekt mit einem höheren Index einen Agenten mit einem niedrigeren Index verschiebt. Auf diese Weise können "ältere" Objekte "neuere" Objekte anstoßen, aber nicht umgekehrt. Dies ist weniger aufwendig als das Anstehen in der Warteschlange. Im Wesentlichen fungiert der Index als Bewegungspriorität.

Pikalek
quelle

Ich habe dies implementiert und es funktioniert, dass Einheiten nicht mehr stecken bleiben, obwohl ich sagen muss, dass es nicht immer schön ist. Einige Vorsichtsmaßnahmen: Verwenden Sie den Index nur, um die Priorität für das Bewegen von Objekten derselben Masse zu bestimmen. Große Objekte sollten kleine Objekte auf natürliche Weise aus dem Weg schieben. Verwenden Sie den Index nur, um die Priorität für Objekte im selben Team zu bestimmen. Ein feindliches Objekt sollte nicht in der Lage sein, als unbewegliche Wand für ein Spielerobjekt zu fungieren, nur weil es zuerst erzeugt wurde und daher eine höhere Priorität hat.

Fibbles

Ich hatte weder an Masse noch an Team gedacht. Ihre Optimierungen scheinen der logische Weg zu sein, um meine Antwort zu patchen.

Pikalek

Fügen Sie der Pfadfindung Zeit hinzu

Hier ist ein Artikel, der über diesen Zeitwürfel spricht: http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Applications_files/coop-path-AIWisdom.pdf

und hier ist eine Objective-C-Implementierung: http://allseeing-i.com/ASIPathFinder

Rakka Rage
quelle

Ich habe dies bereits gelesen und implementiert. Selbst mit mehreren Threads ist es in meiner Situation nicht sehr nützlich. In einem RTS-Spiel kann es Hunderte von sich bewegenden Einheiten und Kartengittern geben, die mehr als 500 Quadrate pro Seite haben. Der Aufwand für die Berechnung zeitbasierter Pfade für jede Einheit ist einfach zu hoch. Nur um hinzuzufügen, ich sage nicht, dass Rakkarages Antwort falsch ist, es ist ein sehr ordentlicher Algorithmus. Ich sage nur, dass die Situationen, in denen es nützlich ist, durch seine Komplexität begrenzt sind.

Fibbles

ya ich führe einfach meinen gesamten Pfadfindungsalgorithmus in jeder Runde erneut aus, anstatt dies vollständig zu verstehen und zu implementieren, aber ich denke, ich muss es irgendwann

tun

Eigentlich denke ich nicht, dass Sie es reparieren sollten. Wenn (ich kann raten) die Pfeile Kraftvektoren anzeigen, die auf eine Kugel an einer beliebigen Position im Gitter angewendet werden (wahrscheinlich "bi-linear" oder ähnlich interpoliert oder irgendwie "analoger" als nur 0/1), dann ist das Verhalten ist körperlich korrekt und Sie sollten sich selbst zu einer gut benommenen Lösung beglückwünschen.

Die beiden Kugeln sind in einem guten Gleichgewicht, da sie dort sitzen und sich gegenseitig hassen. Wenn sie sich etwas nach rechts bewegen, wirkt sich der "Kraftpfeil" nach rechts anscheinend etwas stärker auf die rechte Kugel aus (und umgekehrt auf die linke Kugel; etwas weniger), und so bewegen sie sich zurück zum Gleichgewicht. So sollte es sein.

Imho, was repariert werden sollte , ist die Wand oder die Kugelgrößen oder etwas anderes unter den Bausteinen selbst. Sie haben eine Unmöglichkeit geschaffen und das richtige Verhalten in dieser Situation ist dementsprechend ein Stillstand (Entschuldigung für den Missbrauch von Wörtern, ich hoffe, Sie bekommen sie trotzdem :-)).

Deaktivieren Sie stattdessen möglicherweise die nächsten Pfeile für die linke / rechte Kraft oder ordnen Sie sie auf eine andere Weise an, die nicht symmetrisch ist und nicht zum Ausgleich anregt .

Ich denke, es wäre eine schlechte Lösung, es künstlich zu reparieren ... würde zu früh haarig werden.

Sturmwind
quelle

Dies beantwortet die Frage nicht. Ich verstehe Ihre Motivation, aber letztendlich ist die Frage, wie Sie mit der Situation umgehen sollen. Wir kennen die Spielabsichten nicht, daher liegt es an Fibbles, ob dies ein Problem ist oder nicht. Durch Ändern der Wand kann der Zweck des Chokepoints geändert werden. Die Frage ist ein gültiges Problem, das gelöst werden kann.

Felsir

Meine Antwort lautet grundsätzlich: Ordnen Sie die Kräfte (neu) an oder ordnen Sie etwas anderes im Szenario neu an, aber verschlüsseln Sie den Physiklöser nicht (" Imho, was repariert werden sollte, ist die Wand oder die Kugelgrößen oder etwas anderes unter den Bausteinen selbst. "). Die Frage lautet: " Welche Methoden werden üblicherweise verwendet, um solche Situationen zu lösen?" Ich denke, mein A ist eine "häufig verwendete Methode" und eine Lösung für das Problem. Zum Beispiel ersticken Online-Minigolfspiele (an die das Q sehr erinnert) die Bälle, wenn die Umgebung dies verlangt. Erratische Physik ist ein schlechter Weg, imo.

Sturmwind

Ich bin damit einverstanden, dass der Physiklöser im Takt bleibt. Die Frage besagt, dass die Sphären das Ziel suchen sollten, im Grunde genommen, wie das Verhalten der Agenten geändert werden soll (also nicht die Physik oder das Ebenenlayout). Das Ändern des Ebenenlayouts kann dieses Problem beheben, kann jedoch in einem anderen Layout auftreten. Die Frage unterscheidet sich also von dem von Ihnen angegebenen Minigolf-Beispiel, da in diesem Fall die Frage darin besteht, einen Deadlock gezielt zu vermeiden.

Felsir

Wie Sie sehen, schlage ich auch vor, die Kräfte in der Antwort neu anzuordnen. Scheint danach wenig übrig zu sein :-).

Sturmwind

Das Neuanordnen der Wände oder das Ändern der Kugelgrößen ist in meinem Fall nicht möglich, obwohl dies in anderen Fällen der Fall sein kann. Der Screenshot stammt aus dem Debug-Modus einer RTS-Engine. Es gibt viele verschiedene Einheitengrößen und die Wände können vom Spieler nach Belieben platziert werden. Die angezeigten Pfeile werden von meinem Fast Flow Fields-Algorithmus generiert. Sie sind normalisierte Vektoren, mit denen die Fahrtrichtung der beweglichen Einheiten beeinflusst wird. Es ist nicht möglich, die Länge der Vektoren zu ändern, da alle beweglichen Einheiten in der Gruppe dasselbe Flussfeld verwenden.

Fibbles