How can I test if one point can "see" another point. (XNA)

Question

I want to test if my enemy can see the player, however I want this to be pixel-perfect.

I already have all of the solid objects drawing into a separate render state. It should be noted that every solid object is changing and warping all over the place constantly. I cannot check individual walls because a distortion effect is applied to all of them. The walls blend together.

Essentially it would lerp between the enemy's position and the player's position and see if there are any pixels that have an alpha value of greater than 0. The rotation of the enemy and the player do not matter.

All of my attempts at doing this on the cpu have worked, however they slowed the game down dramatically. All of my attempts at going this on the gpu just didn't work at all.

What is the most efficient way of doing this? Is there any way to do this in the gpu?

Edit: There is no geometry at all. The walls are completely amorphous.

I did not realize that global variables were constant in hlsl until after I wrote this:

sampler s0;
texture tex;
sampler tex_sampler = sampler_state{Texture = tex;};

float2 screenSize;
float2 from;
float2 to;
float2 impact;
int impacted;

float4 PixelShaderFunction(float2 coords: TEXCOORD0) : COLOR0  
{  
    from /= screenSize;
    to /= screenSize;

    impacted = 0;

    for (float i = 0; i < 1; i += 1.0f / length(to - from))
    {
        float2 test = lerp(from, to, i);

        if ( (tex2D(tex_sampler, test)).a )
        {
            impacted = 1;
            impact = test * screenSize;
            break;
        }
    }

    return tex2D(s0, coords);
}  

technique Technique1  
{  
    pass Pass1  
    {  
        PixelShader = compile ps_2_0 PixelShaderFunction();  
    }  
} 

The solid pixels would be passed into the "tex" variable. I would read the "impacted" and "impact" variables after one pass on a 1x1 texture. hlsl just doesn't want to let me do this. Apparently global variables are implicitly constant. Is there another way of doing this?

on the variable syntax page it says "Global variables are considered const by default (suppress this behavior by supplying the /Gec flag to the compiler)." How do I add the /Gec flag to the compiler?

I also wrote this, but it slowed the game down:

private bool CanSee(Vector2 from, Vector2 to)
{
    Color[] t = new Color[target_solid_final.Width * target_solid_final.Height];
    target_solid_final.GetData(t);

    for (float i = 0; i < 1; i += 8.0f / (to - from).Length())
    {
        Vector2 test = Vector2.Lerp(from, to, i);
        Point test_p = new Point((int)test.X, (int)test.Y);

        if (viewportRect.Contains(test_p) &&
            t[test_p.X + test_p.Y * target_solid_final.Width].A > 0)
            return false;
    }

    return true;
}

Answer 1

EDIT: I see your updates now, I'd suggest you try implementing something such as my first suggestion.

Since you didn't post any of your code, I'm going to have to guess at how you're doing the collisions. Are you using a single pixel collision check between the player and the enemy with the wall or other related sprites around it? If so, there are probably some ways you can speed this up.

First, it's not really necessary to use pixel perfect lines to check - all that does is slow down C# / XNA. Instead, try checking to see if there is any wall between the player and enemy every 3 pixels or 4 pixels. As long as the walls are at least 5 or so pixels thick, then using a 3 pixel skip in your line of sight to the player won't lose you much accuracy, but it will increase the speed.

Second, you can take the distance of each enemy to the player, and for each enemy, any walls that are greater than the distance from that enemy and the player (+ an inch or so for error) obviously cannot be obstructing the enemy's view of the player.

Third, enemies further than a certain large distance from the player are likely unable to see the player. If the enemy is halfway across the screen, you can probably exclude it from collision checks - how would it be able to see the player that far away anyway, assuming that somehow it wasn't obstructed by a wall?

Fourth, if you're not already doing so, you can use bounding box collision as a precursor to collision checks per enemy. This will make a VERY significant speed difference! If you're already doing this, then you should look into using my first three suggestions. But if you're not doing bounding box collision, start here.

Hope these concepts help you speed up your game! If I assumed how your collision works incorrectly, just leave me a comment.