Vergleichen von Elementen in einer Liste

Programmiersprachen, APIs, Bibliotheken, Open Source Engines, Debugging, Quellcode Fehler und alles was mit praktischer Programmierung zu tun hat.
Antworten
Benutzeravatar
starcow
Establishment
Beiträge: 523
Registriert: 23.04.2003, 17:42
Echter Name: Mischa Schaub
Kontaktdaten:

Vergleichen von Elementen in einer Liste

Beitrag von starcow »

Abend zusammen

Ich bin gerade dabei mein kleines Mini-Spielchen gemäss den guten Ratschlägen von joeydee ein bisschen weiter zu entwickeln.
Nun steht eine Art Manager in groben Zügen, welcher die verschiedenen Entitys gegeneinander auf Kollision untersuchen soll.
Zur Zeit geht es lediglich darum, die Organisation sinnvoll umzusetzen. Die eigentliche Kollisions-Prüfung besteht demnach bis jetzt nur aus einem simplen Zahlenvergleich.

Meine Ueberlegung war folgende:
Element 1 wird gegen alle Elemente, die weiter unten in der Liste stehen getestet.
Ist die ganze Liste durchgelaufen, wird das ganze nochmals mit Element 2 druchgespielt. Auch hier wieder gegen alle Elemente, die weiter unten in der Liste stehen.
Bei 4 Elementen sähe die komplette Prüfung also folglich so aus:

1) Element[0] gegen Element[1]
2) Element[0] gegen Element[2]
3) Element[0] gegen Element[3]
4) Element[1] gegen Element[2]
5) Element[1] gegen Element[3]
6) Element[2] gegen Element[3]

Wie es mir scheint, gibt es keine effizientere Methode als diese. Was meint ihr dazu?

Beim Umsetzen dieser Idee in Code, bin ich zudem auf ein Problem gestossen,

Code: Alles auswählen

	if (!LISTEntity.empty()) {
		list<BEAST_Entity*>::iterator iEntity, iCompare;

		for (iEntity = LISTEntity.begin(); iEntity != LISTEntity.end(); ++iEntity) {
			for (iCompare = iEntity; iCompare != LISTEntity.end(); ++iCompare) {
				if ((*iCompare)->GetPosition() == (*iEntity)->GetPosition()) {
					cout << "- Kollision festgestellt" << endl;
				}
			}
		}
	}
Eigentlich müsste iCompare bei der Initialisierung um ein Element tiefer unten in der Liste sein, als iEntity.
So wie der Code jetzt geschrieben steht, wird jedes Element noch mit sich selbst auf Kollision untersucht.
Mir fällt aber kein eleganter Weg ein, wie ich iCompare um ein Element höher bekomme, als iEntity.
Ich habs mit:

Code: Alles auswählen

iCompare = iEntity + sizeof(*iEntity)
versucht. Das hat mir aber der Compiler nicht durchgelassen.
Sinnesgemäss wäre es ja irgendwas wie: ++(iCompare = iEntity).

Fällt euch da ein eleganter Weg ein, womit die Initialisierung weiterhin im Schlaufen-Kopf stattfinden kann?

Gruss starcow
Freelancer 3D- und 2D-Grafik
mischaschaub.com
DerAlbi
Establishment
Beiträge: 269
Registriert: 20.05.2011, 05:37

Re: Vergleichen von Elementen in einer Liste

Beitrag von DerAlbi »

std::next hilft da

Code: Alles auswählen

#include <list>
struct BEAST_Entity {};

int abcdefg(int num)
{
    std::list<BEAST_Entity*> LISTEntity;

    std::list<BEAST_Entity*>::iterator iEntity, iCompare;
    for (iEntity = LISTEntity.begin(); iEntity != LISTEntity.end(); ++iEntity)
        for (iCompare = std::next(iEntity, 1); iCompare != LISTEntity.end(); ++iCompare)
        {
                /**/
        }
    return 0;
}
Benutzeravatar
starcow
Establishment
Beiträge: 523
Registriert: 23.04.2003, 17:42
Echter Name: Mischa Schaub
Kontaktdaten:

