I have a question about setting up the internal representation of a game world. Basically I am going to have a 2D game world where game objects can occupy the same space. It is a space themed game where from the perspective of the player, the world is divided up into sectors and then world is composed of a grid of sectors. The simplest and most strait-forward approach is to simply have some list of objects, maybe a list attached to a sector object, or maybe just everything in one big list. However such a list isn't efficient for searching. One important search will be: What is within 5 spaces of (X,Y)? This search will happen very frequently and will be used for such things like giving a player a view of what is around a unit, or giving a unit a list interesting things in the area such as enemies, friends, resources and whatnot. A linked list of objects will be really slow to search. I imagine 1000 objects wanting to know all the objects within 5 squares of each other? Another container can be a 2D array. Lets say that my universe is 1k x 1k big. If objects attach themselves to a cell then finding all objects within 5 spaces of (500, 500) will be fairly fast. The problem with this approach is that it takes a lot of memory. If each 'cell' only has 1k of data, then a 1k x 1k grid would suck up 1 gig of RAM. Of course I could just make smaller grids too. However it is worth noting that most of a 1k x 1k grid will be empty. Space, after all, has an abundance of nothing. How about a sparse array? In theory that would be the answer, but there is no native sparse array types in c# or cpp for that matter. In a manner of speaking though, a sparse array is just a wrapper for what I have asked. The implementation is what matters. Most I have found use a hashcode, which isn't of use to me because I need to reference the element by Cartesian coordinates. Does anyone know of a data structure I can use that will let me do fast searches for collections of objects in an (X, Y) system but isn't a total memory hog?

google for:

octtree
quadtree
kdTree

-me

First of all, there is no One True Data Structure for holding your game objects. It's not just that there are tradeoffs between them. Fundamentally, a single data structure will not be adequate for all your needs. So use multiple ones.

For proximity searches, you'll want either a grid, a quadtree/octree, or an adaptive binary tree. BTW: I'm not sure how you'd use up a thousand bytes representing a single cell in a grid, but if you've figured out a method of doing that I suggest you figure out a different method.

The 1k bytes is just a number I pulled out of the air. If each cell had a list of all the object in it, then that could easily suck up 1k. How much memory does an empty instance of a list class (in C#) take?

I know what and Oct tree is, and I can imagine a what a quad tree is, but how are they used to help store objects in a manner where I can easily find all objects at location X and Y?

How about memory management as objects move around? Leaving cell X, Y and going to X + 1, Y.

Quote:Original post by TheSilverHammer
How about memory management as objects move around? Leaving cell X, Y and going to X + 1, Y.

That's what pointers are for. Or unique object IDs, if you must.

Quote:How much memory does an empty instance of a list class (in C#) take?

Dunno about C#, but 64 bytes should be a generous estimate for a class with only one or two pointers as member variables. But as you say, a sparse data structure is the right way to go when you have a big, mostly-empty grid. Accessing an empty cell could return a singleton, which would handle queries and additions appropriately.

Quote:Most I have found use a hashcode, which isn't of use to me because I need to reference the element by Cartesian coordinates.

Surely C# has a dictionary or hash map data type; even C++ has std::map. They do the hashing for you, or at least O(log n) lookups. Map the coordinates to the appropriate cell object.

Quote:Original post by TheSilverHammerI know what and Oct tree is, and I can imagine a what a quad tree is, but how are they used to help store objects in a manner where I can easily find all objects at location X and Y?

Take another look at octrees and quadtrees. They are used for spatial partitioning. Meaning that if you want to know all the objects in say an AABB region you can recursively drop through the tree starting with the 8 top level nodes and going down until you hit the leaf nodes containing most objects (depending how you set it up).

Quote:Original post by TheSilverHammerHow about memory management as objects move around? Leaving cell X, Y and going to X + 1, Y.

This is one major hit about octrees and quadtrees. Moving objects aren't their forte. There are methods (which I have little experience with) that solve this problem though.

For my current "game engine" framework I've really been delving into nested grids. While they are similar to quadtrees they allow for a greater level of control on complex areas and best of all grid transversal and fast AABB region checks.

You're going to have to research octrees and quadtrees in depth however to learn what's best.

Quote:Original post by TheSilverHammer
The 1k bytes is just a number I pulled out of the air. If each cell had a list of all the object in it, then that could easily suck up 1k.

If you're talking about 100+ objects in the one cell, yeah. But as you said, space is mostly empty, so I'm assuming this will be a rare occurence.

Anyone have links to a quad tree implementation that arn't so bad a moving objects around but are still great for finding all objects within N units of (X,Y) ?