Jump to content
  • Advertisement
suliman

C++ Using pointers and id for referencing game objects?

This topic is 399 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

Hi

Im making a city builder/simulation game where a building can house up to 15 units. Units and buildings are located in a list (std::list <unit> unitList). 

They need to keep track of eachother (the building: which units live here, how many free slots do I have) (unit: where do I live, where do i work, is workplace full of resources, is food missing at home etc).

Pointers between these is quicker but seems unreliable. Also, when I load/save the game i need to do same special handling of the pointers.

The other idea is to just save the IDs of the building/units. IDs are unique so a ID relates to a single unit/building. But then each time I need to find the units inside a building or whatever i need to getUnitFromID(myID) and use that function to loop through the entire list of objects and return the correct one. Might be slow with hundreds of objects looking for other object all the time.

Or a combination? Or something completely else?
Thanks!
Erik

Share this post


Link to post
Share on other sites
Advertisement
24 minutes ago, suliman said:

Im making a city builder/simulation game where a building can house up to 15 units. Units and buildings are located in a list (std::list <unit> unitList). 

First of, you'd probably not want to have an std::list, but rather an std::vector. While lists technically have some benefits over (dynamic) arrays, in practice their non-linear memory layout makes them really imperformant for anything but removing an object by its list-node (when do you have that anyways?). I'd go for a vector by default any time unless you have very specific needs that justify a list.

27 minutes ago, suliman said:

Pointers between these is quicker but seems unreliable. Also, when I load/save the game i need to do same special handling of the pointers.

How are pointers unreliable? The only point where they should become invalid is when eigther a unit or building is destroyed, but you can simply notify the other connected entities to let them know when that happens. Otherwise, if you still feel they are unsafe, you could use a smart-pointer like std::shared_ptr/std::weak_ptr. They impose some overhead over raw points, but those are neglectible for what you need.

29 minutes ago, suliman said:

The other idea is to just save the IDs of the building/units. IDs are unique so a ID relates to a single unit/building. But then each time I need to find the units inside a building or whatever i need to getUnitFromID(myID) and use that function to loop through the entire list of objects and return the correct one. Might be slow with hundreds of objects looking for other object all the time.

Or a combination? Or something completely else?

I personally use a combination of both: pointers for storing stuff at runtime, and for serialization, write the entities unqiue ID, and later on loadup just make a one-time lookup by that ID to reaquire the pointer. Other people just save the pointer and modulate it at runtime to point to the correct entity, but that probably requires some advanced memory management to work (I belive, havn't tried it myself). Also, its totally possible, and can even have significant benefits to store a handle/ID instead of a pointer, as it allows you ie. to switch out the entire object, makes the case of deleting entities easier, etc...

So I couldn't give you a clear "do this, do that" answer - since there isn't really a clear best-way. I hope I still gave you some ideas that help you choose what to do.

 

Share this post


Link to post
Share on other sites

it did, thanks. I might just use pointers and lookup by ID when saving/loading.

But isnt a list better when I remove objects from the middle? (such as when i destroy buildings or kill units). I always add to the end though. Otherwise I loop through them alot so thats important for speed.

Both buildings and units are somethat large classes with lots of members. Would that make lists a better option?

Share this post


Link to post
Share on other sites
55 minutes ago, suliman said:

But isnt a list better when I remove objects from the middle? (such as when i destroy buildings or kill units). I always add to the end though. Otherwise I loop through them alot so thats important for speed.

Well, it depends. Do you have the list-node ready when you remove from the middle? Otherwise, you have to search for it first, which is way slower in a list. Also, while remove from the node is O(1) and from vector is O(N) for the worst case, there exists a pattern for arrays called erase & swap, where you put the last element to the position of the one you erased, making it O(1) as well. So I'd say, specially if you need to loop through a lot like you said, there's really no reason to use a list for you :)

55 minutes ago, suliman said:

Both buildings and units are somethat large classes with lots of members. Would that make lists a better option?

Nope, doesn't make a difference in your case - since you are storing the pointer, which is always equally large regardless of what you actually store. If you were to store large classes by value, which can't take advantage of move-semantics/can't use C++11, and you can't use erase&swap, then yeah, theoretically lists would gain some advantage. Though, unless you erase/insert more then you actually iterate (which i find doubtful for most cases, its still not worth thinking about).

Share this post


Link to post
Share on other sites

In many large games it is somewhat common to use a placeholder object, a proxy for the real thing that will never move and never become invalid over the course of the game.  Inside the various systems the real object can be present and the proxy object forwards everything to the real object, or the object can be unloaded and a placeholder object is used.  In debug builds the placeholder is something obvious like a huge box or a rapid spinning animation or a checkerboard hot pink texture, something that lets people know the placeholder is being used. In release builds the placeholder is something that can still be manipulated but isn't distracting like a small cube, or a static animation, or a light gray texture.  This also avoids issues with null pointers or missing objects because there is ALWAYS something there, even if it is just the placeholder object or an "error object".

When external systems are involved I love using constant IDs. The ID can remain the same all through development, be used by tools outside the game as well as all the systems within the game. You need to follow careful practices that IDs are never reused and each one is fully identified, but they are very fast to work with, small, and never change, making them ideal for most purposes.  There are usually few drawbacks for working with IDs. If you want to convert an ID to a pointer that is easy enough, even if you've got 10,000 IDs you can maintain a simple array of pointers for about 40KB or 80KB. That gives instant lookup to convert an ID to pointer, and less than a half microsecond to look up an ID by pointer (if it wasn't in the object already).

