[Andorra2D] Ein paar Fragen - Kollisionen und Timer

[nuclearping]

Hey,

ich habe ein paar Fragen bezüglich Andorra 2D.

1) Kollisionen

Ich habe in meinem Projekt mehrere Sprite-Klassen, die von einer TAnimationSprite(TImageSprite)-Klasse abgeleitet werden:

Code:

TCustomCharacter(TAnimationSprite)
|-- TAICharacter(TCustomCharacter)
+-- TPlayerCharacter(TCustomCharacter)

TCustomProjectile(TAnimationSprite)
|-- TFireballProjectile(TCustomProjectile)
+-- T...Projectile(TCustomProjectile)

TPlayerCharacter und TAICharacter laufen über das Spielfeld (isometrisch) und können mit TCustomProjectile schießen (diverse "Zauber" wie Feuerball, Blitz, Flächenzauber, ...).

Das Problem hierbei: Bei all diesen Klassen (oder der TAnimationSprite-Hauptklasse) müßte - nach meinem Andorra-Verständnis jedenfalls - im DoMove "Collision" aufgerufen werden, damit diese Sprites ihre eigene Kollision mit anderen Sprites mitbekommen.

Zum Beispiel sollen sich auch Charaktere gegenseitig blocken, also nicht einfach gegenseitig durchlaufen können. AI-Charaktere müssen, genauso wie der Player-Charakter und Projektile auch, an Bäumen, Gebäuden, usw. kollidieren.

Wenn ich in die TAnimationSprite-Klasse im DoMove Collision aufrufe und somit das Problem für alle abgeleiteten Klassen löse, klappt das auch alles, so wie es soll. Aber: Umso mehr Sprites es werden, desto mehr geht die Performance in den Keller. ~100 Charaktere sind noch ok, ab 200 sinken die FPS von 60 (VSync) auf ~20. Es ist nicht so, dass diese Menge ein Dauerzustand wäre, aber möglich könnte es schon werden.

Gibt es da einen besseren Weg? CollisionOptimizationTyp ist bei allen schon auf ctOptimized gestellt. Was mir noch einfallen würde wäre, bei Sprites, die nicht im Sichtfeld des Spielers sind, die Kollisionserkennung zu überspringen. Allerdings geht das im Prinzip nicht, da sich AI-Charaktere auch ausserhalb der Reichweite des Spielers gegenseitig angreifen können sollen, wenn sie sich begegnen. Wobei man hier dann wieder sagen kann: Solange das Sprite nicht im Kampf ist, findet keine Kollisionserkennung statt. Sonst ja.

2) Timer

Wie löst man mit Andorra am besten Aufgaben, die Timer involvieren? Zum Beispiel Abklingzeiten auf Fähigkeiten oder "Schaden / Heilung über Zeit"-Zauber? TThread? TTimer? GetTickCount?

[Aphton]

Wie wärs wenn du ein Quadtree verwendest?

[nuclearping]

Ok, hab mich damit noch nie mit beschäftigt, aber das was ich gerade darüber gelesen habe, klingt auf jeden Fall interessant. :)

Edit: Hab mich grad mal bisschen belesen. Dabei scheinen sich ja die Meinungen zu spalten? Die einen meinen "Spatial Hashing" wäre für 2D-Objekte besser als ein QuadTree? Vorallem für bewegliche / bewegende Objekte soll ein QuadTree angeblich eher nachteile gegenüber dem "Spatial Hashing" haben?

Die Größe der im Spiel befindlichen Sprites variiert. Die Charaktere zB sind in der Regel 96x96 groß, können aber auch bei bestimmten Animationen 128x128 groß sein. Projektile sind entweder TParticleSprites oder TCustomProjectile und können dabei (je nach Zauber und "Zauberstufe") entweder 16x16 oder teilweise bis zu 64x64 groß sein.

Was wäre hier nun besser? "Spatial Hashing" oder QuadTree?

[Aphton]

Uff da müsste dir einer antworten, der sich auch mit Spatial Hashing auskennt.

[Namenloser]

„Spatial Hashing“ heißt glaube ich einfach nur, dass man das Spielfeld in ein grobes Gitter einteilt und dann für jede Zelle speichert, welche Objekte darin liegen. Dann testet man nur Objekte, die sich mindestens eine Zelle teilen, gegeneinander. Das ist denke ich für bewegliche Objekte eindeutig die bessere Variante, da die Datenstruktur flach ist, sodass der Overhead bei Änderungen nicht zu groß wird. Außerdem ist es einfacher zu implementieren. So weit ich weiß, verwaltet Andorra2D Sprites intern allerdings schon in so einer Struktur, zumindest schrieb Andreas (Entwickler von Andorra2D) mir das vor Jahren hier im Forum.

Entscheidend für die Effizienz dieses Verfahrens ist aber die Größe der Zellen. Ich weiß nicht, ob Andorra2D die Größe automatisch ermittelt, aber ich würde mal mit verschiedenen Größen experimentieren.

Zum 2.:

Zitat:

Wie löst man mit Andorra am besten Aufgaben, die Timer involvieren? Zum Beispiel Abklingzeiten auf Fähigkeiten oder "Schaden / Heilung über Zeit"-Zauber? TThread? TTimer? GetTickCount?

Die beste Lösung ist imo pro Sprite (oder ggf. global) eine Liste zu führen mit Tupeln bestehend aus „Zeitpunkt“ und „Ereignis“. Bei jedem Tick ermittelst du dann die Ereignisse deren Zeitpunkt in der Vergangenheit liegt, führst diese aus und löscht sie aus der Liste. Das wäre also quasi eine „GetTickCount“-Lösung, auch wenn ich nicht unbedingt direkt GetTickCount verwenden würde. Ich meine Andorra stellt den Sprites die aktuelle Zeit sowieso bereit oder bietet zumindest eine Kapselung (TAdPerformanceCounter?) an. Habe aber schon lange nicht mehr damit gearbeitet, daher ohne Gewähr...

[nuclearping]

Zitat:

Zitat von NamenLozer (Beitrag 1183783)

„Spatial Hashing“ heißt glaube ich einfach nur, dass man das Spielfeld in ein grobes Gitter einteilt und dann für jede Zelle speichert, welche Objekte darin liegen. Dann testet man nur Objekte, die sich mindestens eine Zelle teilen, gegeneinander. Das ist denke ich für bewegliche Objekte eindeutig die bessere Variante, da die Datenstruktur flach ist, sodass der Overhead bei Änderungen nicht zu groß wird. Außerdem ist es einfacher zu implementieren. So weit ich weiß, verwaltet Andorra2D Sprites intern allerdings schon in so einer Struktur, zumindest schrieb Andreas (Entwickler von Andorra2D) mir das vor Jahren hier im Forum.

Entscheidend für die Effizienz dieses Verfahrens ist aber die Größe der Zellen. Ich weiß nicht, ob Andorra2D die Größe automatisch ermittelt, aber ich würde mal mit verschiedenen Größen experimentieren.

Ja, nach dem, was ich über das Hashing gelesen habe, denke ich auch, dass das wohl in dem Fall die bessere Variante wäre. Hab mir die Andorra-Codes zur Kollision noch nicht genau angeschaut, aber wenn es ein ähnliches Verfahren verwendet, kann man's sicher optimieren. Man merkt zB auch einen Perfomanceverlust, wenn viele Objekte da sind, aber ALLE stehen und sich nichts und niemand bewegt. Aber ich will jetzt bei weitem nicht an Andorra rummeckern, die Engine ist echt top und läuft super :mrgreen: :thumb:

Mir gehts hauptsächlich um das Prinzip eventueller Performancegewinne, um die Spielengine so skalierbar wie möglich zu halten und nicht künstlich den Spielverlauf zu limitieren, weil sonst die Kollisionsprüfung alles in den Keller ziehen würde.

Ich hab mir auch schon ein paar grobe Gedanken über ein mögliches alternatives System gemacht, was auch mit Zellen und Gewichtungen arbeiten würde. Wobei die Zellen je nach "Inhalt" ein Gewicht bekommen. Also könnte man ein Gitter aus 16x16 pro Zelle erstellen. Ein 96x96 Sprite würde 4 Zellen ausfüllen, wobei das Zentrum das höchste Gewicht bekommt und nach aussen hin das Gewicht abnimmt. Je nach Bewegung der Sprites verteilt man die Gewichtung in den Zellen neu und addiert diese Gewichtung mit (zB je nach Bewegungsrichtung) benachbarten Zellen. Überschreitet das Ergebnis einen bestimmten Schwellwert findet eine Kollision statt, sonst nicht. :gruebel: Keine Ahnung, ob und wie gut das aufgehen würde und wie performant das wäre. Aber interessant finde ich es schon.

Zitat:

Zitat von NamenLozer (Beitrag 1183783)

Zum 2.:
Die beste Lösung ist imo pro Sprite (oder ggf. global) eine Liste zu führen mit Tupeln bestehend aus „Zeitpunkt“ und „Ereignis“. Bei jedem Tick ermittelst du dann die Ereignisse deren Zeitpunkt in der Vergangenheit liegt, führst diese aus und löscht sie aus der Liste. Das wäre also quasi eine „GetTickCount“-Lösung, auch wenn ich nicht unbedingt direkt GetTickCount verwenden würde. Ich meine Andorra stellt den Sprites die aktuelle Zeit sowieso bereit oder bietet zumindest eine Kapselung (TAdPerformanceCounter?) an. Habe aber schon lange nicht mehr damit gearbeitet, daher ohne Gewähr...

Ja, genau so hab ich's jetzt auch gemacht. In der GameEngine eine globale TList angelegt, die einen eigenen Timer-Record verwaltet:

Delphi-Quellcode:

type
  TTimerRecord = record
    Duration,
    Interval: Integer;
    StartTicks: Cardinal;
    IntervalStartTicks: Cardinal;
    PassedTicks: Cardinal;
    TicksLeft: Integer;
    Enabled: Boolean;
    Finished: Boolean;
    FreeOnTimeOut: Boolean;
    Data: Integer;
    OnInterval: TNotifyEvent;
    OnTerminate: TNotifyEvent;
  end;
  PTimerRecord = ^TTimerRecord;

Im Haupt-Render-Event der GameEngine wird UpdateTimers aufgerufen, der die ganzen Timer durchgeht, TickCounts aktualisiert und ggf. entsprechende Events ausführt, Timer wieder aus der Liste entfernt, wenn sie nicht mehr gebraucht werden, etc. Läuft butterweich. :thumb:

[Aphton]

Achso, dann wäre ja die Quadtree Optimierung eine dynamischere Variante davon... Nun gut, stimmt, da wäre diese Methode angebrachter. Man muss dann halt nur die richtige Zellengröße auswählen

[nuclearping]

Hab die Kollision jetzt per Bitmaske gelöst. Jedes Sprite hat 'ne eigene 1-Bit-Kollisionsmaske, die beim DoCollision-Event übereinandergelegt werden und dann wird geschaut, ob und wo sie sich überschneiden. Optimiert und (offenbar :mrgreen:) bugbefreit läuft das jetzt selbst mit 500 Bots, die quer durch die Gegend rennen und fröhlig rumkollidieren, noch akzeptabel und spielbar. :thumb: