12 Jan, 2009, Chris Bailey wrote in the 1st comment:
Votes: 0
Ok, so I wrote a little recursive flood fill algorithm to fill in areas of my overland map. The idea is that it runs out in each direction until it encounters a border of the same sector it is filling with. Most of the time it works wonderfully, but every now and then it leaves a randomly shaped and sized patch untouched. I'm not able to actually recreate this, it seems pretty random. Not being able to intentionally "cause" it to happen is making it a difficult bug to trace. Here is the basic layout.

@rooms is a 2d array of variable size that contains instances of a "field" object. The field object has a variable "sector" that is just a symbol representing a type of terrain, like :grass, :dirt, etc. Any ideas?

EDIT: I forgot to mention, @width is the width of the @rooms array, and @height is it's height, incase it wasn't very obvious.
The flood_fill method

def flood_fill(x,y,fill_sector)
@rooms[x][y].sector = fill_sector
if (y + 1) <= (@width -1)
if @rooms[x][y+1].sector != fill_sector
y += 1
flood_fill(x,y,fill_sector)
end
end
if (y - 1) >= 0
if @rooms[x][y-1].sector != fill_sector
y -= 1
flood_fill(x,y,fill_sector)
end
end
if (x + 1) <= (@height - 1)
if @rooms[x+1][y].sector != fill_sector
x += 1
flood_fill(x,y,fill_sector)
end
end
if (x - 1) >= 0
if @rooms[x-1][y].sector != fill_sector
x -= 1
flood_fill(x,y,fill_sector)
end
end
end
12 Jan, 2009, Davion wrote in the 2nd comment:
Votes: 0
I don't know Ruby at all, so I'm going out on a limb here :S. You may want to preserve the values of x and y. It looks to me that in the first case you increment y, then continue. The next check is for y again (which could be y+1 from when the function started) so it'd be like a step back. Just remove the "* += 1" and "* -= 1" and then in the flood_fill() call pass off x/y as an incremented value (eg. flood_fill(x+1, y, fill_sector) )
12 Jan, 2009, Chris Bailey wrote in the 3rd comment:
Votes: 0
But if I remove the increment from the x and y values, it will always be passed as original plus/minus 1. You mean put the increment itself inside the method call? Like (recursive call) flood_fill(x+=1,y,fill_sector) ?
12 Jan, 2009, Davion wrote in the 4th comment:
Votes: 0
Chris Bailey said:
But if I remove the increment from the x and y values, it will always be passed as original plus/minus 1. You mean put the increment itself inside the method call? Like (recursive call) flood_fill(x+=1,y,fill_sector) ?


I don't think so… that still modifies the value of x so all the other uses of it below that will be using the new value. Doesn't something like this
flood_fill(x+1, y, fill_sector)

alter the value of X (incrementing by one) for the next recursive call and leave the original value preserved in current scope of the function? What I'm saying is the value of x and y change throughout the function instead, they should only change on the recursive call. Say you start out with x=0, and y=0. With this, you should only make two calls to flood_fill, but instead, because of the incrementing you make 4 calls.

flood_fill(0,1, fill_sector)
flood_fill(0,0, fill_sector) <- Initially y is == 0. But it's being incremented on the previous check, so y-1 is 0. Instead of -1 which it ought to be and this should never be called.
flood_fill(1,0, fill_sector)
flood_fill(0,0, fill_sector) <- Same thing here as for y. x should be 0, and when compared using if( x-1 >= 0 ) this should fail, as x ought to be 0 instead of 1.

Instead you should only be calling
flood_fill(0,1, fill_sector)
flood_fill(1,0, fill_secotr)
12 Jan, 2009, Chris Bailey wrote in the 5th comment:
Votes: 0
You are absolutely correct, I wasn't thinking straight. I will give it a go as soon as I get a chance. I think that will solve the problem. Thanks Davion! =)
12 Jan, 2009, Tyche wrote in the 6th comment:
Votes: 0
Davion said:
I don't think so… that still modifies the value of x so all the other uses of it below that will be using the new value. Doesn't something like this
flood_fill(x+1, y, fill_sector)


Exactly so.
12 Jan, 2009, Chris Bailey wrote in the 7th comment:
Votes: 0
Just checked it out, works like a charm! Thanks for the help.
0.0/7