Jump to content

  • Log In with Google      Sign In   
  • Create Account

Vector Efficiency question


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
13 replies to this topic

#1 DarkRonin   Members   -  Reputation: 616

Like
0Likes
Like

Posted 27 June 2014 - 05:04 AM

Hi Guys,
 
I am writhing a game where I have all of the game assets in an std::vector.
 
But, I am wondering if there is a faster way to do what I am doing.
 
Essentially, when ever I deal with a particular game asset I get the data from it similar to below
 

std::vector<ObjectInstance>::iterator it;
for(it=vObject.begin();it<vObject.end();it++)
{
	if(szName==it->szName.c_str())
		return it->x;
}

So, everything is handled this way, collisions, rendering, positioning, etc...

I am finding (in particular collisions) that this seems to be fairly expensive on the CPU as I am calling the above code (or similar to) possibly several hundred (maybe thousand) times per loop. Whilst it works perfectly in its current form, I am worried that when I get a lot of game assets in the scene (currently only four) that this will be too slow.

For example, I have a function that sorts out collisions and if the object is intersecting with another object the function calls a while loop to place the object back where it should have been before the collision.

So, I did a check. If the object is 256 pixels deep into the other object it takes 0.5 seconds for the loop to be exited.

Normally you wouldn't let an object collide that far into another object. But, the recovery time is quite long.

Some testing points the finger at the Vector routine (as it loops over and over).

Is there a faster way to achieve what I am after (while making the code as flexible as it is)?

Thanks in advance smile.png



Sponsor:

#2 Jan2go   Members   -  Reputation: 942

Like
4Likes
Like

Posted 27 June 2014 - 05:18 AM

If you always search for objects by name, you could use std::map to get the right one. That way the lookup is only O(log n) instead of O(n); you won't see a difference with your 4 objects, but once you add more objects you will see the difference. When using std::map, you might also take a look at hashing to avoid string compares when looking for the data, as string compares can be quite expensive compared to integer compares.

#3 kunos   Crossbones+   -  Reputation: 2207

Like
0Likes
Like

Posted 27 June 2014 - 05:21 AM

I don't really understand how you use that code.. it would be interesting to see an usage example.

 

If you are retrieving often your entities by name (but I don't see why you should).. you might want to use a std::map<string,Object*> .

 

As I said.. I don't see why you'd want to call your objects by name.. to do stuff on your objects you just need a loop:

 

for (auto object : objects)

{

object->doStuff();

}


Stefano Casillo
Lead Programmer
TWITTER: @KunosStefano
AssettoCorsa - netKar PRO - Kunos Simulazioni

#4 Kian   Members   -  Reputation: 242

Like
3Likes
Like

Posted 27 June 2014 - 05:30 AM

That will call doStuff on every object. If you only want to call a method on one object, however, it's not helpful.

I'll also suggest that you use a map for lookups, but I would suggest changing the key from string to some kind of id like an unsigned int. Maybe hash the string, for example.

#5 DarkRonin   Members   -  Reputation: 616

Like
0Likes
Like

Posted 27 June 2014 - 06:08 AM

Thanks for the suggestions so far guys :)

So the string comparisons are relatively slow? The reason behind it was so I could call objects "player", "ground", "enemy", etc..

I could 'define' or 'enum' them instead if that would speed up the loop.

#6 NotYourAverageUser   Members   -  Reputation: 500

Like
0Likes
Like

Posted 27 June 2014 - 06:24 AM

+1 for the std::map<>



#7 kunos   Crossbones+   -  Reputation: 2207

Like
2Likes
Like

Posted 27 June 2014 - 06:25 AM

The reason to put object in a list is to allow fast iterations of common operations.

If you need operation on a "player".. then you should have a Object* player; Object* ground; and so on.. having to go through a list to find a object EVERY TIME makes no sense, and having a list without performing common operations on that list doesn't make sense.

 

Unless it's a VERY rare occurrence, it should never be necessary to retrieve an element from a list, by name, in the game loop.

 

In other words.. if you are retrieving an object by name "hundreds" of time in a frame, you are doing it wrong, map or no map.


Edited by kunos, 27 June 2014 - 06:31 AM.

Stefano Casillo
Lead Programmer
TWITTER: @KunosStefano
AssettoCorsa - netKar PRO - Kunos Simulazioni

#8 DarkRonin   Members   -  Reputation: 616

Like
0Likes
Like

Posted 27 June 2014 - 06:49 AM

Thanks for the reply kunos.

You are probably right. I'll have to take a look at my code and see if I can remember why I went down that vector path in the first place - LOL

I am about a month in to this project (i remember it made sense at the time of designing - but no idea at the moment - due to being sleepy hehe).

I am about to go to bed and am way too tired to think at the moment. So, I'll take a look again in the morning when I am refreshed again.

[edit]
Thinking further on this I can't see how you could avoid retrieving object information hundreds of times per frame, as a level might consist of hundreds of ground tiles alone.

In my object class I have a variable that marks the object as solid and then I sort these (once) per loop to bring the solid objects to the top of the vector to cut out unnecessary comparisons. So, if I have 100 solid objects and 900 un-solid objects the loop will be more efficient than an unsorted one.

But yeah, I'll take a good look at what I am doing in the morning.

Thanks again so far. :)

#9 Jason Z   Crossbones+   -  Reputation: 5300

Like
4Likes
Like

Posted 27 June 2014 - 07:20 AM

If you are using a vector, you will get a contiguous block of memory used for your objects which may be helpful for cache performance and things like that.  If you want to find a particular entity, then I would suggest using an index into the vector instead of by string name.  You could easily create a helper function to convert to / from index and name, which will ease the process.

 

I wouldn't see any particular need to use a map in this case, since you don't need to really store the items by a unique ID or key.



#10 jHaskell   Members   -  Reputation: 1087

Like
1Likes
Like

Posted 27 June 2014 - 09:07 AM

With regards to iterating over all objects in a given container, there's really nothing that beats vector.  It's unlikely that changing the container will have any significant impact on your collision detection code.  Should be perfectly fine for entity logic and rendering though, and there are options to eliminate the necessity of actually deleting elements in the vector to avoid that problem.

 

For collision detection though, If your collision detection algorithm is O(N^2), there's no container that's going to allow that sort of brute force method to work even remotely efficiently for large N.  You need to focus more on the collision detection algorithm itself, partition your objects to minimize the total number of collision tests that need to be made.  A simple grid, a BSP tree, etc.  That's where you'll see real gains.



#11 King Mir   Members   -  Reputation: 2050

Like
1Likes
Like

Posted 27 June 2014 - 12:53 PM

If you're iterating over all members, a vector is as fast as it gets. If you want to be able to lookup by id, a sorted vector is pretty fast too.



#12 Servant of the Lord   Crossbones+   -  Reputation: 20998

Like
6Likes
Like

Posted 27 June 2014 - 01:27 PM

If you must have string-lookups, then use std::unordered_map.  By using std::unordered_map, you are saying, "I don't care whether you preserve the order I add elements to the map, you can store them however you want, just make them as fast as possible."

 

However, string comparisons are (relatively) slow. If you're only gonna have 10000 or so entities, it'd probably be fine, but strings have other problems: How do you handle case sensitivity? std::strings, and thus also strings in maps, are case-sensitive by default, so "Bob" is not the same as "bob" or "BOB". You can normalize your names before using them to look up elements, but then that's another issue of unnecessary slowness. Also, what if there is more than one enemy named "skeleton" - you'll have to detect that, and then create "skeleton_01", "skeleton_02", and so on. For what purpose?

 

If you want better efficiency, use consecutive integer keys (e.g. 0, 1, 2, 3, etc...) with std::vector, doing myVector[index].

 

When you add an entity, do something like this:

typedef size_t EntityID;

EntityID MyClass::AddEntity(const Entity &entity)
{
    EntityID entityID = myVector.size();
    myVector.push_back(entity);

    return entityID;
}

Then you can go:

EntityID entityID = myClass.AddEntity(Entity(stuff));

And you save your entityID for later lookups for things like collisions and so on.


Edited by Servant of the Lord, 27 June 2014 - 01:47 PM.

It's perfectly fine to abbreviate my username to 'Servant' rather than copy+pasting it all the time.
All glory be to the Man at the right hand... On David's throne the King will reign, and the Government will rest upon His shoulders. All the earth will see the salvation of God.
Of Stranger Flames - [indie turn-based rpg set in a para-historical French colony] | Indie RPG development journal

[Fly with me on Twitter] [Google+] [My broken website]

[Need web hosting? I personally like A Small Orange]


#13 Álvaro   Crossbones+   -  Reputation: 13905

Like
0Likes
Like

Posted 27 June 2014 - 02:00 PM

What Servant of the Lord said. The only reason to have strings in such a data structure is for debugging purposes.

#14 Shannon Barber   Moderators   -  Reputation: 1390

Like
0Likes
Like

Posted 05 July 2014 - 10:14 PM

So the string comparisons are relatively slow?
 

 

You would have to get very creative to find a slower way.

 

Perhaps you load a data file into a vector (or map) with string names, but then you would process that data into trees of data using pointers.


- The trade-off between price and quality does not exist in Japan. Rather, the idea that high quality brings on cost reduction is widely accepted.-- Tajima & Matsubara




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS