Steve's Magical Paint Fill

[SMcNeill]

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

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!

[STxAxTIC]

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?

[SMcNeill]

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

[bplus]

Try filling other spots, I get subscript out of range allot, no fills.

[SMcNeill]

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

[bplus]

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. OPTION _EXPLICIT
2. _TITLE "PathFinder Paint mod"
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. RANDOMIZE TIMER
9. DIM bc AS _UNSIGNED LONG, start
10.  
11. start = TIMER
12. bc = &HFFFF0000
13. CIRCLE (500, 400), 100, bc
14. Fill 510, 400, &HFFFFFF00, bc
15.  
16. CIRCLE (xmax - 1, ymax - 1), 400, bc
17. Fill xmax - 10, ymax - 10, &HFFFF0088, bc
18.  
19. LINE (100, 100)-(500, 500), bc, B
20. Fill 150, 150, &HFFFF0000, bc
21. PRINT TIMER - start
22.  
23. SUB Fill (x0, y0, fillC AS _UNSIGNED LONG, bC AS _UNSIGNED LONG)
24.     DIM W, H, parentF, tick, ystart, ystop, xstart, xstop, y, x
25.     W = _WIDTH - 1: H = _HEIGHT - 1
26.     DIM temp(W, H)
27.     temp(x0, y0) = 1: parentF = 1
28.     WHILE parentF = 1
29.         parentF = 0: tick = tick + 1
30.         ystart = max(y0 - tick, 0): ystop = min(y0 + tick, H)
31.         y = ystart
32.         WHILE y <= ystop
33.             xstart = max(x0 - tick, 0): xstop = min(x0 + tick, W)
34.             x = xstart
35.             WHILE x <= xstop
36.                 IF POINT(x, y) <> bC AND temp(x, y) = 0 THEN
37.                     IF temp(max(0, x - 1), y) THEN
38.                         temp(x, y) = 1: parentF = 1: PSET (x, y), fillC
39.                     ELSEIF temp(min(x + 1, W), y) THEN
40.                         temp(x, y) = 1: parentF = 1: PSET (x, y), fillC
41.                     ELSEIF temp(x, max(y - 1, 0)) THEN
42.                         temp(x, y) = 1: parentF = 1: PSET (x, y), fillC
43.                     ELSEIF temp(x, min(y + 1, H)) THEN
44.                         temp(x, y) = 1: parentF = 1: PSET (x, y), fillC
45.                     END IF
46.                 END IF
47.                 x = x + 1
48.             WEND
49.             y = y + 1
50.         WEND
51.     WEND
52. END SUB
53.  
54. FUNCTION rand% (lo%, hi%)
55.     rand% = INT(RND * (hi% - lo% + 1)) + lo%
56. END FUNCTION
57. FUNCTION min (n1, n2)
58.     IF n1 > n2 THEN min = n2 ELSE min = n1
59. END FUNCTION
60. FUNCTION max (n1, n2)
61.     IF n1 < n2 THEN max = n2 ELSE max = n1
62. END FUNCTION
63.  
64.  

EDIT: 3 secs off time with DEFINT A-Z

[SMcNeill]

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.

[bplus]

What was causing the magic jump?

[SMcNeill]

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

[SMcNeill]

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

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.  ;)

[SMcNeill]

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.) 

[bplus]

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. RANDOMIZE TIMER
9. DIM bc AS _UNSIGNED LONG, start#
10.  
11. start# = TIMER
12. bc = &HFFFF0000
13. CIRCLE (500, 400), 100, bc
14. fill 510, 400, &HFFFFFF00, bc
15.  
16. CIRCLE (xmax - 1, ymax - 1), 400, bc
17. fill xmax - 10, ymax - 10, &HFFFF0088, bc
18.  
19. LINE (100, 100)-(500, 500), bc, B
20. fill 150, 150, &HFFFF0000, bc
21. PRINT TIMER - start#
22.  

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).

[SMcNeill]

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.

[bplus]

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.

[SMcNeill]

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??