Archived

This topic is now archived and is closed to further replies.

Stucture for handling UniqueIDed entities?

This topic is 5008 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello All, I am wondering what a good data structure, or system, for storing and searching for Unique Entity IDs is. I tested out a Linked List with a search which looped through till it found what I was looking for and it turned out to be prety slow. I was thinking maybe a std::map<>, or possibly a binary tree? Oh, a static NPC[MAX_NPCS] with looping through seraching was really fast, but I can''t have all that memory allocated all the time... If you don''t quite know what i''m asking, this is my attempt at an example... So i''m making a network game, and that game has NPCs as many do. Now the server tells the client "yo, NPC 553 is now at x,y" or whatever, the actual message isn''t important. Now, the client is holding a list of NPCs which it is currently displaying, or keeping tabs on, obvioulsy this list is probably much smaller than the total NPC list the server has. So npc 553 on the server is most likely not goign to be npc 553 on the client, might be NPC 10. Since these numbers arn''t going to make it easy for me to just do something like NPC[inpcid] I need a way to search through the data structure holding all the npcs as efficiently as possible to find the one whith the requested ID. Hope someone has an idea on this... - GeekPlusPlus

Share this post


Link to post
Share on other sites
One way would be to create a class for the unique id which stores the unique id but also the index where the object with that id is stored. This has the advantages that the unique id can be any number (or type) and you still have fast access with the stored index and you don't have to create a huge array with MAX_NPC elements like in the example.

#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>


// Create a class for a unique id which stores the unique id but also the

// reference to the array which it is stored in

class HasUniqueId
{
public:
HasUniqueId(int ID, const std::string & Attribute) {UniqueID = ID; SomeAttribute = Attribute;};
void setArrayIndex(int Index) {ArrayIndex = Index;};

int UniqueID; // unique id

int ArrayIndex; // index for easy access


std::string SomeAttribute;
};

int main(int argc, char *argv[])
{
// create your arry or vector of entities which all have a unique id

std::vector<HasUniqueId*> NPC;
NPC.reserve(2);
int CurrentNPCIndex = 0;

// here are some simple samples which will be stored in a vector

HasUniqueId SomeNPC(1234567, "Attribute of SomeNPC");
HasUniqueId OtherNPC(9999999, "Attribuet of OtherNPC");

// now the objects are put into a vector but don't forget to store the

// index at which the objects are placed (setArrayIndex!)

CurrentNPCIndex = NPC.size();
NPC.push_back(&SomeNPC);
SomeNPC.setArrayIndex(CurrentNPCIndex);
CurrentNPCIndex = NPC.size();
NPC.push_back(&OtherNPC);
OtherNPC.setArrayIndex(CurrentNPCIndex);

// e.g.: if you want to have access to the attribute of the NPC with the

// ID 9999999 you can get access to it by getting the index of that NPC

std::cout << NPC[OtherNPC.ArrayIndex]->SomeAttribute << std::endl;

// wait for input before closing console window

std::cin.get();
return EXIT_SUCCESS;
}

Hope that helps to explain my idea. Of course this is very simplified but you should get the concept


[edited by - baumep on March 26, 2004 5:21:49 AM]

Share this post


Link to post
Share on other sites