QB64.org Forum

Active Forums => Programs => Topic started by: SMcNeill on November 22, 2019, 11:49:50 pm

Title: Steve's Magical Paint Fill
Post by: SMcNeill on November 22, 2019, 11:49:50 pm
Here's a paint fill with which I simply can not figure out the logic behind WHY it's doing what it's doing.  It seems quick.  It seems like it'd be useful.  It seems...  Impossibly Broken.

Code: QB64: [Select]
  1. SCREEN _NEWIMAGE(640, 480, 32)
  2.  
  3.  
  4. LINE (100, 100)-(300, 300), -1, B
  5. FOR r = 99 TO 101 STEP .25
  6.     CIRCLE (300, 300), r, -1
  7. 'PAINT (301, 301), -1
  8.  
  9. fill 200, 200, &HFFFF0000, -1
  10.  
  11.  
  12.  
  13.  
  14.  
  15.  
  16.  
  17.  
  18. SUB fill (tx, ty, kolor AS _UNSIGNED LONG, bordercolor AS _UNSIGNED LONG)
  19.     x = tx: y = ty
  20.     DIM Array(_WIDTH, _HEIGHT) AS LONG
  21.     FOR x1 = 0 TO _WIDTH - 1
  22.         FOR y1 = 0 TO _HEIGHT - 1
  23.             IF POINT(x1, y1) = bordercolor THEN S(x1, y1) = -1 'This is actually Sneaky Steve Logic at its best!
  24.             'Here we're checking to see if our array matches the proper border color or not.
  25.             'If it doesn't, then it might be a spot to fill (which is 0 -- the same as our inital Array()).
  26.         NEXT
  27.     NEXT
  28.     MinX = x: MinY = y
  29.     MaxX = x: MaxY = y
  30.     Array(x, y) = 1
  31.     pass = 1
  32.     DO
  33.         finished = -1
  34.         np = pass + 1 'next pass
  35.         TMX = MinX: TMX2 = MaxX
  36.         TMY = MinY: TMY2 = MaxY
  37.         FOR y = TMY TO TMY2
  38.             FOR x = TMX2 TO TMX STEP -1
  39.                 fill_left:
  40.                 IF Array(x - 1, y) = S(x - 1, y) THEN
  41.                     Array(x - 1, y) = np
  42.                     finished = 0
  43.                     x = x - 1
  44.                     IF x < MinX THEN MinX = x
  45.                     GOTO fill_left
  46.                 END IF
  47.             NEXT
  48.             FOR x = TMX TO TMX2
  49.                 fill_right:
  50.                 IF Array(x + 1, y) = S(x + 1, y) THEN
  51.                     Array(x + 1, y) = np
  52.                     finished = 0
  53.                     x = x + 1
  54.                     IF x > MaxX THEN MaxX = x
  55.                     GOTO fill_right
  56.                 END IF
  57.             NEXT
  58.         NEXT
  59.         FOR x = TMX TO TMX2
  60.             FOR y = TMY2 TO TMY STEP -1
  61.                 fill_up:
  62.                 IF Array(x, y - 1) = S(x, y - 1) THEN
  63.                     Array(x, y - 1) = np
  64.                     finished = 0
  65.                     y = y - 1
  66.                     IF y < MinY THEN MinY = y
  67.                     GOTO fill_up
  68.                 END IF
  69.             NEXT
  70.             FOR y = TMX TO TMX2
  71.                 fill_down:
  72.                 IF Array(x, y + 1) = S(x, y + 1) THEN
  73.                     Array(x, y + 1) = np
  74.                     finished = 0
  75.                     y = y + 1
  76.                     IF y > MaxY THEN MaxY = y
  77.                     GOTO fill_down
  78.                 END IF
  79.             NEXT
  80.         NEXT
  81.  
  82.         pass = pass + 1
  83.     LOOP UNTIL finished
  84.  
  85.  
  86.     FOR x = MinX TO MaxY
  87.         FOR y = MinY TO MaxY
  88.             IF Array(x, y) THEN PSET (x, y), kolor
  89.         NEXT
  90.     NEXT

Now how am I painting inside the confines of that circle?  I've gave it a heckuva border; there shouldn't be any sort of leaks in it; so just how the heck am I doing the magic that I'm doing here??

For a glitch, this is a pretty cool glitch.  LOL!
Title: Re: Steve's Magical Paint Fill
Post by: STxAxTIC on November 23, 2019, 12:30:59 am
I think I see what's going on but I'd like to know the overall goal before fixing it. This is just a run-o-the mill fill routine right? Just like PAINT basically?
Title: Re: Steve's Magical Paint Fill
Post by: SMcNeill on November 23, 2019, 01:07:03 am
I think I see what's going on but I'd like to know the overall goal before fixing it. This is just a run-o-the mill fill routine right? Just like PAINT basically?

Aye, but it’s skipping the boundary somehow.  LOL
Title: Re: Steve's Magical Paint Fill
Post by: bplus on November 23, 2019, 01:24:17 am
Try filling other spots, I get subscript out of range allot, no fills.
Title: Re: Steve's Magical Paint Fill
Post by: SMcNeill on November 23, 2019, 01:41:03 am
Try filling other spots, I get subscript out of range allot, no fills.

Aye.  There’s no error checking in there for off-screen checks yet.  (X < 0 for example). I just thought for a glitch, this was a fun one all by itself.  I have no clue how it’s skipping that circle edge.  LOL
Title: Re: Steve's Magical Paint Fill
Post by: bplus on November 23, 2019, 01:49:27 am
Hi Steve,

It does look like it would be fast. I used your example on Paint Image thread to improve the one I was working on from Pathfinder like dumping a check on all 8 neighbors that needed 3 or 4 layers of circle to stop flooding, down to 4 neighbor checks and one circle now stops fill. I had heck of time with unknown floods testing bottom right corner. Turns out screen boundary is _width -1 and _height -1.

Code: QB64: [Select]
  1. _TITLE "PathFinder Paint mod"
  2. 'start code from PathFinder Paint mod
  3. DEFINT A-Z
  4. CONST xmax = 800, ymax = 600
  5. SCREEN _NEWIMAGE(xmax, ymax, 32)
  6. _SCREENMOVE 300, 40
  7. DIM bc AS _UNSIGNED LONG, start
  8.  
  9. start = TIMER
  10. bc = &HFFFF0000
  11. CIRCLE (500, 400), 100, bc
  12. Fill 510, 400, &HFFFFFF00, bc
  13.  
  14. CIRCLE (xmax - 1, ymax - 1), 400, bc
  15. Fill xmax - 10, ymax - 10, &HFFFF0088, bc
  16.  
  17. LINE (100, 100)-(500, 500), bc, B
  18. Fill 150, 150, &HFFFF0000, bc
  19. PRINT TIMER - start
  20.  
  21. SUB Fill (x0, y0, fillC AS _UNSIGNED LONG, bC AS _UNSIGNED LONG)
  22.     DIM W, H, parentF, tick, ystart, ystop, xstart, xstop, y, x
  23.     W = _WIDTH - 1: H = _HEIGHT - 1
  24.     DIM temp(W, H)
  25.     temp(x0, y0) = 1: parentF = 1
  26.     WHILE parentF = 1
  27.         parentF = 0: tick = tick + 1
  28.         ystart = max(y0 - tick, 0): ystop = min(y0 + tick, H)
  29.         y = ystart
  30.         WHILE y <= ystop
  31.             xstart = max(x0 - tick, 0): xstop = min(x0 + tick, W)
  32.             x = xstart
  33.             WHILE x <= xstop
  34.                 IF POINT(x, y) <> bC AND temp(x, y) = 0 THEN
  35.                     IF temp(max(0, x - 1), y) THEN
  36.                         temp(x, y) = 1: parentF = 1: PSET (x, y), fillC
  37.                     ELSEIF temp(min(x + 1, W), y) THEN
  38.                         temp(x, y) = 1: parentF = 1: PSET (x, y), fillC
  39.                     ELSEIF temp(x, max(y - 1, 0)) THEN
  40.                         temp(x, y) = 1: parentF = 1: PSET (x, y), fillC
  41.                     ELSEIF temp(x, min(y + 1, H)) THEN
  42.                         temp(x, y) = 1: parentF = 1: PSET (x, y), fillC
  43.                     END IF
  44.                 END IF
  45.                 x = x + 1
  46.             WEND
  47.             y = y + 1
  48.         WEND
  49.     WEND
  50.  
  51. FUNCTION rand% (lo%, hi%)
  52.     rand% = INT(RND * (hi% - lo% + 1)) + lo%
  53. FUNCTION min (n1, n2)
  54.     IF n1 > n2 THEN min = n2 ELSE min = n1
  55. FUNCTION max (n1, n2)
  56.     IF n1 < n2 THEN max = n2 ELSE max = n1
  57.  
  58.  

EDIT: 3 secs off time with DEFINT A-Z
Title: Re: Steve's Magical Paint Fill
Post by: SMcNeill on November 23, 2019, 01:52:09 am
Code: [Select]
SCREEN _NEWIMAGE(640, 480, 32)


LINE (100, 100)-(300, 300), -1, B
FOR r = 99 TO 101 STEP .25
    CIRCLE (300, 300), r, -1
NEXT
'PAINT (301, 301), -1

SLEEP
fill 200, 200, &HFFFF0000, -1








SUB fill (tx, ty, kolor AS _UNSIGNED LONG, bordercolor AS _UNSIGNED LONG)
    x = tx: y = ty
    DIM Array(_WIDTH, _HEIGHT) AS LONG
    DIM S(_WIDTH, _HEIGHT) AS LONG
    FOR x1 = 0 TO _WIDTH - 1
        FOR y1 = 0 TO _HEIGHT - 1
            IF POINT(x1, y1) = bordercolor THEN S(x1, y1) = -1 'This is actually Sneaky Steve Logic at its best!
            'Here we're checking to see if our array matches the proper border color or not.
            'If it doesn't, then it might be a spot to fill (which is 0 -- the same as our inital Array()).
        NEXT
    NEXT
    MinX = x: MinY = y
    MaxX = x: MaxY = y
    Array(x, y) = 1
    pass = 1
    DO
        finished = -1
        np = pass + 1 'next pass
        TMX = MinX: TMX2 = MaxX
        TMY = MinY: TMY2 = MaxY
        FOR y = TMY TO TMY2
            FOR x = TMX2 TO TMX STEP -1
                IF Array(x, y) = pass THEN
                    fill_left:
                    IF Array(x - 1, y) = S(x - 1, y) THEN
                        Array(x - 1, y) = np
                        finished = 0
                        x = x - 1
                        IF x < MinX THEN MinX = x
                        GOTO fill_left
                    END IF
                END IF
            NEXT
            FOR x = TMX TO TMX2
                IF Array(x, y) = pass THEN
                    fill_right:
                    IF Array(x + 1, y) = S(x + 1, y) THEN
                        Array(x + 1, y) = np
                        finished = 0
                        x = x + 1
                        IF x > MaxX THEN MaxX = x
                        GOTO fill_right
                    END IF
                END IF
            NEXT
        NEXT
        FOR x = TMX TO TMX2
            FOR y = TMY2 TO TMY STEP -1
                IF Array(x, y) = pass THEN
                    fill_up:
                    IF Array(x, y - 1) = S(x, y - 1) THEN
                        Array(x, y - 1) = np
                        finished = 0
                        y = y - 1
                        IF y < MinY THEN MinY = y
                        GOTO fill_up
                    END IF
                END IF
            NEXT
            FOR y = TMY TO TMY2
                IF Array(x, y) = pass THEN
                    fill_down:
                    IF Array(x, y + 1) = S(x, y + 1) THEN
                        Array(x, y + 1) = np
                        finished = 0
                        y = y + 1
                        IF y > MaxY THEN MaxY = y
                        GOTO fill_down
                    END IF
                END IF
            NEXT
        NEXT

        pass = pass + 1
    LOOP UNTIL finished


    FOR x = MinX TO MaxX
        FOR y = MinY TO MaxY
            IF Array(x, y) THEN PSET (x, y), kolor
        NEXT
    NEXT
END SUB

Almost sorted.  I think it just needs error checking now.
Title: Re: Steve's Magical Paint Fill
Post by: bplus on November 23, 2019, 02:02:13 am
What was causing the magic jump?
Title: Re: Steve's Magical Paint Fill
Post by: SMcNeill on November 23, 2019, 07:01:47 am
The final, working version, (I think):

Code: QB64: [Select]
  1. SCREEN _NEWIMAGE(640, 480, 32)
  2.  
  3.  
  4. LINE (100, 100)-(300, 300), -1, B
  5. FOR r = 99 TO 101 STEP .25
  6.     CIRCLE (300, 300), r, -1
  7. 'PAINT (301, 301), -1
  8.  
  9. fill 20, 200, &HFFFF0000, -1
  10.  
  11.  
  12.  
  13.  
  14.  
  15.  
  16.  
  17.  
  18. SUB fill (tx, ty, kolor AS _UNSIGNED LONG, bordercolor AS _UNSIGNED LONG)
  19.     x = tx: y = ty
  20.     DIM Array(_WIDTH, _HEIGHT) AS LONG
  21.     FOR x1 = 0 TO _WIDTH - 1
  22.         FOR y1 = 0 TO _HEIGHT - 1
  23.             IF POINT(x1, y1) = bordercolor THEN S(x1, y1) = -1 'This is actually Sneaky Steve Logic at its best!
  24.             'Here we're checking to see if our array matches the proper border color or not.
  25.             'If it doesn't, then it might be a spot to fill (which is 0 -- the same as our inital Array()).
  26.         NEXT
  27.     NEXT
  28.     MinX = x: MinY = y
  29.     MaxX = x: MaxY = y
  30.     Array(x, y) = 1
  31.     pass = 1
  32.     DO
  33.         finished = -1
  34.         np = pass + 1 'next pass
  35.         TMX = MinX: TMX2 = MaxX
  36.         TMY = MinY: TMY2 = MaxY
  37.         FOR y = TMY TO TMY2
  38.             FOR x = TMX2 TO TMX STEP -1
  39.                 IF Array(x, y) = pass THEN
  40.                     fill_left:
  41.                     IF x > 0 THEN
  42.                         IF Array(x - 1, y) = S(x - 1, y) THEN
  43.                             Array(x - 1, y) = np
  44.                             finished = 0
  45.                             x = x - 1
  46.                             IF x < MinX THEN MinX = x
  47.                             GOTO fill_left
  48.                         END IF
  49.                     END IF
  50.                 END IF
  51.             NEXT
  52.             FOR x = TMX TO TMX2
  53.                 IF Array(x, y) = pass THEN
  54.                     fill_right:
  55.                     IF x < _WIDTH - 2 THEN
  56.                         IF Array(x + 1, y) = S(x + 1, y) THEN
  57.                             Array(x + 1, y) = np
  58.                             finished = 0
  59.                             x = x + 1
  60.                             IF x > MaxX THEN MaxX = x
  61.                             GOTO fill_right
  62.                         END IF
  63.                     END IF
  64.                 END IF
  65.             NEXT
  66.         NEXT
  67.         FOR x = TMX TO TMX2
  68.             FOR y = TMY2 TO TMY STEP -1
  69.                 IF Array(x, y) = pass THEN
  70.                     fill_up:
  71.                     IF y > 0 THEN
  72.                         IF Array(x, y - 1) = S(x, y - 1) THEN
  73.                             Array(x, y - 1) = np
  74.                             finished = 0
  75.                             y = y - 1
  76.                             IF y < MinY THEN MinY = y
  77.                             GOTO fill_up
  78.                         END IF
  79.                     END IF
  80.                 END IF
  81.             NEXT
  82.             FOR y = TMY TO TMY2
  83.                 IF Array(x, y) = pass THEN
  84.                     fill_down:
  85.                     IF y < _HEIGHT - 2 THEN
  86.                         IF Array(x, y + 1) = S(x, y + 1) THEN
  87.                             Array(x, y + 1) = np
  88.                             finished = 0
  89.                             y = y + 1
  90.                             IF y > MaxY THEN MaxY = y
  91.                             GOTO fill_down
  92.                         END IF
  93.                     END IF
  94.                 END IF
  95.             NEXT
  96.         NEXT
  97.  
  98.         pass = pass + 1
  99.     LOOP UNTIL finished
  100.  
  101.  
  102.     FOR x = MinX TO MaxX
  103.         FOR y = MinY TO MaxY
  104.             IF Array(x, y) THEN PSET (x, y), kolor
  105.         NEXT
  106.     NEXT
  107.  
Title: Re: Steve's Magical Paint Fill
Post by: SMcNeill on November 23, 2019, 07:56:19 am
Cleaned up a bit, all variables defined so OPTION _EXPLICIT won't complain, here's a timed comparison of the routine vs PAINT:

Code: QB64: [Select]
  1.  
  2. SCREEN _NEWIMAGE(640, 480, 32)
  3.  
  4. t# = TIMER(0.01)
  5. FOR i = 1 TO 10
  6.     CLS
  7.     CIRCLE (320, 240), 200, -1
  8.     PAINT (320, 240), &HFFFF0000, -1
  9. t2# = TIMER(0.01)
  10. FOR i = 1 TO 10
  11.     CLS
  12.     CIRCLE (320, 240), 200, -1
  13.     fill 320, 240, &HFFFF0000, -1
  14. t3# = TIMER(0.01)
  15.  
  16. PRINT USING "##.### seconds with PAINT"; t2# - t#
  17. PRINT USING "##.### seconds with FILL"; t3# - t2#
  18.  
  19.  
  20. SUB fill (tx AS INTEGER, ty AS INTEGER, kolor AS _UNSIGNED LONG, bordercolor AS _UNSIGNED LONG)
  21.     DIM x AS INTEGER, y AS INTEGER
  22.     DIM W AS INTEGER, H AS INTEGER
  23.     DIM pass AS INTEGER, finished AS INTEGER, np AS INTEGER
  24.     DIM TMX AS INTEGER, TMX2 AS INTEGER
  25.     DIM TMY AS INTEGER, TMY2 AS INTEGER
  26.     DIM left AS INTEGER, x1 AS INTEGER, y1 AS INTEGER
  27.     DIM MinX AS INTEGER, MinY AS INTEGER
  28.     DIM MaxX AS INTEGER, MaxY AS INTEGER
  29.  
  30.     x = tx: y = ty
  31.  
  32.     W = _WIDTH: H = _HEIGHT
  33.     DIM Array(W, H) 'AS INTEGER
  34.     DIM S(W, H) 'AS INTEGER
  35.     STATIC M AS _MEM: M = _MEMIMAGE(_DEST)
  36.     FOR x1 = 0 TO W - 1
  37.         FOR y1 = 0 TO H - 1
  38.             IF _MEMGET(M, M.OFFSET + (y1 * W + x1) * 4, _UNSIGNED LONG) = bordercolor THEN S(x1, y1) = -1 'MRM replacement for point below
  39.             'IF POINT(x1, y1) = bordercolor THEN S(x1, y1) = -1 'This is actually Sneaky Steve Logic at its best!
  40.             'Here we're checking to see if our array matches the proper border color or not.
  41.             'If it doesn't, then it might be a spot to fill (which is 0 -- the same as our inital Array()).
  42.         NEXT
  43.     NEXT
  44.     MinX = x: MinY = y
  45.     MaxX = x: MaxY = y
  46.     Array(x, y) = 1
  47.     pass = 1
  48.     DO
  49.         finished = -1
  50.         np = pass + 1 'next pass
  51.         TMX = MinX: TMX2 = MaxX
  52.         TMY = MinY: TMY2 = MaxY
  53.         FOR y = TMY TO TMY2
  54.             FOR x = TMX2 TO TMX STEP -1
  55.                 IF Array(x, y) = pass THEN
  56.                     fill_left:
  57.                     IF x > 0 THEN
  58.                         IF Array(x - 1, y) = S(x - 1, y) THEN
  59.                             Array(x - 1, y) = np
  60.                             finished = 0
  61.                             x = x - 1
  62.                             IF x < MinX THEN MinX = x
  63.                             GOTO fill_left
  64.                         END IF
  65.                     END IF
  66.                 END IF
  67.             NEXT
  68.             FOR x = TMX TO TMX2
  69.                 IF Array(x, y) = pass THEN
  70.                     fill_right:
  71.                     IF x < W - 2 THEN
  72.                         IF Array(x + 1, y) = S(x + 1, y) THEN
  73.                             Array(x + 1, y) = np
  74.                             finished = 0
  75.                             x = x + 1
  76.                             IF x > MaxX THEN MaxX = x
  77.                             GOTO fill_right
  78.                         END IF
  79.                     END IF
  80.                 END IF
  81.             NEXT
  82.         NEXT
  83.         FOR x = TMX TO TMX2
  84.             FOR y = TMY2 TO TMY STEP -1
  85.                 IF Array(x, y) = pass THEN
  86.                     fill_up:
  87.                     IF y > 0 THEN
  88.                         IF Array(x, y - 1) = S(x, y - 1) THEN
  89.                             Array(x, y - 1) = np
  90.                             finished = 0
  91.                             y = y - 1
  92.                             IF y < MinY THEN MinY = y
  93.                             GOTO fill_up
  94.                         END IF
  95.                     END IF
  96.                 END IF
  97.             NEXT
  98.             FOR y = TMY TO TMY2
  99.                 IF Array(x, y) = pass THEN
  100.                     fill_down:
  101.                     IF y < H - 2 THEN
  102.                         IF Array(x, y + 1) = S(x, y + 1) THEN
  103.                             Array(x, y + 1) = np
  104.                             finished = 0
  105.                             y = y + 1
  106.                             IF y > MaxY THEN MaxY = y
  107.                             GOTO fill_down
  108.                         END IF
  109.                     END IF
  110.                 END IF
  111.             NEXT
  112.         NEXT
  113.         pass = pass + 1
  114.     LOOP UNTIL finished
  115.  
  116.     FOR y = MinY TO MaxY
  117.         FOR x = MinX TO MaxX
  118.             IF Array(x, y) THEN 'PSET (x, y), kolor
  119.                 IF left = 0 THEN left = x
  120.             ELSE
  121.                 IF left THEN LINE (left, y)-(x - 1, y), kolor, BF: left = 0
  122.             END IF
  123.         NEXT
  124.         IF left THEN LINE (left, y)-(x - 1, y), kolor, BF: left = 0
  125.     NEXT