Re: Vergleichen von Elementen in einer Liste

Beitrag von starcow »

Super, vielen Dank! Das funktioniert perfekt. :)

Gruss starcow
Freelancer 3D- und 2D-Grafik
mischaschaub.com
Benutzeravatar
starcow
Establishment
Beiträge: 523
Registriert: 23.04.2003, 17:42
Echter Name: Mischa Schaub
Kontaktdaten:

Re: Vergleichen von Elementen in einer Liste

Beitrag von starcow »

Jetzt ist in diesem Kontext nochmal eine Frage aufgetaucht.
Und zwar nämlich folgende:

Wenn ich die Objekte alle untereinander auf Kollision teste, dann kriege ich nach der bekannten Formel ->
(x² - x) / 2
bei 10'000 Objekten bereits 49'995'000 Funktionsaufrufe.
Da dürfte aber die Schwelle der maximalen Loop-Zeit für eine Echtzeit-Anwendung bei weitem überschritten sein.

Ist das tatsächlich so? Sind 10'000 Objekte für ein Spiel zu viel des guten? Oder übersehe ich da etwas entscheidendes?

Edit:
1000 Objekte dürften da ja bereits (mit rund einer halben Million Funktionsaufrufe) ziemlich kritisch werden...

Gruss starcow
Freelancer 3D- und 2D-Grafik
mischaschaub.com
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Vergleichen von Elementen in einer Liste

Beitrag von Krishty »

Ja, so ist das auch. 10.000 Objekte auf einem Haufen schlagen sich auch in einer modernen Physikengine in der Leistung nieder.

Normalerweise nutzt man räumliche Strukturen für sowas – z.B. binäre Bäume, Octrees, Zellen, usw. In solchen Hierarchien liegen Objekte in den selben Knoten/Blättern/Zellen, wenn sie räumlich nah aneinander sind. Man braucht also „nur“ durch die Hierarchie gehen und benachbarte Knoten/Blätter/Zellen gegen einander prüfen. Wenn die Objekte nicht auf einem Haufen liegen, sondern gestreut sind, ist das viel schneller.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
starcow
Establishment
Beiträge: 523
Registriert: 23.04.2003, 17:42
Echter Name: Mischa Schaub
Kontaktdaten:

Re: Vergleichen von Elementen in einer Liste

Beitrag von starcow »

Danke Krishty.
Also dann ordne ich das unter "erweiterte Optimierungsmöglichkeiten" ein und lasse es erstmal aussen vor.

Gruss starcow
Freelancer 3D- und 2D-Grafik
mischaschaub.com
DerAlbi
Establishment
Beiträge: 269
Registriert: 20.05.2011, 05:37

Re: Vergleichen von Elementen in einer Liste

Beitrag von DerAlbi »

Nein, mach es jetzt. Später wird das nur kompliziert nachzurüsten und dieses Baum-Prinzip, wenns einmal da ist, hilft bei sehr vielen Skalierungsthemen. Auf auf!
joeydee
Establishment
Beiträge: 1039
Registriert: 23.04.2003, 15:29
Kontaktdaten:

Re: Vergleichen von Elementen in einer Liste

Beitrag von joeydee »

Oh, ich bin schuld wie ich gerade lese :D
Eleganter und kürzer zu lösen als mit Zellen finde ich Sweep & Prune. Braucht keine vorgegebene räumliche Struktur und verwaltet problemlos beliebig verschiedene Größenunterschiede.
Prinzipiell werden alle Objekt-Bounds auf eine Achse projiziert (möglichst die mit der größten Verteilung), und von links nach rechts die Überlappungsbereiche festgestellt (linearer Aufwand). Bei Überlappungen ergeben sich relativ kleine Prüfgruppen, die man dann einzeln durchgehen kann. Such mal danach, wenns nicht in den Kopf geht frag nochmal, dann kann ich das in den nächsten Tagen mal auseinanderpflücken und vorstellen.
joeydee
Establishment
Beiträge: 1039
Registriert: 23.04.2003, 15:29
Kontaktdaten:

