gdalgorithms-list

[Algorithms] Broadphase collision

[Priyank J. <fly...@gm...>]

Hi,
I am trying to implement broadphase collision for my game (3D FPS 
genre). I have been reading about the commonly used techniques and I 
have tailored the grid approach to my game. I want to know if this is 
the right direction to go in or not.
The involved actors are :-
Players
Bullets(Fired)
Weapons (placed at points located throughout the level, which other 
players can pick up, aka static objects)
World
As of now, I am just trying to get the Players and bullet collision pairs.
Players: Players are represented by a bounding sphere, located at a 
position and moving with a velocity. Each player would have 
approximately the bounding sphere of same size.
Players - weapons
Players - World
Bullets: Bullets are represented by a segment with a start point and an 
end point (using posn, posn + vel) (each frame). Bullet can hit :-
Fired Bullet 	Player
(Other) Bullet
World

Approach:
- As each player and bullet is created, associate a reference to each 
entity within CollisionMgr as a list<Player*> and list<Bullet*>.
- On each update frame, do the following:
- For each player, find Cell(s); it is associated with :=> list< Cell* > 
PlayerCells
- For each Bullet (segment), find Cell(s); it is associated with :=> 
list< Cell* > BulletCells
- For each entity, the cell(s) can be found out based on the entity.
- Player: Bounding sphere :The grid size are uniformly sized cell (size, 
M) such that the M = 2R (R = radius of the bounding sphere). Thus, at 
any given time, at most the bounding sphere can be in contact with 4 
cells. To determine the cells associated, find the 8 points for a given 
sphere (each at 45 degrees to the X,Y,Z axis along the 8 octants). (And 
then find out, in which grid cell does each of the point lie. This could 
at max return 4 cells).
- Bullet: Segmented Ray with endpoints at : Posn and (Posn + vel). Thus, 
all the cells that the line passes through would yield the cells.
- Cell can be a structure like
Cell {
List < Player*>
List < Bullet* >
Value (x,y,z) => unique value based on these three coordinates
}
- As a cell is found by either of the entities, given its coordinates 
and grid position, a cell can be put on the hash-map. As the players and 
bullets yield cells, they can be referenced using this map and in-turn 
populate the list of player and bullet residing within that cell structure.
- After all the player and bullet –affected cells have been found, if we 
iterate through the hash-map, then it would yield all the possible pair 
of colliding players and bullets in a given cell. This can then be 
further handled using narrow-phase collision.

Does this sound feasible ? I'd really like to get some feedback on this.

Thank you
/Priyank Jain

Re: [Algorithms] Broadphase collision

[Priyank J. <fly...@gm...>]

Hi,

I apologize in advance, but I'm not sure if my earlier message about 
broadphase collision got posted or not. Earlier when I posted it, it 
gave me a bounce-back error, saying that the message was too long, so am 
not sure if my question got posted.

If none of you received it, please let me know.

Thanks
/Priyank

On 3/24/2010 1:22 PM, Priyank Jain wrote:
> Hi,
> I am trying to implement broadphase collision for my game (3D FPS 
> genre). I have been reading about the commonly used techniques and I 
> have tailored the grid approach to my game. I want to know if this is 
> the right direction to go in or not.
> The involved actors are :-
> Players
> Bullets(Fired)
> Weapons (placed at points located throughout the level, which other 
> players can pick up, aka static objects)
> World
> As of now, I am just trying to get the Players and bullet collision 
> pairs.
> Players: Players are represented by a bounding sphere, located at a 
> position and moving with a velocity. Each player would have 
> approximately the bounding sphere of same size.
> Players - weapons
> Players - World
> Bullets: Bullets are represented by a segment with a start point and 
> an end point (using posn, posn + vel) (each frame). Bullet can hit :-
> Fired Bullet     Player
> (Other) Bullet
> World
>
> Approach:
> - As each player and bullet is created, associate a reference to each 
> entity within CollisionMgr as a list<Player*> and list<Bullet*>.
> - On each update frame, do the following:
> - For each player, find Cell(s); it is associated with :=> list< Cell* 
> > PlayerCells
> - For each Bullet (segment), find Cell(s); it is associated with :=> 
> list< Cell* > BulletCells
> - For each entity, the cell(s) can be found out based on the entity.
> - Player: Bounding sphere :The grid size are uniformly sized cell 
> (size, M) such that the M = 2R (R = radius of the bounding sphere). 
> Thus, at any given time, at most the bounding sphere can be in contact 
> with 4 cells. To determine the cells associated, find the 8 points for 
> a given sphere (each at 45 degrees to the X,Y,Z axis along the 8 
> octants). (And then find out, in which grid cell does each of the 
> point lie. This could at max return 4 cells).
> - Bullet: Segmented Ray with endpoints at : Posn and (Posn + vel). 
> Thus, all the cells that the line passes through would yield the cells.
> - Cell can be a structure like
> Cell {
> List < Player*>
> List < Bullet* >
> Value (x,y,z) => unique value based on these three coordinates
> }
> - As a cell is found by either of the entities, given its coordinates 
> and grid position, a cell can be put on the hash-map. As the players 
> and bullets yield cells, they can be referenced using this map and 
> in-turn populate the list of player and bullet residing within that 
> cell structure.
> - After all the player and bullet –affected cells have been found, if 
> we iterate through the hash-map, then it would yield all the possible 
> pair of colliding players and bullets in a given cell. This can then 
> be further handled using narrow-phase collision.
>
> Does this sound feasible ? I'd really like to get some feedback on this.
>
> Thank you
> /Priyank Jain