A lot of work to create something which is 4-5 times slower than what we already have, but I'm rather happy with it. 

A few decent points in this one's corner:

This isn't recursive, so it shouldn't ever generate those memory/stack crashes that other experiments with recursive paint fills have.

This could be easily customized to work with Petr's or Bplus's image fill routines, or adapted for use with textures and such.

If someone really needed it to be faster still, they could go ahead and swap everything over to _MEM calls instead.  I think in the end, it'd be comparable in speed to our current PAINT speed, (or maybe even faster as _MEM is often 10x faster than non-mem graphics commands,) but I'm too lazy at the moment to do that.  As it currently exists is good enough for me.  ;)
Title: Re: Steve's Magical Paint Fill
Post by: SMcNeill on November 23, 2019, 08:22:17 am
What was causing the magic jump?

I wasn't checking to make certain that we were only expanding upon points found in our previous pass.  ( IF Array(x, y) = pass THEN )

I'm pretty happy with the lessons I taught myself with this one, and here's one you might like to take advantage of with your pathfinding algorithms Bplus:

Let's take a normal 10x10 grid and work some pathfinding on it as we have on the past.  Imagine the starting point is in the center, and we want to know how far it is to reach any other point.

PASS 1:
0000000000
0000000000
0000000000
0000000000
0000100000
0000000000
0000000000
0000000000
0000000000
0000000000

PASS 2:
0000000000
0000000000
0000000000
0000200000
0002120000
0000200000
0000000000
0000000000
0000000000
0000000000

PASS 3:
0000000000
0000000000
0000300000
0003230000
0032123000
0003230000
0000300000
0000000000
0000000000
0000000000

With each process, we've been checking the whole array and incrementing the surrounding points if they match our current pass...

My EUREKA moment, which really changes the performance levels of this type of work, came with the complexity of using PAINT with pathfinding on the whole screen.  That's a TON of pixels to check each pass...

Instead, what I'm doing here is this leap of logic:

PASS 1
1

PASS 2
020
212
020

PASS 3
00300
03230
32123
03230
00300

Here, I set MinX to 1 less, MaxX to 1 more, MinY to 1 less, MaxY to 1 more each pass.  I don't check the whole array each time around; I only check to the points which are relevant and possible on this given pass.

On Pass 3, why do I need to check point (0,0), if my hero is starting at point(10,10)??

Once I came to this little revelation in logic, I could ignore checking a large portion of my screen and times improved dramatically, and I see no reason why this same logic wouldn't apply to the way we've been doing pathfinding with 2D arrays either.

Only check the area you need to check; no more, no less.

******************

I think we can also eliminate checking a whole swath of points each pass, if we ONLY bother to check the outer rows like this, but I haven't implemented it yet:

For example, take a look at PASS 3:
PASS 3
00300
03230
32123
03230
00300

I don't see any reason why we couldn't exclude the following on our next pass:
00300
0XXX0
3XXX3
0XXX0
00300

There should be some simple formula we could plug in to say IF X > this point AND X < that point and Y > this point and Y < that point THEN we don't need to check these values... Once that's sorted out and plugged in, the larger the pathfinding gets, the more of the results we can exclude from checking over and over and over again...

I imagine it'd make as large of a leap in performance as the first EUREKA moment of only checking MinX to MaxX and MinY to MaxY did.  I just haven't sorted out the math needed for the exclusion yet, but my mind is visualizing the concept fairly nicely at least.  ;)

EDIT:

(This might be as simple as a (PASS \ 2 -1 ) type exception.  I need more coffee and a lot of testing with the concept before I'd swear to it, but I'm thinking it'll fit our pattern for segments we can safely exclude.) 
Title: Re: Steve's Magical Paint Fill
Post by: bplus on November 23, 2019, 10:42:03 am
Dang Steve, that's lightning fast compared to my Fill routine tests, like 100 x's.

I've been expanding out from PAINT point all along since Pathfinder, something else is making this faster.

$CHECKING ON/OFF is not it, not much difference with or without.

I will have to study more, nice one Steve!

I hope your wife is doing better,
Mark

PS here is my test code, same as I was running times on with my Fill routine, mine was down to 8 secs, yours .1... wow! And does work fine with OPTION _EXPLICIT.
Code: QB64: [Select]
  1. OPTION _EXPLICIT ''Fill test by Steve routine  2019-11-22 mod to compare tp test times of mine
  2. _TITLE "PathFinder Paint mod" 'b+ 2019-11-23
  3. 'start code from PathFinder Paint mod
  4. DEFINT A-Z
  5. CONST xmax = 800, ymax = 600
  6. SCREEN _NEWIMAGE(xmax, ymax, 32)
  7. _SCREENMOVE 300, 40
  8. DIM bc AS _UNSIGNED LONG, start#
  9.  
  10. start# = TIMER
  11. bc = &HFFFF0000
  12. CIRCLE (500, 400), 100, bc
  13. fill 510, 400, &HFFFFFF00, bc
  14.  
  15. CIRCLE (xmax - 1, ymax - 1), 400, bc
  16. fill xmax - 10, ymax - 10, &HFFFF0088, bc
  17.  
  18. LINE (100, 100)-(500, 500), bc, B
  19. fill 150, 150, &HFFFF0000, bc
  20. PRINT TIMER - start#
  21.  

Yours also handles that bottom right corner.

Oh!  I don't think skipping inner rechecks will work for more complicated Fills, you need to go back in and check nooks and crannies missed or left unfinished in previous passes. I will work up a more rigorous test (but I've yet to learn why this is so fast).

Title: Re: Steve's Magical Paint Fill
Post by: SMcNeill on November 23, 2019, 10:59:07 am
There's a couple of more tricks in here which improve performance.

Trick 2 is expanding to the limits each pass.  If I go back to a 10x10 grid to illustrate, let's let B represent the border and fill from some point in the middle:


PASS 1:
BBBBBBBBBB
B00000000B
B00000000B
B00000000B
B00000000B
B00010000B
B00000000B
B00000000B
B00000000B
BBBBBBBBBB

PASS 2:
BBBBBBBBBB
B00020000B
B00020000B
B00020000B
B00020000B
B22212222B
B00020000B
B00020000B
B00020000B
BBBBBBBBBB

PASS 3:
BBBBBBBBBB
B33323333B
B33323333B
B33323333B
B33323333B
B22212222B
B33323333B
B33323333B
B33323333B
BBBBBBBBBB


Three passes, and we're finished.  MinX, MaxX, MinY and MaxY expand as we push our boundaries, and we only make a few runs through the whole DO... LOOP until we're finished.
Title: Re: Steve's Magical Paint Fill
Post by: bplus on November 23, 2019, 11:07:44 am
Oh so 2 expands out x, y directions from 1, and 3 expands out each of level 2 cells, 3 passes that's it! that's the new one to me, thanks.

I was thinking a maze fill would be perfect test for nook and cranny catching.
Title: Re: Steve's Magical Paint Fill
Post by: SMcNeill on November 23, 2019, 11:19:06 am
Trick #3 is this one, but I think it's the hardest to explain.  Let me know if this explaination doesn't make any sense to you.  The super secret code is here:

Code: [Select]
    FOR x1 = 0 TO W - 1
        FOR y1 = 0 TO H - 1
            IF _MEMGET(M, M.OFFSET + (y1 * W + x1) * 4, _UNSIGNED LONG) = bordercolor THEN S(x1, y1) = -1 'MRM replacement for point below
            'IF POINT(x1, y1) = bordercolor THEN S(x1, y1) = -1 'This is actually Sneaky Steve Logic at its best!
            'Here we're checking to see if our array matches the proper border color or not.
            'If it doesn't, then it might be a spot to fill (which is 0 -- the same as our inital Array()).
        NEXT
    NEXT

We're not actually plotting to the screen as we go along; instead we're storing our changes in an array and then implementing them all at once when we're finished.  This avoids us having to PSET point by point, and then get information back from each POINT to see if colors match.

Array() is the array which contains the information about what I want to change, or not.
S() is the array to store the screen information once, so I don't have to use POINT over and over.

And the little code above prepares the routine for a little tricky logic -- it eliminates the need for us to check colors at all!!

If this case, S() compares pixel by pixel ONCE to see which points on our screen are the border colors.  Those are *the only* colors we care about.  It doesn't matter if a point is Red, Blue, or Green, if we're painting until we reach White, we cover all those up...  We can turn this array into a simple binary array of "YES, this point is the border color", or "NO, this point isn't the border color."

Now, since Array() is going to be our array to hold our changes, it starts out as being all values of ZERO.

We set our PASS to 1, and make the center point we want to fill = PASS.

At this point, the program then starts the DO... LOOP process:

DO
    check each point to if they're equal to PASS.
        IF they are, then check to see if the points beside them are EQUAL TO Array() at the same point... 
            IF they are, make them EQUAL PASS and continue to check the points along the same axis... 
LOOP

As we change our Array(), keep in mind that unaltered points have a value of 0...
And we set S() so that NON-border colors have a value of 0...

Only IF Array(x,y) = S(x,y) is it a point to fill in!!

