# Efficient way to calculate “vision cones” on 2D tile map?

I'm trying to calculate which tiles a particular unit can "see" if facing a certain direction on a tile map (within a certain range and angle of facing). The easiest way would be to draw a certain number of tiles outward and raycast to each tile. However, I'm hoping for something slightly more efficient. A picture says a thousand words:

The red dot is the unit (who's facing upwards). My goal is to calculate the yellow tiles. The green blocks are walls (walls are between tiles, and it's easy to check if you can pass between two tiles). The blue line represents something like the "raycasting" method I was talking about, but I'd rather not have to do this.

EDIT: Units can only be facing north/south/east/west (0, 90, 180, or 270 degrees) and FoV is always 90 degrees. Should simplify some calculations. I'm thinking there's some sort of recursive-ish/stack-based/queue-based algorithm, but I can't quite figure it out.

Thanks!

-
Can the facing direction be any angle or just 0,45,90,.. etc.? – wondra Aug 20 '14 at 18:29
Also is the FoV always 90? – J_F_B_M Aug 20 '14 at 18:37
@wondra Only NSEW (0, 90, 180, 270). – Robert Fraser Aug 20 '14 at 18:44
@Larethian - Yes, FoV is always 90. This should help simplify things. I'm thinking there might be a way based on depth-first search, but I can't quite figure it out. – Robert Fraser Aug 20 '14 at 18:46
This sounds like the vision algorithms used in roguelikes. Those might be some inspiration. I found a page listing various approaches to the problem. – Anko Aug 20 '14 at 19:09

## 1 Answer

Yay I found a research paper!

In terms of computational cost Shadow Mapping seems pretty clear winner.

Algorithm used can be found here and a C# implementation can be found here, relevant bit below.

``````    #region FOV algorithm

//  Octant data
//
//    \ 1 | 2 /
//   8 \  |  / 3
//   -----+-----
//   7 /  |  \ 4
//    / 6 | 5 \
//
//  1 = NNW, 2 =NNE, 3=ENE, 4=ESE, 5=SSE, 6=SSW, 7=WSW, 8 = WNW

/// <summary>
/// Start here: go through all the octants which surround the player to
/// determine which open cells are visible
/// </summary>
public void GetVisibleCells()
{
VisiblePoints = new List<Point>();
foreach (int o in VisibleOctants)
ScanOctant(1, o, 1.0, 0.0);

}

