4. Wie am besten NPCs und Gegenstände verwalten im großen 2d-Koordinatensystem

Wie am besten NPCs und Gegenstände verwalten im großen 2d-Koordinatensystem

  • F

    Hallo,
    ich hoffe ich bin hier richtig.

    Also ich habe mein Spiel jetzt soweit fertig das man 2d-Tile-Karten (also ohne Objekte darauf) laden kann. Als nächstes will ich zB. Häuser, Bäume und Steine implementieren. Diese soll man jedoch pixelgenau plazieren können.
    Das heisst wenn die Karte zB 100*100 Tiles hat, hat das Koordinatensystem für NPCs, Objekte etc. (100*32)(10032) Felder.
    Jetzt zerbreche ich mir den Kopf daran wie ich das alles verwalten will. Wenn ich die Position des Objekts in seine struct mit aufnehme müsste ich ja zB für jede Kollisionabfrage alle Objekte durchgehen (?).
    Eine andere Lösung wäre zb ein Array[100*32][100*32] indem ich Zeiger auf die Objekte lege. Allerdings würde das wohl sehr viel Speicher verbrauchen und wirklich perfekt ist es auch nicht. Stellt euch mal vor jemand macht ein sehr große Karte mit zB 1000*1000 Tiles huhhuu.
    Außerdem würde in dem Array dann ja auch nur die obere Linke Ecke des Objekts markiert, das heisst ich müsste für eine Kollisionsabfrage alle Objekte in der Nähe suchen, deren Höhe und Breite auslesen und dann eine BB-Kollision abfragen.

    Also letztendlich soll es so sein, dass man ohne ALLE Objekte durchzugehen zB schnell alle Objekte innerhalb eines bestimmten Bereichs finden kann, oder einfach schnell WelchesObjektIstBei(1345,2347);
    Wie macht ihr das in euren Spielen?
    -fnorfd

    0
  • C

    Dein 100x100 TileArray hat n Pointer auf ne Struktur die sagt welche(s) Objekt(e) sich in dem Tile befinden. Vielleicht dort dann auch mit Pixelgenauen angaben relativ zum Tile.

    0
  • F

    Zur Zeit sieht mein KartenArray so aus:

    (pseudocode)

    int terrain_map[][];  <-- Hier werden Nummern gespeichert
GLuint terrain_tex[];  <-- Hier werden die Nummern eingesetzt

    Aber wenn ich jetzt davon ausgehe das auf einem Tile praktisch unendlich viele Objekte sein können, müsste ich das doch mit verketten Listen machen oder so (?)

    meinst du das vielleicht ungefähr so:

    int terrain_map[][];
GLuint terrain_tex[];

(struct *) npc npc_map[][];
struct {
  char *name
  int HP;
  ...
  (sruct *) npc next_npc; <-- Zeigt gegebenenfalls auf weitere npcs im selben tile
} npc;

(struct *) objekt objekt_map[][];
struct {
  char *name
  ...
  (sruct *) objekt next_objekt;
} objekt;

    Leider weiss ich nicht mehr so ganz wie das mit den verketteten Listen noch war 😕 Und mit strukturen bin ich auch nicht so vertraut.
    Also kannst du vielleicht mal ein bischen (pseudo)Code schreiben, dass würde mir sehr helfen 🙂
    mfG -fnord

    0
  • G

    was is wenn du für jedes object nen bool anlegst object[px_x][px_y]=true; oder so ne map die dann die coordinaten direct auf das object ummünzt?

    is wahrscheinlich ne scheiss lösung, aber besser kann ichs net 🙂

    0
  • F

    Sorry ich versteh garnicht so richtig was du meinst.
    Kannst du das nochmal erklären oder einfach ein bischen code posten?

    0
  • U

    Willst du unbedingt C verwenden, oder geht auch C++?

    0
  • F

    ee sgeht auch c++,
    ich bin für alles offen

    0
  • F

    Ich werde es jetzt erstmal testweise machen wie oben beschrieben, also bei jeder Abfrage alle Objekte durchgehen. Mal sehen wie das die Performance beeinflusst.

    Die anderen Ansätze versteh ich leider nicht so ganz 😕

    0
  • M

    Ich hab bis jetzt auch immer alles einfach in Vektoren gepackt und bin die dann für Kollisionserkennung und so alle durchgegangen ... wenns da alternativen gibt würde mich das auch mal interessieren 🙂

    0
  • C

    Die einfachste Art die Anzahl der zu überprüfenden Objekte zu reduzieren ist eine ordentliche Baumstruktur.
    Lest euch mal was zu OcTree's, BSPTree's etc... durch ...
    Einfachste Idee: Per Divide & Conquer das Level rekursiv unterteilen, so braucht man ganz wenig schritte um alle Objekte zu finden die für eine Kollision in Frage kommen.

    0
  • C

    Alles was du wissen musst, ist wie gross ein Tile ist und welche Objekte auf welchem Tile stehen.
    Wenn du ein Objekt bewegst musst du es ggf am neuen Tile "anmelden" und beim vorherigen "abmelden". Kollisionen prüfst du dann mit den anderen Objekten des Tiles oder meinetwegen auch mit denen der Nachbar-Tiles.
    Um die Objekte frei bewegen zu können brauchst du btw kein riesen Array 🙂
    Es reicht wenn du die Tiles hast. Aus jeder globalen Position kannst du auch eine Tile-Position errechnen durch X = (int)(PosX / TileSize) und Y = (int)(PosY / TileSize)

    0
  • F

    Ok, danke schonmal, ein Frage habe ich aber noch 🙂

    Das Array, das auf verschiedene Structs zeigen kann müsste doch vom Typ void *ObjektKarte[x][y] sein oder?
    Aber was ist, wenn man mehrere Objekte innerhalb von einem Tile hat? ObjektKarte kann ja immer nur auf ein Objekt zeigen...
    😕 😕

    -fnord

    0
  • C

    Besser ist es, eine Klasse (oder struct wenn du unbedingt C benutzen willst 🙄 ) für die Tiles und eine(s) für die Objekte zu erstellen.
    Quasi so:

    struct sObject
{
    int nTyp;
    int nBlaBlubb;
    // Usw...
    sObject* pNextObject;
};

struct sTile
{
    sObject* pObjects;
    // Irgendwelche weiteren Eigenschaften...
};

    Die Karte wir dann so erzeugt:

    sTile Karte[100][100];

    Beim hinzufügen von Objekten zu einem Tile musst du dich entsprechend an der Linked-List entlanghangeln bis du eines mit pNextObject == NULL triffst bzw wenn der pObjects des Tiles == NULL, dann isses der 😃
    Geschnallt ? 🙂

    0
Anmelden zum Antworten