One comparison which we have to do over and over, simplified down as much as I could figure out how to simplify it....


Compare it to what I was checking for over in the version I posted in your paint fill topic:

 IF Array(x, y - 1) = 0 AND POINT(x, y - 1) <> backkolor THEN Array(x, y - 1) = pass + 1: finished = 0

All that comparison in red was taken care of once, in the precalculations for me.  All I need to know is now:

IF Array(x, y - 1) = S(x, y -1) THEN...



If that makes any sense at all??
Title: Re: Steve's Magical Paint Fill
Post by: bplus on November 23, 2019, 11:38:40 am
Make sense?

A little, amazing trickery there Steve, tricks upon tricks, but doing things only once makes allot of sense like reading POINTs off screen and checking around for connecting neighbors. Another great reading job by bplus who totally missed the MEM part but glad you explained in English what I was supposed to be getting from code.

I'm afraid I don't understand it enough to make any prediction about what will happen when you try the skipping scheme.

I am eager to test this on a maze fill, a maze with 1 pixel passage ways? ;-)
Title: Re: Steve's Magical Paint Fill
Post by: SMcNeill on November 23, 2019, 11:45:07 am
Make sense?

A little, amazing trickery there Steve, tricks upon tricks, but doing things only once makes allot of sense like reading POINTs off screen and checking around for connecting neighbors. Another great reading job by bplus who totally missed the MEM part but glad you explained in English what I was supposed to be getting from code.

I'm afraid I don't understand it enough to make any prediction about what will happen when you try the skipping scheme.

I am eager to test this on a maze fill, a maze with 1 pixel passage ways? ;-)

Sounds fine.  I don't think it should have any trouble filling in the whole maze for you.  I just hope nobody fusses over the use of the dreaded GOTO in the code.  Everyone says that there's never any use for it in modern languages, but my brain just can't decipher a pretty way to sort out the logic which is any better than this:
Code: [Select]
               IF Array(x, y) = pass THEN
                    fill_left:
                    IF x > 0 THEN
                        IF Array(x - 1, y) = S(x - 1, y) THEN
                            Array(x - 1, y) = np
                            finished = 0
                            x = x - 1
                            IF x < MinX THEN MinX = x
                            GOTO fill_left
                        END IF
                    END IF
                END IF
Title: Re: Steve's Magical Paint Fill
Post by: SMcNeill on November 23, 2019, 11:51:45 am
I'm afraid I don't understand it enough to make any prediction about what will happen when you try the skipping scheme.

I imagine you're correct.  We can't really skip based on the simple idea I had before.  Even though a point is only a few pixels away from our starting position, it might be the very last point we color in, in a maze-like situation.  It's not going to be something as simple as "after X passes, we can rule it out"...  I think the way it is, is the way it's going to have to stay.  The only optimizing I can see that I could do to it now is to just convert the whole thing over to _MEM to speed it up, and I don't know if my brain is up to that math at the moment.  :P
Title: Re: Steve's Magical Paint Fill
Post by: SMcNeill on November 23, 2019, 12:07:05 pm
Here's a little test code, which should answer your question about, "Will it handle single pixel maze fills?"  I can't imagine something getting much more complicated for the routine than this for filling:

Code: QB64: [Select]
  1. SCREEN _NEWIMAGE(800, 600, 32)
  2.  
  3. 'make a maze to fill
  4. FOR i = 1 TO 100
  5.     dir = INT(RND * 2) - 1 '0 or 1
  6.     IF dir THEN
  7.         LINE (RND * 800, RND * 600)-STEP(RND * 800, 0), &HFF0000FF
  8.     ELSE
  9.         LINE (RND * 800, RND * 600)-STEP(0, RND * 600), &HFF0000FF
  10.     END IF
  11.  
  12. FOR x = 0 TO _WIDTH - 1
  13.     FOR y = 0 TO _HEIGHT - 1
  14.         IF POINT(x, y) = &HFF0000FF~& GOTO done 'find a point which is on one of those lines
  15.     NEXT
  16.  
  17. done:
  18.  
  19. SLEEP 'pause for a keypress
  20.  
  21.  
  22. fill x, y, &HFFFF0000, 0 'then fill them in
  23.  
  24. SUB fill (tx AS INTEGER, ty AS INTEGER, kolor AS _UNSIGNED LONG, bordercolor AS _UNSIGNED LONG)
  25.     DIM x AS INTEGER, y AS INTEGER
  26.     DIM W AS INTEGER, H AS INTEGER
  27.     DIM pass AS INTEGER, finished AS INTEGER, np AS INTEGER
  28.     DIM TMX AS INTEGER, TMX2 AS INTEGER
  29.     DIM TMY AS INTEGER, TMY2 AS INTEGER
  30.     DIM left AS INTEGER, x1 AS INTEGER, y1 AS INTEGER
  31.     DIM MinX AS INTEGER, MinY AS INTEGER
  32.     DIM MaxX AS INTEGER, MaxY AS INTEGER
  33.  
  34.     x = tx: y = ty
  35.  
  36.     W = _WIDTH: H = _HEIGHT
  37.     DIM Array(W, H) 'AS INTEGER
  38.     DIM S(W, H) 'AS INTEGER
  39.     STATIC M AS _MEM: M = _MEMIMAGE(_DEST)
  40.     FOR x1 = 0 TO W - 1
  41.         FOR y1 = 0 TO H - 1
  42.             IF _MEMGET(M, M.OFFSET + (y1 * W + x1) * 4, _UNSIGNED LONG) = bordercolor THEN S(x1, y1) = -1 'MRM replacement for point below
  43.             'IF POINT(x1, y1) = bordercolor THEN S(x1, y1) = -1 'This is actually Sneaky Steve Logic at its best!
  44.             'Here we're checking to see if our array matches the proper border color or not.
  45.             'If it doesn't, then it might be a spot to fill (which is 0 -- the same as our inital Array()).
  46.         NEXT
  47.     NEXT
  48.     MinX = x: MinY = y
  49.     MaxX = x: MaxY = y
  50.     Array(x, y) = 1
  51.     pass = 1
  52.     DO
  53.         finished = -1
  54.         np = pass + 1 'next pass
  55.         TMX = MinX: TMX2 = MaxX
  56.         TMY = MinY: TMY2 = MaxY
  57.         FOR y = TMY TO TMY2
  58.             FOR x = TMX2 TO TMX STEP -1
  59.                 IF Array(x, y) = pass THEN
  60.                     fill_left:
  61.                     IF x > 0 THEN
  62.                         IF Array(x - 1, y) = S(x - 1, y) THEN
  63.                             Array(x - 1, y) = np
  64.                             finished = 0
  65.                             x = x - 1
  66.                             IF x < MinX THEN MinX = x
  67.                             GOTO fill_left
  68.                         END IF
  69.                     END IF
  70.                 END IF
  71.             NEXT
  72.             FOR x = TMX TO TMX2
  73.                 IF Array(x, y) = pass THEN
  74.                     fill_right:
  75.                     IF x < W - 2 THEN
  76.                         IF Array(x + 1, y) = S(x + 1, y) THEN
  77.                             Array(x + 1, y) = np
  78.                             finished = 0
  79.                             x = x + 1
  80.                             IF x > MaxX THEN MaxX = x
  81.                             GOTO fill_right
  82.                         END IF
  83.                     END IF
  84.                 END IF
  85.             NEXT
  86.         NEXT
  87.         FOR x = TMX TO TMX2
  88.             FOR y = TMY2 TO TMY STEP -1
  89.                 IF Array(x, y) = pass THEN
  90.                     fill_up:
  91.                     IF y > 0 THEN
  92.                         IF Array(x, y - 1) = S(x, y - 1) THEN
  93.                             Array(x, y - 1) = np
  94.                             finished = 0
  95.                             y = y - 1
  96.                             IF y < MinY THEN MinY = y
  97.                             GOTO fill_up
  98.                         END IF
  99.                     END IF
  100.                 END IF
  101.             NEXT
  102.             FOR y = TMY TO TMY2
  103.                 IF Array(x, y) = pass THEN
  104.                     fill_down:
  105.                     IF y < H - 2 THEN
  106.                         IF Array(x, y + 1) = S(x, y + 1) THEN
  107.                             Array(x, y + 1) = np
  108.                             finished = 0
  109.                             y = y + 1
  110.                             IF y > MaxY THEN MaxY = y
  111.                             GOTO fill_down
  112.                         END IF
  113.                     END IF
  114.                 END IF
  115.             NEXT
  116.         NEXT
  117.         pass = pass + 1
  118.     LOOP UNTIL finished
  119.  
  120.     FOR y = MinY TO MaxY
  121.         FOR x = MinX TO MaxX
  122.             IF Array(x, y) THEN 'PSET (x, y), kolor
  123.                 IF left = 0 THEN left = x
  124.             ELSE
  125.                 IF left THEN LINE (left, y)-(x - 1, y), kolor, BF: left = 0
  126.             END IF
  127.         NEXT
  128.         IF left THEN LINE (left, y)-(x - 1, y), kolor, BF: left = 0
  129.     NEXT
  130.  

EDIT:

Modified below to allow for multiple runs, in case your first try gives you a single line which isn't connected to the main grid -- it happens more often than I would've expected!

