• 12
• 9
• 9
• 13
• 10

game entity id search

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

Recommended Posts

Okay, what I want to do is allowing each entity to have a unique id. ( The id only need to be unique in the sense that no 2 entities have the same id at the same time ) This is not a problem to implent. The problem comes when I want to be able to search after a spesific entity by the id. Like:
Object* obj = GetObjectByID( net_packet->target );

The system must work over the ether (the net). So I can use it for server/client comunication. I dont know if this is the best approach on the problem in hand. ( the client/server communication ), if any of you got a smarter way to perform this, be so kind to raise your voice. Im developing a simple FPS game, so you wont have a massive set of entities in the world at the same time. But I recon you can have a bit of them as I use entities for explosions and such... If im unclear about anything say so and I will provide additinal info. Also sorry for the spelling...

Share on other sites
Look into something like std::map, you can reference items by key (in your case your unique ID).

Share on other sites
Quote:
 Original post by evolutionalLook into something like std::map, you can reference items by key (in your case your unique ID).

Yes! STL Map is really good for taking care of this. I recently needed something to use for my OpenAL library to manage the sources and buffers and the map came in real handy. The only inconvience is that if you want to store a lot of data with just one refrence name, you must use a struct as the second type or chain maps together. That link shows everything you need to get up and running with maps. I had never used them until I saw that, and I was able to follow it quite easily.

For example you would have somethign like this:
 std::map <int, tEntity> entity_list;

tEntity is the struct/class for the entity and the int is for the id. Now when you are looking for an entity.
int getid = 3;if(entity_list.find(getid) == entity_list.end()){    std::cout<<"entity not in the map!"<<endl;}else {}

- Drew

Share on other sites
yeah, I know about the stl, and I can use it too. ( Im using stl map for my material manager )

IM just conserned that I will become a bottleneck, how does hash_set perform
compered with map on a relative small set ( 200<N<500 ) of data? with unsigned int as key, using just the default hash operation for the hash_set.

Share on other sites
I have not used anything else in the STL library yet, but here's a possible idea to avoid a bottle neck. As you add your entities to what ever structure you use, add them using a function so they are sorted by the id number. Then when you go to find them, use a binary search to find the element. That way, you are not going to get a bottle net when you find an element. If you had 1 million elements in your array, a binary search can get the item in under 20 searches since it always divides in half. Just an idea to think about as well if you did not want to use a hash.

- Drew

Share on other sites
For my entities I just have a large array and use the array index as the ID. Then you have O(1) time, no searches required and your also garenteed to never have two entities with the same ID at the same time. Of course you'll need to take special care that entity creation and destruction happen in the same order on you server as your client, but a simple packet number should be enough for that.

Share on other sites
Quote:
 Original post by CoMaNdoreyeah, I know about the stl, and I can use it too. ( Im using stl map for my material manager )IM just conserned that I will become a bottleneck, how does hash_set performcompered with map on a relative small set ( 200
Hard to say. Most hash_map implementations have the same interface as std::map (they both model Associative Container, IIRC). typedef the container, build it with a std::map, profile it, replace the typedef with hash_map (which should be the only thing you have to change), profile again, and compare results. Then make a decision.

Because hash_map isn't standarized, there may be subtle differences between compiler versions. If this is a concern, consider using a std::map, but leave the option open (via typedef) to switch to std::unsorted_map (or whatever it's called; hash_map can't be used for a variety of reasons) when it becomes standarized.

Share on other sites
Okay I ended up using a typedef'd version. (right now its a std::map)

Another thing that I made to make sure that I have the right ID that comes
from the server is a object id translator that translate between local and
global id's. I also added suport for searing by entity name.

Thanks for the help folks