2

I have NxM board. I want to add K obstacles to it, but in a way so it is still possible to get from each empty space to every other empty space. I want it to look something like this

example result

where blue squares are obstacles.

In other words, I have a graph grid and I want to randomly remove K vertices from it without disconnecting it.

I know that i could do this by doing dfs from one node and removing farthest vertices, but it will not really be random, it does not look good and it is not what I'm looking for.

Is there an alghoritm which can do what I want, or does anyone have some ideas to test?

edit: typical maze generation algorithms don't apply in my case, because from what I understand they work by removing edges from the graph, and here I need to remove whole vertices

musztardus
  • 47
  • 5
  • Does this answer your question? [What's a good algorithm to generate a maze?](https://stackoverflow.com/questions/38502/whats-a-good-algorithm-to-generate-a-maze) – fafl Jan 02 '20 at 16:36
  • @fafl unfortunately not, because those algorighms work by removing edges from the graph, and in my case i want to remove whole vertices. – musztardus Jan 02 '20 at 16:46
  • What are the constraints on `K`? – Raj Jan 02 '20 at 17:01
  • @Raj None, other than it being smaller than N*M. However it could be limited to N*M/2 if it helps solve the problem – musztardus Jan 02 '20 at 17:08
  • Seems like you need three rules: 1) each blue region forms a tree, i.e. no cycles, 2) the nodes of one blue region cannot be adjacent to another blue region, even diagonally, 3) each blue region can only have one node on the edge of the board. In general, this means that K must be much smaller than MxN. – user3386109 Jan 03 '20 at 00:16

1 Answers1

2

You can do this with a disjoint set data structure: https://en.wikipedia.org/wiki/Disjoint-set_data_structure

  • Every vertex is assigned to a set that identifies which "boundary" it is a part of
  • Initially, the vertexes on the outer boundary are all in the same set, and each internal vertex is in its own set.
  • Randomly choose a "valid" square and fill it. Correspondingly merge the boundary sets for each of its 4 corners.
  • Repeat until K squares have been chosen

A square is "invalid" if filling it would create a boundary loop:

  • Any unfilled square with 3 filled neighbors is valid. Otherwise...
  • For each unfilled neighbor, if its adjacent corners are in the same boundary, then filling the square would create a loop, so it's invald.
  • If either pair of opposite corners are in the same boundary, but neither of the other corners are, then filling the square would create a loop, so it's invalid.

For an efficient implementation, randomly try all the squares in a pseudorandom order. Since filling a square might make a previously invalid square valid, however, whenever you fill a square, add its previously excluded neighbors back into the pool of possibilities.

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87
  • This seems to work like something that could work. However if I understand correctly, [in this case](https://i.imgur.com/7urTcct.png), the yellow square would be considered invalid, because two corners of the upper white square are in the same set. How can this be dealt with? – musztardus Jan 02 '20 at 22:21
  • Good catch. I added a special case for that. I'll go through all the cases later to make sure they all work. – Matt Timmermans Jan 03 '20 at 00:19