Code: QB64: [Select]
  1. SCREEN _NEWIMAGE(800, 600, 32)
  2.  
  3.     CLS , 0
  4.     'make a maze to fill
  5.     FOR i = 1 TO 200
  6.         dir = INT(RND * 2) - 1 '0 or 1
  7.         IF dir THEN
  8.             LINE (RND * 400, RND * 600)-STEP(RND * 800, 0), &HFF0000FF
  9.         ELSE
  10.             LINE (RND * 800, RND * 600)-STEP(0, RND * 600), &HFF0000FF
  11.         END IF
  12.     NEXT
  13.  
  14.     FOR x = 0 TO _WIDTH - 1
  15.         FOR y = 0 TO _HEIGHT - 1
  16.             IF POINT(x, y) = &HFF0000FF~& GOTO done 'find a point which is on one of those lines
  17.         NEXT
  18.     NEXT
  19.     done:
  20.  
  21.     SLEEP 'pause for a keypress
  22.  
  23.     fill x, y, &HFFFF0000, 0 'then fill them in
  24.     SLEEP
  25.  
  26. SUB fill (tx AS INTEGER, ty AS INTEGER, kolor AS _UNSIGNED LONG, bordercolor AS _UNSIGNED LONG)
  27.     DIM x AS INTEGER, y AS INTEGER
  28.     DIM W AS INTEGER, H AS INTEGER
  29.     DIM pass AS INTEGER, finished AS INTEGER, np AS INTEGER
  30.     DIM TMX AS INTEGER, TMX2 AS INTEGER
  31.     DIM TMY AS INTEGER, TMY2 AS INTEGER
  32.     DIM left AS INTEGER, x1 AS INTEGER, y1 AS INTEGER
  33.     DIM MinX AS INTEGER, MinY AS INTEGER
  34.     DIM MaxX AS INTEGER, MaxY AS INTEGER
  35.  
  36.     x = tx: y = ty
  37.  
  38.     W = _WIDTH: H = _HEIGHT
  39.     DIM Array(W, H) 'AS INTEGER
  40.     DIM S(W, H) 'AS INTEGER
  41.     STATIC M AS _MEM: M = _MEMIMAGE(_DEST)
  42.     FOR x1 = 0 TO W - 1
  43.         FOR y1 = 0 TO H - 1
  44.             IF _MEMGET(M, M.OFFSET + (y1 * W + x1) * 4, _UNSIGNED LONG) = bordercolor THEN S(x1, y1) = -1 'MRM replacement for point below
  45.             'IF POINT(x1, y1) = bordercolor THEN S(x1, y1) = -1 'This is actually Sneaky Steve Logic at its best!
  46.             'Here we're checking to see if our array matches the proper border color or not.
  47.             'If it doesn't, then it might be a spot to fill (which is 0 -- the same as our inital Array()).
  48.         NEXT
  49.     NEXT
  50.     MinX = x: MinY = y
  51.     MaxX = x: MaxY = y
  52.     Array(x, y) = 1
  53.     pass = 1
  54.     DO
  55.         finished = -1
  56.         np = pass + 1 'next pass
  57.         TMX = MinX: TMX2 = MaxX
  58.         TMY = MinY: TMY2 = MaxY
  59.         FOR y = TMY TO TMY2
  60.             FOR x = TMX2 TO TMX STEP -1
  61.                 IF Array(x, y) = pass THEN
  62.                     fill_left:
  63.                     IF x > 0 THEN
  64.                         IF Array(x - 1, y) = S(x - 1, y) THEN
  65.                             Array(x - 1, y) = np
  66.                             finished = 0
  67.                             x = x - 1
  68.                             IF x < MinX THEN MinX = x
  69.                             GOTO fill_left
  70.                         END IF
  71.                     END IF
  72.                 END IF
  73.             NEXT
  74.             FOR x = TMX TO TMX2
  75.                 IF Array(x, y) = pass THEN
  76.                     fill_right:
  77.                     IF x < W - 2 THEN
  78.                         IF Array(x + 1, y) = S(x + 1, y) THEN
  79.                             Array(x + 1, y) = np
  80.                             finished = 0
  81.                             x = x + 1
  82.                             IF x > MaxX THEN MaxX = x
  83.                             GOTO fill_right
  84.                         END IF
  85.                     END IF
  86.                 END IF
  87.             NEXT
  88.         NEXT
  89.         FOR x = TMX TO TMX2
  90.             FOR y = TMY2 TO TMY STEP -1
  91.                 IF Array(x, y) = pass THEN
  92.                     fill_up:
  93.                     IF y > 0 THEN
  94.                         IF Array(x, y - 1) = S(x, y - 1) THEN
  95.                             Array(x, y - 1) = np
  96.                             finished = 0
  97.                             y = y - 1
  98.                             IF y < MinY THEN MinY = y
  99.                             GOTO fill_up
  100.                         END IF
  101.                     END IF
  102.                 END IF
  103.             NEXT
  104.             FOR y = TMY TO TMY2
  105.                 IF Array(x, y) = pass THEN
  106.                     fill_down:
  107.                     IF y < H - 2 THEN
  108.                         IF Array(x, y + 1) = S(x, y + 1) THEN
  109.                             Array(x, y + 1) = np
  110.                             finished = 0
  111.                             y = y + 1
  112.                             IF y > MaxY THEN MaxY = y
  113.                             GOTO fill_down
  114.                         END IF
  115.                     END IF
  116.                 END IF
  117.             NEXT
  118.         NEXT
  119.         pass = pass + 1
  120.     LOOP UNTIL finished
  121.  
  122.     FOR y = MinY TO MaxY
  123.         FOR x = MinX TO MaxX
  124.             IF Array(x, y) THEN 'PSET (x, y), kolor
  125.                 IF left = 0 THEN left = x
  126.             ELSE
  127.                 IF left THEN LINE (left, y)-(x - 1, y), kolor, BF: left = 0
  128.             END IF
  129.         NEXT
  130.         IF left THEN LINE (left, y)-(x - 1, y), kolor, BF: left = 0
  131.     NEXT
  132.     PRINT pass; " passes to completion"
  133.  

What I find astonishing is that this never needs more than 8 or 9 passes to complete.  How the heck was we running out of stack space before, with the recursive calls to the paint fill routines??
Title: Re: Steve's Magical Paint Fill
Post by: bplus on November 23, 2019, 12:17:35 pm
Quote
I just hope nobody fusses over the use of the dreaded GOTO in the code.

Oh my the GOTO thing, what a joke, underneath everything the machine code is using GOTO all the time.

Sure GOTO can be abused and make code very hard to read, doesn't mean it should be forbidden or even bad form all the time. BTW it beats the heck out of a FOR loop in my timed tests.

LET It += Be ;-))
Title: Re: Steve's Magical Paint Fill
Post by: bplus on November 23, 2019, 12:26:24 pm
Quote
What I find astonishing is that this never needs more than 8 or 9 passes to complete.  How the heck was we running out of stack space before, with the recursive calls to the paint fill routines??

Because recursion has to work all the way to the end, pass #xxx, and then work it's way back to level #1 before going down another rabbit hole.

Your routine that cuts down the number of passes tremendously might make recursion possible?
Title: Re: Steve's Magical Paint Fill
Post by: bplus on November 23, 2019, 12:54:03 pm
Ha, Steve that test might be handy for finding non connected lines!
Title: Re: Steve's Magical Paint Fill
Post by: bplus on November 23, 2019, 04:33:26 pm
Wow PAINT is fast through the maze! For Steve's fill routine I had to draw as I go because it sure beats staring at a blank screen for the time it takes to run out the maze (at first I thought it wasn't even working!):
Code: QB64: [Select]
  1. _TITLE "Maze Generator to test Paint or Fills, press any to awaken from SLEEP, esc to quit" 'B+
  2. '2019-11-23 using Maze Generator to test Steve's nice fill routine posted 2019-11-23
  3.  
  4. ' 2019-09-02 isolated and updated generator code for OPTION _EXPLICIT
  5. ' from trans 2018-06-15 for Amazing Rat.bas (QB64)
  6. ' From SmallBASIC code written by Chris WS developer
  7. ' Backtracking maze generator by chrisws 2016-06-30 now found at
  8. ' https://github.com/smallbasic/smallbasic.github.io/blob/5601c8bc1d794c5b143d863555bb7c15a5966a3c/samples/node/1623.bas
  9. '
  10. ' Chris notes:
  11. ' https://en.wikipedia.org/wiki/Maze_generation_algorithm
  12. ' - Starting from a random cell,
  13. ' - Selects a random neighbouring cell that has not been visited.
  14. ' - Remove the wall between the two cells and marks the new cell as visited,
  15. '   and adds it to the stack to facilitate backtracking.
  16. ' - Continues with a cell that has no unvisited neighbours being considered a dead-end.
  17. '   When at a dead-end it backtracks through the path until it reaches a cell with an
  18. '   unvisited neighbour, continuing the path generation by visiting this new,
  19. '   unvisited cell (creating a new junction).
  20. '   This process continues until every cell has been visited, backtracking all the
  21. '   way back to the beginning cell. We can be sure every cell is visited.
  22. '
  23.  
  24. 'B+ notes for using:
  25. ' The most important item is that the maze uses 2 arrays one for vertical walls the other for horizontal
  26. ' CONST xmax, ymax is pixel size used in maze coder, using SW, SH for screen dimensions
  27. ' Maze should mount in top left corner of screen with min border space around it at left and top at least.
  28. ' CONST W, H - number of cells Wide and High you can specify.
  29. ' CONST wallThk - adjusts thickness of walls
  30. ' CONST mazeClr - colors walls made with BF in LINE statement
  31. ' CONST border - will create a space around the maze
  32. ' SHARED cellW, cellH - are pixels sizes for cell, see calcs before SCREEN command
  33. ' SHARED  h_walls(W, H) AS INTEGER, v_walls(W, H) AS INTEGER - these are your Maze, 0 no wall, 1 = wall
  34. ' When player occupies cell x, y that cell may v_wall that blocks player going left;
  35. ' a cell v_wall(x+1, y) = 1 will block a player going right;
  36. ' cell (x, y) may have an h_wall that stops player from going up;
  37. ' cell (x, y+1) may have h_wall that stops player at x, y from going down.
  38. ' Cells at (W, y) should not be occupied with W cells wide and array base 0 only W-1 can be occupied
  39. ' unless game needs something special.
  40. ' Likewise cells at (x, H) should only provide wall to stop player from going out of box.
  41. DEFINT A-Z
  42. CONST xmax = 801, ymax = 601, SW = 801, SH = 601 'maze pixels from 0,0 and screen SH, SW
  43. CONST W = 200, H = 150, border = 0, wallThk = 1 'maze cells wide and high
  44. CONST mazeClr = &HFFFF8800
  45.  
  46. TYPE cell
  47.     x AS INTEGER
  48.     y AS INTEGER
  49.  
  50. DIM SHARED cellW AS SINGLE, cellH AS SINGLE, h_walls(W, H) AS INTEGER, v_walls(W, H) AS INTEGER
  51. cellW = (xmax - 2 * border - wallThk) / W
  52. cellH = (ymax - 2 * border - wallThk) / H
  53.  
  54. SCREEN _NEWIMAGE(SW, SH, 32)
  55. _SCREENMOVE 100, 20
  56. WHILE _KEYDOWN(27) = 0
  57.     LINE (0, 0)-(xmax, ymax), &HFF000000, BF
  58.     init_walls
  59.     generate_maze
  60.     show_maze
  61.     'PSET (border + 0 * cellW + wallThk + 1, border + 0 * cellH + wallThk + 1), &HFFFFFFFF 'ok looks right
  62.     SLEEP
  63.     _KEYCLEAR
  64.     'first test with normal PAINT
  65.     'PAINT (border + 0 * cellW + wallThk + 1, border + 0 * cellH + wallThk + 1), &HFFFFFFFF, mazeClr
  66.     fill border + 0 * cellW + wallThk + 1, border + 0 * cellH + wallThk + 1, &HFFFFFFFF, &HFFFF8800
  67.     SLEEP
  68.     _KEYCLEAR
  69.  
  70. SUB init_walls ()
  71.     DIM x AS INTEGER, y AS INTEGER
  72.     FOR x = 0 TO W
  73.         FOR y = 0 TO H
  74.             v_walls(x, y) = 1
  75.             h_walls(x, y) = 1
  76.         NEXT
  77.     NEXT
  78.  
  79. SUB show_maze ()
  80.     DIM py AS SINGLE, px AS SINGLE, y AS INTEGER, x AS INTEGER
  81.     py = border
  82.     FOR y = 0 TO H
  83.         px = border
  84.         FOR x = 0 TO W
  85.             IF x < W AND h_walls(x, y) = 1 THEN
  86.                 LINE (px, py)-STEP(cellW + wallThk, wallThk), mazeClr, BF
  87.             END IF
  88.             IF y < H AND v_walls(x, y) = 1 THEN
  89.                 LINE (px, py)-STEP(wallThk, cellH + wallThk), mazeClr, BF
  90.             END IF
  91.             px = px + cellW
  92.         NEXT
  93.         py = py + cellH
  94.     NEXT
  95.  
  96. SUB rand_cell (rWx, rHy)
  97.     rWx = INT(RND * 1000) MOD W
  98.     rHy = INT(RND * 1000) MOD H
  99.  
  100. SUB get_unvisited (visited() AS INTEGER, current AS cell, unvisited() AS cell, uvi AS INTEGER)
  101.     REDIM unvisited(0) AS cell
  102.     DIM x AS INTEGER, y AS INTEGER
  103.     x = current.x
  104.     y = current.y
  105.     uvi = 0
  106.     IF x > 0 THEN
  107.         IF visited(x - 1, y) = 0 THEN
  108.             uvi = uvi + 1
  109.             REDIM _PRESERVE unvisited(uvi) AS cell
  110.             unvisited(uvi).x = x - 1
  111.             unvisited(uvi).y = y
  112.         END IF
  113.     END IF
  114.     IF x < W - 1 THEN
  115.         IF visited(x + 1, y) = 0 THEN
  116.             uvi = uvi + 1
  117.             REDIM _PRESERVE unvisited(uvi) AS cell
  118.             unvisited(uvi).x = x + 1
  119.             unvisited(uvi).y = y
  120.         END IF
  121.     END IF
  122.     IF y > 0 THEN
  123.         IF visited(x, y - 1) = 0 THEN
  124.             uvi = uvi + 1
  125.             REDIM _PRESERVE unvisited(uvi) AS cell
  126.             unvisited(uvi).x = x
  127.             unvisited(uvi).y = y - 1
  128.         END IF
  129.     END IF
  130.     IF y < H - 1 THEN
  131.         IF visited(x, y + 1) = 0 THEN
  132.             uvi = uvi + 1
  133.             REDIM _PRESERVE unvisited(uvi) AS cell
  134.             unvisited(uvi).x = x
  135.             unvisited(uvi).y = y + 1
  136.         END IF
  137.     END IF
  138.  
  139. SUB generate_maze ()
  140.     DIM visited(W, H) AS INTEGER
  141.     DIM num_visited AS INTEGER, num_cells AS INTEGER, si AS INTEGER
  142.     DIM cnt AS INTEGER, rc AS INTEGER, x AS INTEGER, y AS INTEGER
  143.     REDIM stack(0) AS cell
  144.     DIM curr_cell AS cell, next_cell AS cell, cur_cell AS cell
  145.  
  146.     rand_cell cur_cell.x, cur_cell.y
  147.     visited(curr_cell.x, curr_cell.y) = 1
  148.     num_visited = 1
  149.     num_cells = W * H
  150.     si = 0
  151.     WHILE num_visited < num_cells
  152.         REDIM cells(0) AS cell
  153.         cnt = 0
  154.         get_unvisited visited(), curr_cell, cells(), cnt
  155.         IF cnt > 0 THEN
  156.  
  157.             ' choose randomly one of the current cell's unvisited neighbours
  158.             rc = INT(RND * 100) MOD cnt + 1
  159.             next_cell.x = cells(rc).x
  160.             next_cell.y = cells(rc).y
  161.  
  162.             ' push the current cell to the stack
  163.             si = si + 1
  164.             REDIM _PRESERVE stack(si) AS cell
  165.             stack(si).x = curr_cell.x
  166.             stack(si).y = curr_cell.y
  167.  
  168.             ' remove the wall between the current cell and the chosen cell
  169.             IF next_cell.x = curr_cell.x THEN
  170.                 x = next_cell.x
  171.                 y = max(next_cell.y, curr_cell.y)
  172.                 h_walls(x, y) = 0
  173.             ELSE
  174.                 x = max(next_cell.x, curr_cell.x)
  175.                 y = next_cell.y
  176.                 v_walls(x, y) = 0
  177.             END IF
  178.  
  179.             ' make the chosen cell the current cell and mark it as visited
  180.             curr_cell.x = next_cell.x
  181.             curr_cell.y = next_cell.y
  182.             visited(curr_cell.x, curr_cell.y) = 1
  183.             num_visited = num_visited + 1
  184.  
  185.         ELSEIF si > 0 THEN
  186.  
  187.             ' pop a cell from the stack and make it the current cell
  188.             curr_cell.x = stack(si).x
  189.             curr_cell.y = stack(si).y
  190.             si = si - 1
  191.             REDIM _PRESERVE stack(si) AS cell
  192.  
  193.         ELSE
  194.             EXIT WHILE
  195.         END IF
  196.     WEND
  197.  
  198. FUNCTION max (a, b)
  199.     IF a > b THEN max = a ELSE max = b
  200.  
  201. SUB fill (tx AS INTEGER, ty AS INTEGER, kolor AS _UNSIGNED LONG, bordercolor AS _UNSIGNED LONG)
  202.     '''$CHECKING:OFF  '                                                                 <<<<<<<<<<<<<<<<< B+ mod
  203.     DIM x AS INTEGER, y AS INTEGER
  204.     DIM fillW AS INTEGER, fillH AS INTEGER  ' <<<<<<<<<<<<<<<< B+ mod already using W and H
  205.     DIM pass AS INTEGER, finished AS INTEGER, np AS INTEGER
  206.     DIM TMX AS INTEGER, TMX2 AS INTEGER
  207.     DIM TMY AS INTEGER, TMY2 AS INTEGER
  208.     DIM left AS INTEGER, x1 AS INTEGER, y1 AS INTEGER
  209.     DIM MinX AS INTEGER, MinY AS INTEGER
  210.     DIM MaxX AS INTEGER, MaxY AS INTEGER
  211.  
  212.     x = tx: y = ty
  213.  
  214.     fillW = _WIDTH: fillH = _HEIGHT
  215.     DIM Array(fillW, fillH) 'AS INTEGER
  216.     DIM S(fillW, fillH) 'AS INTEGER
  217.     STATIC M AS _MEM: M = _MEMIMAGE(_DEST)
  218.     FOR x1 = 0 TO fillW - 1
  219.         FOR y1 = 0 TO fillH - 1
  220.             IF _MEMGET(M, M.OFFSET + (y1 * fillW + x1) * 4, _UNSIGNED LONG) = bordercolor THEN S(x1, y1) = -1 'MRM replacement for point below
  221.             'IF POINT(x1, y1) = bordercolor THEN S(x1, y1) = -1 'This is actually Sneaky Steve Logic at its best!
  222.             'Here we're checking to see if our array matches the proper border color or not.
  223.             'If it doesn't, then it might be a spot to fill (which is 0 -- the same as our inital Array()).
  224.         NEXT
  225.     NEXT
  226.     MinX = x: MinY = y
  227.     MaxX = x: MaxY = y
  228.     Array(x, y) = 1: LINE (x, y)-STEP(0, 0), kolor, BF '                                   <<<<<<<<<<<<<<<<< B+ mod
  229.     pass = 1
  230.     DO
  231.         finished = -1
  232.         np = pass + 1 'next pass
  233.         TMX = MinX: TMX2 = MaxX
  234.         TMY = MinY: TMY2 = MaxY
  235.         FOR y = TMY TO TMY2
  236.             FOR x = TMX2 TO TMX STEP -1
  237.                 IF Array(x, y) = pass THEN
  238.                     fill_left:
  239.                     IF x > 0 THEN
  240.                         IF Array(x - 1, y) = S(x - 1, y) THEN
  241.                             Array(x - 1, y) = np
  242.                             finished = 0: LINE (x, y)-STEP(0, 0), kolor, BF '                     <<<<<<<<<<<<<<<<< B+ mod
  243.                             x = x - 1
  244.                             IF x < MinX THEN MinX = x
  245.                             GOTO fill_left
  246.                         END IF
  247.                     END IF
  248.                 END IF
  249.             NEXT
  250.             FOR x = TMX TO TMX2
  251.                 IF Array(x, y) = pass THEN
  252.                     fill_right:
  253.                     IF x < fillW - 2 THEN
  254.                         IF Array(x + 1, y) = S(x + 1, y) THEN
  255.                             Array(x + 1, y) = np
  256.                             finished = 0:: LINE (x, y)-STEP(0, 0), kolor, BF '                     <<<<<<<<<<<<<<<<< B+ mod
  257.                             x = x + 1
  258.                             IF x > MaxX THEN MaxX = x
  259.                             GOTO fill_right
  260.                         END IF
  261.                     END IF
  262.                 END IF
  263.             NEXT
  264.         NEXT
  265.         FOR x = TMX TO TMX2
  266.             FOR y = TMY2 TO TMY STEP -1
  267.                 IF Array(x, y) = pass THEN
  268.                     fill_up:
  269.                     IF y > 0 THEN
  270.                         IF Array(x, y - 1) = S(x, y - 1) THEN
  271.                             Array(x, y - 1) = np
  272.                             finished = 0:: LINE (x, y)-STEP(0, 0), kolor, BF '                     <<<<<<<<<<<<<<<<< B+ mod
  273.                             y = y - 1
  274.                             IF y < MinY THEN MinY = y
  275.                             GOTO fill_up
  276.                         END IF
  277.                     END IF
  278.                 END IF
  279.             NEXT
  280.             FOR y = TMY TO TMY2
  281.                 IF Array(x, y) = pass THEN
  282.                     fill_down:
  283.                     IF y < fillH - 2 THEN
  284.                         IF Array(x, y + 1) = S(x, y + 1) THEN
  285.                             Array(x, y + 1) = np
  286.                             finished = 0:: LINE (x, y)-STEP(0, 0), kolor, BF '                     <<<<<<<<<<<<<<<<< B+ mod
  287.                             y = y + 1
  288.                             IF y > MaxY THEN MaxY = y
  289.                             GOTO fill_down
  290.                         END IF
  291.                     END IF
  292.                 END IF
  293.             NEXT
  294.         NEXT
  295.         pass = pass + 1
  296.     LOOP UNTIL finished
  297.  
  298.     FOR y = MinY TO MaxY
  299.         FOR x = MinX TO MaxX
  300.             IF Array(x, y) THEN 'PSET (x, y), kolor
  301.                 IF left = 0 THEN left = x
  302.             ELSE
  303.                 IF left THEN LINE (left, y)-(x - 1, y), kolor, BF: left = 0
  304.             END IF
  305.         NEXT
  306.         IF left THEN LINE (left, y)-(x - 1, y), kolor, BF: left = 0
  307.     NEXT
  308.     '''$CHECKING:ON   '<<<<<<<<<<<<<<<<< B+ mod
  309.  
  310.  
  311.  

