Oct
10
2012

Flood Fill Algorithm

An article by mgear

Converted this c# flood fill algorithm to unityscript.

Using list, instead of that queue thing and modified it to work with grid array, instead of bitmap colors..
Bit too slow, if I want to try big grid.. maybe 4096×4096. (wont be using setpixel on that, just grid checking..)

Version 1:
– Fill 1024×1024 area : 2.2secs (with setpixel), 1.99secs (without setpixel)

Version 2 (from this c# script: RevisedQueueFloodFill)
– Fill 1024×1024 area : 1.8secs = 1800ms (with setpixel), 1.69secs = 1690ms (without setpixel)

Version 3 (from this vb.net script: UnsafeFloodFill)
– Fill 1024×1024 area : 1.43secs = 1430ms (with setpixel), 1.26secs = 1260ms (without setpixel)

Version 3b (same as above, but using preset 1x border around the grid and fill starts from fixed position in the corner..)
– Fill 1024×1024 area : 1.21secs = 1210ms (with setpixel), 0.97secs = 970ms (without setpixel)

Version 4 (calling the c# in javascript – code by alexzzzz *see comments section 12/10/2012 at 19:24 )
– Fill 1024×1024 area :0.158secs = 158ms (with setpixel), 0.08secs = 18ms (without setpixel)
What I want to test with it:
– Big grid map (for example 4096×4096
– Player can insert walls to map (except map borders)
– Need to determinate which areas are blocked by the walls
– Similar to rampart (youtube video)

Webplayer: (v1)
http://unitycoder.com/upload/demos/FloodFill_algorithm_unity/ (64×64 image)

Download source:
coming later..

Source: v3 (needs a prefilled grid with borders..)

function UnsafeFloodFill3(x:int,y:int)
{
var ptsx:List.<int> = new List.<int>();
ptsx.Add(x);
var ptsy:List.<int> = new List.<int>();
ptsy.Add(y);

while (ptsx.Count > 0)
{
if (grid[ptsx[0]-1,ptsy[0]]==0)
{
ptsx.Add(ptsx[0]-1); ptsy.Add(ptsy[0]);grid[ptsx[0]-1,ptsy[0]]=1;
}
if (grid[ptsx[0],ptsy[0]-1]==0)
{
ptsx.Add(ptsx[0]);ptsy.Add(ptsy[0]-1);grid[ptsx[0],ptsy[0]-1]=1;
}
if (grid[ptsx[0]+1,ptsy[0]]==0)
{
ptsx.Add(ptsx[0]+1); ptsy.Add(ptsy[0]);grid[ptsx[0]+1,ptsy[0]]=1;
}
if (grid[ptsx[0],ptsy[0]+1]==0)
{
ptsx.Add(ptsx[0]); ptsy.Add(ptsy[0]+1);grid[ptsx[0],ptsy[0]+1]=1;
}
ptsx.RemoveAt(0);
ptsy.RemoveAt(0);
}
}

Tags: algorithm, flood fill, paint, pixels

About the Author:

.fi

19 Comments + Add Comment

alexzzzz 10/10/2012 at 21:51

The source code from wiki is too overcomplicated. Here is mine that work with grid of integers:
http://pastebin.com/ng8EmpgX

~28ms for 1024×1024 array on my machine.

Reply
alexzzzz 12/10/2012 at 00:35

I guess, RemoveAt(0) takes 90% of the execution time.

Since the order of list items is not very important, it’s better to change it into
list[0] = list[list.Count – 1];
list.RemoveAt(list.Count – 1];

Here is my final source: http://pastebin.com/nYjM7Ana
~19ms on 1024×1024
~265ms on 4096×4096

Right now I have no ideas how to make it faster.

Reply
- mgear 03/08/2014 at 03:17
  
  yes, just tested with Queue(), instead of List(), the “source v3” is then ~10 times faster.
  
  Reply
alexzzzz 12/10/2012 at 01:30

~12ms on 1024×1024
~206ms on 4096×4096

http://pastebin.com/TGj5gq7A

Reply
alexzzzz 12/10/2012 at 19:24

~6ms on 1024×1024
~140ms on 4096×4096

http://pastebin.com/KHD8axSL

—
FastQueue class from the last post has an error, here is the correct one: http://pastebin.com/GFPQ5nuN

Reply
- mgear 12/10/2012 at 22:42
  
  Amazing! Case closed 🙂
  
  Reply
- mgear 15/10/2012 at 01:49
  
  If modify it to use bool[] map, it seems to get marginally faster (on even larger grids >8192).
  
  Reply
alexzzzz 26/02/2013 at 23:16

http://pastebin.com/C6Dpsj6g

10ms faster than the previous version on 4096×4096, but even less readable.

Reply
- mgear 27/02/2013 at 12:42
  
  🙂
  
  Other ideas that could be tested,
  
  – Can agree that all the borders are already blocked by 1pixel line, then no need to do boundary checking?
  – Threaded?
  – Using GPU/Compute shaders..?
  – ..
  
  Reply
  - alexzzzz 01/03/2013 at 00:44
    
    Using 1 pixel border:
    
    ~5ms on 1024×1024
    ~118ms on 4096×4096
    
    http://pastebin.com/mCg8wq1J
    
    Reply
    - mgear 01/03/2013 at 10:27
      
      Would be interesting to test this scanline floodfill also (less grid testing?)
      http://will.thimbleby.net/scanline-flood-fill/
      
      Reply
mgear 24/03/2013 at 14:54

Some interesting link (related to optimisations)
Square root calculation speed in Flash and Unity3D
http://blog.alladvanced.net/2011/02/21/square-root-calculation-speed-in-flash-and-unity3d/

Reply
Valomo 13/11/2013 at 10:53

sorry, when can you get sourceCode?

Reply
- mgear 13/11/2013 at 12:04
  
  use those floodfill sources from alexzzzz, they are much faster.
  
  Reply
mgear 13/06/2014 at 21:04

Bitmap Drawing API (free)
http://forum.unity3d.com/threads/bitmap-drawing-api-for-textures.251557/

Reply
- ProtoTurtle 14/06/2014 at 00:00
  
  Thanks for posting about it! I used one of alexzzzz’s flood fill algorithm examples as a base but found the big bottleneck to be comparing Color instances instead of ints or booleans. It makes it very slow, but I couldn’t think of a way to go around since I would still need to convert the ints to Colors to push the bitmap array back to the texture. Any ideas on how one of the fast algorithms would work with a array of Colors that the texture2d.GetPixels() provides?
  
  Reply
  - mgear 14/06/2014 at 03:26
    
    Would Color32 work better?
    
    Or if want to make it super-amazing fast (including the time for texture.Apply()), should use LoadRawTextureData().
    
    Reply
    - ProtoTurtle 14/06/2014 at 06:23
      
      Switching to Color32 didn’t make much of a difference, it uses bytes but I guess it still has to do 4 comparisons (1 byte for r, g, b and a) instead of 1 for just an array of integers. LoadRawTextureData looks promising since I was thinking of having a buffer that would get copied only when you all Apply(). Unfortunately it’s undocumented so it’ll be a bit difficult but I think it looks like the best way to go.
      
      Reply
mgear 16/03/2021 at 13:34

Jump Flood Fill (with shader)
https://bgolus.medium.com/the-quest-for-very-wide-outlines-ba82ed442cd9

Reply