Guter freier (GPL lizenz oder so) BSP( kd-tree) code für moving objs management

[SimonX]

Hi,

Ich suche BSP tree bzw kd-tree code den man zum Verwalten von sich bewegenden Objekten gut verwenden kann. Es gibt einige sich bewegende Objekte und viele statische Objekte.

Nach meiner Recherche sind kd-tree's nicht so gut geeignet dynamische Objekte zu verwalten. BSP tree's sollen ok sein.

Es geht hier nicht um 3d render sonder um die Verwaltung von Spielern auf einen Server mit 100++ Leuten und Bots.

TIA

[Demirug]

BSP's dynamisch zu bauen ist eigentlich keine gute Idee.

Erkläre doch bitte mal etwas genauer was du mit "Verwalten" meinst damit ich ein Gefühl für deine Problemstellung bekomme.

[SimonX]

Also,

Wir haben eine Spielzone mit vielen statischen Objekten wie z.b. Häuser, Wände, Türen, Hügel usw ...

Dann habe wir Bots die vom Server gesteuert werden und irgend was machen.

Dann habe wir echte Spieler die da auch rumlaufen.

Ein Bot soll nicht durch Wände, Hügel usw eine Spieler angreifen können. Ein Spieler soll das auch nicht.

Somit muss man wissen ob zwischen zwei dynamischen Objekten (Spieler oder Bot) eine LOS (line of sight) existiert.

Ein BSP tree bietet diese Möglichkeit. Da die dynamischen Objekte nur Punkte sind, wird irgendwo gesagt das die einfach verwaltet werden können.

kd-tree's sind eher noch schlechter für dynamische Punkt-Objekte geeigent, da die Balance des Baumes schnell verloren geht.


Hilft dir das?

BTW: Wir sprechen hier von so 300 Bots, 1000+ Spieler (das ist der worst case, average ist so <100) und so 50 Hügel, 10 Häuser.

Vielleicht macht es Sinn einen statischen BSP aufzubauen und zu prüfen ob Punkt A eine LOS zu Punkt B hat. Welche A's und B's gecheckt werden (welche Bots/Spieler im Range sind) wird über eine andere Datenstruktur gemacht (vielleicht auch ein BSP tree aber nur mit Punkten)

[Demirug]

Deine dynamischen Objekte sind nicht wirklich Punkte. Für Spieler und Bots in einer 3d Welt braucht man leider immer einen Volumenkörper (z.b. Bounding-Box). In deinem Fall kommt dann ja noch ein Aktionsvolumen hinzu.

Das alles hört sich für mich wie ein klasiches "Teile und Hersche" Problem an. Bei der grossen Summe an dynamischen Objekte in der Welt dürfte sich eine alles gegen alles Prüfung von selbst ausschliessen.

Mein Vorschlag wäre es daher die Welt in Zonen aufzuteilen. Für jede Zone erstellt man dann einen BSP für die statische Geometrie und speichert zusätzliche eine dynamsiche Liste mit den Spielern und Bots welche sich in der Zone aufhalten (bzw deren Aktionsbereich in dieser Zone liegt.) Dadurch läst sich der Aufwand schon ein gutes Stück reduzieren da nur noch jeweils innerhalb einer Zone geprüft werden muss. Sollte die dynamische Liste denoch zu gross werden könnte man diese durchaus noch weiter unterteilen.

Das ganze funktioniert natürlich leider nicht mehr ganz so einfach wenn die Reichweiten der Waffen im verhältniss zu der Weltgrösse eine gute Einteilung in Zonen nicht erlaubt den eine Zone sollte auf jedenfall grösser sein als die Reichweite einer Waffe sein. Das ganze funktioniert zwar auch wenn die Waffen eine grössere Reichweite haben aber dann muss man Zonen übergreifend rechnen.

Schafft man es die Zonen weitgehend unabhängig voneinader zu halten kann man die Berechungen für die einzelnen Zonen auch schön auf mehrer Processoren verteilen. Aber ich vermute mal das Mehrprozessor Systeme derzeit noch nicht zu deinen Überlegungen gehören.

Das Zonenprinzip lässt sich auch auf meherer Rechner die als Serververbund arbeiten ausdehnen. Aber jetzt gehe ich wohl entgültig zu weit.