CODEWITHSUNDEEP
algorithm
Bagel03
Bagel03

Reputation: 715

Fill in Tiles on a Grid so all Unfilled Tiles are Reachable

Could someone point me towards an algorithm that solves the issue below:

Say that I have a 10 * 10 grid of tiles. Each tile can be "full" (the player can't walk on them) or "empty" (the player can walk on them). I want to go through and randomly fill in tiles (to create a more interesting map), however I need all the "empty" tiles to be reachable. Here is a quick graphic:

We start at this:

 _ _ _ _ _ _ _ _ _ _
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|

Then go through and fill some of the tiles in:

 _ _ _ _ _ _ _ _ _ _
|#|_|_|#|_|#|_|_|_|_|
|_|_|#|_|_|_|_|_|#|_|
|_|_|#|_|_|#|#|_|#|_|
|_|_|_|_|#|#|#|_|_|#|
|_|#|_|_|_|_|_|_|_|_|
|_|_|_|#|_|#|_|#|_|_|
|#|#|_|_|_|_|#|_|_|#|
|_|_|_|_|#|_|#|_|_|_|
|_|_|#|_|_|_|_|#|_|_|

And remove all the extra lines (Just for show):

 _ _ _ _ _ _ _ _ _ _
|#     #   #        |
|    #           #  |
|    #     # #   #  |
|        # # #     #|
|  #                |
|      #   #   #    |
|# #         #     #|
|        #   #      |
|_ _ # _ _ _ _ # _ _|

As you can see, we are now left with a map that is much more interesting, and can be randomly generated (Based on how we decide when to "fill" a tile in). However, using simple randomness could lead to situations like this:

 _ _ _ _ _ _ _ _ _ _
|#     #   #       #|
|    #     #     #  |
|    #     #     #  |
|      # #         #|
|  #                |
|      # # #     #  |
|#     #     #     #|
|      # # # #      |
|_ _ # _ _ _ _ # _ _|

Here, there are plenty of spaces that are blocked off from the rest of the map. If the player started outside of these "rooms", it would be impossible to get in. If they started inside one of the "rooms", they could not get out. I understand I could test this using floodfill or something similar, however that means I would have to generate new map until one randomly fits these criteria. What I was thinking about was a new ruleset for "filling" tiles. Right now I am just walking through each tile, and checking if a random number is above a threashold. If it is fill it in, if not, go to the next tile. However, this means each tile is completely unrelated to the other in the grid. I have been thinking about a lot of rulesets that could help, alough I can wrap my head around most of them. If anyone has any suggestions, please let me know

Upvotes: 0

Views: 334

Answers (2)

Ehsan Gerayli
Ehsan Gerayli

Reputation: 594

You can follow this approach:

We can create a graph with your Tiles which the Tiles are the nodes of graph and define edges if two Tiles are both filled and adjacent (diagonally is optional if your player can move diagonally). To support the edges , make the grid 12*12 and fill all the edges. In this graph a Tile is isolated if and only if a loop exists in the graph So you can randomly fill a value of Tile, and check if the new Graph is still Tree accept it, otherwise redo the filling and go for the next Tail. Checking if Graph is Tree or not can be done with DFS.

Upvotes: 1

Shridhar R Kulkarni
Shridhar R Kulkarni

Reputation: 7063

Preventive approach

In this approach, you don't allow forming closed spaces.

One of the approaches could be using union-find or disjoint set data structure.

One ends up with closed spaces if

  • Without touching border: a cycle is formed
  • With touching border: two non-adjacent (horizontally or vertically) full tiles, connected via some path of full tiles, are also connected with the border.

So as you fill up this grid, for every tile being chosen as full tile, efficiently check for the above two cases with a union-find.

Corrective approach

In this approach, you fill up the grid randomly with some full tiles. This approach might form closed spaces. Now detect if the space is closed using union-find data structure for full tiles or flood fill of empty tiles. If the space is closed, correct it by emptying some full tiles. Which full tiles to empty? There could be multiple approaches. One of them could be to empty the full tiles, associated with the closed space, that are touching the border or forming a cycle. Again, for this union-find or any algorithms related to graph connectivity like BFS, DFS, etc. could be used.

I'll let you know if any more approaches cross my mind. Hope the above helped.

Upvotes: 1

Related Questions