Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Designfrage: Verwaltung von Spielobjekten

Werbeanzeige

daG

Treue Seele

  • »daG« ist der Autor dieses Themas

Beiträge: 130

Wohnort: Hamburg

  • Private Nachricht senden

1

11.12.2011, 18:04

Designfrage: Verwaltung von Spielobjekten

Hallo alle zusammen,

Ich habe eine Frage bezüglich der Verwaltung von Spielobjekten. Ich programmiere zur Zeit einen Dune II Clone, also ein RTS (aber mit realistischer Umsetzungsmöglichkeit in absehbarer Zeit für eine Person).
Ich habe bereits eine Lösung zur Verwaltung der Spielobjekte, wollte aber mal Fragen wie ihr das evtl. handhabt bzw. welche Möglichkeiten ihr noch kennt.

Anforderungen sind:
  • Durchlaufen aller Objekte zum Updaten / Rendern.
  • Zugriff auf Objekte via Koordinate und Ebene.
  • Besonders schneller Zugriff auf Objekte via Koordinate (für Pfadfindung).
  • Finden eines bestimmten Objektes innerhalb eines bestimmten Radius / Rechtecks.
  • Nach Möglichkeit speicherschonend. (Ist eigentlich keine wichtige Anforderung)

Möglichkeiten die ich in Betracht gezogen habe:
  • Tiles als 2D Array. Jedes Tile speichert in einem Array die Objekte aller möglichen Ebenen.
  • Tiles als 2D Array. Jedes Tile hat (nur wenn nötig) eine Referenz auf ein Objekt welches die eigentlichen Spielobjekte referenziert.
  • Tiles als 2D Array. Ein Quadtree für die Spielobjekte.
  • Tiles als 2D Array. Hashtable (bzw. Dictonary, da C#) zum Speichern der Objekte (Index wird einfach berechnet nach der Formal: x + (y * width) + (level * (width * height))).

Ich benutze die letzte Variante. Wobei ich mir noch ein spezielles System ausgedacht habe um je nach Bedarf an die benötigten Spielobjekte zu gelangen ohne jedes mal alle Objekte in einer Schleife durch zu gehen.

Ich habe eine extra Klasse (GameEntityStore) die die Spielobjekte in einem Dictonary speichert. Wenn man eine neue Instanz der Klasse macht, kann man ihr eine andere als Elternliste übergeben. Dadurch sind die Listen in einer Baumstruktur angeordnet und synchronisieren sich gegenseitig. Da es schwer ist das zu erklären hier mal ein Beispiel:

C#-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// World erbt von der Liste
public class World : GameEntityStore<GameEntity>
{
}

// Jeder Spieler hat z.B. eine eigene Liste:
public class Player
{
    public Player(World world)
    {
        // PlayerGameEntityStore (das auch von GameEntityStore erbt) filtert alle Objekte die nicht von diesem Spieler sind raus.
        this.entities = new PlayerGameEntityStore<GameEntity>(world, this);
    }
}

// woanders kann man z.B. eine Liste aller Harvester des blauen Spielers haben indem man schreibt:
this.harvesters = new GameEntityStore<Harvester>(this.player.Entities);


Wird jetzt in einer der Listen ein Objekt hinzugefügt, wird dieses an die darüber liegende Liste sowie an alle darunterliegenden Listen gemeldet. Die Synchronisation wird also nur beim Ändern einer der Listen angestoßen. Der Vorteil ist, dass ich Listen habe, die meistens nur die Objekte beinhalten die mich an der Stelle interessieren.

Ok wie Ihr seht, habe ich mir bereits viele Gedanken gemacht und habe auch bereits eine Lösung gefunden die mir gefällt. Dennoch wollte ich fragen, wie Ihr so etwas gelöst habt oder lösen würdet.

Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von »daG« (11.12.2011, 21:21)

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

2

11.12.2011, 19:32

Naja spontan würde ich einfach irgendeine Baumstruktur wählen. Octrees oder Quadtrees bieten sich ja an. In deinem Fall dann halt ein Quadtree. Damit hättest du dann alle Anforderungen erfüllt. Auf mich wirken die Dictionaries etwas merkwürdig. Kann sich dort auch keine Indices überschneiden? Wenn zum Beispiel für 2 Objekte die selben Werte gelten. Selbst, wenn man die Werte passend wählt, müssten sich so Überschneidungen ergeben können. Das ist jetzt nur eine Vermutung von mir, aber warum sollte es nicht gelten. Weiß ich nicht. Ich würde wie gesagt spontan Quadtrees benutzen.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

daG

Treue Seele

  • »daG« ist der Autor dieses Themas

Beiträge: 130

Wohnort: Hamburg

  • Private Nachricht senden

3

11.12.2011, 21:16

Im Dictonary gibt es nur Überschneidungen, wenn sich zwei Einheiten auf der selben Ebene und auf der Selben Kachel befinden. Das ist im diesem Spiel aber eh nicht erlaubt, daher kein Problem.

Ein Quadtree wäre auch eine Lösung. Man hätte dann noch den Vorteil, die Einheiten die sich in einem größeren Bereich befinden schnell zu finden. Aber ich denke der Zugriff darüber wäre für Pfadfindung langsamer oder? So wie ich Quadtrees kenne, sind die Leaves oft z.B. 8x8 Tiles groß und man müsste die dann nochmal nach dem passenden Objekt durchsuchen.

Edit:
@Schorsch: Falls du Kollisionen meinst, die Auftreten durch die GetHashKey()-Methode, da hast du recht, da können Kollisionen auftreten. Ich benutze aber einen Integer als Schlüssel, den ich wie oben geschrieben selbst berechne. Daher gibt es keine (bis auf die oben genannte) Kollisionen.

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »daG« (11.12.2011, 21:25)

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

4

11.12.2011, 21:29

Kommt doch drauf an, wie weit du die Einteilung durchführst. Und ist die Frage, wie schnell das Dictionary arbeitet. Klar sind Hashmaps in der Theorie ne super Sache, ich weiß aber nicht wie die Zugriffszeiten da so aussehen. Wenn du mit deiner Idee zufrieden bist, dann lass es doch einfach so. Man muss ja nicht unnötig optimieren. Und nein diese Funktion meinte ich nicht.
Aber du berechnest dir den Index aus vielen Werten. Und je nachdem wie diese Werte zusammenspielen, kann es ja sein, dass bei 2 verschiedenen Objekten der gleiche Index herauskommt. Ob das bei dir der Fall ist keine Ahnung.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

daG

Treue Seele

  • »daG« ist der Autor dieses Themas

Beiträge: 130

Wohnort: Hamburg

  • Private Nachricht senden

5

11.12.2011, 21:47

Ja, es funktioniert gut. Die Pfadfindung braucht bei mir für z.B. 1200 Kacheln die untersucht werden müssen ca 28ms, denke das ist ausreichend. Die Frage war halt einfach wie andere dieses Problem lösen.

Ich hatte vor kurzem ein Video gesehen wo jemand bei Terraria ein Bug gezeigt hatte, wo beim Platzieren einer Jukebox diese sofort wieder abgerissen wird und sich verzehnfacht. Er hatte versucht das Spiel zum Absturz zubringen, jedoch fing es nicht mal an zu laggen, dabei hatte er extrem viele Jukeboxes erstellt. Daher hatte ich mich gefragt, wie das bei Terraria wohl funktioniert. Da die Karten bei Terraria sehr groß sind, muss es ja eine effiziente Möglichkeit geben nur die Objekte die zur Zeit auf dem Bildschirm sichtbar sind zu finden. Quadtrees sind dafür auf jeden Fall sehr gut geeignet. Ein Dictonary würde da nicht funktionieren, da die Objekte ja pixelgenau platziert sind. Dennoch hatte es mich verwundert und hatte mich gefragt wie die das wohl gemacht haben. Ich denke das war der Ursprung für diese Frage.

Werbeanzeige

Ähnliche Themen