JLI Spieleprogrammierung

[Jonathan_Klein]

Also, ich hab ein kleines Bäumchen, ich glaube nicht, das man das Octree nennt, da es jeweils nur 2 Unterteilungen gibt, und es insgesamt 2D ist aber das Prinzip ist ja immer ähnlich.

Das ganze ist Primär gedacht um Kollision zu beschleunigen, aber natürlich werde ich es auch zum Rendern und für andere Sachen benutzen.

Naja, ich habe also den einfachen Ansatz, ich nehme ein Rechteck, welches das gesammte Level ausfüllt (das Spiel ist 2d aus Isoperspektive) und in jedem Schritt wird das Rechteck halbiert, bis die gewünschte Tiefe an jeder Stelle erreicht wird. Naja, man möchte ja vielleicht eine variable Auflösung haben, beispielsweise wenn man einen geschlängelten Waldweg hat, dann gibt es ja sehr große Bereiche, die niemals irgendwer betreten können wird.

Ich kann jetzt also ein Objekt anhand seiner Position immer weiter reichen, bis ich zu einem Node komme, der keine Childs mehr hat, dort wird es dann gespeichert.
Will ich dieses Objekt jetzt bewegen, dann muss ich testen, ob der Punkt wo es hin will frei ist. Da ja alles räumlich unterteilt ist, guck ich mir alle Objekte im selben Node an und teste diese auf Kollision. Statt 10.000 Tests also nur 5-10. Dafür weiß jedes Objekt evtl. sogar noch, in welchem Node es sich befindet, so dass ich von diesem die Kollisionsprüfung direkt aufrufen kann.

Allerdings muss sich mein Objekt auch in einen anderen Node bewegen können. Ich könnte also, wenn ich eine Grenze überschreite wieder von vorne anfangen und das Objekt neu einsortieren.
Ich könnte aber auch versuchen, dass ein wenig zu beschleunigen, indem jeder Node seine 4 Nachbarn kennt. Überschreitet ein Objekt eine Grenze wird es an den entsprechenden Nachbar weitergegeben. Jetzt macht die unterschiedliche Auflösung aber Probleme, den von einem Node könnte man ja, je nach dem wo man einen Schritt nach oben macht, in verschiedene angrenzende Nodes gelangen.
Naja, dann wird halt als Nachbar der Node gespeichert, der z.B. oberhalb liegt und zusätzlich höchstens die selbe Tiefe hat. Hat er eine geringere Tiefe, ist seine Fläche auf jeden Fall größer, also muss es hier einsortiert werden. Verzweigt sich der Node allerdings weiter, kann er ab hier dann das Objekt weiterreichen.
Das Problem hierbei ist noch, dass alle Nodes immer gleich geteilt werden müssen. 2 Nodes die übereinander liegen könnten ja trotzdem einmal horizontal und einmal Vertikal geteilt werden, dann wäre es wieder nicht eindeutig, von wo man nach wo gelangt.

Ein weiteres Problem ist, dass Objekte über die Grenzen eines Nodes reichen können müssen. Dieses Objekt müsste dann auch in sämtlichen Nodes gespeichert werden, die es berührt, denn sonst würden die Objekte, die sich in Nodes befinden, die von dem großen Objekt nur berührt werden nicht auf Kollision mit eben diesem großen Objekt getestet.
Ebenso muss das große Objekt beim bewegen natürlich nicht nur in dem Node, in dem sein Mittelpunkt ist, die Kollision prüfen, sondern auch in allen die es berührt.

Dadurch, dass ein Objekt in mehreren Nodes sein kann, wird natürlich auch das verschieben etwas komplizierter. Denn man muss dann ja für jeden Node, aus den es sich bewegen könnte das entsprechend testen.



Ich würde mich freuen, wenn jemand so weit gelesen hat und mir jetzt ein paar gute Ideen geben kann. Ich habe das Gefühl, dass meine Überlegungen soweit schon funktionieren könnten, allerdings erscheint mir das ganze doch ein wenig kompliziert. Vielleicht kann man es daher einfacher machen oder vielleicht habe ich sogar etwas sehr schlimmer übersehen?
_________________
https://jonathank.de/games/

[Christian Rousselle]

Ja, scheint mir auch kompliziert. Warum nimmst du (wenn es nur 2D ist) nicht ein Quadrat, dass den ganzen Level umfasst und teilst das Quadrat wieder in 4 Quadrate mit fester Größe auf und das machst du für jedes Quadrat so lange wie es sinnvoll ist (ist schwer zu sagen ohne die Beschaffenheit deiner Welt zu kennen) - z.b. bis max. 4 Quadrate auf den Bildschirm passten. Die Quadrate kennen jeweils ihr Parentquadrat. Wenn jetzt ein Objekt aus einem Quadrat rausläuft, dann gibt du es dem Parent zum einsortieren.

Das Parentquadrat versucht es in eins seiner Quadrate einzusortieren. Wenn es auch da nicht reinpasst, hat das Objekt das Parentquadrat verlassen, dann gibt das Parent das Objekt seinem Parent. Da sollte es dann reinpassen.

Beim Rendern machst du einen Frustum-Test gegen das oberste Quadrat. Da dies immer im Frustum liegt, muss du alle Objekte die in der Liste dieses Quadrat sind rendern (z.b. sehr große Objekte, die immer da sind) rendern, dann gehst du alle Quadrate durch und machst den Test gegen das Frustum und renderst entsprechend.

C.

[Jonathan_Klein]

D.h. nicht nur die untersten Nodes können Objekte haben, sondern alle?
Wenn sich ein Objekt aus einem Node bewegt, wird es so lange nach oben weitergegeben, bis es dort einsortiert werden kann?
Allerdings stellt sich da fast schon die Frage, ob es nicht im Durchschnitt schneller ist, direkt von oben anzufangen, dass Objekt einzuordnen. Den her könnte ja im schlimmsten Fall das Objekt einmal komplett nach oben und dann wieder komplett nach unten durchgereicht werden.

Und ein Objekt kann niemals in mehreren Nodes sein sondern würde dann dementsprechend soweit hochgereicht, bis es nur noch in einem Node ist?
Dann müsste ich zur Kollisionsprüfung immer im aktuellen Node und in allen Parents von ihm testen?

Klint auf jeden Fall ein wenig simpler. Aber wohl auch auf jeden Fall ein wenig langsamer und unoptimaler, jedenfalls müsste man bei einer Kollisionsprüfung z.B. ja ein paar mehr Objekte prüfen und das auch noch in ein paar mehr Objekten, wobei letzteres wohl nicht so ins Gewicht fallen dürfte.
Ich meine, ich hab sowas noch nie programmiert, nur öfters mal was darüber gelesen, von daher kann ich wohl nicht so genau abschätzen, wie toll das jetzt ist.
_________________
https://jonathank.de/games/

[Christian Rousselle]

Ja Probiere doch erstmal eine einfache Variante aus. Denke, das sollte für die allermeinsten Fälle schnell genug sein. Das neue Einsortieren macht dann Sinn, wenn sich die Objekte schnell bewegen.

[Jonathan_Klein]

Naja, es wird ein RPG, vielleicht mit Diablo 2 mäßigen Maps. Da ist schon n bissle was los und die Karten sind schon groß, aber so der totale Overkill ist das da ja auch nicht. Außerdem lief das damals mit 233 Mhz wenn ich mich nicht irre oO
_________________
https://jonathank.de/games/