Re: [Algorithms] Broadphase collision

[John R. <jra...@gm...>]

Priyank,

Unless you want to write your own collision/physics engine yourself 'just
for fun' I strongly recommend you just use one of the many freely available
versions.  It's a large engineering project and almost for sure not worth
your time.

Check out; 'Bullet', 'OpCode', or 'PhysX' to name just a few.  All three of
these are free for commercial or non-commercial use and represent literally
man-years of engineering time invested.

Personally, I get no pleasure from re-writing code that is readily available
from other sources.  Unless you are writing it purely as a learning
exercise, I can't fathom a reason why you would do this.  Presumably you are
trying to create an actual game project, so wouldn't you prefer to be
working on your game instead of solving problems that have been solved many
times before by others and shared with the development community free of
charge?

John

On Wed, Mar 24, 2010 at 1:50 PM, Priyank Jain <fly...@gm...> wrote:

> Hi,
>
> I apologize in advance, but I'm not sure if my earlier message about
> broadphase collision got posted or not. Earlier when I posted it, it
> gave me a bounce-back error, saying that the message was too long, so am
> not sure if my question got posted.
>
> If none of you received it, please let me know.
>
> Thanks
> /Priyank
>
> On 3/24/2010 1:22 PM, Priyank Jain wrote:
> > Hi,
> > I am trying to implement broadphase collision for my game (3D FPS
> > genre). I have been reading about the commonly used techniques and I
> > have tailored the grid approach to my game. I want to know if this is
> > the right direction to go in or not.
> > The involved actors are :-
> > Players
> > Bullets(Fired)
> > Weapons (placed at points located throughout the level, which other
> > players can pick up, aka static objects)
> > World
> > As of now, I am just trying to get the Players and bullet collision
> > pairs.
> > Players: Players are represented by a bounding sphere, located at a
> > position and moving with a velocity. Each player would have
> > approximately the bounding sphere of same size.
> > Players - weapons
> > Players - World
> > Bullets: Bullets are represented by a segment with a start point and
> > an end point (using posn, posn + vel) (each frame). Bullet can hit :-
> > Fired Bullet     Player
> > (Other) Bullet
> > World
> >
> > Approach:
> > - As each player and bullet is created, associate a reference to each
> > entity within CollisionMgr as a list<Player*> and list<Bullet*>.
> > - On each update frame, do the following:
> > - For each player, find Cell(s); it is associated with :=> list< Cell*
> > > PlayerCells
> > - For each Bullet (segment), find Cell(s); it is associated with :=>
> > list< Cell* > BulletCells
> > - For each entity, the cell(s) can be found out based on the entity.
> > - Player: Bounding sphere :The grid size are uniformly sized cell
> > (size, M) such that the M = 2R (R = radius of the bounding sphere).
> > Thus, at any given time, at most the bounding sphere can be in contact
> > with 4 cells. To determine the cells associated, find the 8 points for
> > a given sphere (each at 45 degrees to the X,Y,Z axis along the 8
> > octants). (And then find out, in which grid cell does each of the
> > point lie. This could at max return 4 cells).
> > - Bullet: Segmented Ray with endpoints at : Posn and (Posn + vel).
> > Thus, all the cells that the line passes through would yield the cells.
> > - Cell can be a structure like
> > Cell {
> > List < Player*>
> > List < Bullet* >
> > Value (x,y,z) => unique value based on these three coordinates
> > }
> > - As a cell is found by either of the entities, given its coordinates
> > and grid position, a cell can be put on the hash-map. As the players
> > and bullets yield cells, they can be referenced using this map and
> > in-turn populate the list of player and bullet residing within that
> > cell structure.
> > - After all the player and bullet –affected cells have been found, if
> > we iterate through the hash-map, then it would yield all the possible
> > pair of colliding players and bullets in a given cell. This can then
> > be further handled using narrow-phase collision.
> >
> > Does this sound feasible ? I'd really like to get some feedback on this.
> >
> > Thank you
> > /Priyank Jain
>
>
> ------------------------------------------------------------------------------
> Download Intel&#174; Parallel Studio Eval
> Try the new software tools for yourself. Speed compiling, find bugs
> proactively, and fine-tune applications for parallel performance.
> See why Intel Parallel Studio got high marks during beta.
> http://p.sf.net/sfu/intel-sw-dev
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] Broadphase collision

[Darren G. <dg...@ke...>]

By way of anecdote, here is my experience: I am 
inserting bounding boxes into an implementation 
of the hierarchical hash table described in mirtich96a (2.4.2):

         <http://cg.cs.uni-bonn.de/docs/teaching/2004/SS/seminar_anim/documents/Mirtich96a.pdf>http://cg.cs.uni-bonn.de/docs/teaching/2004/SS/seminar_anim/documents/Mirtich96a.pdf 


This approach has proven effective for a 
relatively even distribution of many dynamic 
objects of reasonably varying size and velocity. 
The memory requirements can be quite large, which 
makes it more suitable for PC. I have thousands 
of objects running roughly 1-m to 1000-m in 
diameter and capped at 200-m/s, for instance, but 
very few are moving noticeably at any given time.

You may want to explore a hybrid partitioning 
approach to get the most out of your static world 
geometry. If you have a scenario with only a 
moderate number of small objects moving around 
there are better options. A tighter space 
partitioning and quad tree may be a better option.


Cheres,
Darren Grant.



At 10:22 AM 3/24/2010, Priyank Jain wrote:
>Hi,
>I am trying to implement broadphase collision for my game (3D FPS
>genre). I have been reading about the commonly used techniques and I
>have tailored the grid approach to my game. I want to know if this is
>the right direction to go in or not.
>The involved actors are :-
>Players
>Bullets(Fired)
>Weapons (placed at points located throughout the level, which other
>players can pick up, aka static objects)
>World
>As of now, I am just trying to get the Players and bullet collision pairs.
>Players: Players are represented by a bounding sphere, located at a
>position and moving with a velocity. Each player would have
>approximately the bounding sphere of same size.
>Players - weapons
>Players - World
>Bullets: Bullets are represented by a segment with a start point and an
>end point (using posn, posn + vel) (each frame). Bullet can hit :-
>Fired Bullet    Player
>(Other) Bullet
>World
>
>Approach:
>- As each player and bullet is created, associate a reference to each
>entity within CollisionMgr as a list<Player*> and list<Bullet*>.
>- On each update frame, do the following:
>- For each player, find Cell(s); it is associated with :=> list< Cell* >
>PlayerCells
>- For each Bullet (segment), find Cell(s); it is associated with :=>
>list< Cell* > BulletCells
>- For each entity, the cell(s) can be found out based on the entity.
>- Player: Bounding sphere :The grid size are uniformly sized cell (size,
>M) such that the M = 2R (R = radius of the bounding sphere). Thus, at
>any given time, at most the bounding sphere can be in contact with 4
>cells. To determine the cells associated, find the 8 points for a given
>sphere (each at 45 degrees to the X,Y,Z axis along the 8 octants). (And
>then find out, in which grid cell does each of the point lie. This could
>at max return 4 cells).
>- Bullet: Segmented Ray with endpoints at : Posn and (Posn + vel). Thus,
>all the cells that the line passes through would yield the cells.
>- Cell can be a structure like
>Cell {
>List < Player*>
>List < Bullet* >
>Value (x,y,z) => unique value based on these three coordinates
>}
>- As a cell is found by either of the entities, given its coordinates
>and grid position, a cell can be put on the hash-map. As the players and
>bullets yield cells, they can be referenced using this map and in-turn
>populate the list of player and bullet residing within that cell structure.
>- After all the player and bullet ­affected cells have been found, if we
>iterate through the hash-map, then it would yield all the possible pair
>of colliding players and bullets in a given cell. This can then be
>further handled using narrow-phase collision.
>
>Does this sound feasible ? I'd really like to get some feedback on this.
>
>Thank you
>/Priyank Jain
>
>------------------------------------------------------------------------------
>Download Intel&#174; Parallel Studio Eval
>Try the new software tools for yourself. Speed compiling, find bugs
>proactively, and fine-tune applications for parallel performance.
>See why Intel Parallel Studio got high marks during beta.
>http://p.sf.net/sfu/intel-sw-dev
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>Archives:
>http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list