10
2012
Flood Fill Algorithm
An article by 
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);
}
}
Related Posts
19 Comments + Add Comment
Leave a comment
Recent posts
- Use TikTok-TTS in Unity (with WebRequest)
- Create Scene Thumbnail Image using OnSceneSaved & OnPreviewGUI
- webgl+javascript TTS
- Using Moonsharp (LUA) + Unity Webgl
- Using 3D gameobject prefabs with Unity Tilemap + NavMesh Surface
- Custom Unity Hub Project Template Preview Image/Video (using HTML+CSS in package description)
- Check if point is inside polygon 2D (using line intersection)
- UnityHub: Enable Create Project Button (without having to select Cloud Organization)
- UI: Make Tooltip background fit Text content length
- Pong-Wars in Unity
- Install Android SDK+JDK+NDK for Unity (without AndroidStudio or Unity Hub)
- UnityHub: Add support for custom project title (instead of folder name) or use ProductName
Connect
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.
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.
yes, just tested with Queue(), instead of List(), the “source v3” is then ~10 times faster.
~12ms on 1024×1024
~206ms on 4096×4096
http://pastebin.com/TGj5gq7A
~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
Amazing! Case closed 🙂
If modify it to use bool[] map, it seems to get marginally faster (on even larger grids >8192).
http://pastebin.com/C6Dpsj6g
10ms faster than the previous version on 4096×4096, but even less readable.
🙂
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..?
– ..
Using 1 pixel border:
~5ms on 1024×1024
~118ms on 4096×4096
http://pastebin.com/mCg8wq1J
Would be interesting to test this scanline floodfill also (less grid testing?)
http://will.thimbleby.net/scanline-flood-fill/
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/
sorry, when can you get sourceCode?
use those floodfill sources from alexzzzz, they are much faster.
Bitmap Drawing API (free)
http://forum.unity3d.com/threads/bitmap-drawing-api-for-textures.251557/
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?
Would Color32 work better?
Or if want to make it super-amazing fast (including the time for texture.Apply()), should use LoadRawTextureData().
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.
Jump Flood Fill (with shader)
https://bgolus.medium.com/the-quest-for-very-wide-outlines-ba82ed442cd9