/// <summary>
/// Examine the provided octant and calculate the visible cells within it.
/// </summary>
/// <param name="pDepth">Depth of the scan</param>
/// <param name="pOctant">Octant being examined</param>
/// <param name="pStartSlope">Start slope of the octant</param>
/// <param name="pEndSlope">End slope of the octance</param>
protected void ScanOctant(int pDepth, int pOctant, double pStartSlope, double pEndSlope)
{

int visrange2 = VisualRange * VisualRange;
int x = 0;
int y = 0;

switch (pOctant)
{

case 1: //nnw
y = player.Y - pDepth;
if (y < 0) return;

x = player.X - Convert.ToInt32((pStartSlope * Convert.ToDouble(pDepth)));
if (x < 0) x = 0;

while (GetSlope(x, y, player.X, player.Y, false) >= pEndSlope)
{
if (GetVisDistance(x, y, player.X, player.Y) <= visrange2)
{
if (map[x, y] == 1) //current cell blocked
{
if (x - 1 >= 0 && map[x - 1, y] == 0) //prior cell within range AND open...
//...incremenet the depth, adjust the endslope and recurse
ScanOctant(pDepth + 1, pOctant, pStartSlope, GetSlope(x - 0.5, y + 0.5, player.X, player.Y, false));
}
else
{

if (x - 1 >= 0 && map[x - 1, y] == 1) //prior cell within range AND open...
//..adjust the startslope
pStartSlope = GetSlope(x - 0.5, y - 0.5, player.X, player.Y, false);

VisiblePoints.Add(new Point(x, y));
}
}
x++;
}
x--;
break;

case 2: //nne

y = player.Y - pDepth;
if (y < 0) return;

x = player.X + Convert.ToInt32((pStartSlope * Convert.ToDouble(pDepth)));
if (x >= map.GetLength(0)) x = map.GetLength(0) - 1;

while (GetSlope(x, y, player.X, player.Y, false) <= pEndSlope)
{
if (GetVisDistance(x, y, player.X, player.Y) <= visrange2)
{
if (map[x, y] == 1)
{
if (x + 1 < map.GetLength(0) && map[x + 1, y] == 0)
ScanOctant(pDepth + 1, pOctant, pStartSlope, GetSlope(x + 0.5, y + 0.5, player.X, player.Y, false));
}
else
{
if (x + 1 < map.GetLength(0) && map[x + 1, y] == 1)
pStartSlope = -GetSlope(x + 0.5, y - 0.5, player.X, player.Y, false);

VisiblePoints.Add(new Point(x, y));
}
}
x--;
}
x++;
break;

case 3:

x = player.X + pDepth;
if (x >= map.GetLength(0)) return;

y = player.Y - Convert.ToInt32((pStartSlope * Convert.ToDouble(pDepth)));
if (y < 0) y = 0;

while (GetSlope(x, y, player.X, player.Y, true) <= pEndSlope)
{

if (GetVisDistance(x, y, player.X, player.Y) <= visrange2)
{

if (map[x, y] == 1)
{
if (y - 1 >= 0 && map[x, y - 1] == 0)
ScanOctant(pDepth + 1, pOctant, pStartSlope, GetSlope(x - 0.5, y - 0.5, player.X, player.Y, true));
}
else
{
if (y - 1 >= 0 && map[x, y - 1] == 1)
pStartSlope = -GetSlope(x + 0.5, y - 0.5, player.X, player.Y, true);

VisiblePoints.Add(new Point(x, y));
}
}
y++;
}
y--;
break;

case 4:

x = player.X + pDepth;
if (x >= map.GetLength(0)) return;

y = player.Y + Convert.ToInt32((pStartSlope * Convert.ToDouble(pDepth)));
if (y >= map.GetLength(1)) y = map.GetLength(1) - 1;

while (GetSlope(x, y, player.X, player.Y, true) >= pEndSlope)
{

if (GetVisDistance(x, y, player.X, player.Y) <= visrange2)
{

if (map[x, y] == 1)
{
if (y + 1 < map.GetLength(1)&& map[x, y + 1] == 0)
ScanOctant(pDepth + 1, pOctant, pStartSlope, GetSlope(x - 0.5, y + 0.5, player.X, player.Y, true));
}
else
{
if (y + 1 < map.GetLength(1) && map[x, y + 1] == 1)
pStartSlope = GetSlope(x + 0.5, y + 0.5, player.X, player.Y, true);

VisiblePoints.Add(new Point(x, y));
}
}
y--;
}
y++;
break;

case 5:

y = player.Y + pDepth;
if (y >= map.GetLength(1)) return;

x = player.X + Convert.ToInt32((pStartSlope * Convert.ToDouble(pDepth)));
if (x >= map.GetLength(0)) x = map.GetLength(0) - 1;

while (GetSlope(x, y, player.X, player.Y, false) >= pEndSlope)
{
if (GetVisDistance(x, y, player.X, player.Y) <= visrange2)
{

if (map[x, y] == 1)
{
if (x + 1 < map.GetLength(1) && map[x+1, y] == 0)
ScanOctant(pDepth + 1, pOctant, pStartSlope, GetSlope(x + 0.5, y - 0.5, player.X, player.Y, false));
}
else
{
if (x + 1 < map.GetLength(1)
&& map[x + 1, y] == 1)
pStartSlope = GetSlope(x + 0.5, y + 0.5, player.X, player.Y, false);

VisiblePoints.Add(new Point(x, y));
}
}
x--;
}
x++;
break;

case 6:

y = player.Y + pDepth;
if (y >= map.GetLength(1)) return;

x = player.X - Convert.ToInt32((pStartSlope * Convert.ToDouble(pDepth)));
if (x < 0) x = 0;

while (GetSlope(x, y, player.X, player.Y, false) <= pEndSlope)
{
if (GetVisDistance(x, y, player.X, player.Y) <= visrange2)
{

if (map[x, y] == 1)
{
if (x - 1 >= 0 && map[x - 1, y] == 0)
ScanOctant(pDepth + 1, pOctant, pStartSlope, GetSlope(x - 0.5, y - 0.5, player.X, player.Y, false));
}
else
{
if (x - 1 >= 0
&& map[x - 1, y] == 1)
pStartSlope = -GetSlope(x - 0.5, y + 0.5, player.X, player.Y, false);

VisiblePoints.Add(new Point(x, y));
}
}
x++;
}
x--;
break;

case 7:

x = player.X - pDepth;
if (x < 0) return;

y = player.Y + Convert.ToInt32((pStartSlope * Convert.ToDouble(pDepth)));
if (y >= map.GetLength(1)) y = map.GetLength(1) - 1;

while (GetSlope(x, y, player.X, player.Y, true) <= pEndSlope)
{

if (GetVisDistance(x, y, player.X, player.Y) <= visrange2)
{

if (map[x, y] == 1)
{
if (y + 1 < map.GetLength(1) && map[x, y+1] == 0)
ScanOctant(pDepth + 1, pOctant, pStartSlope, GetSlope(x + 0.5, y + 0.5, player.X, player.Y, true));
}
else
{
if (y + 1 < map.GetLength(1) && map[x, y + 1] == 1)
pStartSlope = -GetSlope(x - 0.5, y + 0.5, player.X, player.Y, true);

VisiblePoints.Add(new Point(x, y));
}
}
y--;
}
y++;
break;

case 8: //wnw

x = player.X - pDepth;
if (x < 0) return;

y = player.Y - Convert.ToInt32((pStartSlope * Convert.ToDouble(pDepth)));
if (y < 0) y = 0;

while (GetSlope(x, y, player.X, player.Y, true) >= pEndSlope)
{

if (GetVisDistance(x, y, player.X, player.Y) <= visrange2)
{

if (map[x, y] == 1)
{
if (y - 1 >=0 && map[x, y - 1] == 0)
ScanOctant(pDepth + 1, pOctant, pStartSlope, GetSlope(x + 0.5, y - 0.5, player.X, player.Y, true));

}
else
{
if (y - 1 >= 0 && map[x, y - 1] == 1)
pStartSlope = GetSlope(x - 0.5, y - 0.5, player.X, player.Y, true);

VisiblePoints.Add(new Point(x, y));
}
}
y++;
}
y--;
break;
}

if (x < 0)
x = 0;
else if (x >= map.GetLength(0))
x = map.GetLength(0) - 1;

if (y < 0)
y = 0;
else if (y >= map.GetLength(1))
y = map.GetLength(1) - 1;

if (pDepth < VisualRange & map[x, y] == 0)
ScanOctant(pDepth + 1, pOctant, pStartSlope, pEndSlope);

}

