I need a fill function
BlitzMax Forums/BlitzMax Programming/I need a fill function
| ||
| Hi I have a grid that is based on an array: Grid[8,8] Its 8x8 grid with block size 32x32.  How do I fill the black area with the white blocks? Starting with my mouse at the red cross. I know I should do it in the array, and then draw the grid based on the array. Any one have an idea? |
| ||
| you might consider a reccursive function... perhaps something like this..: - check the 8 (or 4 if you don't want diagonal) slots around the current point. (starting f.ex. from the top left) - if one of the slots is "open", run the same function again, jumping to that current "open" slot.. it will the check the slots around the new point/slot. when it's done, all open slots should be filled... I hope you understood what I meant.. |
| ||
| you could try converting this: http://www.blitzbasic.com/codearcs/codearcs.php?code=314 or this: http://www.blitzbasic.com/codearcs/codearcs.php?code=263 |
| ||
| LarsG: I think that your method will stop in one of the corners and not fill the entire area. Perturbatio: I'll look into thoose, see if I can get them to work. Thanx both of you! |
| ||
| No, what happens is that when you enter the function you fill the pixel and then check each of the surrounding pixels in turn. If the pixel is unfilled, then you call the function again. When the pixel is already filled and you've checked all 4 or 8 neighbouring pixels, the function returns where the checking that was being done is resumed. A function calling itself is called recursion. You do have to be careful with it though, as you could cause the system to crash if it doesn't back out correctly - causing stack overflows and killing your system. The pseudo code would look something like this. Function FillPoint(x,y,colour) Plot x,y If <pixel at x,y-1 open> Then FillPoint(x,y-1,colour) If <pixel at x+1,y open> Then FillPoint(x+1,y,colour) If <pixel at x,y+1 open> Then FillPoint(x,y+1,colour) If <pixel at x-1,y open> Then FillPoint(x-1,y,colour) Return End Function The above doesn't check for diagonals, but remember it is just pseudo code. Hope it helps. |
| ||
| And maybe it can add an empty point to some kind of list. Then when is finshed, take a point from that list and start again. Every time a point is used from that list it is deleted. Maybe that way I can get it filled. |
| ||
| Because its Recursive, LarsG's function will fill everything because when a function quits it continues where it got called from. On "end function", execution continues from where the function was called each time... |
| ||
| You mean it will try to fill everything and get a stack overflow error. lol I tried recursion and got a stack overflow, but only when the area was like 250x250 or larger. |
| ||
| I got it to work. Heres how I did it: 1) Make a list 2) Add the first point to the list as a string ("4,4") 3) Split the "4,4" string into to INT's 4) Check the array with thoose two INT's 5) Check the 8 slot around my point (4,4) 6) If any of the slots is empty insert their coordinate into the list. 7) Remove point from list (delete "4,4") 8) Do a While Wend until ListIsEmpty This way it fills the grid shown above. It's not fast, but it fills the grid. Theres still some minor ajustments to make, but its coming along. Thanx to everyone! B.t.w I used RobK's StringUtils for the Split function When I'm done I'll post my code in the archives! |
| ||
| TGD - looks like you've cracked the problem, but I recommend leaving stings alone. Just use types with fields x and y - saves conversions and should be faster. |
| ||
| @Coorae: I use an array, and store how deep the recursion goes. Now, whenever the recursion gets too deep, store the location that would have been next in the array, and dont fill it. Now, at the end of the function when recursions=1, Go through and call the function once at each of these points. :) |
| ||
| Aren't there any other funky algorithms that also fill a given area? |
| ||
| I am wondering .... if the area that needs to be filled is a specific color or value which doesn't exist anywhere else within the array or image, you don't have to do a complicated recursive fill routine. All you need is a remapping routine. You just go through the whole thing and when you find a pixel or value that is the color or value of the inside of the fillable area, you change it to the fill color/value. I don't know if this works in your case but it's sure simpler and maybe even faster than a flood-fill. |
| ||
| I'm actually using this for 400x400 grid. My code works but if I try to fill the hole area it's takes a long time. I tried it just to testand it was very slow. But as I don't need this function to fill a 400x400 grid it works okay. I'll only be using it to fill smaller areas. But I have been thinking about Falkens suggestion and try using Types |
| ||
Here is a recursive routine for your fill problem. Enjoy.; ; Flood Fill example... by Brien King ; Check out FrostByte Freddie at http://www.arcaderestoration.com under "Software" ; Graphics 800,600,8 Dim G_grid(10,10) ;------------------------------------ ; Initialize our grid to all Zeros ;------------------------------------ For x% = 1 To 10 For y% = 1 To 10 G_grid(x%,y%) = 0 Next Next ;------------------------------------ ; Now create a block that we want ; to fill in. ;------------------------------------ For x% = 4 To 7 For y% = 4 To 7 G_grid(x%,y%) = 1 Next Next G_grid(3,3) = 1 G_grid(3,4) = 1 G_grid(8,3) = 1 ;------------------------------------ ; Display our "Before" block ;------------------------------------ For y% = 1 To 10 temp$ = "" For x% = 1 To 10 temp$ = temp$ + G_grid(x%,y%) Next Print temp$ Next ;------------------------------------ ; This FILL should do nothing as it ; won't find the color we want to ; fill in here. ; We want to fill COLOR 1 with ; COLOR 2. ;------------------------------------ FloodFill(1,2,1,1) Print Print "The next grid should look just like the one above" Print ;------------------------------------ ; Display the Results of our fill ; they should be the same as before ;------------------------------------ For y% = 1 To 10 temp$ = "" For x% = 1 To 10 temp$ = temp$ + G_grid(x%,y%) Next Print temp$ Next ;------------------------------------ ; Now lets fill in the block in ; the Center. We want to fill ; COLOR 1 with COLOR 3. We should ; see the 1's turn into 3's and ; the 0's stay the same. ;------------------------------------ FloodFill(1,3,5,5) Print Print "The next grid should have all 3's in the center" Print ;------------------------------------ ; Show us the Results.... ;------------------------------------ For y% = 1 To 10 temp$ = "" For x% = 1 To 10 temp$ = temp$ + G_grid(x%,y%) Next Print temp$ Next ;------------------------------------ ; Now lets fill outside block in ; the Center. We want to fill ; COLOR 0 with COLOR 5. We should ; see the 0's turn into 5's and ; the 3's stay the same. ;------------------------------------ FloodFill(0,5,1,1) Print Print "The next grid should be 5's, 3's and a single 1" Print ;------------------------------------ ; Show us the Results.... ;------------------------------------ For y% = 1 To 10 temp$ = "" For x% = 1 To 10 temp$ = temp$ + G_grid(x%,y%) Next Print temp$ Next WaitKey ;--------------------------------------------------- ; This function Recursivly fills in an area. of a ; Grid... ; ; NOTE: This does not handle Diagnols ; as you will see the Upper Right 1 doesn't change. ; If you need that and can't figure it out, ; let me know. Also you should keep in mind that ; if you have a HUGE area to fill you could run into ; stack overflow issues. But that would have ; to be a VERY LARGE area. ;--------------------------------------------------- Function FloodFill(P_colorToFill%, P_color%, P_x%, P_y%) ;--------------------------------------------- ; If the spot we are on is not the color we ; want to fill then exit the function, else ; fill in the color. ;--------------------------------------------- If G_grid(P_x%,P_y%) <> P_colorToFill% Then Return Else G_grid(P_x%,P_y%) = P_color% EndIf ;--------------------------------------------- ; We start by looking behind our current ; position to see if have the color we want. ;--------------------------------------------- If P_x% > 1 Then FloodFill(P_colorToFill%, P_color%, P_x%-1, P_y%) EndIf ;--------------------------------------------- ; Now look in front of our current ; position to see if have the color we want. ;--------------------------------------------- If P_x% < 10 Then FloodFill(P_colorToFill%, P_color%, P_x% + 1, P_y%) EndIf ;--------------------------------------------- ; Now look above our current ; position to see if have the color we want. ;--------------------------------------------- If P_y% > 1 Then FloodFill(P_colorToFill%, P_color%, P_x%, P_y%-1) EndIf ;--------------------------------------------- ; Now look below our current ; position to see if have the color we want. ;--------------------------------------------- If P_y% < 10 Then FloodFill(P_colorToFill%, P_color%, P_x%, P_y%+1) EndIf End Function |
| ||
| Thanks I'll see if I can use it. |
| ||
| the problem with recursive functions like someone already said is that you easily get a stack overflow if the gris is too big... so then you can simulate(convert) you recursive function to an iterative one... Since I recently wrote a fill function myself, here is how I did it (and it's pretty fast... got it filling a grid of 30x30 tiles wich gives you 900 tiles and it took only about 4-5 seconds): let's say you click on the tile x,y 1) store the "color" of that tile and add that tile in an array. While this array is not empty, here is what to do with it: Loop Until Lenght(Array)=0 (<- pseudo code of course) 3) test the last tile of the array (change its color if needed) and remove it from the array 4) then test the tile [x-1,y], if you must change its color, add it to your array, then test the tile [x+1,y] and add it to your array if you have to change its color, then do the same for the tiles [x,y+1] and [x,y-1] End Loop the array will be empty once all the good tiles are filled because you'll be removing the last tiles without adding any new one (since no more tiles will have to be changed)... that's it, and the algo is fast and shouldn't take more than some 20 lines of code. in fact, you just emulate the recursive algo, but use an array instead of the stack (and an array is hard to "overflow")... |
| ||
| here it is using types this is not optimised for speed. |
   |