Hacker News Reader

Comment by yorwba | Hacker News Reader

"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

View on HN

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

Reply on news.ycombinator.com