Wednesday 29 September 2010

Line of sight algorithm

I have been trying to find a algorithm which when given a integer which will determine "sight range" will produce a two dimensional array containing all the x,y values of tiles which fulfill x+y<=sight range in both positive and negative directions.

This is the method I used to accomplish this:

for (int y=0;y&lt;mapHeight;y++)
{
for (int x=0;x&lt;mapWidth;x++)
{
if(currentMap.getUnit(x, y)!=null)
{
int sightRange = currentMap.getUnit(x, y).getMovementRange()/2;
for(int sightStepY = -sightRange;sightStepY&lt;sightRange;sightStepY++)
{
for(int sightStepX = -sightRange;sightStepX&lt;sightRange;sightStepX++)
{
if(x+sightStepX>=0&&x+sightStepX&lt;mapWidth&&y+sightStepY>=0&&y+sightStepY&lt;mapHeight)
{

if(sightStepY>=0&&sightStepX>=0)
{
if(sightStepY+sightStepX&lt;=sightRange)
{
currentMap.fogArray[x+sightStepX][y+sightStepY]=0;
}
}

if(y+sightRange&lt;mapHeight){
currentMap.fogArray[x][y+sightRange]=0;}
if(x+sightRange&lt;mapHeight){
currentMap.fogArray[x+sightRange][y]=0;}


if(sightStepY&lt;=0&&sightStepX>=0)
{
if(sightStepX-sightStepY&lt;=sightRange)
{
currentMap.fogArray[x+sightStepX][y+sightStepY]=0;
}
}

if(sightStepY&lt;=0&&sightStepX&lt;=0)
{
if(-sightStepX-sightStepY&lt;=sightRange)
{
currentMap.fogArray[x+sightStepX][y+sightStepY]=0;
}
}

if(sightStepY>=0&&sightStepX&lt;=0)
{
if(sightStepY-sightStepX&lt;=sightRange)
{
currentMap.fogArray[x+sightStepX][y+sightStepY]=0;
}
}

}}}
}}}
Fog array is the two dimensional array which states if the tile should fog(1) or not (0).
Here is an example of the result when rendered in the game:



I think the above is rather messy and was achieved with a good deal of trial and error. I'm sure there is a more elegant way of achieving this. Any suggestions would be appreciated.

No comments:

Post a Comment