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