Re: Vergleichen von Elementen in einer Liste

Beitrag von joeydee »

Hier der S&P-Algo veranschaulicht:

Bild

Wenn du Spheres statt Boxen hast, ist in=x-radius, out=x+radius und Test(A,B) vergleicht, ob der Abstand von A.position zu B.position kleiner ist als A.radius+B.Radius.
Flaschenhälse sind zum einen der Sortieralgo (aber da gibts ja gute Standard-Implementierungen), und zum anderen das Finden und Rauswerfen von Elementen aus der Kandidatenliste; nicht jeder Listentyp ist ja für alle Operationen ideal.
Benutzeravatar
starcow
Establishment
Beiträge: 523
Registriert: 23.04.2003, 17:42
Echter Name: Mischa Schaub
Kontaktdaten:

Re: Vergleichen von Elementen in einer Liste

Beitrag von starcow »

Wow super! Wirklich sehr verständlich, deine Illustration. Jetzt verstehe ich die Ueberlegung hinter "sweep und prune". Das ganze ist wirklich raffiniert.
Kann man für die Sortierung der Liste den standard Algorithmus aus der STL benutzen?

Nach einigem brüten bin ich jetzt zum Schluss gekommen, das für meine Spiel-Idee Linien als Wände mir die nötigen Freiheiten ermöglichen würden.

Wenn man jetzt diese Linien gegen Kreise abfragen will, die sich auch "sprunghaft" über das Spielbrett bewegen können, komme ich zu einer Lösung von der ich nicht so recht weiss, ob sie überhaupt sinnvoll mit dem sweep & prune Algorithmus zusammenarbeiten kann. (Aber möglicherweise geht es doch besser als ich denke)

Ich habe dazu nochmals eine Skizze erstellt, damit klarer wird, was ich meine.
Bild

Rein auf die Geometrie bezogen, hätte ich eine Lösung, mit welcher ich feststellen könnte, an welcher Stelle die Kollision zwischen Kreis und Linie stattfinden würde - selbst wenn der neue Zielort des Kreises sich hinter einer Linie befindet. So liesse sich die neue "Destination" des Kreises sauber bestimmen.
Problem ist allerdings, dass ich sinnigerweise die Spielwelt (Linienpunkte) um den Player rum rotieren müsste, anstatt den Spieler selbst. So würden sich die Berechnungen einfacher gestalten, da sich der Kreis immer nur von Links nach Rechts bewegen würde.

Hier könnte man ja jetzt mit dem sweep & prune Algorithmus zwar vorselektionieren, doch würden sich um den Spieler herum (sofern man die Spielwelt nicht rotiert) und um die Wände (Linien) herum schnell recht grosse Rechtecke bilden.

Es scheint mir doch ein recht grosser Unterschied zu sein, ob man einfach Abfragen möchte, ob eine Kollision zwischen Objekten in einer statischen Situation auftreten - oder ob die Situation dynamisch ist. Im Sinne von: Jeder Kreis hat eine Zielposition, die er erreichen möchte.

Danke nochmals joeydee, dass Du Dich ins Zeug gelegt hast und extra eine Grafik erstellt hast. Ich weiss das sehr zu schätzen.
Falls ich mal mit einem 3D-Modell oder einer Textur aushelfen kann, sag bescheid!

Gruss starcow
Freelancer 3D- und 2D-Grafik
mischaschaub.com
joeydee
Establishment
Beiträge: 1039
Registriert: 23.04.2003, 15:29
Kontaktdaten:

Re: Vergleichen von Elementen in einer Liste

Beitrag von joeydee »

Faustregel: Sobald du eine Liste statischer Objekte hast, musst du diese nur einmalig sortieren, nicht in jedem Frame, und du kannst i.d.R. mit linearem Aufwand explizit abfragen welche Objekte an einer bestimmten Position/Umgebung in Frage kommen ohne durch alle durchiterieren zu müssen. Zudem musst du statische Objekte wie Wände nicht gegeneinander auf Kollision prüfen.
Wenn du alles in eine dynamische Prüfung mit reinwirfst, funktioniert das zwar, aber du produzierst verdammt viel unnötigen Overhead.

