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.
The Visible Region Problem
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.