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

In my previous article, A Short and Direct Walk with Pascal’s Triangle, I explain how grid-based pathfinding could 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 , which computes visible regions without line-of-sight tests. Grid-based visibility is virtually unheard of in the pc science community, however it’s a practical method that is smart for quite a lot of artificial intelligence applications. It’s also extremely easy to implement, requiring as few as 3 lines of code. Read on to find your simplest option for solving visibility problems in video games, mobile robotics, or architectural design.

Much like pathfinding, visibility evaluation arises in plenty of fields involving artificial intelligence and spatial environments. A video game developer should want to compute the region of a game map that’s visible from an enemy watch tower. A mobile robotics engineer may have to compute a robot’s field of view in a simulation that tests the robot’s control system. An architect should want to analyze people’s views at various locations in a constructing or along a street. Visibility evaluation may also be used to approximate the realm illuminated by a source of sunshine.

The fundamental problem is that this: Given a 2D top-down map, compute the region of space that’s visible from some extent.

If you happen to ask a pc scientist solve this problem, it is incredibly unlikely that they may even consider what I call a : a way where numbers in every grid cell are computed based on numbers in neighboring grid cells. The visible region problem is nearly all the time tackled using a algorithm involving line-of-sight tests. One of the crucial popular vector-based visibility techniques is , where quite a few rays are forged in several directions from a viewpoint. If you happen to’re unfamiliar with ray casting and other vector-based solutions to the visible region problem, the Red Blob Games tutorial on 2D Visibility provides a wonderful backgrounder.

Each grid-based and vector-based approaches are popular for other spatial applications like pathfinding and 2D graphics. We’re all acquainted with raster (grid-based) and vector images, for instance, and we recognize that each forms of images have benefits and downsides. So why is it that only vector-based approaches are widely used for visibility? I’ve come to imagine that while each grid-based and vector-based methods have benefits and downsides for visibility problems, grid-based visibility has been curiously missed and deserves to be higher 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 provide visibility results. As we will 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 brief program. Be happy to repeat 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()

This system first creates and displays the map, a 25×25 grid where cells crammed with an obstacle have a worth of 0 and empty cells have a worth of 1. As shown below, the map has three square obstacles.

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

Each obstacle casts a shadow away from the highest left corner, though you’ll notice that the sides of the shadows are blurry. One option to sharpen those edges is to extend the resolution of the map. If we modify the grid size from 25 to 225 cells in each dimensions…

nx = 225
ny = 225

…we get the next results.

Here we see sharper and more accurate shadows. If we proceed to extend the resolution, the visibility scores will get an increasing number of accurate. The truth is, the outcomes will converge on the precise solution because the grid spacing approaches zero.

Depending on the application, we may need to categorise every grid cell as either visible (1) or not visible (0). We are able to do that 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.

It’s vital to do not forget that grid-based visibility is an approximate method. A number of the grid cells could also be classified as visible even in the event that they ought to be just inside a shadow, and a few could also be classified as blocked even in the event that they ought to be just throughout the visible region. But generally speaking, the outcomes must 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 couple of tricks to get the algorithm all the way down to 3 lines:

1. The expression int(x==0) within 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.
2. I’m counting on the incontrovertible fact that the NumPy library allows arrays to be accessed using negative indices. Other programming languages might require a couple of more lines of code to envision for this condition.
3. All of the code above assumes the point of view is within the corner of the map. Moving the point of view to an arbitrary cell with coordinates x0 and y0 requires the calculation to be repeated 4 times, once in each of 4 quadrants.

To position the point of view in the middle of the map, replace the code within the Compute visibility section of the script with the next.

# 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])

Listed below are the outcomes with the point of view in the middle.

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

Need to try it yourself? Follow the instructions below. It should take just one or 2 minutes.

1. Open MS Excel and create a .
2. Select cell , click on the (or press F2), paste in the next text, and press Enter:
   =((COLUMN(B2)-2)*A2+(ROW(B2)-2)*B1)/((COLUMN(B2)-2)+(ROW(B2)-2))
3. Reselect cell , press Ctrl-C to repeat, select a spread of cells from to , press Ctrl-V to stick.
4. Within the tab, select , , . Type 0.5 into the primary box (“Format cells which might be LESS THAN”), then select any “Fill” option from the drop-down menu on the suitable (e.g. “Light Red Fill with Dark Red Text”). Click .
5. Select cell and press 1, then Enter.
6. Select all cells by clicking the green triangle above and to the left of cell , then click and drag the vertical line between and to shrink the cell width so that every one cells find yourself roughly square.
7. Create obstacles by clicking on cells and pressing Backspace. Shadows extending away from the highest left corner should routinely appear.

Observe that the obstacles have to be multiple cells wide to provide reasonable looking shadows.

The history of grid-based visibility explains why the tactic never gained widespread recognition. Initially, despite its simplicity, grid-based visibility wasn’t invented until 2004 [2], and its convergence properties weren’t established until 2008 [3]. By that point, vector-based approaches like ray casting had grow to be ubiquitous. Computer scientists were not trying to find competing approaches. Secondly, the primary papers on grid-based visibility got here from a branch of mathematics called level set theory, where geometry is represented in an implicit manner unfamiliar to most computer scientists. While the extent 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 concrete informatics researchers in 2013 [4].

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

1. The Python code near the highest of this text is an example of an implementation that mixes the unique interpolation formula with explicit grid-based geometry.
2. The examples in this text have up to now 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 each the paper and an architectural design tool called SpaceAnalysis.
3. The unique proof from the extent set community used numerical evaluation [3].

That last remark revealed that , the predominant subject of the paper and my previous Medium article, relies on the identical underlying mathematics as grid-based visibility. The truth is, it is feasible to compute visible regions by simply counting paths.

To display , we’ll assume as before that the point of view is in the highest left corner. We start by placing a 1 in that corner, then we repeatedly copy numbers downward and to the suitable. When two numbers converge on the identical grid cell, we add them together. The result’s that each grid cell accommodates the variety of grid paths heading away from the point of view and ending up at that cell. For instance, there are 742 such paths from the point of view to the underside right corner.

Next, we repeat the method ignoring all obstacles. Every grid cell finally ends up with the utmost possible variety of grid paths from the point of view to that cell. This is definitely just Pascal’s Triangle, a widely known number pattern that the previous article discusses at length. Observe that there are a maximum of 2002 grid paths from the point of view to the underside right corner.

In our pathfinding by counting approach, we took two sets of path counts and multiplied them together. In visibility by counting, we take the 2 sets of path counts and divide. Taking the actual variety of paths to every grid cell (the primary animation above), after which dividing by the utmost possible variety of paths to that cell (the second animation), we find yourself with the visibility rating for every grid cell. We then classify each cell as visible if its rating is at the least 0.5. For instance, the cell in the underside right corner is reached by 742 out of a possible 2002 grid paths. Its visibility rating is 472/2002, or roughly 0.37, and it is classed as not visible.

Again, we demonstrated within the paper that visibility scores computed by counting are mathematically reminiscent of those produced by the unique interpolation formula. In other words, each methods are viable ways of solving the visible region problem. If we elect to implement visibility by counting, nonetheless, we must do not forget that path counts increase exponentially with distance. If we represent these counts using 64-bit floating-point numbers, the trail counts will overflow after reaching 1030 grid moves from the point of view. For that reason, I think it is smart to default to the linear interpolation method when implementing grid-based visibility. At the identical time, I feel that the connection to path counting is interesting and deserves to be shared.

One concern you’ll have about grid-based visibility is its accuracy, especially since certain vector-based visibility methods are considered to provide exact solutions to the visible region problem. Here’s the fact about exact solutions: They’re only exact if the input geometry is exact, which is never the case in practice. When performing a visibility evaluation, a pathfinding evaluation, or any type of spatial evaluation on a model of a real-world environment, the model is nearly all the time an approximation as a consequence of discretization errors, measurement errors, and in some cases construction errors. The incontrovertible fact that grid-based visibility introduces some additional error may or is probably not a serious drawback, depending on the applying.

Having said that, there’s a option to improve the accuracy of grid-based visibility results without increasing the resolution of the grid. Our examples up to now have used only the 4-neighborhood, which is the best but least accurate 2D grid neighborhood. As previously mentioned, we’ve got the choice of selecting a bigger grid neighborhood for more accurate results. The diagram below depicts the 4-, 8-, and 16-neighborhoods for rectangular grids, in addition to the 6- and 12-neighborhoods for triangular grids.

To see the effect of larger neighborhoods, we’ll rewrite the Python script from the highest of the article. On this new edition of this system, the visibility_within_cone function computes visibility scores inside a cone bracketed by two vectors. This may occasionally not be probably the most efficient implementation, but it is going to help us understand that transitioning to larger grid neighborhoods means applying the identical algorithm inside a greater variety 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’re calling the function with the vectors [1,0] and [0,1], we’re still using the 4-neighborhood. The outcomes are similar to those produced by our first script.

But now we will easily modify the code to make use of the 8-neighborhood. To do that, replace the code within the Compute visibility section with the code below. The visibility function is now applied twice, first throughout the cone between the diagonal [1,1] and the grid axis [1,0], after which between [1,1] and [0,1].

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

Listed below are the outcomes for the 8-neighborhood. The shadow edges have sharpened.

Finally, we will transition to the 16-neighborhood by applying the visibility function inside 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])

Listed below are the 16-neighborhood results.

The 16-neighborhood looks like it might offer good enough accuracy for many applications. Nonetheless, it is feasible to proceed upgrading to the 32-neighborhood, the 64-neighborhood, etc., if higher quality results are needed.

That takes care of the oblong grids. Triangular grids, also often called hexagonal grids, are trickier to implement because there’s no ideal option to index the grid cells. Various indexing strategies are described within the Red Blog Games tutorial on Hexagonal Grids, which incorporates a bit 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 an easy and practical alternative to ray casting and other vector-based visibility methods. As a consequence of the timing and context of its discovery, the approach stays largely unknown to computer scientists. But I hope you’ll agree that it’s time for grid-based visibility to grow to be visible, and I hope you’ll find a chance to make use of it in one in every of your individual 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 Evaluation of Urban Environments (2013), Survey Review, vol. 45, no. 333, pp. 451–461