A Quick and Clear Look at Grid-Based Visibility | by Rhys Goldstein

How a 3-line algorithm provides a decent alternative to ray casting

Image by Autodesk Research [1]. (Used with permission)

In my previous article, A Short and Direct Walk with Pascal’s Triangle, I explain how grid-based pathfinding can be improved to yield highly direct walking paths without using line-of-sight tests. This follow-up article will show you a related technique called grid-based visibility, which computes visible regions without line-of-sight tests. Grid-based visibility is virtually unheard of in the computer science community, but it’s a practical method that makes sense for a variety of artificial intelligence applications. It’s also extremely easy to implement, requiring as few as 3 lines of code. Read on to discover your simplest option for solving visibility problems in video games, mobile robotics, or architectural design.

Similar to pathfinding, visibility analysis arises in a number of fields involving artificial intelligence and spatial environments. A video game developer may want to compute the region of a game map that is visible from an enemy watch tower. A mobile robotics engineer may need to compute a robot’s field of view in a simulation that tests the robot’s control system. An architect may want to analyze people’s views at various locations in a building or along a street. Visibility analysis can also be used to approximate the area illuminated by a source of light.

The basic problem is this: Given a 2D top-down map, compute the region of space that is visible from a point.

If you ask a computer scientist how to solve this problem, it is extremely unlikely that they will even consider what I call a grid-based algorithm: a method where numbers in every grid cell are computed based on numbers in neighboring grid cells. The visible region problem is almost always tackled using a vector-based visibility algorithm involving line-of-sight tests. One of the most popular vector-based visibility techniques is ray casting, where numerous rays are cast in different directions from a viewpoint. If you’re unfamiliar with ray casting and other vector-based solutions to the visible region problem, the Red Blob Games tutorial on 2D Visibility provides an excellent backgrounder.

Both grid-based and vector-based approaches are popular for other spatial applications like pathfinding and 2D graphics. We are all familiar with raster (grid-based) and vector images, for example, and we recognize that both types of images have advantages and disadvantages. So why is it that only vector-based approaches are widely used for visibility? I’ve come to believe that while both grid-based and vector-based methods have advantages and disadvantages for visibility problems, grid-based visibility has been curiously overlooked and deserves to be better known.

Here is grid-based visibility written in 3 lines of Python code.

for x in range(grid.shape[0]):
for y in range(int(x==0), grid.shape[1]):
grid[x,y] *= (x*grid[x-1,y] + y*grid[x,y-1]) / (x + y)

The algorithm takes a grid representing a map and modifies it to produce visibility results. As we can see, the transformation consists of looping over every grid cell and applying a linear interpolation. Let’s test these 3 lines of code by placing them in a short program. Feel free to copy and run the Python script below.

import numpy as np
import matplotlib.pyplot as plt# Set dimensions
nx = 25
ny = 25
# Create map
grid = np.ones((nx,ny))
wx = nx//10 + 1
wy = ny//10 + 1
grid[int(.3*nx):int(.3*nx)+wx,int(.1*ny):int(.1*ny)+wy] = 0
grid[int(.1*nx):int(.1*nx)+wx,int(.5*ny):int(.5*ny)+wy] = 0
grid[int(.6*nx):int(.6*nx)+wx,int(.6*ny):int(.6*ny)+wy] = 0
# Display map
plt.figure("Map")
plt.imshow(np.transpose(grid))
# Compute visibility
for x in range(grid.shape[0]):
for y in range(int(x==0), grid.shape[1]):
grid[x,y] *= (x*grid[x-1,y] + y*grid[x,y-1]) / (x + y)
# Display visibility
plt.figure("Visibility")
plt.imshow(np.transpose(grid))
plt.show()

The program first creates and displays the map, a 25×25 grid where cells filled with an obstacle have a value of 0 and empty cells have a value of 1. As shown below, the map has three square obstacles.

The 25×25 input map. (Image by author)

The program then transforms the map into a visibility grid and displays it. The visibility grid is filled with visibility scores, which approximate the degree to which each grid cell is visible from a viewpoint in the top left corner. Visibility scores range from 0 (completely blocked) to 1 (completely visible). Here’s the visibility grid.

The resulting 25×25 visibility grid. (Image by author)

Each obstacle casts a shadow away from the top left corner, though you’ll notice that the edges of the shadows are blurry. One way to sharpen those edges is to increase the resolution of the map. If we change the grid size from 25 to 225 cells in both dimensions…

nx = 225
ny = 225

…we get the following results.

The visibility grid with resolution increased to 225×225. (Image by author)

Here we see sharper and more accurate shadows. If we continue to increase the resolution, the visibility scores will get more and more accurate. In fact, the results will converge on the exact solution as the grid spacing approaches zero.

Depending on the application, we may wish to classify every grid cell as either visible (1) or not visible (0). We can do this by applying a threshold of 0.5 after the loop.

for x in range(grid.shape[0]):
for y in range(int(x==0), grid.shape[1]):
grid[x,y] *= (x*grid[x-1,y] + y*grid[x,y-1]) / (x + y)
grid[:] = (grid >= 0.5)

Inserting that 4th line into the script gives us the result below.

The 225×225 visibility grid after applying a threshold. (Image by author)

It’s important to remember that grid-based visibility is an approximate method. Some of the grid cells may be classified as visible even if they should be just within a shadow, and some may be classified as blocked even if they should be just within the visible region. But generally speaking, the results should have decent accuracy if the grid spacing is small compared with the obstacles and the gaps between them.

Before we move on, I should confess that I used a few tricks to get the algorithm down to 3 lines:

The expression int(x==0) in the 2nd for loop is a clever trick that skips over the grid cell [0, 0] where the interpolation formula would produce a divide-by-zero error.
I’m relying on the fact that the NumPy library allows arrays to be accessed using negative indices. Other programming languages might require a few more lines of code to check for this condition.
All the code above assumes the viewpoint is in the corner of the map. Moving the viewpoint to an arbitrary cell with coordinates x0 and y0 requires the calculation to be repeated four times, once in each of four quadrants.

To place the viewpoint in the center of the map, replace the code in the Compute visibility section of the script with the following.

# Set viewpoint
x0 = nx//2
y0 = ny//2# Define visibility function
def visibility_from_corner(grid):
for x in range(grid.shape[0]):
for y in range(int(x==0), grid.shape[1]):
grid[x,y] *= (x*grid[x-1,y] + y*grid[x,y-1]) / (x + y)
# Compute visibility
visibility_from_corner(grid[x0:,y0:])
visibility_from_corner(grid[x0::-1,y0:])
visibility_from_corner(grid[x0::-1,y0::-1])
visibility_from_corner(grid[x0:,y0::-1])

Here are the results with the viewpoint in the center.

The 225×225 visibility grid with the viewpoint in the center. (Image by author)

Here’s a little trick I can’t resist showing: Grid-based visibility implemented in Excel. The following screen recording is roughly 1 minute.

Grid-based visibility in Excel. (Recording by author)

Want to try it yourself? Follow the instructions below. It should take only 1 or 2 minutes.

Open MS Excel and create a Blank workbook.
Select cell B2, click on the Formula Bar (or press F2), paste in the following text, and press Enter:
=((COLUMN(B2)-2)*A2+(ROW(B2)-2)*B1)/((COLUMN(B2)-2)+(ROW(B2)-2))
Reselect cell B2, press Ctrl-C to copy, select a range of cells from B2 to Z26, press Ctrl-V to paste.
In the Home tab, select Conditional Formatting, Highlight Cells Rules, Less Than. Type 0.5 into the first box (“Format cells that are LESS THAN”), then select any “Fill” option from the drop-down menu on the right (e.g. “Light Red Fill with Dark Red Text”). Click OK.
Select cell B2 and press 1, then Enter.
Select all cells by clicking the green triangle above and to the left of cell A1, then click and drag the vertical line between A and B to shrink the cell width so that all cells end up approximately square.
Create obstacles by clicking on cells and pressing Backspace. Shadows extending away from the top left corner should automatically appear.

Observe that the obstacles need to be multiple cells wide to produce reasonable looking shadows.

The history of grid-based visibility explains why the method never gained widespread recognition. First of all, despite its simplicity, grid-based visibility wasn’t invented until 2004 [2], and its convergence properties weren’t established until 2008 [3]. By that time, vector-based approaches like ray casting had become ubiquitous. Computer scientists were no longer searching for competing approaches. Secondly, the first papers on grid-based visibility came from a branch of mathematics called level set theory, where geometry is represented in an implicit manner unfamiliar to most computer scientists. While the level set visibility method works in 2D or 3D and uses linear interpolation, a strictly 3D alternative using bi-linear interpolation was developed by architectural and urban informatics researchers in 2013 [4].

Around 2019, my colleagues and I became interested in grid-based visibility as means of analyzing large numbers of computer-generated building designs. In our open access journal paper “Path Counting for Grid-Based Navigation” [1], we made the following observations:

The original level set visibility method is easily adapted to work with explicit geometry familiar to computer scientists. The Python code near the top of this article is an example of an implementation that combines the original interpolation formula with explicit grid-based geometry.
The size of the grid neighborhood can be increased to produce more accurate results. The examples in this article have so far used the 4-neighborhood, where information flows to the north, south, east, and/or west. My colleagues and I used the 8-neighborhood, which allows information to flow diagonally, in both the paper and an architectural design tool called SpaceAnalysis.
Grid-based visibility results can be shown to converge on the exact solution using probability theory, specifically the central limit theorem. The original proof from the level set community used numerical analysis [3].
Visibility scores produced by linear interpolation can be reinterpreted as the fraction of shortest grid paths heading away from the viewpoint that are not blocked by obstacles.

That last observation revealed that central grid-based pathfinding, the main subject of the paper and my previous Medium article, is based on the same underlying mathematics as grid-based visibility. In fact, it is possible to compute visible regions by simply counting paths.

To demonstrate visibility by counting, we’ll assume as before that the viewpoint is in the top left corner. We begin by placing a 1 in that corner, then we repeatedly copy numbers downward and to the right. When two numbers converge on the same grid cell, we add them together. The result is that every grid cell contains the number of grid paths heading away from the viewpoint and ending up at that cell. For example, there are 742 such paths from the viewpoint to the bottom right corner.

Counting grid paths from the viewpoint in the top left corner. (Animation by author)

Next, we repeat the process ignoring all obstacles. Every grid cell ends up with the maximum possible number of grid paths from the viewpoint to that cell. This is actually just Pascal’s Triangle, a well-known number pattern that the previous article discusses at length. Observe that there are a maximum of 2002 grid paths from the viewpoint to the bottom right corner.

Counting grid paths from the viewpoint while ignoring obstacles. (Animation by author)

In our pathfinding by counting approach, we took two sets of path counts and multiplied them together. In visibility by counting, we take the two sets of path counts and divide. Taking the actual number of paths to each grid cell (the first animation above), and then dividing by the maximum possible number of paths to that cell (the second animation), we end up with the visibility score for each grid cell. We then classify each cell as visible if its score is at least 0.5. For example, the cell in the bottom right corner is reached by 742 out of a possible 2002 grid paths. Its visibility score is 472/2002, or approximately 0.37, and it is classified as not visible.

Dividing path counts to obtain visibility scores. (Animation by author)

Again, we demonstrated in the paper that visibility scores computed by counting are mathematically equivalent to those produced by the original interpolation formula. In other words, both methods are viable ways of solving the visible region problem. If we choose to implement visibility by counting, however, we must remember that path counts increase exponentially with distance. If we represent these counts using 64-bit floating-point numbers, the path counts will overflow after reaching 1030 grid moves from the viewpoint. For that reason, I believe it makes sense to default to the linear interpolation method when implementing grid-based visibility. At the same time, I feel that the connection to path counting is interesting and deserves to be shared.

One concern you may have about grid-based visibility is its accuracy, especially since certain vector-based visibility methods are considered to produce exact solutions to the visible region problem. Here’s the reality about exact solutions: They’re only exact if the input geometry is exact, which is rarely the case in practice. When performing a visibility analysis, a pathfinding analysis, or any kind of spatial analysis on a model of a real-world environment, the model is almost always an approximation due to discretization errors, measurement errors, and in some cases construction errors. The fact that grid-based visibility introduces some additional error may or may not be a serious drawback, depending on the application.

Having said that, there is a way to improve the accuracy of grid-based visibility results without increasing the resolution of the grid. Our examples so far have used only the 4-neighborhood, which is the simplest but least accurate 2D grid neighborhood. As previously mentioned, we have the option of choosing a larger grid neighborhood for more accurate results. The diagram below depicts the 4-, 8-, and 16-neighborhoods for rectangular grids, as well as the 6- and 12-neighborhoods for triangular grids.

Rectangular and triangular grid neighborhoods. (Image by Autodesk Research [1], used with permission)

To see the effect of larger neighborhoods, we’ll rewrite the Python script from the top of the article. In this new version of the program, the visibility_within_cone function computes visibility scores within a cone bracketed by two vectors. This may not be the most efficient implementation, but it will help us understand that transitioning to larger grid neighborhoods means applying the same algorithm within a greater number of thinner cones.

import numpy as np
import matplotlib.pyplot as plt# Set dimensions
nx = 25
ny = 25
# Create map
grid = np.ones((nx,ny))
wx = nx//10 + 1
wy = ny//10 + 1
grid[int(.3*nx):int(.3*nx)+wx,int(.1*ny):int(.1*ny)+wy] = 0
grid[int(.1*nx):int(.1*nx)+wx,int(.5*ny):int(.5*ny)+wy] = 0
grid[int(.6*nx):int(.6*nx)+wx,int(.6*ny):int(.6*ny)+wy] = 0
# Display map
plt.figure("Map")
plt.imshow(np.transpose(grid))
# Define visibility function
def visibility_within_cone(grid, u_direction, v_direction):
u = np.asarray(u_direction, dtype=int)
v = np.asarray(v_direction, dtype=int)
origin = np.array([0,0], dtype=int)
dims = np.asarray(grid.shape, dtype=int)
m = 0
k = 0
position = np.array([0,0], dtype=int)
while np.all(position < dims):
while np.all(position < dims):
if not np.all(position == 0):
pos = tuple(position)
pos_minus_u = tuple(np.maximum(origin, position - u))
pos_minus_v = tuple(np.maximum(origin, position - v))
grid[pos] *= (m*grid[pos_minus_u] + 
k*grid[pos_minus_v]) / (m + k)
k += 1
position += v
m += 1
k = 0
position = m*u
# Compute visibility
visibility_within_cone(grid, [1,0], [0,1])
# Display visibility
plt.figure("Visibility")
plt.imshow(np.transpose(grid))
plt.show()

Since we are calling the function with the vectors [1,0] and [0,1], we are still using the 4-neighborhood. The results are the same as those produced by our first script.

The 25×25 visibility grid for the 4-neighborhood. (Image by author)

But now we can easily modify the code to use the 8-neighborhood. To do this, replace the code in the Compute visibility section with the code below. The visibility function is now applied twice, first within the cone between the diagonal [1,1] and the grid axis [1,0], and then between [1,1] and [0,1].

# Compute visibility
visibility_within_cone(grid, [1,1], [1,0])
visibility_within_cone(grid, [1,1], [0,1])

Here are the results for the 8-neighborhood. The shadow edges have sharpened.

The 25×25 visibility grid for the 8-neighborhood. (Image by author)

Finally, we can transition to the 16-neighborhood by applying the visibility function within 4 cones.

# Compute visibility
visibility_within_cone(grid, [2,1], [1,0])
visibility_within_cone(grid, [2,1], [1,1])
visibility_within_cone(grid, [1,2], [1,1])
visibility_within_cone(grid, [1,2], [0,1])

Here are the 16-neighborhood results.

The 25×25 visibility grid for the 16-neighborhood. (Image by author)

The 16-neighborhood seems like it would offer more than enough accuracy for most applications. However, it is possible to continue upgrading to the 32-neighborhood, the 64-neighborhood, etc., if higher quality results are needed.

That takes care of the rectangular grids. Triangular grids, also known as hexagonal grids, are trickier to implement because there’s no ideal way to index the grid cells. Various indexing strategies are described in the Red Blog Games tutorial on Hexagonal Grids, which includes a section on visibility using line-of-sight tests. I leave it as a challenge to you to implement grid-based visibility on a triangular grid.

Grid-based visibility is a simple and practical alternative to ray casting and other vector-based visibility methods. Due to the timing and context of its discovery, the approach remains largely unknown to computer scientists. But I hope you’ll agree that it’s time for grid-based visibility to become visible, and I hope you’ll find an opportunity to use it in one of your own artificial intelligence projects.

[1] R. Goldstein, K. Walmsley, J. Bibliowicz, A. Tessier, S. Breslav, A. Khan, Path Counting for Grid-Based Navigation (2022), Journal of Artificial Intelligence Research, vol. 74, pp. 917–955

[2] Y.-H. R. Tsai, L.-T. Cheng, H. Osher, P. Burchard, G. Sapiro, Visibility and its Dynamics in a PDE Based Implicit Framework (2004) [PDF]. Journal of Computational Physics, vol. 199, no. 1, pp. 260–290

[3] C.-Y. Kao, R. Tsai, Properties of a Level Set Algorithm for the Visibility Problems (2008) [PDF], Journal of Scientific Computing, vol. 35, pp. 170–191

[4] D. Fisher-Gewirtzman, A. Shashkov, Y. Doytsher, Voxel Based Volumetric Visibility Analysis of Urban Environments (2013), Survey Review, vol. 45, no. 333, pp. 451–461

How a 3-line algorithm provides a decent alternative to ray casting

Image by Autodesk Research [1]. (Used with permission)

The basic problem is this: Given a 2D top-down map, compute the region of space that is visible from a point.

Here is grid-based visibility written in 3 lines of Python code.

for x in range(grid.shape[0]):
for y in range(int(x==0), grid.shape[1]):
grid[x,y] *= (x*grid[x-1,y] + y*grid[x,y-1]) / (x + y)

import numpy as np
import matplotlib.pyplot as plt# Set dimensions
nx = 25
ny = 25
# Create map
grid = np.ones((nx,ny))
wx = nx//10 + 1
wy = ny//10 + 1
grid[int(.3*nx):int(.3*nx)+wx,int(.1*ny):int(.1*ny)+wy] = 0
grid[int(.1*nx):int(.1*nx)+wx,int(.5*ny):int(.5*ny)+wy] = 0
grid[int(.6*nx):int(.6*nx)+wx,int(.6*ny):int(.6*ny)+wy] = 0
# Display map
plt.figure("Map")
plt.imshow(np.transpose(grid))
# Compute visibility
for x in range(grid.shape[0]):
for y in range(int(x==0), grid.shape[1]):
grid[x,y] *= (x*grid[x-1,y] + y*grid[x,y-1]) / (x + y)
# Display visibility
plt.figure("Visibility")
plt.imshow(np.transpose(grid))
plt.show()

The 25×25 input map. (Image by author)

The resulting 25×25 visibility grid. (Image by author)

nx = 225
ny = 225

…we get the following results.

The visibility grid with resolution increased to 225×225. (Image by author)

Depending on the application, we may wish to classify every grid cell as either visible (1) or not visible (0). We can do this by applying a threshold of 0.5 after the loop.

for x in range(grid.shape[0]):
for y in range(int(x==0), grid.shape[1]):
grid[x,y] *= (x*grid[x-1,y] + y*grid[x,y-1]) / (x + y)
grid[:] = (grid >= 0.5)

Inserting that 4th line into the script gives us the result below.

The 225×225 visibility grid after applying a threshold. (Image by author)

Before we move on, I should confess that I used a few tricks to get the algorithm down to 3 lines:

The expression int(x==0) in the 2nd for loop is a clever trick that skips over the grid cell [0, 0] where the interpolation formula would produce a divide-by-zero error.
I’m relying on the fact that the NumPy library allows arrays to be accessed using negative indices. Other programming languages might require a few more lines of code to check for this condition.
All the code above assumes the viewpoint is in the corner of the map. Moving the viewpoint to an arbitrary cell with coordinates x0 and y0 requires the calculation to be repeated four times, once in each of four quadrants.

To place the viewpoint in the center of the map, replace the code in the Compute visibility section of the script with the following.

# Set viewpoint
x0 = nx//2
y0 = ny//2# Define visibility function
def visibility_from_corner(grid):
for x in range(grid.shape[0]):
for y in range(int(x==0), grid.shape[1]):
grid[x,y] *= (x*grid[x-1,y] + y*grid[x,y-1]) / (x + y)
# Compute visibility
visibility_from_corner(grid[x0:,y0:])
visibility_from_corner(grid[x0::-1,y0:])
visibility_from_corner(grid[x0::-1,y0::-1])
visibility_from_corner(grid[x0:,y0::-1])

Here are the results with the viewpoint in the center.

The 225×225 visibility grid with the viewpoint in the center. (Image by author)

Here’s a little trick I can’t resist showing: Grid-based visibility implemented in Excel. The following screen recording is roughly 1 minute.

Grid-based visibility in Excel. (Recording by author)

Want to try it yourself? Follow the instructions below. It should take only 1 or 2 minutes.

Open MS Excel and create a Blank workbook.
Select cell B2, click on the Formula Bar (or press F2), paste in the following text, and press Enter:
=((COLUMN(B2)-2)*A2+(ROW(B2)-2)*B1)/((COLUMN(B2)-2)+(ROW(B2)-2))
Reselect cell B2, press Ctrl-C to copy, select a range of cells from B2 to Z26, press Ctrl-V to paste.
In the Home tab, select Conditional Formatting, Highlight Cells Rules, Less Than. Type 0.5 into the first box (“Format cells that are LESS THAN”), then select any “Fill” option from the drop-down menu on the right (e.g. “Light Red Fill with Dark Red Text”). Click OK.
Select cell B2 and press 1, then Enter.
Select all cells by clicking the green triangle above and to the left of cell A1, then click and drag the vertical line between A and B to shrink the cell width so that all cells end up approximately square.
Create obstacles by clicking on cells and pressing Backspace. Shadows extending away from the top left corner should automatically appear.

Observe that the obstacles need to be multiple cells wide to produce reasonable looking shadows.

The original level set visibility method is easily adapted to work with explicit geometry familiar to computer scientists. The Python code near the top of this article is an example of an implementation that combines the original interpolation formula with explicit grid-based geometry.
The size of the grid neighborhood can be increased to produce more accurate results. The examples in this article have so far used the 4-neighborhood, where information flows to the north, south, east, and/or west. My colleagues and I used the 8-neighborhood, which allows information to flow diagonally, in both the paper and an architectural design tool called SpaceAnalysis.
Grid-based visibility results can be shown to converge on the exact solution using probability theory, specifically the central limit theorem. The original proof from the level set community used numerical analysis [3].
Visibility scores produced by linear interpolation can be reinterpreted as the fraction of shortest grid paths heading away from the viewpoint that are not blocked by obstacles.

Counting grid paths from the viewpoint in the top left corner. (Animation by author)

Counting grid paths from the viewpoint while ignoring obstacles. (Animation by author)

Dividing path counts to obtain visibility scores. (Animation by author)

Rectangular and triangular grid neighborhoods. (Image by Autodesk Research [1], used with permission)

import numpy as np
import matplotlib.pyplot as plt# Set dimensions
nx = 25
ny = 25
# Create map
grid = np.ones((nx,ny))
wx = nx//10 + 1
wy = ny//10 + 1
grid[int(.3*nx):int(.3*nx)+wx,int(.1*ny):int(.1*ny)+wy] = 0
grid[int(.1*nx):int(.1*nx)+wx,int(.5*ny):int(.5*ny)+wy] = 0
grid[int(.6*nx):int(.6*nx)+wx,int(.6*ny):int(.6*ny)+wy] = 0
# Display map
plt.figure("Map")
plt.imshow(np.transpose(grid))
# Define visibility function
def visibility_within_cone(grid, u_direction, v_direction):
u = np.asarray(u_direction, dtype=int)
v = np.asarray(v_direction, dtype=int)
origin = np.array([0,0], dtype=int)
dims = np.asarray(grid.shape, dtype=int)
m = 0
k = 0
position = np.array([0,0], dtype=int)
while np.all(position < dims):
while np.all(position < dims):
if not np.all(position == 0):
pos = tuple(position)
pos_minus_u = tuple(np.maximum(origin, position - u))
pos_minus_v = tuple(np.maximum(origin, position - v))
grid[pos] *= (m*grid[pos_minus_u] + 
k*grid[pos_minus_v]) / (m + k)
k += 1
position += v
m += 1
k = 0
position = m*u
# Compute visibility
visibility_within_cone(grid, [1,0], [0,1])
# Display visibility
plt.figure("Visibility")
plt.imshow(np.transpose(grid))
plt.show()

Since we are calling the function with the vectors [1,0] and [0,1], we are still using the 4-neighborhood. The results are the same as those produced by our first script.

The 25×25 visibility grid for the 4-neighborhood. (Image by author)

# Compute visibility
visibility_within_cone(grid, [1,1], [1,0])
visibility_within_cone(grid, [1,1], [0,1])

Here are the results for the 8-neighborhood. The shadow edges have sharpened.

The 25×25 visibility grid for the 8-neighborhood. (Image by author)

Finally, we can transition to the 16-neighborhood by applying the visibility function within 4 cones.

# Compute visibility
visibility_within_cone(grid, [2,1], [1,0])
visibility_within_cone(grid, [2,1], [1,1])
visibility_within_cone(grid, [1,2], [1,1])
visibility_within_cone(grid, [1,2], [0,1])

Here are the 16-neighborhood results.

The 25×25 visibility grid for the 16-neighborhood. (Image by author)

[1] R. Goldstein, K. Walmsley, J. Bibliowicz, A. Tessier, S. Breslav, A. Khan, Path Counting for Grid-Based Navigation (2022), Journal of Artificial Intelligence Research, vol. 74, pp. 917–955

[3] C.-Y. Kao, R. Tsai, Properties of a Level Set Algorithm for the Visibility Problems (2008) [PDF], Journal of Scientific Computing, vol. 35, pp. 170–191

[4] D. Fisher-Gewirtzman, A. Shashkov, Y. Doytsher, Voxel Based Volumetric Visibility Analysis of Urban Environments (2013), Survey Review, vol. 45, no. 333, pp. 451–461

Read original article here

Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – admin@technoblender.com. The content will be deleted within 24 hours.

A Quick and Clear Look at Grid-Based Visibility | by Rhys Goldstein | May, 2023

How a 3-line algorithm provides a decent alternative to ray casting

How a 3-line algorithm provides a decent alternative to ray casting

Related Posts