I have an integer array (N x N)… the contents are loaded from a datafile (encrypted).
Once it is loaded, I need to change any exterior cells that are Zero to -1, and as quickly as possile
example
0000000
0088800
0080080
0080800
0008000
would become
.......
..888..
..8008.
..808..
...8...
where “.” is the -1 value
I think it would need to take four passes
with each pass stopping when it hits a non-zero value
any other ideas?
Add zero padding and do flood-fill from there?
flood fill requires a known “safe” starting place…not all arrays need to have this done
Instead of doing four passes, you could start at every zero on the outer edge of the grid and spread inward from each one, marking zeros as you go. You’d stop spreading whenever you hit a non-zero number. This spreading technique would give the same result as your four-pass method, but your way is probably faster for most grids.
right, that misses any the are bounded by a odd shape… I don’t think there is a way to do it in one pass, Flood Fill is a good idea, except there could be multple “areas” . Take this for example
0008000
0008000
8888888
0008000
0008000
All the zeros need to be removed,
If you start left-to-right (at the top-left corner), won’t that mess up the top-to-bottom later by having filled the first row?
Also, if you don’t do some sort of flood fill, how do you get elements in a “bay” like this?
0000000
0088800
0080800
0000800
0008000
To manage all of these kinds of cases, I think you need to floodfill from the points around the perimeter. I’m going to guess that starting with the corners is most efficient, and then just test the other edge bits from there. You may even be able to be more efficient if you implement your own floodfill so you can memoize places where you hit a nonzero on any of the edges as you fill them – you only need to test inside of those bounds (-1 in both directions, of course), and you could just repeat this until the bounds converge (in case you had a pathological edge like 0808080)
That’s why I proposed adding “invisible” extra border of zeroes around the grid map when reading in the grid map data (or use a border of eights and zeroes, so you don’t need to separately check outer edges of border limits when doing a flood fill) and starting a flood fill from the border.
Because floodfill is recursive, you’re basically just guaranteeing the first recursion. This makes it simpler to implement since you don’t need to walk the border in your own code, at some space cost. I’m not immediately sure if there is a significant difference in actual operations one way or the other; it might depend on N.
I totally understand how floodfill works, but it requires that the first point be in that area that needs to be filled. in my previous example there are FOUR such areas that each need to be “filled” indepentdly. and it is possible that NO cells need to be altered.. as in
888888
800008
800008
800008
888888
Array grid could be transformed into a graph by building node list and adding edges between neighboring nodes that contain value zero. One extra node could be added and edges could be added between nodes located at the grid borders that contain value zero. Extra node could be selected as starting point and graph could be traversed marking visited nodes. After that all the values of visited nodes can be changed to -1.
but it requires that the first point be in that area that needs to be filled
Maybe? I imagine if you try to floodfill starting at a solid point, it just returns without effect.
In my solution, either test each point on the perimeter first or, assuming I’m right about it just returning, just apply it at each point as described. In Jalih’s solution, you add a perimeter layer to guarantee the first point needs to be filled and that the floodfill itself walks the perimeter (which is now +1 in each direction, so easier to implement, but maybe a little more expensive?)
just make flood-fill from the border one time around your grid.
maybe In an optimized version, with full lines/columns already marked as done
Ok. that will NOT work, as I would have to examine every border cell first to even find a “starting place”, and then there could be multiple areas (see the example I posted above), it would require FOUR different floods.
I will go with my first approach, thanks to everyone who tried
Convex hull algorithm?
// Edge Detection
//
for y in(0...mazeSIZE-1) {
// Left to Right
for x in(0...mazeSIZE-1) {
if mainLevel[y,x] != nil && mainLevel[y,x]!.tileID != .floor { break }
mainLevel[y,x] = nil
}// Right to Left
for x in(0...mazeSIZE-1).reversed() {
if mainLevel[y,x] != nil && mainLevel[y,x]!.tileID != .floor { break }
mainLevel[y,x] = nil
}
}
for x in(0...mazeSIZE-1) {
// Top to Bottom
for y in(0...mazeSIZE-1) {
if mainLevel[y,x] != nil && mainLevel[y,x]!.tileID != .floor { break }
mainLevel[y,x] = nil
}// Bottom to Top
for y in(0...mazeSIZE-1).reversed() {
if mainLevel[y,x] != nil && mainLevel[y,x]!.tileID != .floor { break }
mainLevel[y,x] = nil
}
}
Thanks
Not true, the solution I presented guarantees any border cell from the extra cell padding around the grid can be used as a starting point and only one flood fill is required.
Altering the structure of the array is not an option… but thanks… the above solution works perfectly and takes a fraction of a second to run
I think the suggest @jalih made is to turn
888888
800008
800008
800008
888888
into
00000000
08888880
08000080
08000080
08000080
08888880
00000000
so you can ALWAYs start at the top left, then trim out the stuff you added
In this case you’d flood fill and nothing in the interior would be filled because its not reachable
Your other example
0008000
0008000
8888888
0008000
0008000
would turn into
000000000
000080000
000080000
088888880
000080000
000080000
000000000
And the flood fill would fill all the four areas
I understand what he suggested… but as I said. altering the array is not an option
clone it ?
doesnt have to be done “in place”
but since you have a solution the point is moot
Looking at your code its an 2rowscolumns # of passes since you have to check each column from left to right top to bottom & bottom to top
Quite literally “exhaustive search”