[gameprogrammer] Re: storing lists of units

I forgot, there's one more technique i know about that i think is worth
while/ relatively easy to code.

This technique is good for collision detection (and if you use some
imagination, probably good for some other things as well).  Actualy its just
good for a pre-filter to collision detection, what it's really good at is
finding "groups" of objects that possibly overlap.

after you have these groups, you can test them all against eachother
combinatorily or do whatever else you might want to do.

Here's a rough how you do it, if you want more details i forget what it's
called sorry but maybe someone else on this list knows, i got this out of
one of the "game programming gems" books.

Store every object in it's own circle or sphere (they dont all have to be
the same size).

Next, you build a linked list of start's and stops for each axis.

for example, you might use this struct:

struct SphereEdgeNode:
{
  float X,Y,Z; //Z only if you are in 3d
  char EndingEdge; //set to 0 if it's the starting side of a circle/sphere,
1 if its the ending side
  unsigned int ObjectID; //some kinda id or pointer to be able to reference
the object later
}

so lets say you have a circle at 30,12 with a radius of 4, you would add to
the list:

SphereEdgeNode Start,Stop;

Start.X=26;
Start.Y=8;
Start.EndingEdge=0;
Start.ObjectID=1;

Stop.X=34;
Stop.Y=16;
Stop.EndingEdge=1;
Stop.ObjectID=2;

next, after you have all your objects stored in this list, sort the list
based on the X axis (quicksort or something fast).

Then, initialize a counter variable to 0.

go through the list, when you hit a starting edge, you add 1 to the counter,
when you hit an ending edge, subtract 1 from from the counter.

if you subtract 1 from the counter, and the counter becomes 0, what you do
is take all the nodes from the begining of the list all the way up to the
last node you were at and make a new list w/ those (so now you would have 2
lists...or more as time goes on) and recurse to do the same to the new list.

After you are done w/ the X axis, you sort by the Y axis and do the same
thing...traverse through the list, breaking it apart where appropriate into
more lists.

If you are in 3d, you would then do it for the Z axis.

Then, after you are done with your last axis, start over with X! (evil
huh??)

the reason for this is complicated but you know you can stop analyzing a
list when you evaluate all axis' and for all of them, you havent had to
break apart the list in any way.

So, eventualy, you are done and left with 1 or many many lists.

Each list turns out to be a group of overlapping spheres believe it or not
(:

so, if you have alot of crap on your map, and it's all bunched together you
will have very few groups and if you care about finding what is colliding
with what, you will have to brute force test each thing against every other
thing (oh god!!!) which is a bad case scenario for this technique.

if you have alot of crap on your map, and alot of it is spread out, you will
have many many groups.  To figure out what's collided with what, you only
need to brute force test groups that have more than one object in them.

Like i said this is a really good pre-filter for collision detection.

Lets say you made warcraft 3 and you wanted to be able to tell when complex
models colide.

What you would do is put every model in it's own sphere and then do the
above technique.

Next, for the lists that have more than one member in them you know it is
possible that they have collision so then, you can take it down to the
polygon level and test for collisions, or if you want, you can use some
other technique at this point to optomize collision detection.

This fucked w/ my head alot when i was coding it, but i was once working on
a 3d space combat game where every object was contained in a sphere like
this.

however, each object sphere had child spheres (for instance if it was a
person in the sphere, there was a sphere around the head, one for each hand,
forearm, upper arm, foot, shin, upper leg, one for the torso, one for the
chest, one for the neck) and then from here, it would put the entire group's
spheres into a new list and then preform the same test again against this
level of spheres.  It could go to any depth needed to be able to get an
"accurate enough" collision detection system.

this stuff might be cool to add to the wiki

----- 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: