• 15
• 15
• 11
• 9
• 10
• ### Similar Content

• Trying to get ideas here on how I could do this:
I have created a game for a university coursework assignment using a custom game engine (internal to my university, but it's based on OpenGL).
I know that I can use threading but am unsure how thread-safe the operation would be to init the game on another thread.

• I have a particle system with the following layout:
system / emitter / particle

particle is driven by particle data, which contains a range of over lifetime properties, where some can be random between two values or even two curves. to maintain a smooth evaluation between two ranges, i randomize a "lerp offset" on particle init and use that value when evaluating curves. the issue is that i'm using that same offset value for all properties (10ish) and as a result i'm seeing some patterns, which i'd like to remove. The obvious way is to just add more storage for floats, but i'd like to avoid that. The other way is to generate a seed of some sort and a random table, and use that to generate 10 values, ie: start with short/integer, mask it, then renormalize to float 0-1.

any other ideas?
• By dgi
Hey all ,
For a few days I'm trying to solve some problems with my engine's memory management.Basically what is have is a custom heap with pre allocated memory.Every block has a header and so on.I decided to leave it like that(not cache friendly) because my model is that every block will be large and I will have a pool allocators and stack allocators dealing with those blocks internally. So far so good I figure out how to place my per scene resources . There is one thing that I really don't know how to do and thats dealing with containers.What kind of allocation strategy to use here.
If I use vector for my scene objects(entities , cameras , particle emitters .. ) I will fragment my custom heap if I do it in a standard way , adding and removing objects will cause a lot of reallocations . If I use a linked list this will not fragment the memory but it's not cache friendly.I guess if a reserve large amount of memory for those vectors it will work but then I will waste a lot memory.I was thinking for some sort of mix between a vector and a linked list , where you have block of memory that can contain lets say 40 items and if you go over that number a new one will be created and re location of the data would not be needed.There would be some cache misses but it will reduce the fragmentation.

How you guys deal with that ? Do you just reserve a lot data ?

dgi
• By Hermetix
I am trying to setup the custom wizard for making a 3ds MAX 2018 plug-in (to export a character animation data), but I can't locate the wizard file folder to put the .vsz file in. In the 3ds MAX 2018 docs, it only mentions where the folder is in VS 2015 (VC/vcprojects). It's a VC++ project, but I don't see any folder in VC for the wizard files. I'm using VS 2017 update 15.5.6 Enterprise, and the folders in VC are: Auxiliary, Redist and Tools.

Thanks.
• By KarimIO
Hey guys! Three questions about uniform buffers:
1) Is there a benefit to Vulkan and DirectX's Shader State for the Constant/Uniform Buffer? In these APIs, and NOT in OpenGL, you must set which shader is going to take each buffer. Why is this? For allowing more slots?
2) I'm building an wrapper over these graphics APIs, and was wondering how to handle passing parameters. In addition, I used my own json format to describe material formats and shader formats. In this, I can describe which shaders get what uniform buffers. I was thinking of moving to support ShaderLab (Unity's shader format) instead, as this would allow people to jump over easily enough and ease up the learning curve. But ShaderLab does not support multiple Uniform Buffers at all, as I can tell, let alone what parameters go where.
So to fix this, I was just going to send all Uniform Buffers to all shaders. Is this that big of a problem?
3) Do you have any references on how to organize material uniform buffers? I may be optimizing too early, but I've seen people say what a toll this can take.

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

## 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 on other sites
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 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 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 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 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 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 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 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 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.