# How can one implement a 3D Grid-based Line of Sight algorithm?

I'm creating a grid based Tactical RPG game in XNA.

Image below kinda explains the idea. But if you've played Dwarf Fortress before, I'm basically trying to create that 3D line of sight and you can ignore my explanation. (Also I don't care about how efficient the algorithm is at this time.)

Currently I am drawing a Bresenham line to each square within a radius, and each square I visit I check in the direction I am headed if I run into any walls.

The code below is my check for if a position is visible. sx, sy, sz is the change in the grid. For instance, if the line is traveling north east, sx = 1, sy = -1, sz = 0. if I'm headed straight up it would be sx=0, sy = 0, sz = 1; etc.

    private bool IsVisible(APoint Cur, int sx, int sy, int sz)
{
bool Visible = true;
if (ValidCoordinates(Cur))
{
int newsx = -1;
int newsy = -1;
int newsz = -1;
switch (sx)
{
case -1:
newsx = 3; //west
break;
case 0:
newsx = -1;
break;
case 1:
newsx = 1; //east
break;
}

switch (sy)
{
case -1:
newsy = 0;// north
break;
case 0:
newsy = -1;
break;
case 1:
newsy = 2; //south
break;
}

switch (sz)
{
case -1:
newsz = 4; // down
break;
case 0:
newsz = -1;
break;
case 1:
newsz = 5; // up
break;
}
if (ValidCoordinates(Cur.X + sx, Cur.Y + sy, Cur.Z + sz))
{
if (newsx != -1 && newsy == -1 && newsz == -1) // X only.
{
if (TileArray[Cur.X + sx, Cur.Y + sy, Cur.Z + sz].AllowSight(newsx))
Visible = true;
else
Visible = false;
}

if (newsx == -1 && newsy != -1 && newsz == -1) // Y only.
{
if (TileArray[Cur.X + sx, Cur.Y + sy, Cur.Z + sz].AllowSight(newsy))
Visible = true;
else
Visible = false;
}

if (newsx != -1 && newsy != -1 && newsz == -1) // X and Y only
{
if (Visible && TileArray[Cur.X + sx, Cur.Y + sy, Cur.Z + sz].AllowSight(newsx))
Visible = true;
else
Visible = false;

if (Visible && TileArray[Cur.X + sx, Cur.Y + sy, Cur.Z + sz].AllowSight(newsy))
Visible = true;
else
Visible = false;
}

}
return Visible;
}
return false;
}


The Allow sight function is here:

        public bool AllowSight(int i)
{
if (i == -1)
return true;

if (i >= 0 && i <= 3)
{
if (TileCreateCliff && HDifferenceUp > 0)
{
return false;
}
}

if (i == 4)
{
if (TileVoid)
return true;
else
return false;
}
if (i == 5)
{
if (TileVoid)
return true;
else
return false;
}
return true;
}


This works fine when my character is on the base level, but looking up at higher elevations, or looking down just causes everything to break.

How should I implement this?

This is very similar to how you might do lighting with shadows in a cube/voxel game.

Essentially, you recursively walk through all the cubes within the sight range of the character. For each cube that's air you do a ray test between the center of that cube and the eyes of your character. I wrote a post about it as well. The ray test can be an actual ray test with the geometry (likely faster, more complex) or simply step a test point out at small increments towards the target continually checking if your test point is at a solid position (slower, but very easy to implement).

I was able to perform lighting very quickly even using the simple step method for a ray test.

• Thanks, but I'm not sure how I would implement that method in a 2D game from a orthographic viewpoint. May 28 '13 at 21:47
• You said it was a 3D grid? This utilizes a 3D grid. As long as you have some kind of isSolidAt(x,y,z) function, you can use this. How you draw the world is irrelevant.
– House
May 28 '13 at 21:49