BTW couldn't get 1 pixel passages, got tired of trying, 2 pixels bad enough.
Title: Re: Steve's Magical Paint Fill
Post by: TempodiBasic on November 23, 2019, 06:12:34 pm
Hi
if you mind about GOTO here a version without GOTO:-)

Code: QB64: [Select]
  1. 'DIM c AS _UNSIGNED LONG
  2.  
  3. SCREEN _NEWIMAGE(640, 480, 32)
  4.  
  5. 'c = _RGBA32(127, 127, 127, 200)
  6. c = -1
  7. t# = TIMER(0.01)
  8. FOR i = 1 TO 10
  9.     CLS
  10.     CIRCLE (320, 240), 200, c
  11.     PAINT (320, 240), &HFFFF0000, c
  12. t2# = TIMER(0.01)
  13. FOR i = 1 TO 10
  14.     CLS
  15.     CIRCLE (320, 240), 200, c
  16.     fill 320, 240, &HFFFF0000, c
  17. t3# = TIMER(0.01)
  18.  
  19. PRINT USING "##.### seconds with PAINT"; t2# - t#
  20. PRINT USING "##.### seconds with FILL"; t3# - t2#
  21.  
  22.  
  23. SUB fill (tx AS INTEGER, ty AS INTEGER, kolor AS _UNSIGNED LONG, bordercolor AS _UNSIGNED LONG)
  24.     DIM x AS INTEGER, y AS INTEGER
  25.     DIM W AS INTEGER, H AS INTEGER
  26.     DIM pass AS INTEGER, finished AS INTEGER, np AS INTEGER
  27.     DIM TMX AS INTEGER, TMX2 AS INTEGER
  28.     DIM TMY AS INTEGER, TMY2 AS INTEGER
  29.     DIM left AS INTEGER, x1 AS INTEGER, y1 AS INTEGER
  30.     DIM MinX AS INTEGER, MinY AS INTEGER
  31.     DIM MaxX AS INTEGER, MaxY AS INTEGER
  32.  
  33.     x = tx: y = ty
  34.  
  35.     W = _WIDTH: H = _HEIGHT
  36.     DIM Array(W, H) 'AS INTEGER
  37.     DIM S(W, H) 'AS INTEGER
  38.     STATIC M AS _MEM: M = _MEMIMAGE(_DEST)
  39.     FOR x1 = 0 TO W - 1
  40.         FOR y1 = 0 TO H - 1
  41.             IF _MEMGET(M, M.OFFSET + (y1 * W + x1) * 4, _UNSIGNED LONG) = bordercolor THEN S(x1, y1) = -1 'MRM replacement for point below
  42.             'IF POINT(x1, y1) = bordercolor THEN S(x1, y1) = -1 'This is actually Sneaky Steve Logic at its best!
  43.             'Here we're checking to see if our array matches the proper border color or not.
  44.             'If it doesn't, then it might be a spot to fill (which is 0 -- the same as our inital Array()).
  45.         NEXT
  46.     NEXT
  47.     MinX = x: MinY = y
  48.     MaxX = x: MaxY = y
  49.     Array(x, y) = 1
  50.     pass = 1
  51.     DO
  52.         finished = -1
  53.         np = pass + 1 'next pass
  54.         TMX = MinX: TMX2 = MaxX
  55.         TMY = MinY: TMY2 = MaxY
  56.         FOR y = TMY TO TMY2
  57.             FOR x = TMX2 TO TMX STEP -1
  58.                 IF Array(x, y) = pass THEN
  59.                     '    fill_left:
  60.                     '    IF x > 0 THEN
  61.                     '        IF Array(x - 1, y) = S(x - 1, y) THEN
  62.                     '            Array(x - 1, y) = np
  63.                     '            finished = 0
  64.                     '            x = x - 1
  65.                     '            IF x < MinX THEN MinX = x
  66.                     '            GOTO fill_left
  67.                     '        END IF
  68.                     '    END IF
  69.                     DO WHILE x > 0
  70.                         IF Array(x - 1, y) = S(x - 1, y) THEN
  71.                             Array(x - 1, y) = np
  72.                             finished = 0
  73.                             x = x - 1
  74.                             IF x < MinX THEN MinX = x
  75.                         ELSE
  76.                             EXIT DO
  77.                         END IF
  78.                     LOOP
  79.                 END IF
  80.  
  81.             NEXT
  82.             FOR x = TMX TO TMX2
  83.                 IF Array(x, y) = pass THEN
  84.                     '    fill_right:
  85.                     '    IF x < W - 2 THEN
  86.                     '        IF Array(x + 1, y) = S(x + 1, y) THEN
  87.                     '            Array(x + 1, y) = np
  88.                     '            finished = 0
  89.                     '            x = x + 1
  90.                     '            IF x > MaxX THEN MaxX = x
  91.                     '            GOTO fill_right
  92.                     '        END IF
  93.                     '    END IF
  94.                     DO WHILE x < W - 2
  95.                         IF Array(x + 1, y) = S(x + 1, y) THEN
  96.                             Array(x + 1, y) = np
  97.                             finished = 0
  98.                             x = x + 1
  99.                             IF x > MaxX THEN MaxX = x
  100.                         ELSE
  101.                             EXIT DO
  102.                         END IF
  103.                     LOOP
  104.                 END IF
  105.             NEXT
  106.         NEXT
  107.         FOR x = TMX TO TMX2
  108.             FOR y = TMY2 TO TMY STEP -1
  109.                 IF Array(x, y) = pass THEN
  110.                     '    fill_up:
  111.                     '    IF y > 0 THEN
  112.                     '        IF Array(x, y - 1) = S(x, y - 1) THEN
  113.                     '            Array(x, y - 1) = np
  114.                     '            finished = 0
  115.                     '            y = y - 1
  116.                     '            IF y < MinY THEN MinY = y
  117.                     '            GOTO fill_up
  118.                     '        END IF
  119.                     DO WHILE y > 0
  120.                         IF Array(x, y - 1) = S(x, y - 1) THEN
  121.                             Array(x, y - 1) = np
  122.                             finished = 0
  123.                             y = y - 1
  124.                             IF y < MinY THEN MinY = y
  125.                         ELSE
  126.                             EXIT DO
  127.                         END IF
  128.                     LOOP
  129.                 END IF
  130.  
  131.  
  132.             NEXT
  133.             FOR y = TMY TO TMY2
  134.                 'IF Array(x, y) = pass THEN
  135.                 '    fill_down:
  136.                 '    IF y < H - 2 THEN
  137.                 '        IF Array(x, y + 1) = S(x, y + 1) THEN
  138.                 '            Array(x, y + 1) = np
  139.                 '            finished = 0
  140.                 '            y = y + 1
  141.                 '            IF y > MaxY THEN MaxY = y
  142.                 '            GOTO fill_down
  143.                 '        END IF
  144.                 '    END IF
  145.                 'END IF
  146.                 IF Array(x, y) = pass THEN
  147.                     DO WHILE y < H - 2
  148.                         IF Array(x, y + 1) = S(x, y + 1) THEN
  149.                             Array(x, y + 1) = np
  150.                             finished = 0
  151.                             y = y + 1
  152.                             IF y > MaxY THEN MaxY = y
  153.                         ELSE
  154.                             EXIT DO
  155.                         END IF
  156.                     LOOP
  157.                 END IF
  158.  
  159.             NEXT
  160.         NEXT
  161.         pass = pass + 1
  162.     LOOP UNTIL finished
  163.  
  164.     FOR y = MinY TO MaxY
  165.         FOR x = MinX TO MaxX
  166.             IF Array(x, y) THEN 'PSET (x, y), kolor
  167.                 IF left = 0 THEN left = x
  168.             ELSE
  169.                 IF left THEN LINE (left, y)-(x - 1, y), kolor, BF: left = 0
  170.             END IF
  171.         NEXT
  172.         IF left THEN LINE (left, y)-(x - 1, y), kolor, BF: left = 0
  173.     NEXT
  174.  
Title: Re: Steve's Magical Paint Fill
Post by: SMcNeill on November 23, 2019, 06:32:21 pm
Why EXIT DO there? 

                    DO
                        IF Array(x - 1, y) = S(x - 1, y) THEN
                            Array(x - 1, y) = np
                            finished = 0
                            x = x - 1
                            IF x < MinX THEN MinX = x
                        END IF
                    LOOP UNTIL X < = 0 OR Array(x - 1, y) <> S (x - 1, y)

Mind you, I don’t think it’s quite as easy to understand or follow (at least not for me, at least), but it does eliminate all evil GOTO and EXIT statements. 
Title: Re: Steve's Magical Paint Fill
Post by: TempodiBasic on November 23, 2019, 07:03:06 pm
OK it is shorter
but you assume that x is >0 the first run of loop!
You can decide this, because your algorithm is your idea, I dunno! :-)
Title: Re: Steve's Magical Paint Fill
Post by: SMcNeill on November 23, 2019, 07:12:10 pm
OK it is shorter
but you assume that x is >0 the first run of loop!
You can decide this, because your algorithm is your idea, I dunno! :-)

DO
  IF X > 0 THEN
      IF Array(x - 1, y) = S(x - 1, y) THEN
          Array(x - 1, y) = np
          finished = 0
          x = x - 1
          IF x < MinX THEN MinX = x
      END IF
  END IF
LOOP UNTIL X < = 0 OR Array(x - 1, y) <> S (x - 1, y)

