Keep 'em (not) separated: detecting discontinuities in grid graphs

In this post, I'm going to describe how I efficiently detected enclosed spaces in my browser game's map.

As the player places obstacles, cells that would create an enclosed space are greyed-out.

In Build + Brawl, a free browser game I recently published, enemies march relentlessly towards the player character. To keep them at bay, the player can place impassable obstacles onto the battlefield, forcing enemies along longer paths and buying time to defeat them. Given free rein in placing these obstacles, the player could avoid the challenge of the game entirely by enclosing their character in an impenetrable box:

A very frustrated enemy, unable to reach the player.

A more sadistic player might instead enclose the enemies in a box, imprisoning them until they can be destroyed:

A very sad enemy, unable to ever leave its prison.

These strategies would make the game trivial and boring, so I needed to prevent the player from using obstacles to create enclosed spaces.

Specifically, I needed to build a system that:

• Detects all cells where placing an obstacle would create an enclosed space
• Updates these results as the player adds or removes obstacles, possibly in rapid succession
• Does so without causing lag while running single-threaded in the browser

The ultimate goal is to produce a grid that shows the player where they can legally place obstacles.

Brute-force solution: flood fill

The map is divided into a grid of uniform cells. When there is no enclosed space, then every cell has a path to every other cell that does not require passing through an impassable obstacle. You can imagine if you turned on a faucet and water starts spreading from cell to cell, unable to pass through obstacles. If it floods every empty cell, then there is no enclosed space:

If some cells stay dry, then it must be because those cells were surrounded by obstacles that kept the water back:

This leads to the brute-force solution: a flood fill from every cell. Let's say we start with this map:

and we want to know whether it's legal to place an obstacle here:

We can pretend there's already an obstacle there, then turn on the (metaphorical) faucet. It doesn't matter from where, as long as the cell is empty. The water spreads to that cell's neighbors, then those cell's neighbors, and so on:

In this case, every empty cell gets flooded, so we can say it's legal to place an obstacle there:

However, if we considered a different cell, we might get a different answer:

In this case, when we start the faucet, it leaves one cell dry:

So we say that it's illegal to place an obstacle in that cell:

You can do this for every cell to get the full sets of legal and illegal placements:

Whenever the player adds or removes an obstacle, you can repeat the flood process again for every cell and get the new legal and illegal placements.

This approach works, but I found it to be too slow for my game. For every cell, we need to run a flood fill, which requires iterating over every other cell. This felt like more work than is necessary; is there a way to speed this up?

Saving time with sandwiches

We're going to take advantage of two useful intuitions:

• If every cell has a path to the boundary of the grid, then there are no enclosed spaces. Any enemy could move along the boundary to eventually get into any cell.
• If placing an obstacle in a given cell would create an enclosed space, then one of that cell's neighbors must be in the enclosed space. Placing an obstacle won't magically create an enclosed space somewhere far away.

Using these intuitions, we can reframe the problem as "placing an obstacle in cell A is legal only if each of A's neighbors still have a path to the grid boundary."

At a high level, to determine the legality of placing an obstacle in a cell, we can run a flood fill from each of its neighbors and see if each reaches the boundary:

The three neighbors of the proposed space are each able to flood to the boundary.

But this alone probably doesn't save much compute, since the flood may reach almost every cell before reaching the boundary. Notice how the faucet to the right still floods a bunch of wasted space. Meanwhile, we're increased the number of flood fills from one per cell to one per neighbor. We're off to a bad start!

To try to salvage this, we'll introduce a third intuition:

• If there is a path from cell A to cell B, and cell B has a path to the boundary, then cell A has a path to the boundary.

This means our flood fills don't need to make it all the way to the boundary -- they just need to make it to any cell that we know has a path to the boundary. Ideally, we can maintain a cache of known "escape routes" and stop flood fills when they reach one.

Of course, if we knew exactly which cells were escape routes, we'd be done; that's the whole problem we're trying to solve! Fortunately, there's one simpler statement we can make: if a cell isn't "sandwiched" by two obstacles, then that cell is definitely an escape route. A cell is sandwiched if you can draw through it a straight, cardinal-direction line that collides with an obstacle on either side of the cell, like this:

A map with three obstacles, and poorly drawn tomato-and-lettuce sandwiches indicating the "sandwiched" cells.

Not every sandwiched cell is necessarily in an enclosed space, as you can see in the example above. However, if a cell is not sandwiched, then it must be "open-faced", and have a direct path to the boundary. Using this heuristic doesn't give us every escape route, but it gives us enough to substantially prune the flood space.

Implementation

Let's get into how this would be implemented. We'll create a cached set of "open-faced" cells, which will contain every cell that is not sandwiched between two obstacles. Since the grid starts with no obstacles, we can initialize this set to contain every cell.

To determine whether we can legally place an obstacle in a cell, we'll start by temporarily placing an obstacle there. This might create new sandwiches; to check, we can fire a ray in each of the four cardinal directions, starting from the new obstacle. If the ray collides with another obstacle, then any cells up that point are sandwiched, and should be temporarily removed from the open-faced set:

The two vertical rays collide with no obstacles, so the cells along them stay open-faced. The rightward ray collides with an obstacle, so everything in between is sandwiched.

Now, we can run our flood fills from the neighbors of the new obstacle. Let's call the first neighbor N. We loop over the empty neighbors of N, looking for any open-faced cells. If we find one, then we know that N has a path to the boundary, and can stop. If we don't find one, then we iterate over the neighbors of those cells.

The flood doesn't need to make it to the boundary; it only needs to make it to a cell that isn't sandwiched.

This continues, flooding outward, until either:

• An open-faced cell is found, meaning that N has a path to the boundary; or
• No unvisited connections remain, meaning that N does not have a path to the boundary.

It's legal to place an obstacle in a cell only if every one of that cell's neighbors find a path to the boundary. When we have our answer, we remove the temporary obstacle and revert the open-faced set. In this case, we found an open-faced cell before actually getting to the boundary, saving us some precious compute.

We can repeat this check for every cell to produce our full map of legalities. The worst-case compute complexity is still the same as with brute-force flood fills: if the potential enclosed space is very large, its entire volume might be flooded. However, in practice, I found these heuristics to reduce lag considerably for the obstacle arrangements players tended to make. Obstacles tended to be towards the center of the map, with large open-faced spaces around them.

Adding and removing obstacles

When the player places a new obstacle, we repeat the same ray-firing process as during the legality check, but remove any newly-sandwiched cells permanently.

Removing an obstacle is a bit more complicated. If the player wants to remove an existing obstacle, we potentially need to add new cells to the open-faced set. We fire a ray to the left and to the right:

The two cells between obstacles start sandwiched.

If the ray to the right hits an obstacle, then we know the cells in between used to be sandwiched (between the hit obstacle and the obstacle-to-be-removed). If the ray to the left makes it to the boundary, then those cells are now open-faced, and can be added to the set:

The leftward ray hits no obstacles, so the cells to the right are no longer sandwiched.

Otherwise, those cells must still be sandwiched by whatever the left ray hit:

There is an obstacle to the left of the removed obstacle, so the cells to the right remain sandwiched.

Likewise, if the left ray hits but the right ray does not, then the cells to the left are no longer sandwiched. This is then repeated for up-down and down-up. We then need to recalculate placement legalities for all other cells, since they may now have new paths to the boundary. 

Other helpful tricks

• Even with this approach, it was still too laggy to update the legality of the entire map in a single frame. Instead, I created a coroutine that iteratively updated cells, taking no more than a fixed number of milliseconds each frame. This spread the work over a few frames.
• Not every cell needs to have its legality updated every time an obstacle is added or removed. For instance, only cells that are adjacent to at least two obstacles could possibly be illegal, so only those need to be checked.

A better option?

My friend Pablo Aldape proposed what might be a faster and more straightforward solution. Instead of treating this as a grid connectivity problem, it could be solved as a cycle detection problem: look for any obstacle that can loop back to itself via a chain of obstacles. If one exists, then an enclosed space also exists. This has a runtime proportional to the number of obstacles, which might still approach the total grid size, but in practice would not.

The one special case needed here is for spaces filled entirely with obstacles, such as a 2x2 region of obstacles. Such spaces easily create a cycle, but for gameplay purposes should still be allowed: the player character or an enemy cannot be trapped in a solid block, and building them is helpful for dealing with certain enemies that have obstacle-penetrating attacks. I'm sure someone can find an easy solution here, but I am too stuck on my good-enough solution to be that someone.