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
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) ?
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! =)
@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