[gameprogrammer] Re: storing lists of units

This stuff would be cool to add to the wiki, please do it.

                Bob Pendleton
P.S.

I just have to get you guy in the habit of posting big long answers to
the wiki :-)

On Tue, 2004-09-28 at 13:05, Alan Wolfe wrote:
> 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
> 
-- 
+--------------------------------------+
+ Bob Pendleton: writer and programmer +
+ email: Bob@xxxxxxxxxxxxx             +
+ blog:  www.Stonewolf.net             +
+ web:   www.GameProgrammer.com        +
+--------------------------------------+



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

Other related posts: