Get ready for the flood!

Flood-fill in a painting program is usually the thing that makes users happy and coders unhappy. It's not a trivial task comparable to e.g. filled block rendering. It's more like exploring a dungeon: when you face a room with three doors and you select the one on your left, you also need to mentally keep track that you should come back and visit the door on the right and that one in the middle afterwards. A computer can do this "mental track" with a data structure that looks like a todo list. It's manageable (unless you're in an odd language like the QuickBasic I used for my early sprite editors), but in evil-designed "dungeons", it may require you large amount of RAM, and with a sufficiently large-and-evil dungeons (pictures, should I say), you might very well run out of memory when "painting". It used to happen from times to times with Deluxe Paint II.

"Vous êtes dans la salle principale du donjon. Trois portes se présentent devant vous: une sur la gauche, une sur la droite, et une au centre... Laquelle allez-vous ouvrir". Bien connu des rôlistes, c'est aussi le genre de dilemme que doit résoudre votre programme de dessin chaque fois que l'artiste utilisera l'outil "remplissage".

Ce qui explique en partie qu'il n'y avait aucun outil de ce genre jusqu'ici dans SEDS: pour le réaliser, il faut maintenir une sorte de "todo list" des salles (pixels) à re-visiter plus tard et des directions qui y restent à explorer. C'est pénible, et on ne sait jamais trop bien quelle quantité de mémoire ça va demander. Deluxe Paint II me gueulait régulièrement dessus pour cette raison. Bon, avec 4Mo de RAM et une image en 32x32, ça ne devrait pas être la fin du monde, mais ce n'est pas marrant pour autant.

Mais j'ai trouvé une astuce pour contourner la difficulté: la DS fait la moitié du travail: remplir horizontalement uniquement, en s'arrètant sur les bords, et l'artiste fait l'autre moitié : balayer verticalement de son stylet la zone à remplir. Eh oui, c'est comme ça: les programmeurs sont des feignasses. Il faudra vous y faire. On verra à l'usage si ça suffit.

I figured out a few days ago that there was an "easy way out" for that situation. Rather than having the CPU doing all the job, I can safely share the job between the user and the CPU: The user will point out regions that needs to be filled, and the CPU fills them one scanline at a time. That is, to flood-fill a rectangle as the one depicted, you'll have to swipe it bottom-up (or top-down ;-) with the "bucket fill" tool (L+B). Pick another color and swipe it "not quite up to the corners", and you'll obtain something like the picture shown.
When there are "holes" in the border, the fill just "evades" horizontally, rahter than flooding the whole outer area as you'll usually see in painting programs.

So why don't you download the "nightly build" and give it a beta-try yourself ?