Storing large number of objects in a map (Gaming)

[D.V.D]

So I was reading a PDF of the Cuda program for Nvidia Graphics Cards and when I was thinking about how to create my own graphics engine, I came across this problem. So in this case, let's say that im ray casting to find objects on a map that is 10km by 10km. If the smallest point on my map is 1 millimeter, that would result in the map being 10 000 00 00 0ml by 10 000 00 00 0ml. This would result in a ridiculously large 2d array of 1 000 000 000 000 000 000 mm square. So using a 2d array to store all objects on the map would result in terabytes of information which is largely impossible. So then came the problem, how would I find objects on my map? I could loop through every object on the map every time a ray moves to see if the object is hit by the ray but lets say you have a very detailed scene. For example, in Warcraft 3 you would have sometimes 10 000 to 100 000 doodads on a detailed map followed by a number of units that can also be from hundreds to thousands depending on the map. This however is warcraft 3, if your making a detailed map like this so for example skyrim, you can have millions of objects on the map and looping through each one of them for every ray would be far too slow. So my question is, are there any efficient ways of storing large amounts of objects on a large map while not going overboard in the number of operations done to find the objects using ray casting methods.

 

[s3rius]

Usually you don't store what object is in each square millimeter (that's nearly impossible, as you said), but you store each object's X/Y coordinate.

Also, for such large maps you only store a small portion of all objects for ray-casting (or anything else). Say 100m².

Now, I know how games like Dead Rising handle their hundreds of zombies etc:

They take two lists. They put all objects in this 100m² radius into the two lists. The first list keeps them sorted by X-position, the other one by Y-position.
Now it's very easy to determine the position of nearby objects relative to any object.
Just search the object in both lists and check all following (or preceeding) objects whether they intersect the ray.

 

[D.V.D]

Storing the map in a array is only helpful for small maps that would be for example, rooms or inside of houses.

Oh i see, but wouldn't you have to loop through all objects/models on the map to figure out what objects are near you? And for larger maps, that turns out to be thousands+ amount of models in the game.

 

[s3rius]

You'd have to sort them once into the two lists, then regulary update them so the lists are up-to-date.

After that you have a list that looks like this:

[Unit 2] <-> [Unit 6] <-> [Unit 1] <-> [Unit 3] <-> [Unit 5] <-> [Unit 4]

All units are sorted by X-position, so U2 has lowest X position and U4 has highest.
If you now want all units nearby U1 you have to find U1 in the list. Then you can take the previous and following units in the list and see if they're close enough. Once a unit is too far away you know that all following units are too far away too (since they're sorted by x pos).

This would already be enough to make a decently fast search if you have tons and tons of items.
The second list (the only sorted by Y) can help you in finding it even faster, but isn't actually needed so much.

 

[D.V.D]

Oh i see how it works. Before I was thinking of dividing the map into 10 000 squares, if the map is as labeled as 10 by 10km. Each square would then be 10m by 10m and if a object moves or is created, its position is rounded to the nearest square. Each square would then have a list of objects in it and you could rather than loop through all units on the map to find their position, you would just loop through all units in the square that the ray is in.