• Products
  • Solutions
  • Made with Unity
  • Learning
  • Support & Services
  • Community
  • Asset Store
  • Get Unity

UNITY ACCOUNT

You need a Unity Account to shop in the Online and Asset Stores, participate in the Unity Community and manage your license portfolio. Login Create account
  • Blog
  • Forums
  • Answers
  • Evangelists
  • User Groups
  • Beta Program
  • Advisory Panel

Navigation

  • Home
  • Products
  • Solutions
  • Made with Unity
  • Learning
  • Support & Services
  • Community
    • Blog
    • Forums
    • Answers
    • Evangelists
    • User Groups
    • Beta Program
    • Advisory Panel

Unity account

You need a Unity Account to shop in the Online and Asset Stores, participate in the Unity Community and manage your license portfolio. Login Create account

Language

  • Chinese
  • Spanish
  • Japanese
  • Korean
  • Portuguese
  • Ask a question
  • Spaces
    • Default
    • Help Room
    • META
    • Moderators
    • Topics
    • Questions
    • Users
    • Badges
  • Home /
This post has been wikified, any user with enough reputation can edit it.
avatar image
0
Question by vik.vega · Apr 15, 2013 at 08:34 PM · proceduraltileflood

Flood Fill implementation for room tile detection

Hello everyone !

I have a procedurally generated dungeon with two kind of tiles, one for corridors, another one for rooms.

As I instantiate rooms (in the order shown in the image below, the little numbers on red blocks) I also populate an array with the corresponding gameobjects. I'm trying to detect which tiles belong to a room (where a room is a irregulary shaped set of adjacent tiles)

alt text

What i'm trying to accomplish, here, is having

room_control[0]={0,1,2,3,6}

room_control[1]={4,5}

room_control[2]={7,8,9,10}

room_control[3]={11}

And here's a snippet of the code i'm using to detect the rooms

 var temproom = new List.<GameObject>();
     var rooms_list = new List.<GameObject>();
     var last_unused_room:int=0;
      
     var rooms_container = new List.<List.<GameObject> >();
      
      
     function Start()
     {
      
     // At this point, the "rooms_list" List is populated with gameobjects, basically room tiles, and i want to detect all the adjacent of them, and group them into the "rooms_container" List of Lists :)
     room_detector();
      
     }
      
     function room_detector()
     {
             remaining_rooms=rooms_list.Count;
             room_null=false;
      
             for(var m = 0; m<rooms_list.Count;m++)
      
             {
                     temproom.Add(rooms_list[last_unused_room]);
                     rooms_list[last_unused_room].collider.enabled = false;
                     check_adjacent_rooms(rooms_list[last_unused_room]);
                    
                     if(room_null)
                     {
                     rooms_container.Add(copy_array(temproom));
                     remaining_rooms=(remaining_rooms-(temproom.Count-1));
                     last_unused_room=temproom.Count;
                     print("stanza fatta "+rooms_container.Count+" contiene "+(temproom.Count));
                                    
                     last_unused_room = m;
                     temproom.Clear();
                     room_null=false;
                     }
                     last_unused_room=temproom.Count;
                     last_unused_room = m+1;
                     temproom.Clear();
             }
      
     }
      
     function check_adjacent_rooms(segmenti:GameObject)
     {
                     var origin_ray = segmenti.transform.position + Vector3(0,2,0);
                     var hit : RaycastHit;
                    
                     for(var i=-1; i<2;i++)
                             {
                                     for(var j=-1; j<2;j++)
                                     {
                                     if (Physics.Raycast(origin_ray+Vector3(i,0,j), -Vector3.up, hit, 5))
                                             {
                                             if (hit.transform.name.Contains("stanza"))
                                                     {
                                                     Debug.DrawRay(origin_ray+Vector3(i,0,j), -Vector3.up*5,Color.green,10,false);
                                                     if((segmenti.transform.position.x - temproom[temproom.Count-1].transform.position.x) <2 ||(segmenti.transform.position.z - temproom[temproom.Count-1].transform.position.z) <2)
                                                             {
                                                                     hit.collider.enabled = false;
                                                                     temproom.Add(segmenti);
                                                                     room_null=true;
                                                                     check_adjacent_rooms(hit.collider.gameObject);
                                                             }
                                                             else
                                                             {
      
                                                             }
                                                     }
                                             else
                                                     {
                                                     Debug.DrawRay(origin_ray+Vector3(i,0,j), -Vector3.up*5,Color.red,10,false);
                                                     }
                                             }                      
                                     }
                             }
      
     }
      
      
      
      
     function OnGUI ()
     {
             for(var i=0;i<rooms_container.Count;i++)
             {
                     if(GUI.Button(new Rect(10,20+(i*30),100,25),"stanza "+i))
                     {
                             print(rooms_container[i].Count);
                             for(var j=0;j<rooms_container[i].Count;j++)
                             {
                                     rooms_container[i][j].renderer.material.color = Color.blue;
                                    
                                     for(var k = 0; k<rooms_container[i].Count;k++)
                                     {
     //                              select_children_blocks(rooms_container[i][k],Color.blue);
                                     }
      
                             }
                            
                     }
             }
                    
     }
      
     function copy_array(arraystanze:List.<GameObject>)
     {
             var blocchi = new List.<GameObject>();
                              
             for (var j=1; j <= arraystanze.Count-1; j++)
         {
            if(arraystanze[j] == arraystanze[j-1])
            {
               arraystanze.RemoveAt(j);
            }
         }
                              
                     for (var i = 0; i < arraystanze.Count; i++)
                     {
                     blocchi.Add(arraystanze[i]);
                     }
                     return blocchi;
     }


