Jump to content
  • Advertisement
Sign in to follow this  
SpikeViper

Getting objects within a range (In order, fast)

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

Hey guys! After a lot more work, my game is ~1000% faster, but the last optimization is making me scratch my head. To put objects into a dictionary to load, I check every chunk within a radius, get its distance, and have the dictionary sort them by distance. This means the closest chunks load first. I have a few problems with this.

 

1. I have to do !toLoad.ContainsKey(distanceSq), which is using about 30% of my cpu, because you cannot enter a value multiple times into a dictionary. Is there a faster way to prevent repeats?

 

2. Just adding to the dictionary gets laggy - it accounts for 40% of my cpu. I understand this is because of the amount of objects I'm loading.

 

So, I wanted to know if it was possible to get closest objects first without first iterating over all the possibilities. This would remove the need to queue my chunks or anything - just load them as they're detected, and also remove problems 1 and 2 above. I would be extremely appreciative if anyone knows a way I can go about this (It would finally make the game fully optimized)

Share this post


Link to post
Share on other sites
Advertisement

Well, right up front it sounds like you're just using the wrong container, but setting that aside it sounds like you're taking a naive approach to spatial sorting. What are "chunks" here? Do they move or change in any way?

 

Why is near-to-far sorting helpful? Do they really need to be in perfect near-to-far order, or can you just throw them in "really close", "close", "not so close", "far" buckets and go from there?

Share this post


Link to post
Share on other sites

If you're dealing with a large set of objects your best option is to partition the space.

I'd use an octree and place the objects inside the octree based on their position.

This way you don't have to iterate through all of your entities but only through those that

are in your area.

 

LE: If you load your objects from a database, you can easily model it to behave like an octree, thus saving time by loading

only what's needed.

Edited by Cristian D.

Share this post


Link to post
Share on other sites

Well, right up front it sounds like you're just using the wrong container, but setting that aside it sounds like you're taking a naive approach to spatial sorting. What are "chunks" here? Do they move or change in any way?

 

Why is near-to-far sorting helpful? Do they really need to be in perfect near-to-far order, or can you just throw them in "really close", "close", "not so close", "far" buckets and go from there?

 

So far, dictionaries are the fastest I've tried. These chunks stay still, are edited by the player,  and I want them to load from the closest to the player first (makes sense?)

 

 

If you're dealing with a large set of objects your best option is to partition the space.

I'd use an octree and place the objects inside the octree based on their position.

This way you don't have to iterate through all of your entities but only through those that

are in your area.

 

LE: If you load your objects from a database, you can easily model it to behave like an octree, thus saving time by loading

only what's needed.

 

I was thinking about this, but that's my last resort. I was wondering if there's a better way than just iterating.

Edited by SpikeViper

Share this post


Link to post
Share on other sites

 

 

I was thinking about this, but that's my last resort. I was wondering if there's a better way than just iterating.

 

Well, there's nothing wrong with iterating as long as you are iterating through a small set.

Thing is, there's no magic algorithm that could simply retrieve the objects within a range without any iterations.

Space partitioning is your best friend in your case and the implementation is not that complicated.

Share this post


Link to post
Share on other sites

 

 

 

I was thinking about this, but that's my last resort. I was wondering if there's a better way than just iterating.

 

Well, there's nothing wrong with iterating as long as you are iterating through a small set.

Thing is, there's no magic algorithm that could simply retrieve the objects within a range without any iterations.

Space partitioning is your best friend in your case and the implementation is not that complicated.

 

 

Got it - any good resources for learnings how to do octrees and stuff?

Share this post


Link to post
Share on other sites

As mentioned, a dict is probably the wrong container, they can get costly as they grow. How many chunks are we talking about?

 

Not sure the language you are using but you could restructure to something list this to solve handling multiple chunks at the same distance as each distance becomes a bucket for all applicable chunks, lots of memory churn if you build then discard on regular basis

 

IDictionary<double, IList<Chunk>>

 

I mentioned this in another thread of yours.... Are your chunks squares/cubes that have a regular spacing? If so, some form of 2d array where the x/y maps to x*chunkWidth, y*chunk[Length|Height] depending on how you manage your coordinates. If your data is grid based like this a 2d array is the fastest access and means no need to rebuild all the time.

Share this post


Link to post
Share on other sites

When you go for optimizations the details are everything.

 

1. I have to do !toLoad.ContainsKey(distanceSq), which is using about 30% of my cpu, because you cannot enter a value multiple times into a dictionary. Is there a faster way to prevent repeats?
 
It depends on which of the Dictionary types you are using and the quality of the hash. If you expect to actually find a value TryGetValue is sometimes faster than ContainsKey, especially if you plan on using the object. 
 
Your example is a little strange to me since it appears you are using distance squared as a key in the dictionary. That is not a typical dictionary key.
 
 
 
2. Just adding to the dictionary gets laggy - it accounts for 40% of my cpu. I understand this is because of the amount of objects I'm loading.
 
No idea about the number of objects you are adding.  If you know how many items you will be adding you should set its capacity up front.  It sounds like you should know how many items you will be adding, or approximately so. Expanding the capacity means a ton of work for a hashed container, and it can potentially need to expand its capacity every time you add a new item.

Share this post


Link to post
Share on other sites

 

When you go for optimizations the details are everything.

 

1. I have to do !toLoad.ContainsKey(distanceSq), which is using about 30% of my cpu, because you cannot enter a value multiple times into a dictionary. Is there a faster way to prevent repeats?
 
It depends on which of the Dictionary types you are using and the quality of the hash. If you expect to actually find a value TryGetValue is sometimes faster than ContainsKey, especially if you plan on using the object. 
 
Your example is a little strange to me since it appears you are using distance squared as a key in the dictionary. That is not a typical dictionary key.
 
 
 
2. Just adding to the dictionary gets laggy - it accounts for 40% of my cpu. I understand this is because of the amount of objects I'm loading.
 
No idea about the number of objects you are adding.  If you know how many items you will be adding you should set its capacity up front.  It sounds like you should know how many items you will be adding, or approximately so. Expanding the capacity means a ton of work for a hashed container, and it can potentially need to expand its capacity every time you add a new item.

 

 

distanceSq is a float, sorry. Also, I don't think sorteddictionaries can be set a size upfront. The amount of objects goes into the thousands. I'm researching a bit on octrees.

Share this post


Link to post
Share on other sites

As others have said, a dictionary is the wrong container. The huge glaring issue you will run into is the edge case when two objects are exactly the same distance apart. Then you have a key collision.

 

I'd at least use an array. If all you care about is having objects sorted by distance from the position, the objects can be inserted into the array in sorted order. To save on CPU time, you should also not use the distance itself (which has a square root in the calculation) and instead use distance squared.

As others have said, octrees may be the right call for you here. I wrote an article on octrees a while back which may be helpful.

However, to be truly helpful, you could elaborate more on what problem you're trying to solve. Your current solution might not be the best solution of the available solutions at your disposal :)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!