GML [SOLVED] Flood Fill A DS Grid To Create Rooms

P

Poddington

Guest
Hi Everyone,

I'm having a bit of a coders block at the moment and I'm not sure even how to approach this. I have a game where I can create walls using a mixture of a DS grid and tiles. Tiles aren't important, but with the DS grid if I have a region that is surrounded by walls I'd like the area within the walls to be "indoors".

I could make the player assign indoors and outdoors, but I foresee this being exploited as if it's a zoned area they could zone the whole map to remove any outdoors.

Also the walls aren't placed all at once, but can be drawn either one block at a time or a whole section and also if a wall section is removed the room should become outdoors. I guess there will need to be a recurring check to do this.

the grid would look like this.

[1][1][1][1][1]
[1][0][0][0][1]
[1][0][0][0][1]
[1][0][0][0][1]
[1][1][1][1][1]

Any suggestions to attempt would be appreciated, I'll also mark as solved if I figure out a solution. The term flood fill may not be correct, but it's all I could think of at time of posting.

Thanks for your help.
 
P

Poddington

Guest
Hmm, perhaps instead of working out what is inside I instead look for what is outside and everything else must then be inside. Got an idea, but please comment if you have any advice. Thanks.
 
Last edited by a moderator:
P

Poddington

Guest
Ok so I did a quick attempt and solving this and I've added it below. It only runs the check if a section of wall is created or destroyed as it doesn't need to run constantly, so I haven't noticed much change in the average FPS (over 500). I'm happy that it works so I thought I'd post below. I know this thread is me talking to myself right now, but if any one more experienced can check it for me, give suggestions on a better solution etc I'd appreciate it. I'll mark this solved though :D

Code:
///inside_check();

ds_grid_clear(outdoor_grid, INDOOR);       

//first cell is a border so will always be outside
outdoor_grid[# 0,0] = OUTDOOR;

var outdoor_check = 0;

for (i = 0; i < width; i += 1)
    {
    for (j = 0; j < height; j += 1)
        {
        //check grid if location is outside
        outdoor_check = ds_grid_get(outdoor_grid,i,j);
        //check surrounding cells of grid to see if they are outside and if so change to outdoor
        //as check goes from left to right and up to down, if a cell above or left is changed to outdoor we go back a step in that direction
        if(outdoor_check = OUTDOOR)
            {
            if(i+1 < width)
                {
                if(object_grid[# i+1,j] = FLOOR or object_grid[# i+1,j] = BORDER)
                    {
                    outdoor_grid[# i+1,j] = OUTDOOR;
                    }
                }
            if(i-1 > 0)
                {
                if(object_grid[# i-1,j] = FLOOR or object_grid[# i-1,j] = BORDER)
                    {
                    if(outdoor_grid[# i-1,j] != OUTDOOR)
                        {
                        outdoor_grid[# i-1,j] = OUTDOOR;
                        i -= 2;
                        }
                    }
                }
            if(j+1 < height)
                {
                if(object_grid[# i,j+1] = FLOOR or object_grid[# i,j+1] = BORDER)
                    {
                    outdoor_grid[# i,j+1] = OUTDOOR;
                    }
                }
            if(j-1 > 0)
                {
                if(object_grid[# i,j-1] = FLOOR or object_grid[# i,j-1] = BORDER)
                    {
                    if(outdoor_grid[# i,j-1] != OUTDOOR)
                        {
                        outdoor_grid[# i,j-1] = OUTDOOR;
                        j -= 2;
                        }
                    }
                }
            }
        }
    }
 
P

Poddington

Guest
Hello again,

So I was really happy with how this turned out and wanted to post some shots to show how it looks. I'm drawing the grid, so my FPS has taken a hit, but as you can see in the example below the walls are tinted red and ground is green. Hope this thread can help others.

room1.png

Now that the room is completely enclosed you can see that internally all cells are tinted red and outside is green. Outside says 101 still, but it's because my mouse cursor was outside when I took the shot.

room3.png

Removing a wall section on the right and now everything is back to being outside as no sections are enclosed.

room4.png

And just to show what the FPS is like when it runs normally, I'll stop drawing the grid.

room5.png

This is also only 2 instances. The extra 3 are the buttons at the bottom to turn on and off debug options such as drawing grids, which are destroyed when I turn off the debug menu.
 
Top