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)

I am assuming you are using C# or Java by the term dictionary. I'd like to ask for some context by what your chunk is, and what your engine is trying to do. For now I'm going to assume you mean terrain paging.

You're not really using a good option here. Dictionaries are not a viable option for massive amounts of data in realtime use. They will make constant allocations and/or copies as more and more data gets moved in. You want to keep data writing operations on them to a bare minimum.

Don't bother with trying to load in chunk data as you need them. Do that only for the resources. Assuming you are not doing anything crazy stupid, you can safely load most of your world data into memory, and then load the visual resources as you need them sense they take the most space.

If your data is dense and in a regular grid, you could do without any runtime sorting with a percomputed indirection table looking like this for a 5*5 area:

54345
42124
31013
42124
54345

The number is the distance from the center cell, and there would be a second number for the grid index.
After sorting this by distance you get a range of cells per distance, and adding your player grid index to the resulting indices allows to use the same table for any position.

If the data is coarse, a quadtree approach can do this too by classification of player position against current node.
(For a distance sorted traversal order, it matters in which order you visit the child nodes.)
If the player is inside the node, see which quadrant (child region) it's in.
If player is outside, see which node corner or edge is closest.
This gives 12 possibilities times a sequence of 4 children, so the precalculated order table you need is just 24 bits.
(You can get better accuracy be combining quadrant / edge / corner requiring 128 bits)

Both ideas can be extended to 3D (grid->volume, quadtree->octree).
To avoid the problem of 'my object intersects two cells, but i don't want to stor in in both', look up 'loose octree', works for grid too.

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?

http://programmingmind.com/projects/basic-octree

Check out the source code, it's pretty self explanatory.

Good luck!

because you cannot enter a value multiple times into a dictionary. Is there a faster way to prevent repeats?

You can't use anything like an std::multimap (c++)? Such a dictionary would allow multiple values per key, and provide you a range of values matching the key.

because you cannot enter a value multiple times into a dictionary. Is there a faster way to prevent repeats?

You can't use anything like an std::multimap (c++)? Such a dictionary would allow multiple values per key, and provide you a range of values matching the key.

And if you sort on distance from small to large, iterating over it gives you the elements in the right order.

However,no matter how, sorting is expensive. If you can get rid of it, that is much better.

I guess I could use a C++ dll to handle this in C++ instead of C#. I don't know C++, but I would be willing to try if that has any chance of speeding it up.

Please don't. The idea of mixing C++ into your C# scares me. Maybe it's perfectly fine, but like this guy said.. since it's almost Christmas.. (ya, that's right folks just 227 days away!)

http://stackoverflow.com/questions/380595/multimap-in-net

Use that, or look for something like that. Furthermore, I didn't bury my head too deep into your post, so I don't know if that *will* speed anything up. It just sounds like what you are asking for.