Collision Grid

[Bananabert]

Nabend Community,

ich bin gerade dabei eine 2D Jump 'n Run Engine zu schreiben und wollte mal die Kollisionsabfragen verbessern. Anstatt jedes mall über all Objekte zu loopen, dachte ich mir eine ArrayList zu benutzen.

Die ArrayList beinhaltet n CollisionGrid Klassen. Jede CollisionGrid Klasse bedeckt ein Areal im Spiel und speichert die im Spiel befinden Objekte in dem angegeben Grid. Zum Beispiel (0,0|128,128) (bei einer Tile größe von 128 passen hier 4x(4 + n) bewegbare rein).
So müsste ich nur einmal über diese Liste loopen und testen in welchen Grid's ich mich befinde. So wäre ich bei maximal 4x(16+n) Kollisionsabfragen.
Am Ende jedes Update durchlaufs eines bewegbaren Objektes, sofern er sich bewegt hat, müsste ich natürlich nochmal drüber loopen und die eigene Position aus den Klassen der CollisionsGrid's löschen/hinzufügen.

Meine eigentliche Frage ist nun. Hat jemand hierfür Verbesserungsvorschläge? Macht es vielleicht sogar sind die 4x4 Grids nochmal in 2x2 zu unterteilen? Oder gar das ganze größer zu machen?

Danke schonmal für alle Antworten.
Bananabert

 

[Gucky]

Ich würde sagen, die Idee mit den Grids ist schon gut. Allerdings glaube ich, dass es besser wäre die Grids BinärBaum mäßig zu machen. Also ein großes Levelgrid. Das dann durch zwei teilen. Die dann auch wieder durch zwei teilen und so weiter. Dann müsstest du nicht mehr alle Grids auf deine Anwesenheit testen, bis du an dem angekommen bist, in dem du dich befindest.

 

[Vancold]

Hey!

Ja das ist eine gute Idee.
Mit dem Binärbaum auch.

Man stelle sich vor du hast eine Map mit über 1000 Elementen die durch loopen müsstest.
Durch den Binärbaum könntest du mit einer Abfrage 500 Elemente ausschalten.
Und beim nächsten Durchlauf wieder usw, was deine Elemente die iteriert werden sollen drastisch senkt.

Falls du dich fragst wie du das am besten anstellst oder nach welchen Kriterien du die rauslöscht würde ich dir zwei Tipps geben:

1. Position am Spielfeld vergleichen (d.h einfach mal fragen ob du in der ersten hälfte bist oder der zweiten; dieser Vorgang kann beliebig oft wiederholt werden um deine genaue Position festzustellen und den Pool der Elemente zu minimieren)
2. Die Elemente nach Position von Anfang bis ans Ende durch sortieren.
3. Wichtig ist auch zu bedenken ob du auch wieder zurück laufen willst. Du solltest für die Bestimmung des Binärbaums einen Thread machen der dir automatisch das richtige Segment raus gibt. Das würde dir im Spiel viel mehr helfen. Vorallem dann wenn es vorgeladen ist und du dann nur einen Bruchteil überprüfen musst.


lg

Rene

 

[Bananabert]

Der Binärbaum klingt gut, da ich vor hatte, etwas größere bzw. längere Maps zu erstellen.

Der extra Thread, der mir die richtigen Elemente raussucht ist natürlich auch sehr gut.
Wie wäre es denn, wenn ich ein neues Objekt hinzufügen will oder Updaten.
Da müsste ich doch auch wieder die richtigen Knotenpunkte raussuchen.
Aber ich glaube bei ca. 10-30 bewegbaren Objekten, sollte dies nicht allzu sehr an der Performance ziehen oder?

 

[Vancold]

Hey!

Ich denke mir das bei einem Jump n' Run die Elemente und das Level vorgefertig sind, d.h du müsstest nur dieses laden?

Und je nach dem wo dein Char sich befindet kannst du dann locker durch die Liste gehen.
Selbst bei 100 Chars sollte es nicht so schwer sein. Du vergleichst ja nur einen Bruchteil durch den Binärbaum und 100 vergleiche sollte deine CPU hinbekommen


LG

Rene

 

[Bananabert]

ja das stimmt natürlich.

Ich hab eine zeit Lang auf einem etwas älteren MAC programmiert. Da ging die CPU immer gut bis 100% hoch. Mittlerweile bin ich bei 30% angekommen. Ich dachte immer ich Programmier schlecht, bis ich mir mal die CPU angeschaut habe. Dadurch hab ich aber viel über Performance gelernt und auf guten Mittelklasse Computern, laufen meine Minigames mit 5-10% CPU .

 

[Gucky]

Ich versteh noch nicht so ganz, welchen Sinn der zweite Thread hat. Reicht nicht einer, der die gesamte Logik ausführt? Und dann fragt die Figur eine Klasse Kollision, mit welchem Objekt sie gerade zusammenstößt oder auch eben nicht. Die Kollisionsklasse läuft dann den Baum ab, guckt nach, wo die Figur ist und gibt dann eine Enumeration (oben, unten, links, rechts, nichts) zurück, nach der die Figur entscheidet, wo sie sich lang bewegen kann. (die Kollisionsklasse könnte auch Dinge wie z.B. Leiter zurückgeben)

 

[Vancold]

Hey!

Gucky da hast du wohl recht.
Wenn er eine routine eingabut hat wie updateGame(); oder updateLogic() und das dort drinnen gehandhabt wird.
Könnte er das auch so machen.

Ist Geschmackssache.


LG

Rene

 

[Gucky]

Achso. Deine Lösung ist also nur ein anderer Stil. Was nun besser oder schlechter ist, lässt sich wahrscheinlich nicht nachprüfen. Ok. Wieder was gelernt.

 

[Vancold]

Hey!

Ich würde davon ausgehen das es für die Laufzeit besser wäre das so zu machen mit einer GameRoutine, diese macht
(also keinen Thread)

calculateDelta();
update(delta);
render();

Und in update wäre dann auch whs schon die ganze Sache mit den Objekten welche angezeigt werden sollen bzw. welche gezeichnet und überprüften werden soll geklärt.
Update soll ja den Spielinhalt auf neuen Stand bringen.
render zeichnet dann nur.

Ich programmiere immer mit einem Delta (ergibt sich aus den FPS und wie lange ein Frame zum nächsten braucht)
Das veranlasst das Spiel immer gleich schnell zu laufen auch wenn nur 3 FPS angezeigt werden

Aber ja im Grunde ist es Geschmackssache.


LG

Rene

 

[Bananabert]

Ich danke Euch beiden für euere Vorschläge und habe eine Lösung auf mein Problem zugeschnitten.

/closed