• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
BaneTrapper

Getting direct acces to vector<unique_ptr<My_Class>> but there are these factors...

8 posts in this topic

Hello.

So i have a

std::vector<std::unique_ptr<My_Class>> list;

And i want to have direct access to My_Class object as.

My_Class * ptrMy_Class = list[id];

the issues:

The list is going to have its elements be added and erased during run time.

That means the list[id] can get erased, and the ptrMy_Class has no way to check if the object still valid?

 

So how do i get a pointer or a reference to the object, except giving each My_Class unique ID and looping the whole list checking for matching ID.

But downfall is that each My_Class will try to access other My_Class at least once a second and list.size() is more then 1000 at any given time?

0

Share this post


Link to post
Share on other sites

Like dejaime said, you're probably looking for std::map.

You might also want to consider using std::shared_ptr instead of std::unique_ptr as you would have to remove a unqiue_ptr from the list/map when saving it as a separate variable (or you can use the get() method, but that would defeat the purpose of smart pointers).

0

Share this post


Link to post
Share on other sites

Depends on what the id represents and where it comes from (how you calculate/generate it).

If it comes from an ever increasing id counter of some kind, use unordered_map<[u]int32_t, unique_ptr<Object>>.

If it comes from finding a free index in the vector, use the vector, and instead of list.erase(), use list[id].swap(nullptr). This leaves the unique_ptr in the vector (so it can be reused for the same id), and calling list[id].get() will give you nullptr.

 

Don't use shared_ptr unless you know for a fact the lifetime of the object needs to be managed by multiple things.

The point of smart pointers is automatic object destruction for stuff allocated on the heap. If you're using a unique_ptr, you never want to save the underlying raw pointer somewhere else, except for temporary reads during which you know the object will still be alive.

0

Share this post


Link to post
Share on other sites

The problem here is that "id" is not really an ID but an index to an array (or vector, as it happens). Which, as you noticed, isn't unique or may even change if you insert/delete something at a lower index.

 

There are two ways around that issue. The first one is easiest, as proposed by dejaime: Use a map. It's the correct container to use for "look up object by key". Then you just need to make sure your keys are unique, which is easy (just increment a global variable, or return a static which you increment from a global gen_id() function).

Of course, a map is slightly more expensive than a vector on the average (objects are not stored in a contiguous area, lookup usually involves 3-4 indirections, and iteration isn't as trivial as ++pointer), so in some cases this just isn't fast enough (usually it is, though!).

 

In that case, you might keep an implementation backed by a vector, but use handles rather than indices and pointers. What is the difference? A handle uses (abuses) some of the bits in its integer value to encode a revision number. You can tell if two handles refer to the same object if both the index and the revision number are the same (i.e. the complete "binary number" is identical) and you can tell whether an object has been deleted and replaced (same index, different rev) or is the same one you expect.

That is of course a lot more work to implement (and debug!), but it may be somewhat more efficient due to being more compact and more cache-friendly, and lookups only involve a small, constant number of steps. There is ready-to-use code in one of the early Game Programming Game books for that too, but don't ask me in which one.

 

I would first profile whether it's worth the trouble, though. For 90% of all cases, using std::map is just good enough (and it is the correct thing to do, it will not make people frown when they look at your code!).

0

Share this post


Link to post
Share on other sites

I feel that map will be slow.

Thinking about how many times i will have to search for object. Having a vector and removing peaces from it is also a downside thus i decided:
I will have vector in which i will hold all data. When i want object removed, i will just release its pointer. and save the vector position as empty.
The issue: In case allot of objects get removed and little are added, the vector starts to stall, because it never sizes down, but it will provide me with possibility of easy access, and i can make something that will check to sort it when 33% of it is just empty objects

int VecID = 921;
std::vector<std::unique_ptr<My_Class>> list;
std::vector<int> listEmptyPos;
EraseListElement(VecID);
//Adds 921 to listEmptyPos, and releases pointer in list

I really need it to be fast, the downfall compared to gain is unmatched to using map when size is always gonna be 1k+ of objects.

 

Thanks on suggestions, i posted above my solution.

Edited by BaneTrapper
0

Share this post


Link to post
Share on other sites

 


I feel that map will be slow.
premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%.

- Donald Knuth

 

I agree, but if i am making something i will make it right from start, instead of spending time redoing it when i find out its slow, when i know it will be slow, chances that compiler would optimize are close to none, but there may be something out of my knowledge so profiling would be the choice, i just don't have time and i am certain that doing vector thingy i said would provide me with great performance and probably 10-15% more work, which ends up in 10 minute of coding when i know exactly what i am doing or what i want want.

-1

Share this post


Link to post
Share on other sites

when i know exactly what i am doing or what i want

Do you? Early optimization is a problem when you do not. Believe me, when I am starting a program, I never know precisely what I want. I only really understand my needs when part of the code is done and possibly redone some bits here and there.

 

Considering that you'd be using a vector to simulate a map, you'd be wasting a lot of memory and, instead of letting the map care for itself, you'd be concentrating all its relocation to a single operation.

 

If your containers will really be as big as you say, that a map wouldn't suffice, believe me, your cleanup will halt the program for fractions of seconds, causing FPS drops and other issues. This can also affect your physics engine, by generating exceptionally big "delta times" for it to simulate with. In addition, searching the way you mentioned your lookup would result in O(n) complexity or higher (any empty slots would make it > O(n) ), while std::map has it O( log(n) ).

 

In other words, trying to force a vector into a map would probably result in a lot more work for something that performs slower and uses more memory.

Unless you have good algorithms to insert, remove and search (as a red-black tree for an example), or some neat mechanism to avoid runtime stalls when rebalancing and possibly an automated memory pool to control your vector... but that is basically recreating the map container.

Edited by dejaime
2

Share this post


Link to post
Share on other sites

I agree, but if i am making something i will make it right from start, instead of spending time redoing it when i find out its slow

This is a good intent, but it works exactly the other way around. First, you try to do a correct implementation. Correctness is always first.

 

That is, you choose the algorithms and containers which are "correct" for what you want to achieve (in this case, mapping a key to an object ? map). Then you make sure that the program indeed works correctly and is robust for any possible input. And only then you make sure that it performs at the required speed given the minimum spec hardware. If it does, all is good, job complete.

 

Only if you find out that the requirements (say, game runs fluidly at 30fps) are not met with the minimum hardware specs that you target, you start to tweak things like this. And you never tweak a part before profiling, because you have no way of knowing whether you are turning the correct knob without measuring. Guessing is a bad advisor.

 

There is that saying: A good horse jumps over every obstacle. But an excellent horse doesn't jump higher than it needs to.

Edited by samoth
2

Share this post


Link to post
Share on other sites

Ive tested on paper and code, vector provided allot desired performance which was unnoticeable in % cpu usage 0-1%, meanwhile map cpu usage was noticeable ~5.

But vector at worst case used ~15% more memory usage then map, which with 1000objectts  with ~200bytes of data each end up with 150*200, 30kilobytes... unnoticeable memory vise because main platform is PC.

 

With vector i use this:

Class My_Class
{
pubic:
short myVecID;
short TargetObjectVecID;
bool isInUse;
}
std::vector<My_Class> listObject;

Efficiently i can access it directly via

Object o;//Object in use
listObject[o.TargetObjectVecID].Something();

instead of looping and searching trough the whole map if i where to use one, to match the ID.

 

How i manage deleting objects and adding object

//Concider My_Class from above
std::vector<My_Class> listObject;
std::vector<short> listObjectEmptyPos;
 
//Erasing object
listObject[object_id_to_erase].isInUse = false;
listObjectEmptyPos.push_back(object_id_to_erase);
 
//Adding object
if(listObjectEmptyPos.size() > 0)
   listObject[listObjectEmptyPos.back()] = NewMy_Object;
   listObjectEmptyPos.pop_back();
else
   listObject.push_back(NewMy_Object);

 

I am inexperienced in std::map usage, but vector provides me with better cpu usage in theory and practice, and memory is no issue. So i chose vector over map.

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0