Need help with this, Code works sometimes not always

[Cobalt]

So I'm playing around with an idea on a Match-3 type puzzle game and while the function to find the match seem to work its not marking certain tiles sometimes, if it is a group of 3 and the function has to check up or down after finding a match to the right it just doesn't seem to want to mark the last tile. I've attached an image showing what I mean. if you uncomment the  _DELAYs in the function you can see that it checks the last tile in those groups but for some reason it doesn't set the Matched flag.

Code: QB64: [Select]

1. TYPE Tile_Data
2.  ID AS _BYTE 'tile sprite
3.  Searched AS _BYTE 'has tile been matched
4.  Matched AS _BYTE 'set when the total number of connected tiles is greater than Min_match
5.  '                 used to remove matched tiles
6. END TYPE
7.  
8. CONST TRUE = -1, FALSE = NOT TRUE
9. CONST Min_Match = 3
10.  
11. SCREEN 9: RANDOMIZE 183 'TIMER
12. 'define the game board
13. DIM SHARED Board(-1 TO 21, -1 TO 21) AS Tile_Data '1 space boarder buffer area
14.  
15. 'fill game board with data
16. FOR X%% = 0 TO 20
17.  FOR Y%% = 0 TO 20
18.   Board(X%%, Y%%).ID = INT(RND * 6) + 1
19.   Board(X%%, Y%%).Searched = 0
20. NEXT Y%%, X%%
21.  
22. FOR X%% = 0 TO 20
23.  FOR Y%% = 0 TO 20
24.   IF NOT Board(X%%, Y%%).Searched THEN result%% = Check_Tiles(X%%, Y%%, Board(X%%, Y%%).ID)
25.   display_board
26.   IF INKEY$ = CHR$(27) THEN Y%% = 21: X%% = 21
27. NEXT Y%%, X%%
28.  
29. SUB display_board
30.  'display the board
31.  LOCATE 1, 1
32.  FOR X%% = 0 TO 20
33.   FOR Y%% = 0 TO 20
34.    IF Board(X%%, Y%%).Matched THEN COLOR 14 ELSE COLOR 7
35.    LOCATE 1 + Y%%, 1 + X%% * 2: PRINT STR$(Board(X%%, Y%%).ID)
36.  NEXT Y%%, X%%
37.  _DELAY .25
38. END SUB
39.  
40. FUNCTION Check_Tiles%% (StartTileX%%, StartTileY%%, Match%%)
41.  STATIC Count%%, Depth%%
42.  'StartTileX%%- the board X location to start the search from
43.  'StartTileY%%- the board Y location to start the search from
44.  'Match%%- the tile id to be looking for
45.  'current run depth
46.  Depth%% = Depth%% + 1
47.  LOCATE 1, 50: PRINT Count%%
48.  LINE (7 + 16 * StartTileX%%, 0 + 14 * (StartTileY%%))-STEP(7, 14), 4, B
49.  '--------------------check tiles in 4 cardial directions------------------
50.  'check up
51.  IF Board(StartTileX%%, StartTileY%% - 1).ID = Match%% THEN 'we find a match
52.   IF NOT Board(StartTileX%%, StartTileY%% - 1).Searched THEN 'this spot has not already been matched
53.    Count%% = Count%% + 1 'Total number of matches
54.    Board(StartTileX%%, StartTileY%% - 1).Searched = TRUE 'make sure the next function run(if any) does not match this location again
55.    LINE (7 + 16 * StartTileX%%, 0 + 14 * (StartTileY%% - 1))-STEP(7, 13), 12, B
56.    result%% = Check_Tiles(StartTileX%%, StartTileY%% - 1, Match%%) 'move to the matched tile
57.   END IF
58.  END IF
59.  '_DELAY .25
60.  'check down
61.  IF Board(StartTileX%%, StartTileY%% + 1).ID = Match%% THEN 'we find a match
62.   IF NOT Board(StartTileX%%, StartTileY%% + 1).Searched THEN 'this spot has not already been matched
63.    Count%% = Count%% + 1 'Total number of matches
64.    Board(StartTileX%%, StartTileY%% + 1).Searched = TRUE 'make sure the next function run(if any) does not match this location again
65.    LINE (7 + 16 * StartTileX%%, 0 + 14 * (StartTileY%% + 1))-STEP(7, 13), 12, B
66.    result%% = Check_Tiles(StartTileX%%, StartTileY%% + 1, Match%%) 'move to the matched tile
67.   END IF
68.  END IF
69.  '_DELAY .25
70.  'check left
71.  IF Board(StartTileX%% - 1, StartTileY%%).ID = Match%% THEN 'we find a match
72.   IF NOT Board(StartTileX%% - 1, StartTileY%%).Searched THEN 'this spot has not already been matched
73.    Count%% = Count%% + 1 'Total number of matches
74.    Board(StartTileX%% - 1, StartTileY%%).Searched = TRUE 'make sure the next function run(if any) does not match this location again
75.    LINE (7 + 16 * (StartTileX%% - 1), 0 + 14 * StartTileY%%)-STEP(7, 13), 14, B
76.    result%% = Check_Tiles(StartTileX%% - 1, StartTileY%%, Match%%) 'move to the matched tile
77.   END IF
78.  END IF
79.  'check right
80.  IF Board(StartTileX%% + 1, StartTileY%%).ID = Match%% THEN 'we find a match
81.   IF NOT Board(StartTileX%% + 1, StartTileY%%).Searched THEN 'this spot has not already been matched
82.    Count%% = Count%% + 1 'Total number of matches
83.    Board(StartTileX%% + 1, StartTileY%%).Searched = TRUE 'make sure the next function run(if any) does not match this location again
84.    LINE (7 + 16 * (StartTileX%% + 1), 0 + 14 * StartTileY%%)-STEP(7, 13), 14, B
85.    result%% = Check_Tiles(StartTileX%% + 1, StartTileY%%, Match%%) 'move to the matched tile
86.   END IF
87.  END IF
88.  '----------------------------------------------------------------------------
89.  IF Count%% >= Min_Match THEN Board(StartTileX%%, StartTileY%%).Matched = TRUE
90.  Check_Tiles = Count%% 'return how many tiles matched(only used by Main loop)
91.  IF Depth%% = 1 THEN Count%% = 0: Depth%% = 0 ELSE Depth%% = Depth%% - 1
92.  _DELAY .1
93. END FUNCTION
94.  