And i can't quite understand the results; the blue blocks, are the ones successfully pushed into the "List of List of gameobjects", the red aren't behaving as expected.

Thank you, it's really giving me a headache. alt text

**edit

I rewrote the script, breaking it into smaller steps, aiming, for now, just in detecting the first generated room (the one containing the room tile 0) the rest will come later on. results are sometimes perfect, some other times, sometimes it gets lost in a "branch" and completely ignores the rest of adjacent tiles, and often it throws a stack overflow, well known issue with this method, as i've been reading around.

 function room_detector()
 {
 reinit_colliders(temproom);                //reactivate colliders for all tiles of the room
 temproom.Clear();
 
 temproom.Add(room_tiles[0]);            //start with the first block of rooms
 flood(room_tiles[0],Vector3.zero);        
 print_rooms(temproom);                    //lists tiles belonging to the room
 }
 
 function flood(tile:GameObject,offset:Vector3)
 {
         var origin_ray = tile.transform.position+offset + Vector3(0,2,0);
         var hit : RaycastHit;
         
         if (Physics.Raycast(origin_ray, -Vector3.up, hit, 5))
             {
             if (hit.transform.name.Contains("ROOM_TILE")) 
                 {
                 Debug.DrawRay(origin_ray, -Vector3.up*5,Color.green,10,false);
                 var distance = Vector3.Distance(tile.transform.position,temproom[temproom.Count-1].transform.position);
     //            if((tile.transform.position.x - temproom[temproom.Count-1].transform.position.x) <2 ||(tile.transform.position.z - temproom[temproom.Count-1].transform.position.z) <2)
                 if (distance < 2)
                     {
                         if(hit.transform.gameObject!=temproom[temproom.Count-1])
                 {
                 temproom.Add(hit.transform.gameObject);
                 }
                 hit.collider.enabled = false;
                 }
                 flood(hit.transform.gameObject,Vector3(-1,0,0));
                 flood(hit.transform.gameObject,Vector3(1,0,0));
                 flood(hit.transform.gameObject,Vector3(0,0,-1));
                 flood(hit.transform.gameObject,Vector3(0,0,1));
                 }
             }
             else
             {
             return;
             }
 return;
 }


I'm not sure how possibly, if i disable colliders, get into a stack overflow because of the routine running over and over (we're talking about a 10x10 ish grid)

example1.jpg (22.3 kB)
tiles.jpg (30.4 kB)
Comment
Add comment
10 |3000 characters needed characters left characters exceeded
▼
  • Viewable by all users
  • Viewable by moderators
  • Viewable by moderators and the original poster
  • Advanced visibility
Viewable by all users

0 Replies

· Add your reply
  • Sort: 

Your answer

Hint: You can notify a user about this post by typing @username

Up to 2 attachments (including images) can be used with a maximum of 524.3 kB each and 1.0 MB total.

Welcome to Unity Answers

If you’re new to Unity Answers, please check our User Guide to help you navigate through our website and refer to our FAQ for more information.

Before posting, make sure to check out our Knowledge Base for commonly asked Unity questions.

Check our Moderator Guidelines if you’re a new moderator and want to work together in an effort to improve Unity Answers and support our users.

Follow this Question

Answers Answers and Comments

11 People are following this question.

avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image

Related Questions

Strange renderissues with tiled sprites 1 Answer

2D Tilebased Floodfill lightning 1 Answer

Procedural Texturing on Multiple Terrain Mesh 1 Answer

Lightmapping and Diablo3-style big-tile levels 1 Answer

Lightmapping and Diablo3-style big-tile levels 0 Answers


Enterprise
Social Q&A

Social
Subscribe on YouTube social-youtube Follow on LinkedIn social-linkedin Follow on Twitter social-twitter Follow on Facebook social-facebook Follow on Instagram social-instagram

Footer

  • Purchase
    • Products
    • Subscription
    • Asset Store
    • Unity Gear
    • Resellers
  • Education
    • Students
    • Educators
    • Certification
    • Learn
    • Center of Excellence
  • Download
    • Unity
    • Beta Program
  • Unity Labs
    • Labs
    • Publications
  • Resources
    • Learn platform
    • Community
    • Documentation
    • Unity QA
    • FAQ
    • Services Status
    • Connect
  • About Unity
    • About Us
    • Blog
    • Events
    • Careers
    • Contact
    • Press
    • Partners
    • Affiliates
    • Security
Copyright © 2020 Unity Technologies
  • Legal
  • Privacy Policy
  • Cookies
  • Do Not Sell My Personal Information
  • Cookies Settings
"Unity", Unity logos, and other Unity trademarks are trademarks or registered trademarks of Unity Technologies or its affiliates in the U.S. and elsewhere (more info here). Other names or brands are trademarks of their respective owners.
  • Anonymous
  • Sign in
  • Create
  • Ask a question
  • Spaces
  • Default
  • Help Room
  • META
  • Moderators
  • Explore
  • Topics
  • Questions
  • Users
  • Badges