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 will 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 pc science community, however it’s a practical method that is smart for a wide range 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 quite a lot 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 might 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 will also be used to approximate the world illuminated by a source of sunshine.
The essential problem is that this: Given a 2D top-down map, compute the region of space that’s visible from a degree.
Should you ask a pc scientist the way to solve this problem, it is incredibly unlikely that they’ll even consider what I call a grid-based algorithm: a technique where numbers in every grid cell are computed based on numbers in neighboring grid cells. The visible region problem is sort of all the time tackled using a vector-based visibility algorithm involving line-of-sight tests. One of the vital popular vector-based visibility techniques is ray casting, where quite a few rays are forged in numerous directions from a viewpoint. Should 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 a superb 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 drawbacks. So why is it that only vector-based approaches are widely used for visibility? I’ve come to consider that while each grid-based and vector-based methods have benefits and drawbacks for visibility problems, grid-based visibility has been curiously ignored 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 supply 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 stuffed 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 stuffed with visibility scores, 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 perimeters 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 increasingly more accurate. Actually, 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 essential to keep in mind that grid-based visibility is an approximate method. A few of the grid cells could also be classified as visible even in the event that they needs to be just inside a shadow, and a few could also be classified as blocked even in the event that they needs to be just inside 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 just a few tricks to get the algorithm all the way down to 3 lines:
- The expression
int(x==0)
within the 2ndfor
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 counting on the proven fact that the NumPy library allows arrays to be accessed using negative indices. Other programming languages might require just a few more lines of code to envision for this condition.
- 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
andy0
requires the calculation to be repeated 4 times, once in each of 4 quadrants.
To put 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 of trick I can’t resist showing: Grid-based visibility implemented in Excel. The next screen recording is roughly 1 minute.
Wish to try it yourself? Follow the instructions below. It should take only one 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 next text, and pressEnter
:=((COLUMN(B2)-2)*A2+(ROW(B2)-2)*B1)/((COLUMN(B2)-2)+(ROW(B2)-2))
- Reselect cell B2, press
Ctrl-C
to repeat, select a variety of cells from B2 to Z26, pressCtrl-V
to stick. - Within the Home tab, select Conditional Formatting, Highlight Cells Rules, Less Than. Type
0.5
into the primary box (“Format cells which are LESS THAN”), then select any “Fill” option from the drop-down menu on the best (e.g. “Light Red Fill with Dark Red Text”). Click OK. - Select cell B2 and press
1
, thenEnter
. - 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 each one cells find yourself roughly square.
- Create obstacles by clicking on cells and pressing
Backspace
. Shadows extending away from the highest left corner should robotically appear.
Observe that the obstacles should be multiple cells wide to supply reasonable looking shadows.
The history of grid-based visibility explains why the tactic never gained widespread recognition. To start with, 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 turn out 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 keen on 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:
- The unique level set visibility method is well adapted to work with explicit geometry familiar to computer scientists. 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.
- The scale of the grid neighborhood will be increased to supply more accurate results. 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.
- Grid-based visibility results will be shown to converge on the precise solution using probability theory, specifically the central limit theorem. The unique proof from the extent set community used numerical evaluation [3].
- Visibility scores produced by linear interpolation will be reinterpreted because the fraction of shortest grid paths heading away from the point of view that will not be blocked by obstacles.
That last remark revealed that central grid-based pathfinding, the most important subject of the paper and my previous Medium article, is predicated on the identical underlying mathematics as grid-based visibility. Actually, it is feasible to compute visible regions by simply counting paths.
To display visibility by counting, 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 best. When two numbers converge on the identical grid cell, we add them together. The result’s that each grid cell incorporates 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 comparable to 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 keep in mind 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 consider 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 could have about grid-based visibility is its accuracy, especially since certain vector-based visibility methods are considered to supply 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 sort of all the time an approximation because of discretization errors, measurement errors, and in some cases construction errors. The proven fact that grid-based visibility introduces some additional error may or might not be a serious drawback, depending on the appliance.
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 only but least accurate 2D grid neighborhood. As previously mentioned, we now have 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 will not be probably the most efficient implementation, but it should 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 the identical as 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 inside 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 will 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. Because 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 turn out to be visible, and I hope you’ll find a chance to make use of it in certainly one of your personal 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