too lazy to run it, here is a video of it running, though the quality is less than stellar.

[bplus]

How does this look?

  [ You are not allowed to view this attachment ]  

[Petr]

Hi Bplus, yours looks good. I'm also trying to figure it out. So far without success. What did you do with it?

[Cobalt]

How does this look?

  [ You are not allowed to view this attachment ]

that looks like it should.
What did I goof?

[bplus]

What did I goof?

Don't know, yours was too complicated so I went my own route, recursion is tricky!

Code: QB64: [Select]

1. _TITLE "Match 3+ problem"
2. DEFINT A-Z 'to avoid suffix
3. TYPE Tile_Data
4.     ID AS INTEGER 'tile sprite
5.     Matched AS INTEGER 'tile will at least match itself when checked  0 indicates not checked yet
6. END TYPE
7.  
8.  
9. SCREEN 9: RANDOMIZE 183 'TIMER   'same colors as screen 12?
10. 'define the game b
11. DIM SHARED b(-1 TO 21, -1 TO 21) AS Tile_Data '1 space board buffer area, good idea!
12. DIM SHARED f(-1 TO 21, -1 TO 21) AS INTEGER 'finds board
13.  
14. 'fill game board with data
15. FOR x = 0 TO 20
16.     FOR y = 0 TO 20
17.         b(x, y).ID = INT(RND * 6) + 1
18.         b(x, y).Matched = 0 ' with udt good idea to zero init
19.     NEXT
20. NEXT
21.  
22. FOR x = 0 TO 20
23.     FOR y = 0 TO 20
24.         IF b(x, y).Matched = 0 THEN runSearch x, y, b(x, y).ID
25.         display
26.         IF INKEY$ = CHR$(27) THEN SYSTEM
27.     NEXT
28. NEXT
29.  
30. SUB display
31.     CLS
32.     FOR x = 0 TO 20
33.         FOR y = 0 TO 20
34.             IF b(x, y).Matched > 2 THEN COLOR 14 ELSE COLOR 7
35.             LOCATE 1 + y, 1 + x * 2: PRINT STR$(b(x, y).ID)
36.         NEXT
37.     NEXT
38.     '_DELAY 4
39. END SUB
40.  
41. SUB runSearch (x, y, n)
42.     ERASE f 'clear the finds board for next square
43.     search x, y, n
44.     'CLS
45.     'count finds
46.     FOR c = 0 TO 20
47.         FOR r = 0 TO 20
48.             IF f(c, r) = 1 THEN count = count + 1
49.             'LOCATE r + 1, c * 2 + 1: PRINT STR$(f(c, r));
50.         NEXT
51.     NEXT
52.     'now we have counted matches for cells found matching
53.     FOR c = 0 TO 20
54.         FOR r = 0 TO 20
55.             IF f(c, r) = 1 THEN b(c, r).Matched = count
56.         NEXT
57.     NEXT
58.     '_DELAY 2
59. END SUB
60.  
61. SUB search (x, y, n)
62.     IF b(x, y).ID = n THEN
63.         IF b(x, y).Matched = 0 THEN
64.             IF f(x, y) = 0 THEN
65.                 f(x, y) = 1
66.                 search x + 1, y, n
67.                 search x - 1, y, n
68.                 search x, y + 1, n
69.                 search x, y - 1, n
70.             END IF
71.         END IF
72.     END IF
73. END SUB
74.  
75.  

