[gameprogrammer] Re: storing lists of units

a good way for you might be quad trees (if you are making a 2d game).

an oversimplified explanation of how they work is your entire map is
contained in a rectangle right? (or you can make an imaginarey rectangle
thats big enough to fit around your map)

now, divide that rectangle into 4 smaller rectangles and make them a child
of the big rectangle.

next take each of these 4 smaller rectangles and chop them up into 4 smaller
rectangles each and make them the children of the rectangles they were cut
off from.

so now you should have a tree where each node has 4 children and you have a
3 level tree, w/ one root node and 16 leaf nodes.  In practice, you can
continue subdividing to your hearts content though.

each of the leaf nodes represent a rectangle on the grid.

so now what you do is store your game objects in whichever node they fit
into (IE if something is in the very upper left, this opbject would go in
the first child of the first child of the big rectangle that encompasses the
entire map).

If a game object lands on an "edge" between 2 rectangles or is too big to
store in 1 of the leaf rectangles, you just move to the parent and store it
there.  If it's too big for the parent node, or if it's on the edge still of
the parent node, move up another level to that node's parent and continue
until you are able to find a square that can contain the object completely.

whats the benefit of this you ask?

lets imagine that the player is in the lower right quadrant of the screen,
in the very bottom right corner and you wanted to know what was within 50
pixels of the player.

first you start at the topmost level of the tree which is a rectangle that
encompasses the whole map.  You check to see if the player is within the
rectangle defined by that node.  The player IS so what you do is check any
objects within that node to see if they are within 50 pixels of the player.
If they are, add them to a "hit list" and then recurse for the 4 child nodes
of this node.

The first child is the upper left quadrant, since the player is in the lower
right, they are not within 50 pixels of the upper left quadrant so we stop
there.

The next child is the upper right.  Similarly, the player is not within 50
pixels of the upper right so we stop here.

The 3rd child is the lower left. Same thing, the player is not within 50
pixels of the lower left so we stop here.

The 4th child is the lower right.  The player IS within 50 pixels of this
node so we compare the players coordinates to all objects in this node and
add any matches to a "hit list".  Next, we recurse for this node's 4
children (I'll spare you the details hehe).

So what this algorithm is good for is that you can quickly cull portions of
the map that you dont care about when you want to know what objects are
close to something or what objects are in a certain area.

If you are making a 3d game, the same technique is applicable, however
instead of having rectangles and quad trees w/ 4 children, you have
rectangular cubes, and octtrees w/ 8 children.

Instead of dividing a rectangle into 4 smaller rectangles, with an octtree
you are actualy dividing a rectangular cube into 8 smaller rectangular
cubes.

They even have a similar technique w/ circles or spheres, because testing
circle/sphere intersection can sometimes be alot quicker than rectangular.

In rectangular/cube intersection you have to test against each edge or
plane, but with circle/sphere all you have to do is get the distance from
the centerpoint and compare to the radius of the circle/sphere which is alot
faster.

Here's a cool optomization for circle/sphere testing too:

normaly w/ testing if a point is within a circle you would use the distance
formula like this...

distance = square root ( (x2-x1)^2 + (y2-y1)^2)

and then you would say...

if distance < radius
  point is inside circle!
else
  point is not inside circle

square root is a pretty slow operation to do, especialy if you are testing
for collisions of every object in your game, that can really add up.
luckily, we have a cool mathematic trick to speed this up.

here's our modified test, first we get rid of the square root in the
distance formula by squaring the formula:

distance = (x2-x1)^2 + (y2-y1)^2

and then we square the radius of the circle and compare the distance to
that, yes this is mathematicly equivelant for telling if a point is inside a
circle!

radius = circleradius^2

if distance < radius
  point is inside circle!
else
  point is not inside circle

there is a catch to this optomization though.  If you want to know how far a
point is from the center of a circle, you are going to still have to take a
square root of the distance since thats the only way to give you an actual
distance ):

depending on different stuff in your game, you might also be able to use
trig ratios to find the distance instead of using the distance formula or
modified distance formula.  a single divide is much faster than even the
enhanced distance formula.

anyways, hope this helps and that i didnt spam you with too much useless
information :P

----- Original Message ----- 
From: "Roger D. Vargas" <roger@xxxxxxxxxxx>
To: "Game programmer list" <gameprogrammer@xxxxxxxxxxxxx>
Sent: Tuesday, September 28, 2004 9:51 AM
Subject: [gameprogrammer] storing lists of units


> I need to store the list of NPCs in my game, and Im looking the best way
> to do so. I need to be able to quickly find only the ones closer to
> certain location to pass them to my lua script. Whats the best structure
> and algorithm to do this?
>
>
> -- 
> Roger Durañona Vargas
> Linux user #180787
> A cada momento nos rodea lo desconocido. Es alli
> donde uno tiene que buscar el conocimiento.
> Paul Muad'Dib Atreides. Children of Dune
>
>
>
> ---------------------
> To unsubscribe go to http://gameprogrammer.com/mailinglist.html
>
>



---------------------
To unsubscribe go to http://gameprogrammer.com/mailinglist.html

Other related posts: