.Flood fill

Lbl PL
If r3=0

Lbl FF
ReturnIf pxl-Test(S,T)=C


I'm trying to write a drawing program in axe and one of the things i want it to do is to have a bucket fill/flood button, but for some reason instead of returning from the function/subroutine, it just exits out of the program. Am I doing something wrong? I'm trying to use the flood fill algorithm which can be found here
I'm guessing the immediate problem is that you need to use a special function call format to properly call functions recursively in Axe without overwriting the old r1-r6 arguments (due to certain original language design decisions). The syntax is a little weird because it's based on the old function call design: sub(Nameʳ,<arg list>).

Another issue that pops out at me is bounds checking. The FF function stops recursion when the pixel being tested is already the target color, but what if the target color is black and you're filling a white section that extends all the way to an edge of the screen? The algorithm will eventually move to start filling the area outside of the screen image, and because pxl-Test returns 0 not only for white but also for offscreen pixels, you're going to end up with a big mess of the algorithm attempting to fill offscreen pixels, wrapping around to the other side, and general bad stuff. So make sure that the algorithm doesn't try to fill offscreen pixels.

Unless I'm seeing any other issues, this may seem to solve all the problems. However, I have a feeling that it'll still have one less obvious problem. Memory is tight on a device with only 32KB of addressable RAM. The amount of stack space allocated by the OS only gives room for about 170 stack entries in a program. But each of your recursive calls needs to save the execution point and the three arguments, so they consume 1+3=4 stack entries. So if at any point the FF function reaches a recursive call depth of about 42 calls, the stack will overflow. When filling large/intricate areas, this is certainly a possibility. The program may appear to behave normally, but if the stack overflows, chances are you'll have a crash awaiting you when you exit from it.

Unfortunately, stack size is an enemy of many flood fill algorithms. You can try to slightly alleviate the problem by packing more information into each argument to reduce the number of arguments saved each call. A quick note if you didn't already know it: values in Axe are represented as 16-bit integers. Since the x and y coordinates of a (I assume) 96x64 image each individually fit into 8 bits, you could drop down to 2 arguments per recursive call by storing one coordinate in the low 8 bits and the other coordinate in the high 8 bits (I suggest splitting this into 8-bit values because that splits the value evenly into 2 bytes and allows for optimized access). If you want to go even further, you could drop down to only 1 argument per recursive call by doing something like storing one coordinate in the low 8 bits, the other coordinate in the next 7 high bits, and storing the color in the final high bit. This would cut the number of stack words used per recursive call in half, allowing a maximum recursion depth of about 85 calls. But this isn't really a completely fix, as even this would still fail for some large/intricate areas. For a complete fix, you'd need an algorithm that you know is very efficient with stack usage, or one that uses a constant amount of pre-allocated storage.
Another problematic thing I see is that the routines are "declared" before the main code (except if you have something before the PL routine, but if you shared the whole code as it is, then you have the problem I am describing). So the program actually thinks the first routine is the main code, executes it then quits, and never reads the FF(A,B,V) line. So maybe you'd want that line to be before the Lbl PL, and followed by a return.
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
Page 1 of 1
» All times are UTC - 5 Hours
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum