hi, i need a way to detect player and player's structures in enemie's line of sight in real time ,but i dont know how to implement this efficient , all of object in this game has same class with different behaviours and data attached to them, i use very simple 2d spatial hashing (fixed cell size) thx image: http://www.2shared.com/file/12925656/f0474c9a/lineofsight.html

For the field-of-view test, a simple dot-product test should suffice (ask if you don't know how to do this).

For the line-of-sight test, I'm not sure of the details of your spatial partitioning scheme, but if there aren't too many objects in your simulation, you might be able to get away with simply querying the broad phase for potential occluders using an AABB fully containing the line segment representing the sight line, and then testing each of the returned objects for intersection.

If you need something more performant than that, you might look into 2D-DDA.

i didn't get how should i query objects in field of view test with dot product,

and about query objects in environment i need first find cell that line of sight intersect with them how can i exactly do that?

can you give more information on 2d-dda?..

THX

The Dot product of two unit vectors (normalized vectors) returns a number from 0 to +-1 (cosine of their angle) that will be +-1 for parallel vectors and 0 for perpendicular vectors. Therefore, if you compute the cosine of your field of view angle (half of it), you can compare that value to the result of your player orientation DOT vector from player to object.

Pseudocode off top of my head:

  obj_angradius = obj.radius / distance(obj,camera) * somefactor;  obj_view_angle = (obj.x-camera.x)*camera.forward.x + (obj.y-camera.y)*camera.forward.y;  if (ABS(obj_view_angle)+obj_angradius <= cos(field_of_view_angle/2)) render(obj);

Alternatively, you can convert to polar coordinates or project object center and radius to screen coordinates and just 1D clip agaisnt viewport.

This last method allows you to compute a 1D span buffer for obstruction culling on your 2D world assuming you are using a 2D polygon soup for your world and cannot use something more sophisticated (nav meshes/portals).

Quote:can you give more information on 2d-dda?..

You might want to try a simpler solution first (you might find that 2D-DDA isn't needed).

I'm not sure exactly how your spatial partitioning scheme works, but if it's a regular grid, you should be able to do the following:

1. Build an AABB corresponding to the 'line of sight' line segment.

2. Determine the range of grid cells that intersect the AABB (simple arithmetic).

3. Perform a narrow-phase test on all of the objects included in those cells.

Thx For Your help, it worked like you said.