Keep 'em (not) separated: detecting discontinuities in grid graphs
12 comments
·February 3, 2025o11c
xigoi
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.
penteract
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.
thaumasiotes
> 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
XX
+Xyorwba
"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
XXthaumasiotes
> (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
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..xigoi
This seems to be related to the Steinhaus chessboard theorem:
https://en.m.wikipedia.org/wiki/Steinhaus_chessboard_theorem
seveibar
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...
moron4hire
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.
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).