Competition or not, I wrote a simple flood fill-algorithm. Anybody may read, use, alter, spread or curse it however he wants.
set display mode 800,600,32
sync on
sync rate 0
sync
randomize 42
dim Color(3) as dword
Color(0) = 0xFF303030
Color(1) = 0xFFFFFFFF
Color(2) = 0xFFFF0000
Color(3) = 0xFF0000FF
dim Tile(500,500) as byte
SetTiles(0,0,500,500, 0)
SetTiles(80,380,100,425, 1)
SetTiles(80,120,130,170, 1)
SetTiles(130,142,350,148, 1)
SetTiles(351,132,360,141, 1)
SetTiles(340,148,350,420, 1)
for x = 120 to 340
y = 150 + ((x-120)*270)/220
SetTiles(x-5,y,x+5,y+1, 1)
next x
y = 190
for x = 340 to 193 step -1
inc y, 1-rnd(2)
SetTiles(x,y,x+1,y, 1)
next x
DrawTiles()
wait key
print "Starting #1" : sync
t1 = timer()
for i = 1 to 30
FloodFill_1(100,150, 2)
next i
t1 = timer()-t1
print "Done"
DrawTiles()
wait key
print
print "Starting #2" : sync
t2 = timer()
for i = 1 to 30
FloodFill_2(100,150, 2)
next i
t2 = timer()-t2
print "Done"
DrawTiles()
wait key
cls
ink 0xFFFFFFFF,0
print "T1: ", t1
print "T2: ", t2
t# = t2/(1.0*t1)
print "T2/T1: ", t#
sync
wait key
end
function FloodFill_2(x,y, c)
rem your function
endfunction
function FloodFill_1(x,y, c)
dim Flooded(500,500) as boolean
for a = 0 to 500 : for b = 0 to 500 : Flooded(a,b) = 0 : next b : next a
FloodFill__1(x,y, c)
endfunction
function FloodFill__1(x,y,c)
t = Tile(x,y)
Tile(x,y) = c
Flooded(x,y) = 1
if Flooded(x-1,y)=0 then if Tile(x-1,y) = t then FloodFill__1(x-1,y,c)
if Flooded(x+1,y)=0 then if Tile(x+1,y) = t then FloodFill__1(x+1,y,c)
if Flooded(x,y-1)=0 then if Tile(x,y-1) = t then FloodFill__1(x,y-1,c)
if Flooded(x,y+1)=0 then if Tile(x,y+1) = t then FloodFill__1(x,y+1,c)
endfunction
function DrawTiles()
lock pixels
for x = 0 to 500
for y = 0 to 500
t = Tile(x,y)
dot x+150, y+50, Color( t )
next y
next x
unlock pixels
sync
endfunction
function SetTiles(x1,y1,x2,y2, c)
for x = x1 to x2 : for y = y1 to y2 : Tile(x,y) = c : next y : next x
endfunction
To go a step beyond, there's this "competition"-idea: You might write your own flood filling-function and try to make it faster than mine. My function is not that great or optimized, so that should be quite possible. The idea obviously is not to "win" but to find a fast function anybody can use.
By the way, my function does not check if it stays within the array. So, in some cases it might cause errors, but in the chosen example it does not. Thus, it is up to you if you want your function to work in every possible case or just in this example.
Basically, all you need is the Tile(x,y)-Array, which has a fixed size of 500x500. It stores a byte-variable, defining the type of the specific tile.
Edit: Added a second, non-recursive function. Seems to be a bit slower, but is probably more stable.
set display mode 800,600,32
sync on
sync rate 0
sync
randomize 42
dim Color(3) as dword
Color(0) = 0xFF303030
Color(1) = 0xFFFFFFFF
Color(2) = 0xFFFF0000
Color(3) = 0xFF0000FF
dim Tile(500,500) as byte
SetTiles(0,0,500,500, 0)
SetTiles(80,380,100,425, 1)
SetTiles(80,120,130,170, 1)
SetTiles(130,142,350,148, 1)
SetTiles(351,132,360,141, 1)
SetTiles(340,148,350,420, 1)
for x = 120 to 340
y = 150 + ((x-120)*270)/220
SetTiles(x-5,y,x+5,y+1, 1)
next x
y = 190
for x = 340 to 193 step -1
inc y, 1-rnd(2)
SetTiles(x,y,x+1,y, 1)
next x
DrawTiles()
wait key
print "Starting #1" : sync
t1 = timer()
for i = 1 to 30
FloodFill_1(100,150, 2)
next i
t1 = timer()-t1
print "Done"
DrawTiles()
wait key
print
print "Starting #2" : sync
t2 = timer()
for i = 1 to 30
FloodFill_2(100,150, 3)
next i
t2 = timer()-t2
print "Done"
DrawTiles()
wait key
cls
ink 0xFFFFFFFF,0
print "T1: ", t1
print "T2: ", t2
t# = t2/(1.0*t1)
print "T2/T1: ", t#
sync
wait key
end
#constant ff_step = 3141
global ff_cur as integer
global ff_max as integer
function FloodFill_2(x,y, c)
ff_cur = 0
ff_max = ff_step
dim ff_vec(ff_max) as vec2
dim Flooded(500,500) as boolean
for a = 0 to 500 : for b = 0 to 500 : Flooded(a,b) = 0 : next b : next a
ff_vec(0).x = x
ff_vec(0).y = y
t = Tile(x,y)
rem Calculation
i = -1
repeat
inc i
x = ff_vec(i).x
y = ff_vec(i).y
Tile(x,y) = c
if Flooded(x-1,y)=0 then if Tile(x-1,y) = t then FloodFill_2_Add(x-1,y)
if Flooded(x+1,y)=0 then if Tile(x+1,y) = t then FloodFill_2_Add(x+1,y)
if Flooded(x,y-1)=0 then if Tile(x,y-1) = t then FloodFill_2_Add(x,y-1)
if Flooded(x,y+1)=0 then if Tile(x,y+1) = t then FloodFill_2_Add(x,y+1)
until i = ff_cur
endfunction
type vec2
x as integer
y as integer
endtype
function FloodFill_2_Add(x,y)
inc ff_cur
if ff_cur > ff_max
array insert at bottom ff_vec(), ff_step
inc ff_max, ff_step
endif
ID = ff_cur
ff_vec(ID).x = x
ff_vec(ID).y = y
Flooded(x,y) = 1
endfunction ID
function FloodFill_1(x,y, c)
dim Flooded(500,500) as boolean
for a = 0 to 500 : for b = 0 to 500 : Flooded(a,b) = 0 : next b : next a
FloodFill__1(x,y, c)
endfunction
function FloodFill__1(x,y,c)
t = Tile(x,y)
Tile(x,y) = c
Flooded(x,y) = 1
if Flooded(x-1,y)=0 then if Tile(x-1,y) = t then FloodFill__1(x-1,y,c)
if Flooded(x+1,y)=0 then if Tile(x+1,y) = t then FloodFill__1(x+1,y,c)
if Flooded(x,y-1)=0 then if Tile(x,y-1) = t then FloodFill__1(x,y-1,c)
if Flooded(x,y+1)=0 then if Tile(x,y+1) = t then FloodFill__1(x,y+1,c)
endfunction
function DrawTiles()
lock pixels
for x = 0 to 500
for y = 0 to 500
t = Tile(x,y)
dot x+150, y+50, Color( t )
next y
next x
unlock pixels
sync
endfunction
function SetTiles(x1,y1,x2,y2, c)
for x = x1 to x2 : for y = y1 to y2 : Tile(x,y) = c : next y : next x
endfunction
