Keep 'em (not) separated: detecting discontinuities in grid graphs | Hacker News Reader

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

holm.dog

27 pointsfriendshaver12 comments

This is well-studied problem, and trying to make your own solution from scratch you'll often miss the efficient solutions.

https://en.wikipedia.org/wiki/Dynamic_connectivity

To adjust the terminology:

* cells are vertices

* the path between adjacent cells that are both not obstacles are edges

* adding an obstacle means removing all its edges

* removing an obstacle means adding edges for each adjacent cell that isn't also an obstacle

* it's illegal to end up with multiple components (edit: rephrased for correctness) other than obstacles

Personally I've only done the "add edges" direction (which is much simpler).

According to the article, the algorithm for deleting edges runs in amortized O(log n) time, which relies on the fact that if you delete an edge which breaks the graph into two halves (which is the worst-case scenario), the next time you’ll only have half as many vertices in each component. However, the OP is not actually deleting the edges, just checking if deleting them would disconnect the graph. Therefore, unless I’m missing something, the amortization would not work.

Unless I'm missing something, this can be done in O(n) time by tracking the connected components of wall (diagonally touching walls are connected). Placing a new wall creates an enclosed region if and only if it touches 2 separated sections of wall that are part of the same component.

The union-find disjoint sets algorithm can find whether they're in the same component. If a wall is added, it should be unioned with all adjacent walls. If a wall piece is removed, the components it was part of need to be recalculated, but it looks like that shouldn't happen more than once per frame.

In this case, the lookups of the union find algorithm will never take more than O(n) overhead per frame while checking all of up to n possible wall positions.

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

> Placing a new wall creates an enclosed region if and only if it touches 2 separated sections of wall that are part of the same component.

What do you mean by "separated"?

You need to be able to fill in the fourth corner of a 2x2 square, for example.

Bad:

    XXX
    X.X
    +XX

Good:

    XX
    +X

"separated" = "not connected when considering only the neighbors of where you intend to place the new wall"

(Your bad example is a bad bad example because the . is already enclosed.)

Bad:

   X
  X.X
  .+.
  ...

   XX
  X..X
  .+X
  ...

   XX
  X..X
  .+.X
  ..X

   XX
  X..X
  .+.X
  .X.X
    X

   XX
  X..X
  .+.X
  X..X
   XX

> (Your bad example is a bad bad example because the . is already enclosed.)

That depends whether diagonal movement is possible. Except for the recording of the actual game, the graphics in the post tend to imply that it is.

If it isn't, then the filling-in-the-square example:

    XX
    +X

meets the definition "touches two separated sections of wall that are part of the same component" (northwest and southeast; northeast isn't a neighbor of the new wall), but fails to create an enclosed region. And by this definition of connectivity, it is never possible for two neighbors of any space not to be "separated".

There was something else in the article that bothered me:

>> 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.

This seems to say that this wall addition is fine, failing to separate the grid into two parts:

    ..X..
    ..X..
    ..+..
    ..X..
    ..X..

Diagonal player movement isn't allowed (from the looks of the article), but wall connections can be diagonal. There's a duality here - if players and enemies could move diagonally, the algorithm could be adapted by only considering horizontal and vertical wall adjacencies (although still looking at the surrounding 8 squares to determine separation of adjacent walls). We're relying on the property "if adding a wall creates an enclosed region, one of the enclosed squares must be move-adjacent to the new wall".

"separated" = "not connected when considering only the 8 neighbors of where you intend to place the new wall; diagonals do count as connections between walls".

In the following example, the walls adjacent to the + are not separated:

    +X
    X.

In the next example, the walls are adjacent to the + are separated:

    X..
    .+.
    ..X

> There was something else in the article that bothered me

Regarding your second point, I think the article changed half way through from assuming the play area is surrounded by a wall to assuming the play area is surrounded by empty space, which I agree is confusing. Either case could be covered by this algorithm - just start with a connected component of wall at the edge of the play area.

This seems to be related to the Steinhaus chessboard theorem:

https://en.m.wikipedia.org/wiki/Steinhaus_chessboard_theorem

This is a very nice writeup, in game engines, they often cache a “nav mesh” that indicates how one point can go to basically any other point. As the author, mentioned, finding a path to a known outer point validates that the point has not been enclosed, so it seems like this could be solved efficiently with a cached pathfinding algorithm I’d also consider forming a graph from the grid cells and using a max flow algorithm, these are very fast! No affiliation but I love this paper on cached pathfinding algorithms for games https://www.gameaipro.com/GameAIPro/GameAIPro_Chapter17_Path...

I haven't taken the time to fully understand the write up, but it seems like it would disallow creating a box that encloses both characters together, which would be a stupid move, but not necessarily "against the rules".

As I understand your algorithm, your true goal is not to determine if cells have a path to the edge, but that the characters can reach each other. So, it seems like it would be better to use the A* Algorithm to determine if there is a path between the two characters.

I just clicked here because of the Offspring reference.

Interestingly, the phrase came from the singers time working in a lab doing work on cells

Reply on news.ycombinator.com