Your concerns about searching through hundreds of objects are probably not a concern. The CPU is amazingly good at identifying linear searches and will prefetch the data so the search is near instant.  For many data types and classes it is faster to do a linear search than a binary search even when there are thousands of items in the collection. A binary search may only hit 13 items where the linear search will average around 2500 items, but thanks to cache effects the linear search may require 200 nanoseconds versus 400 nanoseconds to jump around for the binary search, and while it requires thousands of times more effort, even a worst-case linear search is still on par with the time required for a binary search.

Share this post


Link to post
Share on other sites
10 hours ago, Juliean said:

Do you have the list-node ready when you remove from the middle?

I dont understand this. I just remove whatever unit needs to be removed. I create units at other times, and these are always added to the end of the list : "unitList.push_back(unit());"

 

10 hours ago, Juliean said:

Nope, doesn't make a difference in your case - since you are storing the pointer, which is always equally large regardless of what you actually store.

Lets be clear: you are talking about storing the "which 15 guys live inside this house" as pointers right? I better store them as non-pointers in the main list right?

Also can I really use vector for the "main" collection? If i want to use pointers to these and remove some, wouldnt that corrupt the pointers set to others in the vector? Wouldnt many of them need to be moved  in memory often if I have a vector of 500+ units and start to remove some of them from somewhere in the middle of the vector? While this wouldnt be a problem in a list right?

Thanks for the help!

Edited by suliman

Share this post


Link to post
Share on other sites

std::list is almost never the correct structure to use.

If you store pointers in the vector, then you can delete them from the vector and all your other pointers in the program will still work fine. You have to delete the object itself separately, and ensure there are no pointers to it elsewhere.

If you store objects in the pointer, then sure, when you delete objects from it, pointers to any object in the vector will break.

I'm pretty sure we covered - or at least touched upon - some of this in your other thread: https://www.gamedev.net/forums/topic/690589-debug-assertion-failure-c/ . Note that an iterator, in vector terms, is basically a pointer, and the same rules apply.

As a general rule of thumb, when objects need to be aware of each other, try to do this with the minimum number of pointers and data structures. Sometimes this will mean having to iterate over a structure to find something by name or ID instead of having a direct pointer - but it will save you a lot of grief in terms of not having to meticulously keep all these references valid and synchronised.

And for the other situations, I'd suggest becoming familiar with std::shared_ptr and std::weak_ptr. Weak_ptr is perfect for times when you feel that you need a pointer to something, but will find it awkward to update that pointer if the target gets destroyed. Weak_ptr handles that situation for you by automatically clearing itself when the object is destroyed.

 

Share this post


Link to post
Share on other sites
1 hour ago, suliman said:

I dont understand this. I just remove whatever unit needs to be removed. I create units at other times, and these are always added to the end of the list : "unitList.push_back(unit());"

Yeah, forget that part. I was thinking about a special list implementation we used at work, std::list probaby doesn't support this. Which only furthers my point, because deleting from a list by "removing whathever unit needs to be removed" is way slower than in a vector for most cases since you have to find which position to erase at.

1 hour ago, suliman said:

Lets be clear: you are talking about storing the "which 15 guys live inside this house" as pointers right? I better store them as non-pointers in the main list right?

Yeah, I was talking about that.

1 hour ago, suliman said:

Also can I really use vector for the "main" collection? If i want to use pointers to these and remove some, wouldnt that corrupt the pointers set to others in the vector? Wouldnt many of them need to be moved  in memory often if I have a vector of 500+ units and start to remove some of them from somewhere in the middle of the vector? While this wouldnt be a problem in a list right?

If you intent to store pointers to the objects, then you also have to store them as pointers in the main list, otherwise the pointers will become invalide when the vector has to interally grow in size, or you delete from a certain element. So your main list would become:

std::vector<std::unique_ptr<Object>> vObjects;

If you're not familiar with std::unique_ptr, get familiar with it ;) Otherwise you could also use smart-pointers as discussed.

As for the need to move objects in memory on removal, if you store pointers it doesn't matter. In C++11 with move-semantics, moving objects probably also doesn't matter that much (previously, you'd have to deep-copy objects around the vector). Otherwise, there is still the erase & swap-idiom that I mentioned:

auto itr = std::find(vObjects.begin(), vObjects.end(), object);

*itr = std::move(vObjects.back()); // instead of erasing, copy/move last object to this slot
vObjects.pop_back(); // then, remove the last object

If you do this, then there literally is no advantage to a list anymore whatsoever. The only downside is that you cannot do that if order is important (which it shouldn't in your case).

Share this post


Link to post
Share on other sites

I'll try to take all of this in:) Thanks!

I actually used <*unit> and iterators so I could delete the "loose" object. But I always though this handling was kinda messy.

So basically i COULD use a LISTof non-pointers (as my main collection) and pointers to these wouldnt be invalidated when I add/delete? It would however be slower that using a vector for looping through and such. If using a vector the pointers would be invalidated on add/delete (unless using <*unit> instead of <unit>). Is this correct?

Share this post


Link to post
Share on other sites

Yes, if you have a std::list<Whatever>, and your list has objects A, B, and C, then removing object B from the list will destroy object B, and preserve pointers and iterators to objects A and C.

Obviously you still need to make sure that anything else that refers to B is informed that the object has now gone, or is forced to access the object via a look-up that can also confirm the object is now gone. (e.g. iterate through the list, looking it up by ID.) There are a few ways you can 'delete the loose object' and that's actually the easy part - the hard part is maintaining all the other refererences. After all, if you're so sure that you need to preserve pointers or iterators to objects A and C when deleting B, that implies that there are probably pointers and iterators to B in your system as well.

And yes, it is a bit slower to iterate through a std::list than a std::vector, especially when the number of things you're iterating through is going up towards the hundreds or thousands.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!