# Help me optimize my Line Of Sight on a 2d grid algorithm?

    private bool LOSBetween2Nodes( int2 start , int2 end )
{
int2 dif = new int2(
math.abs( end.x - start.x ) ,
math.abs( end.y - start.y ) );
int2 pos = new int2(
start.x ,
start.y );
int2 inc = new int2(
( end.x > start.x ) ? 1 : -1 ,
( end.y > start.y ) ? 1 : -1 );

int numIterations = 1 + dif.x + dif.y;
int error = dif.x - dif.y;
int walkable = 0;
bool prevY = false;
int numSameDir = 0;

if ( error <= 0 )
prevY = true;

dif.x *= 2;
dif.y *= 2;

for ( ; numIterations > 0; --numIterations )
{
walkable += graphNodeWalkables[ pos.x + pos.y * graphCellLength ];

if ( numSameDir < 1 )
{
if ( prevY )
walkable += graphNodeWalkables[ ( pos.x - inc.x ) + pos.y * graphCellLength ];
else
walkable += graphNodeWalkables[ pos.x + ( pos.y - inc.y ) * graphCellLength ];

if ( error > 0 ) // more steps in x
{
pos.x += inc.x;

if ( !prevY )
numSameDir++;
else
numSameDir = 0;

prevY = false;
error -= dif.y;
}
else // more steps in y
{
pos.y += inc.y;

if ( prevY )
numSameDir++;
else
numSameDir = 0;

prevY = true;
error += dif.x;
}
}
}

return walkable == 0;
}


This currently checks all grid cells along a line between a certain width and returns telling you if any are unwalkable. This can run thousands-tens of thousands of times a frame.

• Has your profiling of this method identified any specific bottleneck? Mar 21, 2020 at 17:48
• The extra if-checks on prevY is a minor performance hit. Is there a way I can re-structure this algorithm to omit those checks for some sort of equation instead? Mar 21, 2020 at 20:05