yeah, but that's compressed programs, with ununderstable code (what, I'm a newbie ?)

Compressed programs? Neither of the three have any sort of compression going on (that I know of), it's just regular Axe.

Yeah, but I meant without any explication of how it work (bad English powaaa)

The term you're looking for is "optimized," not "compressed." Compression is where a set of data is encoded in such a way that the resulting data is smaller in size than the original data. Optimization is when a program is modified so it runs faster or uses less memory, or otherwise becomes more efficient than before.

Quote from: nxtboy III on February 18, 2012, 12:23:52 am

In this game, is there only 1 level or can the player go underground?

Normally there should be a nether, the mines and the air world(or something like that). All of these should be a kind of world. So 4 in total iirc.

three underground worlds, main world, and air world. so five.

If you ever wanted to add grayscale support then you'd need another buffer, meaning 3 buffers...that's a lot of memory to keep track of... The whole point is that this algorithm uses no extra memory other than what is in the routine itself.

Hmm, so your flood fill algorithm just traces around the edge of the region until it is all filled? Nice...
I am curious, will it work properly if you have a setup like an hourglass but at the middle (where it is narrow) you have 1 empty pixel with a black pixel on either side?

EDIT: Ah, I see the screenies, now >.>

Yeah, the algorithm traces the edges and only fills in a pixel if it is positive that filling that pixel will not block off another area to fill. If it is unsure, it places a markat that "questionable" pixel indicating the direction it was heading and continues to trace the edges until it comes back to the mark.

If it reaches the mark and the mark is pointing in the direction that it was already heading, then it knows filling that pixel will still allow it to get to the other side.

However, if it reaches the mark and the mark is pointing in a different direction, then there must be some sort of a loop that turns it back onto itself, meaning it wouldn't be able to reach the other side if it filled the pixel.

To eliminate this loop, it turns around and starts backtracking around the loop. Once it reaches another "questionable" pixel in that loop, a second mark is placed on that pixel. It keeps backtracking until it runs into one of the two marks.

If it runs into the second mark before the first mark, it knows the place where it gets turned around on itself must be further into the loop, so it turns around and backtracks again, finding the NEXT "questionable" pixel.

But if it reaches the first mark before the second it knows that filling the pixel at the second mark will get rid of the loop without blocking off the rest of the map. So it fills in the pixel at the second mark, removes both marks, and continues as usual from where the second mark was.


Hope that explanation helps clarify how the algorithm works. It's certainly easier than trying to interpret that pseudocode.


Edit:

In those screenshots, the screen is being updated 4-5 times per frame, so the program is spending most of the time updating the screen. Also, I haven't even started optimizing the code, and I have some ideas for how to optimize the algorithm. In fact, filling a blank screen from the center without updating the screen currently takes only 10 seconds (That's 24x faster than the screenshot ).

Edit: Updating every 256'th frame looks like this:

What about updating every Xth time it paints, not every Xth frame? That might go even faster.

 ##
###
####
 ##
X##
  #


 ##
###
####
 ##
 ##
  #


 ##
###
####
 ##
###
  X

#=black
X=gray

You said you were using 3-level gray, right?

Ah maybe I didn't notice, since it was going on pretty fast.

Also I'm curious how fast this would be in z80 ASM, considering you don't have to update the LCD every frame but only at the end.

Yeah, I'm wondering that, too. Seeing as it's such an obnoxiously slow routine, a mostly-speed-optimized ASM version would probably be best. I personally don't feel like I'd be able to make a very good routine in ASM. I'd rather that someone else give it a go...

Maybe someone could even write an Axe implementation just so something exists to base some of the ASM off of. This pseudocode is written in structured English, so it's not really written for easy translation directly into ASM.

To be consistent, each case in the main loop should probably end with continue main loop. Also, I don't see any code that sets MARK2.

Oops! I accidentally put MARK instead of MARK2 at the place it should be set. Fixed that now. And I added the "continue main loop" as well.