I have a game which is a Snake/Qix variant.

The player controls a line which is moving on an island. Player has possibility to leave the island in order to connect that island to itself. Once the connection is made, the new area formed by the connection becomes part of the island (see picture: red line is the path the snake has made while outside the island, dark red pixels are the area/island).

enter image description here

I am trying to find a algorithm (even bruteforce) how to fill the new area (in other words how to do transition between first and second line on the picture).

What I have in mind is to run a path finding algorithm between the enter/exit points. If there is a path, it means the snake connect the island to itself. The path (in green) and red line together forms a closed polygon which can then be filled (how ?)

enter image description here

As it is now, the data is simply defined a 2D array of pixels (eg : 0 = empty, 1 = island, 2 = player snake)

  • 1
    \$\begingroup\$ A simple flood fill algorithm will do the trick here. All you have to do is start at one of the inside pixels, and flood fill the rest. \$\endgroup\$ – jgallant Aug 25 '16 at 12:07
  • \$\begingroup\$ The problem is to find which side is the "inside". If you flood fill the wrong side you will fill the whole board. \$\endgroup\$ – tigrou Aug 25 '16 at 12:12

One way you could do this, is by performing multiple flood fills in a defined area. You could keep track of your Path's Max and Min X and Y positions, so that you can have a defined area to check. This would look something like this:

enter image description here

Then, process the black tiles inside of this area with a flood fill. If the floodfill at any point hits that Yellow border, then you know it is not going to be inside of your path. You can discard these tiles, and move on to the next Black tile.

If the flood fill never reaches that yellow border, than you know you are inside of the path, and you can fill it all in.

  • \$\begingroup\$ Thanks. I need to test this before flagging it as answer to make sure there is no a special case where it won't work. \$\endgroup\$ – tigrou Aug 25 '16 at 13:31

I think you should flood from the outside, start with the bounding box of your snake path and the island and then use the unmarked edge pixels as a seed to flood your "true" outside. Then you can mark the inverse as your island.

outside filling

The issue with flooding from the inside, is that you will have to keep track of which flooded pixel belong to which seed, since you have to be able to remove them when you hit the boundary.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.