[Petr]

Great job, BPlus!

[Cobalt]

well that helps and doesn't help at the same time! :(

what exactly are you doing with f()?

and how do you keep track of tiles already searched so you don't waste time researching them say if they were right and left of each other?
I mean if there was only 2 so not a 3(or more) set.

[bplus]

f() the finds array, is cleaned out for every non searched tile in the board.

Starting at that tile x, y not checked yet from b() board array, all matching tiles are marked with the recursive search sub that touch the start tile. The search sub will always at least mark the original tile as searched first and then branch left/right/up/down for another match. If another one is found (not already matched up in f() or b() then it is marked as match in f() and another search is issued around that square... keeps going until no more matches found or already matched up.

Then runSearch counts all tiles marked as matching and puts that count in the b().Matching for all those x, y tiles found in f() array.

[TempodiBasic]

Hi Guys
execellent algorythm Bplus!

Hi Cobalt about the debugging of your algorythm
I have tryed to modify to my use your code to see where it makes the glicth but it is not necessary!. As you have already pointed out the issue is about to catch the right MATCHED tiles!

You can notice that

1. only after going to right at recursive way... in fact you loose the UP or the DOWN tile founded

so the issue is in the part of code that mark as MATCHED the tile!

Code: QB64: [Select]

1. IF Count%% >= Min_Match THEN Board(StartTileX%%, StartTileY%%).Matched = TRUE

it is a single line of code, but why  does it loose the UP and DOWN tile after a RIGHT tile in n matched tiles? 
We can note that DEPTH%% and COUNT%% don't have always the same value, can this make the difference?

[bplus]

See, that was the problem. You don't mark the tiles until you know the count and you can't count properly unless you mark the tiles, a Catch-22 situation.

So I thought you needed another array f() for a temp storage array (SHARED so it is seen by every recursion instance of Search sub) to track the matching tiles found for the particular tile you are searching from, that's how my f() array came about.

[TempodiBasic]

Yes this is the reason that let me say excellent  to your solution,
 IMHO you touch the problem in its essence.

I have tried to chunk down the part of  code about searching but the issue is in the evaluation of matched (marking the tile) tile.
I was thinking about to use  3 different code for the flag .search of tile  and a flag to sign when count is over cutoff (2 in this homework) but I need a fresh mind to go on with this idea. Surely the evaluation task must be put out of searching block code!

Interesting lesson about the traps of recursion!  :-)

[TempodiBasic]

Yes I got it! :-)

A fresh mind is the best tool to code!  ;)

here the solution of code of Cobalt using a Flag%% for output and evaluating the tiles out of the recursive function and plus options for the flag of status of tile .searched.

  [ You are not allowed to view this attachment ]  

it seems to work well.

and here the code chunked down to my habit

Code: QB64: [Select]

