# Identifying patterns of object positions in a grid - solved, works as intended

#### MagnumVulcanos

##### Member
Works now, here's a look:

Thank you all for your help!
As you can see this thing ignores walls, (but can still mark them if needed) and will take any floors, to be later added onto an array or flagged or whatever. and it does nothing if it finds an empty space in there, such as a wall being missing, or an empty tile. In this case, it counted 12 tiles.

/-------------------------------------------------/
The situation is as follows, I have a few square walls, all of which have par_wall as a parent, same for par_floor.
Both the walls and floor have a width that doesn't change, neither can move, they are always the same distance apart.
There are no floors and walls occupying the same place, meaning that if a collision was detected, it would never be with both.
Doors or windows are irrelevant, they are walls, items within the walls don't matter when detecting the "room".

Whenever I create a wall, I want to detect the pattern in which the floors and walls have been created.
I believe that this may not be too difficult when creating square rooms, but I want to give the player the capacity to create any shape of room they want.

To be specific, I want to detect a room, meaning a specific pattern of objects arranged with a floor surrounded with walls on all sides, external corners are irrelevant.

I don't know where to begin, but the ideal result would be a list with all the items that a room is compromised of, or at the very least a less elegant object (probably laggier) would be for every object to determine what room it's a part of?

TL;DR: given the objects floor and wall, detect if tehres an amount of floors with no holes in the middle surrounded 100% by walls, how would I detect and get all of those items within a list?

Last edited:

#### NightFrost

##### Member
I'd probably go with a floor fill algorithm to figure where the enclosed spaces are (that is, surrounded by wall pieces), repeat until all squares have been detected as inside, outside or wall. You just have to guess where in the room to start flood filling, because you don't know what areas are enclosed. If you knew, you'd already know where the rooms are and wouldn't need to flood fill to figure them out.

The flood fill basically has two end results once you've exhausted all the grid positions it can expand into: if none of the positions touch room edges, it is an enclosed space; if any touches room edges, it is not an enclosed space. Floor tiling pieces are just fluff and don't enter the equation, unless you want to specify that areas inside walled regions that do not have floor tiling do not count as part of the room.

#### MagnumVulcanos

##### Member
I'd probably go with a floor fill algorithm to figure where the enclosed spaces are (that is, surrounded by wall pieces), repeat until all squares have been detected as inside, outside or wall. You just have to guess where in the room to start flood filling, because you don't know what areas are enclosed. If you knew, you'd already know where the rooms are and wouldn't need to flood fill to figure them out.

The flood fill basically has two end results once you've exhausted all the grid positions it can expand into: if none of the positions touch room edges, it is an enclosed space; if any touches room edges, it is not an enclosed space. Floor tiling pieces are just fluff and don't enter the equation, unless you want to specify that areas inside walled regions that do not have floor tiling do not count as part of the room.
That's a pretty good response. is there any better way than filling the whole place?
Secondly how would you go about doing that on a technical side? would it be an object "roomchecker" which moves in increments?

#### NightFrost

##### Member
Flood filling is probably the fastest and best method, since it ensures every grid spot is checked once, and is checked only once. (It is best to view your layout as a grid since you said every wall and floor tile conforms to standard size.) The technical side is bit complex I'm afraid (and uses the same base methodology as pathfinder algos).

