3 ms·

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 ne

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 https://en.wikipedia.org/wiki/Disjoint-set_data_structure

thaumasiotes 2y ago
> 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
- yorwba 2y ago
  "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
  - thaumasiotes 2y ago
    > (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..
    - penteract 2y ago
      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.
xigoi 2y ago
This seems to be related to the Steinhaus chessboard theorem: https://en.m.wikipedia.org/wiki/Steinhaus_chessboard_theorem https://en.m.wikipedia.org/wiki/Steinhaus_chessboard_theorem

thaumasiotes 2y ago

> 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

yorwba 2y ago
"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
- thaumasiotes 2y ago
  > (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..
  - penteract 2y ago
    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.

xigoi 2y ago

This seems to be related to the Steinhaus chessboard theorem: https://en.m.wikipedia.org/wiki/Steinhaus_chessboard_theorem https://en.m.wikipedia.org/wiki/Steinhaus_chessboard_theorem