spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Hi!

Also: Mein Spiel ist dafür ausgelegt 10.000e von Einheiten gleichzeitig auf einer Welt zu managen. Nun bin ich gerade dabei, ein Koordinierungssystem zu schreiben, mit Kollisionvermeidung und -umgehung, sowie Formationen und Pathfinding.

Mein Problem taucht nun bei den Kollisiontests auf. An und für sich reicht ein einfacher Sphere-Sphere Test aus, doch müsste ich jede Einheit mit jeder anderen testen [O(n²)], und zudem dies mehrmals, weil ich auch zukünftige Kollisionen testen muss. Was einfach viel zu viel ist!!

Nun habe ich mir gedacht, ich könnte die gesamte Welt in Sektoren einteilen, und nur jene Einheiten testen, welche sich in einem Sektor befinden, das Problem dabei sind aber die "Randfehler". Heißt, wenn eine Einheit im Sektor A ist, und eine andere im angrenzenden Sektor B, dann wird A nicht mit B getestet, auch wenn sie vielleicht sehr nahe (schon fast Kollision) beieinander sind.
Abhilfe würde eine feinere Einteilung der Sektoren und das zusäztliche Testen alle 8 angrenzenden Sektoren bringen. Doch das ist dann wieder rechenaufwändiger... (Nicht zu sprechen vom ordentlichen Mehraufwand für die Programmierung!)

Leider ist mir bis jetzt keine bessere Lösung eingefallen, um die Kollisionstests von vornherrein auszuschließen... Hoffe ihr habt eine Idee! Thx

Du meinst einen Quadtree... ja... aber das eigentliche Problem wird dabei nicht umgangen... Nämlich, dass ich ALLE einheiten durchgehen muss. Das spart mir keine iterationen, folglich ist die Komplexität des algorithmus unverändert... immer O(n²)

Ich hab es deshalb mit dem Grid gelöst... scheint recht gut zu funktionieren...