I'm considering making an adventure game with fullscreen backgrounds stored as sets of instructions for drawing, so I tried making a flood fill algorithm in the scanline variety, but found it to be rather slow. Even after fiddling with methods, such as wasting memory to avoid management and making the algorithm twice as long to avoid ever checking a pixel twice, I could only get it down to %128 cpu usage for the test case. Most optimizations I tried saved less than %1 cpu. If told to fill the entire screen, it goes even further up to %267 cpu.
It's definitely fast enough for drawing images that don't need redrawing every frame, but it'd be nice if it were fast enough for real time usage. Anyone know a way to make it faster?
Here's a version of your drawing using a little tool I've been working on that draws shapes from encoded strings. It uses under 6% cpu.
s="b```ラかトi`⬆️かトス`⬆️かトス`█`トかえ★`うかう█`トかう█i`かト█"
::_::cls()
function trifill(x1,y1,x2,y2,c)
local inc=sgn(y2-y1)
local fy=y2-y1+inc/2
for i=inc/2,fy,inc do
local nx=x1+(x2-x1)*i/fy
if(abs(nx-x1)>abs(x2-x1))nx=x2
line(x1+.5,y1+i,nx+.5,y1+i,c)
end
end
--string decoder
t1,ft={},{pset,line,trifill,oval,ovalfill,rect,rectfill,spr,cls}
for i=0,#s-1 do v=ord(s,i+1)-96
t1[i%5+1]=v
if(i%5==4) ft[v\16](unpack(t1))
end
?stat(1),1,1,6
flip()goto _ |
I'm collaborating with TheRoboZ on a comprehensive shape-drawing tool he's making for Pico-8, so consider this kind of a preview. =)
You can find more information in this thread:
https://www.lexaloffle.com/bbs/?pid=79494#p
Hmm...I guess for real-time drawing it would make more sense generally to use known shapes. However, I think if I do decide to make my idea for an adventure game, I'll likely still use some form of floodfill for efficiency in storage. If nothing else, small areas with weird shapes are probably still a good target for flooding.
That said, I also was considering generalizing my scanfill function to allow applying it to memory other than the screen pixels, so I may be able to implement my own version of that trifill (just to suit my own tastes) and then concoct a way to automate its use on the spots that the scanfill finds.
Okay, sounds like you're going for something a little different, that's fine. If you're planning to use my triangle function, though, here's the new version of it I just made. It fixes some little anomalies in the line pattern at some angles, it takes less cpu power, and it's down from 76 tokens to just 63.
function trifill(x1,y1,x2,y2,c) local inc=sgn(y2-y1) local fy=y2-y1+inc/2 for i=inc\2,fy,inc do line(x1+.5,y1+i,x1+(x2-x1)*i/fy+.5,y1+i,c) end line(x1,y1,x2,y2) end |
Oh, right. I was thinking of that. I found out if I just use the fill for unpacking the images, I could hide loading times as usual and store the images as just a series of parameters for pixel setting and line drawing (in a more literal scanline rasterization setup). The result is 9% cpu for drawing the whole screen. It's not as efficient as your method, but close enough to satisfy me. I'll post it here if I can find a nice way to generalize it and a decent way to enter the data in. I've already made a game recently that involved manually entering in image data in byte by byte, but I'm guessing most users wouldn't want to do that.
No, I'm guessing they wouldn't. That's how I made the picture I uploaded since I haven't made an editor yet, and it's not real fun.
[Please log in to post a comment]
