Flood-Fill(-Esque) algorithm on a 2D grid

So in the Minesweeper game I launched recently, one of the small challenges was finding a way to optimise the Flood-Fill(-esque) algorithm I was using to uncover empty tiles across the grid and to find every tile that has a mine and explode / reveal it from in a wave out from the last mine if the player has won or from the mine that has already exploded. Its Flood-Fill(-esque) because floodfill was used for the empty tile reveal but not really for the end of game mines showing. It is however close enough of a topic to bundle in. There were 3 methods that were created / recreated…one of which is definitely not how to do Flood-Fill in a performance critical portion of the game…

Flood-Fill-Esque

Method 1.

Let’s start off with the most expensive method to use and one that you shouldn’t be using. I’m not even going to show you the code because it was that bad.

  1. Determine the max size of the map.
  2. Starting at 0, increase the current size of the checking area
  3. Iterate over 2 for loops, 1 for x and 1 for y starting it at -size and ending at +size
    1. If the tile is out of bounds continue
    2. Else if the tile is in bounds and contains a mine then reveal

The very bad thing about this method was that while it did what I wanted, it also checked every time that has already been checked. This also cause a large amount of frame drops the further away from the point current size became.

Method 2.

Itwas just adding a container to check if I already checked the current tile instead of doing the check. I saved ~5ms. That wasn’t a lot. It also duplicated data I didnt need. Method scrapped.

Method 3.

This involved starting at the center point (centre being a mine of mouse click etc.) and increasing the size value as before. This time however, it would loop through the x axis from -size to +size at either ends of the y dimension and then do the same for the y axis minus 1 on either end as they have already been checked. And because it was in Unity, after each size increase, it would yield until another frame to prevent blocking.

Subsequently, because this method ran a great deal smoother, it happened almost instantaneously with v-sync off. With it on it was capped to 60FPS which provided a nice cascade effect and I thought…’hmm, instead of yielding every frame and continuing until done, I could process a bunch of stuff, wait for a controlled duration and resume’ thanks to the processing time that has freed up. This controlled value is set to 30FPS. This means that it yields a WaitForSeconds instruction that waits for 0.333 seconds (1/30) before revealing or executing the next part of the size increase.

Here’s the algorithm in pseudo-code:

  1. Determine max size of loops from current position to furthest map edge
  2. Starting at 0, increase the current size of the checking area
    1. for x between -size and +size
      1. check(x, +size)
      2. check(x, -size)
    2. for y between (-size + 1) and (+size – 1)
      1. check(+size, y)
      2. check(-size, y)

Flood-Fill

The actual flood-fill method that was used as those methods above aren’t actually flood-fill. Speed is the value that controls how fast the flood-fill actually occurs. Similar to the FPS in method 3. This time, it [speed] was set to 60FPS (1/60).

 

- Check if it hasn't already been revealed
- If adjacent mines > 0 spawn marker
- Else Flood-Fill(pos)



FloodFill(Vector2 pos)
- if pos visited break
- if adjacent mines > 0 spawn marker & break
- else
    - Wait for speed
    - if in bounds FloodFill(pos where pos.x+1)
    - if in bounds FloodFill(pos where pos.x-1)
    - if in bounds FloodFill(pos where pos.y+1)
    - if in bounds FloodFill(pos where pos.y-1)

 

 

Yay recursion! Not going to lie, I screwed up twice by forgetting to have a statement that breaks out of the recursive loop which crashed Unity.

Leave a Reply