Mit Linienobjekten beliebiger Länge wird eine Levelabfrage (und die Optimierung dieser) natürlich um einiges komplizierter als z.B. mit Tiles - je nachdem wie groß und klein die Linien werden können bieten sich hier wieder eine Reihe weiterer Optimierungsstrukturen sowie Kombinationen dieser an ... es macht zu diesem Zeitpunkt keinen großen Sinn, Möglichkeiten aufzuzählen oder dir direkt zu einer bestimmten Kombination zu raten. Einzige sinnvolle Möglichkeit: lerne die Dinge separat voneinander kennen um selbst einschätzen zu können, ab wann welche Strukturen und Kombinationen Sinn machen könnten und wann nicht, und wenn du dir unsicher bist: baue einen Prototypen und teste es aus.

Mein persönlicher Tipp:
Egal von welchem Spiel und Möglichkeiten du gerade träumst, um die grundlegenden Prinzipien überhaupt erstmal zu verstehen, bleibe zuerst bei übersichtlichen Prototypen, die jeweils nur ein Problem auf einmal behandeln. Nicht alles gleichzeitig, und nicht alles sofort in der erträumten Komplexität. Du wirst dir dann im Verlauf des Testens und Umbauens viele Fragen selbst beantworten können.
Fange z.B. mit einer Tile-Engine an (lass die Grafik außen vor, bau alles abstrakt datenbasiert mit 1 Tile = 1 Unit und zeige deine Daten durch gefüllte Rechtecke an) - die Tiles bieten in ihrer Regelmäßigkeit schon eine statisch sortierte Struktur, und wenn du später einmal deine Linien in ein Grid partitionieren und sortieren willst um die Abfrage zu optimieren, wirst du das Tile-Prinzip bestimmt wieder gebrauchen können.
Für die Entities, setze dich mit einzelnen Box-vs.-Box- Kollisionen sowie Kreis-vs.-Box und Kreis-vs.-Kreis auseinander. Den Kreisen und Boxen ist es völlig egal, ob sie z.B. zu einem Tile-Level gehören oder durch S&P vorsortiert wurden. Also: eigener Prototyp ohne Tile-Level und ohne S&P. Kollisionserkennung ist erstmal die eine Sache. Die passende physische Reaktion (Bounce, Slide, Kill, oder nur ein Türöffner-Event) steht nochmal auf einem anderen Blatt. Wenn das geht, schau wie das mit den Optimierungsstrukturen (S&P für die Entities und Tiles für den Level) zusammenspielt und wie hoch das skalierbar ist. Die Strukturen sind absolut austauschbar.

Wenn du das so häppchenweise angehst, wirst du auch viel mehr Material aus dem Netz verarbeiten können (und nicht speziell nach "Optimierte Kollision mehrerer Kreise mit Tile-Level" suchen müssen), sowie Fragen hier viel spezieller zu einem Teilproblem stellen können statt zum großen Ganzen, was die Chancen auf Antworten erhöht.
Benutzeravatar
starcow
Establishment
Beiträge: 523
Registriert: 23.04.2003, 17:42
Echter Name: Mischa Schaub
Kontaktdaten:

Re: Vergleichen von Elementen in einer Liste

Beitrag von starcow »

Ok, vielen Danke joeydee. :)

Das mit (statischen) Linien gegen Kreis, scheint mir ein solch isoliertes Problem zu sein, von welchem Du gesprochen hast. Dass das ganze mit Tiles einfacher umzusetzen ist, klingt natürlich schlüssig.
Jetzt habe ich jedoch schon einiges an Gehirnschmalz in die Ueberlegung der Positionsberechnung für "Kreis-gege-Linien" gesteckt und würde daher das ganze sehr gerne mal in Aktion sehen.
Wenn es doch zu anspruchsvoll werden sollte, wechsle ich zu Tiles über - wie Du es ja empfohlen hast.

Gruss starcow
Freelancer 3D- und 2D-Grafik
mischaschaub.com
Antworten