{"id":1186,"date":"2012-10-10T18:48:47","date_gmt":"2012-10-10T15:48:47","guid":{"rendered":"http:\/\/unitycoder.com\/blog\/?p=1186"},"modified":"2012-10-12T22:42:45","modified_gmt":"2012-10-12T19:42:45","slug":"flood-fill-algorithm","status":"publish","type":"post","link":"https:\/\/unitycoder.com\/blog\/2012\/10\/10\/flood-fill-algorithm\/","title":{"rendered":"Flood Fill Algorithm"},"content":{"rendered":"

\"\"<\/a><\/p>\n

Converted this c# flood fill algorithm<\/a> to unityscript.<\/p>\n

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

Version 1<\/strong>:
\n– Fill 1024×1024 area : 2.2secs (with setpixel), 1.99secs (without setpixel)<\/p>\n

Version 2<\/strong>\u00a0 (from this c# script<\/a>: RevisedQueueFloodFill)<\/strong>
\n– Fill 1024×1024 area : 1.8secs = 1800ms (with setpixel), 1.69secs = 1690ms (without setpixel)<\/p>\n

Version 3<\/strong>\u00a0 (from this vb.net script<\/a>: UnsafeFloodFill)<\/strong>
\n– Fill 1024×1024 area : 1.43secs = 1430ms (with setpixel), 1.26secs = 1260ms (without setpixel)<\/p>\n

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

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

Webplayer: (v1)<\/strong>
\nhttp:\/\/unitycoder.com\/upload\/demos\/FloodFill_algorithm_unity\/<\/a> (64×64 image)<\/p>\n

Download source:<\/strong>
\ncoming later..<\/p>\n

Source:<\/strong> v3 (needs a prefilled grid with borders..)<\/p>\n

\r\nfunction UnsafeFloodFill3(x:int,y:int)\r\n{\r\nvar ptsx:List.<int> = new List.<int>();\r\nptsx.Add(x);\r\nvar ptsy:List.<int> = new List.<int>();\r\nptsy.Add(y);\r\n\r\nwhile (ptsx.Count > 0)\r\n{\r\nif (grid[ptsx[0]-1,ptsy[0]]==0)\r\n{\r\nptsx.Add(ptsx[0]-1); ptsy.Add(ptsy[0]);grid[ptsx[0]-1,ptsy[0]]=1;\r\n}\r\nif (grid[ptsx[0],ptsy[0]-1]==0)\r\n{\r\nptsx.Add(ptsx[0]);ptsy.Add(ptsy[0]-1);grid[ptsx[0],ptsy[0]-1]=1;\r\n}\r\nif (grid[ptsx[0]+1,ptsy[0]]==0)\r\n{\r\nptsx.Add(ptsx[0]+1); ptsy.Add(ptsy[0]);grid[ptsx[0]+1,ptsy[0]]=1;\r\n}\r\nif (grid[ptsx[0],ptsy[0]+1]==0)\r\n{\r\nptsx.Add(ptsx[0]); ptsy.Add(ptsy[0]+1);grid[ptsx[0],ptsy[0]+1]=1;\r\n}\r\nptsx.RemoveAt(0);\r\nptsy.RemoveAt(0);\r\n}\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
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, […]<\/p>\n","protected":false},"author":1,"featured_media":1187,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[4,3],"tags":[93,324,34,325],"class_list":["post-1186","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-demos","category-unity3d","tag-algorithm","tag-flood-fill","tag-paint","tag-pixels"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"https:\/\/i0.wp.com\/unitycoder.com\/blog\/wp-content\/uploads\/2012\/10\/flood_fill_algorithm_unity.jpg?fit=680%2C508&ssl=1","jetpack_shortlink":"https:\/\/wp.me\/p1KTaT-j8","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/unitycoder.com\/blog\/wp-json\/wp\/v2\/posts\/1186","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/unitycoder.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/unitycoder.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/unitycoder.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/unitycoder.com\/blog\/wp-json\/wp\/v2\/comments?post=1186"}],"version-history":[{"count":19,"href":"https:\/\/unitycoder.com\/blog\/wp-json\/wp\/v2\/posts\/1186\/revisions"}],"predecessor-version":[{"id":1209,"href":"https:\/\/unitycoder.com\/blog\/wp-json\/wp\/v2\/posts\/1186\/revisions\/1209"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/unitycoder.com\/blog\/wp-json\/wp\/v2\/media\/1187"}],"wp:attachment":[{"href":"https:\/\/unitycoder.com\/blog\/wp-json\/wp\/v2\/media?parent=1186"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/unitycoder.com\/blog\/wp-json\/wp\/v2\/categories?post=1186"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/unitycoder.com\/blog\/wp-json\/wp\/v2\/tags?post=1186"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}