You need three ds lists, the closed list, the open list and the enclosure list. Start by opening a while loop and pick a random grid spot in the room. If the spot is in the closed list, pick again. If there is a wall in the picked spot, add it to closed list and check if the length of the closed list equals grid size - if so, break the while loop since whole room has now been checked. Do until you get an open grid spot (has floor piece or not, doesn't matter) and add it to the open list. This is done to avoid starting on wall spots, so you don't potentially flood fill from there into two distinct regions separated by it.

Next, you open a second while loop that you tell to run until the length of the open list is zero. Inside the loop, fist pick (and remove) a grid cell from the open list. The rest of the loop's innards is an if-brancher. If the grid cell contains a wall, add it to the closed list and done. Else, it is an open grid cell so add it to the closed list and then go through its eight neighbours; if the neighbour is not already in the closed list, add it to the open list. While going through these neighbours, also check if you are pointing outside the room. If so, don't actually add it to the open list but set a flag that tells you the region is touching room edge so it is an open region. Don't break the while loop at this point because you still need to find out which grid cell positions belong to this open region. Finally, since you want to know which grid cells constitute a region, add the open grid cell to the enclosure list. This ends the while loop.

After the second while loop has ran, the closed list contains every grid position you have checked so far, the open list is empty again, and the enclosure list contains every grid position that could be reached from the starting position you picked. The flag tells you if it is an open or closed region, and you can save the list elsewhere to preserve knowledge of the extent of the region. Now, clear the flag if it was set and empty the enclosure list. Do not empty the closed list as it is your master list of every grid position that has been checked so far. Close the first while loop here by telling it to run until the length of the closed list equals the number of grid cells in the room.

To wrap things up, destroy the three ds lists you created since you don't need them anymore. Now you have a list of walled regions in whatever place you saved the enclosure list's contents after the second loop.

I haven't tried this out but it should work more or less as described as it uses the same "check every grid position once" as A-star and Dijkstra pathfinding, except it runs until every grid position has been checked instead of ending when pathfinding goal has been found. Potentially this code could be made more effective by creating a fourth ds list, the unchecked list, which at start contains a list of every grid position. When you need to pick a new flood fill start position it is picked from this list instead of randomizing so you don't waste time picking grid positions that have already been checked. In every instance where you add a grid position to closed list you also remove it from unchecked list so it only contains positions not already processed.

#### MagnumVulcanos

##### Member
Flood filling is probably the fastest and best method, since it ensures every grid spot is checked once, and is checked only once. (It is best to view your layout as a grid since you said every wall and floor tile conforms to standard size.) The technical side is bit complex I'm afraid (and uses the same base methodology as pathfinder algos).

You need three ds lists, the closed list, the open list and the enclosure list. Start by opening a while loop and pick a random grid spot in the room. If the spot is in the closed list, pick again. If there is a wall in the picked spot, add it to closed list and check if the length of the closed list equals grid size - if so, break the while loop since whole room has now been checked. Do until you get an open grid spot (has floor piece or not, doesn't matter) and add it to the open list. This is done to avoid starting on wall spots, so you don't potentially flood fill from there into two distinct regions separated by it.

Next, you open a second while loop that you tell to run until the length of the open list is zero. Inside the loop, fist pick (and remove) a grid cell from the open list. The rest of the loop's innards is an if-brancher. If the grid cell contains a wall, add it to the closed list and done. Else, it is an open grid cell so add it to the closed list and then go through its eight neighbours; if the neighbour is not already in the closed list, add it to the open list. While going through these neighbours, also check if you are pointing outside the room. If so, don't actually add it to the open list but set a flag that tells you the region is touching room edge so it is an open region. Don't break the while loop at this point because you still need to find out which grid cell positions belong to this open region. Finally, since you want to know which grid cells constitute a region, add the open grid cell to the enclosure list. This ends the while loop.

After the second while loop has ran, the closed list contains every grid position you have checked so far, the open list is empty again, and the enclosure list contains every grid position that could be reached from the starting position you picked. The flag tells you if it is an open or closed region, and you can save the list elsewhere to preserve knowledge of the extent of the region. Now, clear the flag if it was set and empty the enclosure list. Do not empty the closed list as it is your master list of every grid position that has been checked so far. Close the first while loop here by telling it to run until the length of the closed list equals the number of grid cells in the room.

To wrap things up, destroy the three ds lists you created since you don't need them anymore. Now you have a list of walled regions in whatever place you saved the enclosure list's contents after the second loop.

I haven't tried this out but it should work more or less as described as it uses the same "check every grid position once" as A-star and Dijkstra pathfinding, except it runs until every grid position has been checked instead of ending when pathfinding goal has been found. Potentially this code could be made more effective by creating a fourth ds list, the unchecked list, which at start contains a list of every grid position. When you need to pick a new flood fill start position it is picked from this list instead of randomizing so you don't waste time picking grid positions that have already been checked. In every instance where you add a grid position to closed list you also remove it from unchecked list so it only contains positions not already processed.
Well damn that's pretty complicated, I'll make myself a diagram and try to make the code you're talking about since it's pretty complicated as far as I'm reading it, but thanks ofr the extensive explanation, This helps a lot

#### stainedofmind

##### Member
hen you need to pick a new flood fill start position it is picked from this list instead of randomizing so you don't waste time picking grid positions that have already been checked.
A list of unchecked cells is a good idea. I've coded a script before to check for closed spaces, and I just looped through the grid, skipping checked cells, until it reached the end. Not entirely sure which would be more effective. Seems like either way, you'd have to loop through the entire grid once.

#### NightFrost

##### Member
Yeah, one way or another, the whole region needs to be checked in order to gain a complete picture of what belongs where. Flood fill-style iteration over grid positions should be amongst more optimal approaches as it ensures each is checked only once. There of course might be clever algorithmic approaches out there that handle it even faster.

One way to simplify the code a little is to understand that you can give the position as a single number instead of an x/y pair, meaning you can handle 2d region data as 1d array. Any grid position equals y * grid_width + x. So on a 10 tile wide grid position 24 equals 2 * 10 + 4 (remember, row and column coordinates start from zero). Neighbouring grid positions can be found by adding or substracting combinations of width and one, but mind the grid edges. Conversely, position can be split into coordinates by y = position div width and x = position mod width.

#### MagnumVulcanos

##### Member
Thanks for your help, the "enclosure checker" is done, at least as far as the surface goes, I have some stuff to change still, but the thing works like a charm and should do what I need. I ended up using the tiles as references, and didn't realize that I could just cancel the loo at any time IF it found anything that wasn't a floor or a wall thing.
My game will treat doors as walls for the sake of rooms, so the thing is I don't need to make sure everything is surrounded by walls...
Rather I just need to check whether one of the possible "checking places" not to be a wall or floor.
In short, the thing works in practice.