## Organizing Objects in my Game

Sage
Posts: 1,066
Joined: 2004.07
Post: #1
I have reached a point where I need an efficient way of keeping track and checking a fair amount of objects in my game including the user, other players (well I'll need it later but right now there are no other players), eventually enemies, other obstacles (boxes and such), and the level. I figured I'd make a level class that contains information on all of the objects and it will sort through and check but it seems like there might be a better way.

In a game like this (3d with a fair amount of objects and collisions from projectiles) how would you suggest (or how do you) organize all the objects so as to be efficient when updating, tracking, and checking all the objects?
Moderator
Posts: 1,563
Joined: 2003.10
Post: #2
I normally use a simple space partitioning technique. I keep a "master" list of objects in the world somewhere, and a separate 3-dimensional array which basically divides the game world into smaller cubes. Each cube contains a vector of pointers to all of the objects that occupy that space, which is updated every time an object enters or leaves a cube. For collision detection, etc., you only need to check against objects which occupy the same cube(s).

The size of the cubes is fairly arbitrary; you may just have to play with it until you find an appropriate granularity. A more efficient way to do it would be to use an octree algorithm, which is similar to what I described, but the size of the cubes is dynamic. Octrees are more difficult to implement, though.

How big are your levels? Are they relatively small confined areas, or large landscapes the player is free to roam?

- Alex Diener
Sage
Posts: 1,066
Joined: 2004.07
Post: #3
Right now the levels are small but I plan to enlarge them to relatively large areas. I'll try and find a way to do the cube thing like you are suggesting.
Member
Posts: 156
Joined: 2002.11
Post: #4
As a side note, make sure you check the objects in the neighboring cubes as well for interaction between objects. You should do so because two objects may be located very close to the boundaries of two distinct cubes, so they may interect with each other.
Moderator
Posts: 916
Joined: 2002.10
Post: #5
if an object overlaps multiple cubes, then you should include a pointer to it in all cubes it overlaps in
Sage
Posts: 1,066
Joined: 2004.07
Post: #6
Assuming that my player (which is a human) is 6 units high (going for 1unit = 1ft), how big would you suggest making each cube? I don't want them too large or I run into the need to subdivide them but if they are too small it seems like that'd be inefficient. I was thinking using a cube that was 50x50 ground area and 25 tall. What are your suggestions?
Member
Posts: 151
Joined: 2002.09
Post: #7
Nick Wrote:Assuming that my player (which is a human) is 6 units high (going for 1unit = 1ft),...

feet? that's crazy!
let me ask you: how many feet does a mile have? (and don't look this up)
Moderator
Posts: 460
Joined: 2002.09
Post: #8
Hog Wrote:feet? that's crazy!
let me ask you: how many feet does a mile have? (and don't look this up)

Point taken, but if he doesn't need miles in his game then it's irrelevant. His level size could be 1,000 feet x 1,000 feet, for instance.

Look at it this way. If you've grown up with inches and feet it is very easy to say approximately how tall a person is in feet, or how large a car is. Whereas we don't know how many meters that is. So sizing his game objects may be much easier for Nick to do in feet. That's a bit less abstract than your objection.

On the other hand, this could be a good excuse for Nick to practice his metric units, if he has a mind to.

Measure twice, cut once, curse three or four times.
Sage
Posts: 1,066
Joined: 2004.07
Post: #9
I thought about using a metric system but 1unit = 1m seemed to small for me. Any suggestions? I'm just afraid that if I shrink down the textures I'll lose quality (though I can use mipmapping).

To answer your question (without looking it up) there are 5280 feet in a mile. I understand that'd be huge in the unit measurement so I'm up for suggestions. Nothing set in stone yet.
Member
Posts: 156
Joined: 2002.11
Post: #10
I am comfortable with both systems, but I usually use metric for engineering and physics, so using the metric system for games seems like the way to go. My first game used Astronomical Units and light-years. It was interesting to design a system that would work with distances that ranged from less than a meter to several light-years.
Moderator
Posts: 776
Joined: 2003.04
Post: #11
Nick Wrote:I thought about using a metric system but 1unit = 1m seemed to small for me. Any suggestions?

Hmm... 1m > 1ft
You could use 10m as a unit if that is still too small, or 100, or 1000 (1km).

FCCovett Wrote:My first game used Astronomical Units and light-years. It was interesting to design a system that would work with distances that ranged from less than a meter to several light-years.

Interesting related post:

(In particular, the third article mentioned: http://www.gamasutra.com/features/20020712/oneil_01.htm )
Sage
Posts: 1,066
Joined: 2004.07
Post: #12
PowerMacX Wrote:Hmm... 1m > 1ft ;-)
You could use 10m as a unit if that is still too small, or 100, or 1000 (1km). :-)
I meant the number of units per meter was too small but I couldn't find a good way to do it. I started thinking about using 3units=1m or something like that but I'm not sure. That's not very even so I started thinking about 5units=1m so that 1unit=2dm=20cm and that sounded good but I'm not sure yet.
Member
Posts: 184
Joined: 2004.07
Post: #13
Usually for these sort of things like magic numbers, you have to keep playing around until it works right. Just as a bit of advice, you will want to have your game load a configuration file (or if your game is scripted, have the number come from the script instead of hard-coded) so you can try a bunch of different values without having to recompile, since you will almost certainly have to try a bunch of different values.