1. TYPE Tile_Data
2.     ID AS _BYTE 'tile sprite
3.     Searched AS _BYTE 'has tile been matched
4. END TYPE
5.  
6. CONST TRUE = -1, FALSE = NOT TRUE
7. CONST Min_Match = 3, InSearch = 10, Matched = 20, ToSearch = 30, Done = 40
8.  
9. SCREEN 9: RANDOMIZE 183 'TIMER
10. 'define the game board 23x23 with  borders -1 and 21
11. DIM SHARED Board(-1 TO 21, -1 TO 21) AS Tile_Data '1 space boarder buffer area
12. DIM SHARED Flag%%, Count%%
13.  
14. Initialize
15.  
16. ' main search loop
17. FOR X%% = 0 TO 20
18.     FOR Y%% = 0 TO 20
19.         Flag%% = FALSE
20.         Count%% = 0
21.         IF Board(X%%, Y%%).Searched = ToSearch THEN result%% = Check_Tiles(X%%, Y%%, Board(X%%, Y%%).ID)
22.         display_board
23.         ' escape option
24.         IF INKEY$ = CHR$(27) THEN Y%% = 21: X%% = 21
25. NEXT Y%%, X%%
26. END ' a logical end always must be put
27.  
28. '.....................SUB/FUNCTIONs..........
29. SUB display_board
30.     'display the board
31.     LOCATE 23, 40: PRINT Flag%%;
32.     LOCATE 1, 1
33.     FOR X%% = 0 TO 20
34.         FOR Y%% = 0 TO 20
35.             ' this marks the tile to show them
36.             IF Flag%% AND Board(X%%, Y%%).Searched = InSearch THEN Board(X%%, Y%%).Searched = Matched
37.             ' this lets free the tiles with InSearch when No flag is set
38.             IF (NOT Flag%%) AND Board(X%%, Y%%).Searched = InSearch THEN Board(X%%, Y%%).Searched = Done
39.             ' this shows the board
40.             IF Board(X%%, Y%%).Searched = Matched THEN COLOR 14 ELSE COLOR 7
41.             LOCATE 1 + Y%%, 1 + X%% * 2: PRINT STR$(Board(X%%, Y%%).ID)
42.     NEXT Y%%, X%%
43.     LOCATE 24, 1: PRINT "Press ESC to escape";
44.     _DELAY .25
45. END SUB
46.  
47. FUNCTION Check_Tiles%% (StartTileX%%, StartTileY%%, Match%%)
48.     ''    STATIC Count%%, Depth%%
49.     'StartTileX%%- the board X location to start the search from
50.     'StartTileY%%- the board Y location to start the search from
51.     'Match%%- the tile id to be looking for
52.  
53.     LOCATE 1, 50: PRINT Count%%; "  "; Match%%; "   "; Flag%%
54.     LINE (7 + 16 * StartTileX%%, 0 + 14 * (StartTileY%%))-STEP(7, 14), 4, B
55.     '--------------------check tiles in 4 cardial directions------------------
56.     'check up
57.     EvaluateTile StartTileX%%, StartTileY%% - 1, Match%%
58.     'check down
59.     EvaluateTile StartTileX%%, StartTileY%% + 1, Match%%
60.     'check left
61.     EvaluateTile StartTileX%% - 1, StartTileY%%, Match%%
62.     'check right
63.     EvaluateTile StartTileX%% + 1, StartTileY%%, Match%%
64.     '----------------------------------------------------------------------------
65.     Check_Tiles = Count%% 'return how many tiles matched(only used by Main loop)
66.     _DELAY .1
67. END FUNCTION
68.  
69. SUB EvaluateTile (X%%, Y%%, Match%%)
70.     'we find a match
71.     IF Board(X%%, Y%%).ID = Match%% AND Board(X%%, Y%%).Searched = ToSearch THEN 'this spot has not already been matched
72.  
73.         ' if we get a match we can increase count of matched tiles founded
74.         Count%% = Count%% + 1
75.  
76.         ' we activate the flag for output
77.         IF Count%% >= Min_Match THEN Flag%% = TRUE
78.  
79.         'make sure the next function run(if any) does not match this location again
80.         Board(X%%, Y%%).Searched = InSearch
81.         LINE (7 + 16 * X%%, 0 + 14 * (Y%% - 1))-STEP(7, 13), 12, B
82.         result%% = Check_Tiles(X%%, Y%%, Match%%) 'move to the matched tile
83.     END IF
84. END SUB
85.  
86. SUB Initialize
87.     'fill game board with data
88.     FOR X%% = 0 TO 20
89.         FOR Y%% = 0 TO 20
90.             Board(X%%, Y%%).ID = INT(RND * 6) + 1
91.             Board(X%%, Y%%).Searched = ToSearch
92.     NEXT Y%%, X%%
93.     Flag%% = FALSE
94.     Count%% = 0
95. END SUB

As you can see no more STATIC variables Depth%% & Count%% but just a SHARED Count%% and I have left Check_Tiles as Function but it is a real SUB because the result now is dummy.
Thanks to read and try