/// <summary>
/// Get the gradient of the slope formed by the two points
/// </summary>
/// <param name="pX1"></param>
/// <param name="pY1"></param>
/// <param name="pX2"></param>
/// <param name="pY2"></param>
/// <param name="pInvert">Invert slope</param>
/// <returns></returns>
private double GetSlope(double pX1, double pY1, double pX2, double pY2, bool pInvert)
{
if (pInvert)
return (pY1 - pY2) / (pX1 - pX2);
else
return (pX1 - pX2) / (pY1 - pY2);
}

/// <summary>
/// Calculate the distance between the two points
/// </summary>
/// <param name="pX1"></param>
/// <param name="pY1"></param>
/// <param name="pX2"></param>
/// <param name="pY2"></param>
/// <returns>Distance</returns>
private int GetVisDistance(int pX1, int pY1, int pX2, int pY2)
{
return ((pX1 - pX2) * (pX1 - pX2)) + ((pY1 - pY2) * (pY1 - pY2));
}

#endregion
``````
-
Thanks! It looks like it might be tricky to get this to work with walls between cells, but I'll give it a go and see how it works! – Robert Fraser Aug 20 '14 at 21:12
I'd go with one of the permissive algorithms, see the table in the 8th page of the paper – Gustavo Maciel Aug 21 '14 at 1:45
Excellent paper, although my conclusion would be different, that there is no practical speed difference. The results show that for typical rogue-like maps, most algorithms run within 50 microseconds, which means that in practice, you're better off choosing based on criteria other than speed. – congusbongus Aug 21 '14 at 5:38