CODEWITHSUNDEEP
algorithmgridpseudocodeflood-fill
ThatOneGuyInXNA
ThatOneGuyInXNA

Reputation: 111

Connect areas on a grid

I have a tile grid. It is a 2d array of booleans. 'false' means an empty square, 'true' means a wall. I need to connect all of the empty areas by removing the walls. So far all of my ideas were pretty inefficient.

The only guarantee is that all of the empty regions are separated by a one wall thick layer. I would prefer if there were no loops (once two regions are connected no more walls are removed that would reconnect those two regions)

A sample grid (# for wall, . for empty space):

############
#....#.....#
#..##....###
#..#...##..#
######.#...#
#...#..#...#
#....####..#
#.....#....#
############

any algorithms or pseudo code to help with this is appreciated

Upvotes: 3

Views: 287

Answers (1)

Herokiller
Herokiller

Reputation: 2991

I think you are looking for minimum spanning tree algorithm, for example Kruskal's Algorithm (assuming you need to remove minimal amount of walls)

any empty region would be a vertex in the graph, and those of them which could be connected by removing a piece of wall would have an edge among them (in your case only of weight 1).

Upvotes: 2

Related Questions