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

fnord23

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

GreyHound

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

fnord23

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

User--

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

fnord23

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

fnord23

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

Mortal2006

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

ChaosAngel

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.

Cpp_Junky

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)

fnord23

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

Cpp_Junky

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 ?