There; corrected.  ;)
Title: Re: Steve's Magical Paint Fill
Post by: TempodiBasic on November 24, 2019, 10:01:19 am
Also this works using again WHILE instead of UNTIL and AND instead of OR

Code: QB64: [Select]
  1. 'DIM c AS _UNSIGNED LONG
  2.  
  3. SCREEN _NEWIMAGE(640, 480, 32)
  4.  
  5. 'c = _RGBA32(127, 127, 127, 200)
  6. c = -1
  7. t# = TIMER(0.01)
  8. FOR i = 1 TO 10
  9.     CLS
  10.     CIRCLE (320, 240), 200, c
  11.     PAINT (320, 240), &HFFFF0000, c
  12. t2# = TIMER(0.01)
  13. FOR i = 1 TO 10
  14.     CLS
  15.     CIRCLE (320, 240), 200, c
  16.     fill 320, 240, &HFFFF0000, c
  17. t3# = TIMER(0.01)
  18.  
  19. PRINT USING "##.### seconds with PAINT"; t2# - t#
  20. PRINT USING "##.### seconds with FILL"; t3# - t2#
  21.  
  22.  
  23. SUB fill (tx AS INTEGER, ty AS INTEGER, kolor AS _UNSIGNED LONG, bordercolor AS _UNSIGNED LONG)
  24.     DIM x AS INTEGER, y AS INTEGER
  25.     DIM W AS INTEGER, H AS INTEGER
  26.     DIM pass AS INTEGER, finished AS INTEGER, np AS INTEGER
  27.     DIM TMX AS INTEGER, TMX2 AS INTEGER
  28.     DIM TMY AS INTEGER, TMY2 AS INTEGER
  29.     DIM left AS INTEGER, x1 AS INTEGER, y1 AS INTEGER
  30.     DIM MinX AS INTEGER, MinY AS INTEGER
  31.     DIM MaxX AS INTEGER, MaxY AS INTEGER
  32.  
  33.     x = tx: y = ty
  34.  
  35.     W = _WIDTH: H = _HEIGHT
  36.     DIM Array(W, H) 'AS INTEGER
  37.     DIM S(W, H) 'AS INTEGER
  38.     STATIC M AS _MEM: M = _MEMIMAGE(_DEST)
  39.     FOR x1 = 0 TO W - 1
  40.         FOR y1 = 0 TO H - 1
  41.             IF _MEMGET(M, M.OFFSET + (y1 * W + x1) * 4, _UNSIGNED LONG) = bordercolor THEN S(x1, y1) = -1 'MRM replacement for point below
  42.             'IF POINT(x1, y1) = bordercolor THEN S(x1, y1) = -1 'This is actually Sneaky Steve Logic at its best!
  43.             'Here we're checking to see if our array matches the proper border color or not.
  44.             'If it doesn't, then it might be a spot to fill (which is 0 -- the same as our inital Array()).
  45.         NEXT
  46.     NEXT
  47.     MinX = x: MinY = y
  48.     MaxX = x: MaxY = y
  49.     Array(x, y) = 1
  50.     pass = 1
  51.     DO
  52.         finished = -1
  53.         np = pass + 1 'next pass
  54.         TMX = MinX: TMX2 = MaxX
  55.         TMY = MinY: TMY2 = MaxY
  56.         FOR y = TMY TO TMY2
  57.             FOR x = TMX2 TO TMX STEP -1
  58.                 IF Array(x, y) = pass THEN
  59.                     '    fill_left:
  60.                     '    IF x > 0 THEN
  61.                     '        IF Array(x - 1, y) = S(x - 1, y) THEN
  62.                     '            Array(x - 1, y) = np
  63.                     '            finished = 0
  64.                     '            x = x - 1
  65.                     '            IF x < MinX THEN MinX = x
  66.                     '            GOTO fill_left
  67.                     '        END IF
  68.                     '    END IF
  69.                     DO WHILE x > 0 AND Array(x - 1, y) = S(x - 1, y)
  70.                         '                        IF Array(x - 1, y) = S(x - 1, y) THEN
  71.                         Array(x - 1, y) = np
  72.                         finished = 0
  73.                         x = x - 1
  74.                         IF x < MinX THEN MinX = x
  75.                         '                    ELSE
  76.                         '                        EXIT DO
  77.                         '                        END IF
  78.                     LOOP
  79.                 END IF
  80.  
  81.             NEXT
  82.             FOR x = TMX TO TMX2
  83.                 IF Array(x, y) = pass THEN
  84.                     '    fill_right:
  85.                     '    IF x < W - 2 THEN
  86.                     '        IF Array(x + 1, y) = S(x + 1, y) THEN
  87.                     '            Array(x + 1, y) = np
  88.                     '            finished = 0
  89.                     '            x = x + 1
  90.                     '            IF x > MaxX THEN MaxX = x
  91.                     '            GOTO fill_right
  92.                     '        END IF
  93.                     '    END IF
  94.                     DO WHILE x < W - 2 AND Array(x + 1, y) = S(x + 1, y)
  95.                         '                        IF Array(x + 1, y) = S(x + 1, y) THEN
  96.                         Array(x + 1, y) = np
  97.                         finished = 0
  98.                         x = x + 1
  99.                         IF x > MaxX THEN MaxX = x
  100.                         '                       ELSE
  101.                         '                          EXIT DO
  102.                         '                     END IF
  103.                     LOOP
  104.                 END IF
  105.             NEXT
  106.         NEXT
  107.         FOR x = TMX TO TMX2
  108.             FOR y = TMY2 TO TMY STEP -1
  109.                 IF Array(x, y) = pass THEN
  110.                     '    fill_up:
  111.                     '    IF y > 0 THEN
  112.                     '        IF Array(x, y - 1) = S(x, y - 1) THEN
  113.                     '            Array(x, y - 1) = np
  114.                     '            finished = 0
  115.                     '            y = y - 1
  116.                     '            IF y < MinY THEN MinY = y
  117.                     '            GOTO fill_up
  118.                     '        END IF
  119.                     DO WHILE y > 0 AND Array(x, y - 1) = S(x, y - 1)
  120.                         '                        IF Array(x, y - 1) = S(x, y - 1) THEN
  121.                         Array(x, y - 1) = np
  122.                         finished = 0
  123.                         y = y - 1
  124.                         IF y < MinY THEN MinY = y
  125.                         '                       ELSE
  126.                         '                          EXIT DO
  127.                         '                     END IF
  128.                     LOOP
  129.                 END IF
  130.  
  131.  
  132.             NEXT
  133.             FOR y = TMY TO TMY2
  134.                 'IF Array(x, y) = pass THEN
  135.                 '    fill_down:
  136.                 '    IF y < H - 2 THEN
  137.                 '        IF Array(x, y + 1) = S(x, y + 1) THEN
  138.                 '            Array(x, y + 1) = np
  139.                 '            finished = 0
  140.                 '            y = y + 1
  141.                 '            IF y > MaxY THEN MaxY = y
  142.                 '            GOTO fill_down
  143.                 '        END IF
  144.                 '    END IF
  145.                 'END IF
  146.                 IF Array(x, y) = pass THEN
  147.                     DO WHILE y < H - 2 AND Array(x, y + 1) = S(x, y + 1)
  148.                         '                        IF Array(x, y + 1) = S(x, y + 1) THEN
  149.                         Array(x, y + 1) = np
  150.                         finished = 0
  151.                         y = y + 1
  152.                         IF y > MaxY THEN MaxY = y
  153.                         '                       ELSE
  154.                         '                      EXIT DO
  155.                         '                     END IF
  156.                     LOOP
  157.                 END IF
  158.  
  159.             NEXT
  160.         NEXT
  161.         pass = pass + 1
  162.     LOOP UNTIL finished
  163.  
  164.     FOR y = MinY TO MaxY
  165.         FOR x = MinX TO MaxX
  166.             IF Array(x, y) THEN 'PSET (x, y), kolor
  167.                 IF left = 0 THEN left = x
  168.             ELSE
  169.                 IF left THEN LINE (left, y)-(x - 1, y), kolor, BF: left = 0
  170.             END IF
  171.         NEXT
  172.         IF left THEN LINE (left, y)-(x - 1, y), kolor, BF: left = 0
  173.     NEXT
  174.  

focusing
at place of GOTO label loop
Code: QB64: [Select]
  1.                 IF Array(x, y) = pass THEN
  2.                     fill_down:
  3.                     IF y < H - 2 THEN
  4.                         IF Array(x, y + 1) = S(x, y + 1) THEN
  5.                             Array(x, y + 1) = np
  6.                             finished = 0
  7.                             y = y + 1
  8.                             IF y > MaxY THEN MaxY = y
  9.                             GOTO fill_down
  10.                         END IF
  11.                     END IF
  12.                 END IF
we put this
Code: QB64: [Select]
  1.                 IF Array(x, y) = pass THEN
  2.                     DO WHILE y < H - 2 AND Array(x, y + 1) = S(x, y + 1)
  3.                         Array(x, y + 1) = np
  4.                         finished = 0
  5.                         y = y + 1
  6.                         IF y > MaxY THEN MaxY = y
  7.                     LOOP
  8.                 END IF

thanks to read and to play with code together!
Title: Re: Steve's Magical Paint Fill
Post by: SMcNeill on November 24, 2019, 10:22:05 am
                    DO WHILE y < H - 2 AND Array(x, y + 1) = S(x, y + 1)
                        Array(x, y + 1) = np
                        finished = 0
                        y = y + 1
                        IF y > MaxY THEN MaxY = y
                    LOOP
           

You have to separate these conditions, or face runtime errors.

Say y = H -2...   It passes the loop, gets incremented to H -1.

That compound IF statements wants to check “ Array(x, y + 1) = ...”, which makes it checking Array(x, H)...   This is an Out Of Bounds array error, as our array is only dimmed to H-1.

It’s why the original code separates the conditions for us.  ;)
Title: Re: Steve's Magical Paint Fill
Post by: TempodiBasic on November 24, 2019, 02:24:00 pm
Right Steve!
if y increases to be = H-2 and the second dimension of Array or S is lower than H-2 we get an out of bounds error!
So it is safe to put evaluation of arrays  Array and S after the evaluation of y<H-2!

Or you must rule the incrementation with a control like
 IF  y < Ubound(Array,2) then y = y+1
Or
 IF  y < Ubound(S,2) then y = y+1
Or
IF  y +1< H-2 then y = y+1

Or you must project a statement where two or more conditions are not in conflict.
In the specific case if y can reach the value of H-2 the associated conditions must permit that value for y

What I find beautyful of programming is the possibility to use our  mind in creative mode.

Thanks