Xonix polygons filling

Unity Engine
1

Hello everyone. Do you remember Xonix - a retro game with an interesting gameplay. I am trying to develop under Unity its clone, but I have a problem so as to fill polygons when the player progresses in the game “eating” a new zone. I have no clue how to achieve it. I tried some ScanLine methods, but it is not really good. Do you have an idea about the best way to do that ? No code - just an algorithm.

2

Ha! I played the crap out of XONIX… so good. Such a simple game, but so fun.

The two pieces of magic you need are:

  1. a floodfill routine

  2. some code to decide which “side” of your line to fill from.

All I can say for #1 is you have to iterate and get a floodfill going, depending on whatever grid system you’re using. Make a placeholder level to fill, an arbitrary shape, and debug that until it works perfectly: eg, click somewhere and fill.

For #2, the approach you want is to iterate along the new line you just finished making, and check each side of the line. As soon as you find a point on the line with both left and right open areas, use those two areas as your candidate fill spots.

Now that you have those two spots, you basically need to do “fake fills” to see which side has no free-floaty balls. This means you fill the area, but only to see if you touch a free-floaty ball, and if you do not, then you actually go back and fill it.

2 Likes
3

Well, I just moved my two flood fill methods to my TextureTools on github since the Unity wiki does no longer exist. I originally written it 10 years ago in a response to this question. There are two different methods. One would fill an area until it reaches a different color than the starting color. The other will fill until it hits a border color.

As for the game itself, you probably need to fill both sides to determine if an area contains an enemy or not. Because the original game only fills an area if it is actually empty. If both sides have enemies in them, nothing is filled and just the line you drew will stay.

So you may want / need to adapt the algorithm to work with logical cells that can also check for enemies. My implementation was specifically a texture extension. Though the overall logic is still the same.

1 Like
4

Thank you for your help friends. I forgot to say something - I am not using Unity for this project. @Bunny83 your code seems relevant, but I cannot integrate it in my C++ project. I will take a look at this function, and maybe I will convert it. @Kurt-Dekker Your first idea is very interesting, but there is a new question - how (and when) could I determine the point from which the filling process starts ? How may I be sure that I have a closed polygon ?

5

This forum really is specific to Unity (that could be C++ but in your case it is not Unity specific). General programming problems are out of scope. Try stack overflow.

6

Hi, i made my own approach by analizing whole field at once as following:

Codes in array:
0 = sea (what we need to fill)
1 = soil (what we filled)
2 = inner enemy ball
5 = player

if player has closed some shape then:

  1. put 0 to the enemy ball cells by each ball.x and ball.y

  2. make flood-fill algorithm (link below) from enemy balls positions (one by one) with “9” (flood-fill 0s with 9s). So only spaces where the balls are, filled now.

  3. invert it: fill all 0s with 1 and all 9s with zeros across whole field array.

  4. put back 2s to enemy ball cells.

Benefit of it is that even you have 1000 balls in one area, code will fill only one time that area. The rest of 99 times it will not fill as its already filled.

PS don’t use recursive flood-fill algorithm, use BFS instead from here: