Graph Theory? What algorithm do I use to find matching tiles in a 2D array that...

Hello all again, (THIS post is related:)
I am here with my next question to my remake of the SEGA game columns.
What algorithm do I use to find matching tiles of 3 OR more tiles that are of the same color in a 2D array, AND that are on the SAME line in any of the 8 directions. (horz,vert,diag.)
I was also hoping to discuss some presuedo code. Each grid is 6 tile wide, and 16 tiles tall. I have three 2d arrays. one for my Visual grid of game objects, one for the main 2D grid to handle the core logic of the game made of up my special class Type “Gem” where each tile basically keeps track of its color, x and y coords, and a few other things at the moment and finally just a temp storage area where i COPY the main grid to for manipulation of match making of tiles of same color, resettling the board, etc. I have been reading about DFS and BFS algorithms, I am not sure which one that I have already written, but currently I have it so that when my CheckForNeighbor routine finds a matching gem that is adjecent to my “root” gem its doesnt return, but rather keeps on looking in its current direction one tile further from the “root” gem and so on until we hit the edge of the board, and empty tile, or a NON-matching gem… Which one I should use because it is best suited for my situation? with the above method that I have already written it will not “find” all of the correct matches, it does almost all of the time, but in situations where is starts to check “UP” and finds 3 matching gems in a row one after the other, the check WONT go left or right, as its trying to find “the furthest” gem away that is connected to the 1st gem, but never goes back to revisit the child nodes it found along the way to “check its neighbors of neighbors”. and I wrote it that way trying to avoid the “flood fill” effect when trying to make matches that follow the 3 in a row ON the same line rule (which the flood fill does not follow, it just finds all the connecting neighbors of neighbors until it exhausts all options, which i need all neighbors of neighbors, BUT IN A STRAIGHT LINE of 3 or MORE…).

So In a nutshell how would I use this BFS algorithm in my said situation with the Rules of matching as the COLUMNS game has them laid out?:slight_smile: or should i be using something else?

Again, I use C#, and I’m not a unity pro, but I would like to attempt to understand how to implement the best algorithm into this game I’m coding.

Thanks
King

"In graph theory, breadth-first search (BFS) is a strategy for searching in a graph when search is limited to essentially two operations: (a) visit and inspect a node of a graph; (b) gain access to visit the nodes that neighbor the currently visited node. The BFS begins at a root node and inspects all the neighboring nodes. Then for each of those neighbor nodes in turn, it inspects their neighbor nodes which were unvisited, and so on. "

I solved a similar problem recently. I have a 2D array where all of my tokens are at indices which correspond to their position. I walk this array in each possible direction and count how many of a colour I found in a row. This is a matter of checking the colour of the current token against the colour of the last one I looked at. If it’s the same I increment a counter, if it’s different (or if there was no previous token) reset the counter to 1 and optionally take additional action depending on what the value of the counter had been.

penguin, thank you for a fast response. currently i am using a LIST to hold all base gems when the dropping box hits the bottom of the board or another gem below. that starts my check match routine which does pretty much what you have described… hence my question still, i am searching the “end” of the line gem out, but not going back to each gem found along the way ,making it parent and checking neighbors again, im only doing the “360 degree” check basically one line of tiles at a time, not one gem at a time, then im not checking each child of that gem for neighbirs all around, im just checking the child node to the direction we are checking already. i was worried that if i checked the neighbors of the child nodes, i would end up with ALL connected tiles, nit just 3 in a row,in a straight line…thanks King

I don’t understand why parenting has anything to do with anything here. You have a grid of things, and all you need to do is identify certain patterns in that grid of things, right?

I’d start by making sure my data is laid out in a manner that suits the problem I’m solving. In this case, I don’t see a plain ol’ list as offering much help. How are you even identifying adjacent pieces?

i have each tile store its current x and y positions right in each tile, of my custom class type,including the color of the tile also. so when a player drops the gem dropping box to the bottom of the board, i store those 3 gems as ROOT tiles to start checking neighbors from thier x,y positions. after the matching list is destroyed,and the board resettled, i use the same list to cycle through recursively each of those tiles that fell down due to gaps in destroyed matches,as the new root tile list… repeat… its the way my check neighbor method is working (the one that checks for contiguous matches in a row ) incorrectly. so im not sure if understood the bfs algorithm would do what im asking, and how id use it to iterate the board amd track correct matches? sorry im noobish here.

How are you finding adjacent gems? I understand that a gem stores its position, but how do you get from that to knowing what is adjacent?

King,

breadth/depth first searching is for tree structures. I don’t see how they can help you here.

Do you still have a board object with an array [x,y] of gems? If so, then you can find adjacent gems trivially.
e.g. [x-1, y] where x > min_x and [x+1, y] where x < max_x.

Your code should at least be able to do the following:
given a gem [x,y] find:

  1. horizontal matches that include this gem
  2. vertical matches that include this gem
  3. diagonal matches that include this gem

If your current code cannot do this, write a method (or 3) so that it can.

I think that BFS and DFS apply because they’re somehow searching for (and building a tree of) adjacent nodes as they go.

r.lindsay, thank you. once again you understood what i was asking. lol i did write code that finds matches of 3 or more horz and vert only at the moment. but the method just checks for a run from the list of base gems, not checking all directions from each adjecent matching tile that was found. so if there is 2 blue tiles on the same x axis the next gem set i drop down, lets say that it makes up 3 blue gems vertically, my check method will find the tile above ,above,and itself, so thats three…BUT the top gem connects the 2 blue gems i described earlier on the same x axis to for a horz match of 3, but it doesnt register as my check routine is not setup correctly… i think im doing a terrible job of trying to explain this. sorry about that.

penguin thats exactly how i was trying to apply bfs to my check neighbor method… so i agree with you unless im over complicating the game matching logic?

R.Lindsay and I are saying the same thing. You’re very much over complicating it. If you get your data layout right then this is a non-issue and you shouldn’t need anything as heavy as a DFS or BFS.

In my grid game, searches are easy because I don’t have to do anything to “find” adjacent cells. I just know where they are intrinsically. If I’m looking at cell [x,y] I know that adjacent cells are all of [x+/-1,y+/-1]. I just request that cell from the grid and use it. Job done.

1 Like

Even if you weren’t using a Grid, if you were using a Graph of nodes, you could do faster searches at the cost of more memory. As an example, storing references to the nodes in a dictionary where each node is mapped to a unique ID, and each node has a list of references for its neighboring nodes. Then you can do a fast search for any particular node and its neighbors, but again the cost is memory for speed (which is usually the case in these kinds of situations).

Finding adjacent gems is trivial, but to find all matches of a certain length you need to search the adjacency graph for each gem. You just want to use dynamic programming (break the problem into sub-problems and remember the answer) with a simple recursive algorithm.

Pseudocode:

For each gem
     For each direction
          call gem.matches(direction)
     For each line
          matches = 1 + sum of two opposite directions for that line
     If (matches > 3)
          store gem in a list to process later

function gem.matches(direction)
{
  if gem.isEvaluated[direction] = false
       if gem in that direction matches
            gem.matches[direction] = 1 + adjacent_gem(direction).matches(direction)
            gem.isEvaluated[direction] = true
       else
            gem.matches[direction] = 0
            gem.isEvaluated[direction] = true   

  return gems.matches[direction]
}

function adjacent_gem(direction)
{
     simply return the adjacent gem in that direction
}

When getting the matches from adjacent gems you use lazy evaluation. If the gem already knows the number of matches in that direction, then you simply return it. If not, then you evaluate it. If you’ve already visited a gem, all of its matches for every direction should already be evaluated.

It boils down to DFS, but you want to remember the matches in each direction so you don’t have to revisit gems multiple times. If you’ve already visited row 3 and you are currently visiting row 4, all the gems from row 3 should already know how many matches they have below them (straight or diagonally).

Once you’ve checked all the directions for a gem, you get the longest match for each line by adding the matches in two opposite directions and plus one (for the current gem). Then you can simply store a reference gems with a longest match of 3 or greater in a list to process later.

Of course, once you’ve finished processing your results remember to clear all the match/isEvaluated information for the next time you run your algorithm.

That approach will certainly work, but it’s a huge amount of effort compared looping over a grid with a counter.

1 Like

Hello all,
I wanted to post my code that I have written for checking the running color matches of 3 or more in a straight line, and I also want to include my Resettle Board method also. My Horz, Vert, and Diag match checking seems to be working correctly. I have called each directional check method by itself (and I still am just for testing) and tested it visually, and made sure it was doing what it was supposed to on the grid behind the scenes. I left the gaps on the grid visually and empty on the grid board so I could make sure that my match routine was matching directions, color, and basically doing whats its supposed to be, and doing it correctly, LoL. Have you ever added like 100 print statements after each line of your code to “tell” you in the console whats actually going on vs. what you THOUGHT was happenning? Nevermind…(Grin) anyways, If you folks could just skim over my methods here and make sure I have written what we have discussed so far correctly, I will get to my point:
The matches seem to be correct when I call each method one after the other as my CheckForMatch method shows, or If I were (and will) add them all together so its one big “8 direction Check method” it still works fine. I have checked this again, Visually, and In memory (printed to console what was at location “x,y” from the 2D grid after visual blocks are destroyed at same location)
The problem seems to be SOMETIMES, AFTER I haved called the directional check, it finds matches, destroys them,THEN resettles the board… after resettling, the check for match is called again, THEN it seems to find matches that are not color related, or in line with whatever portion of the check routine was running (i.e it was searching up and to the left, and found matches, destroys the correct matches, but also will seem to destory some random block that was not “in line” with the direction it was giong!)
Can anyone see any obvious mistakes that I dont here? I am happy to post other code if needed or explain further if needed.
As always, you guys have been a great help, THANKS
King

Edit: Uploaded two pictures…
Here is the BEFORE and AFTER of the grid. The three black dots just indicate the source of the check, the yellow gem on the bottom is the START gem of recursion.
NOTICE it did NOT register any of the matches but the ones going LEFT. wtf?!

CheckForMatch:

// **CHECKING FOR MATCHING GEMS OF 3 OR MORE**
public static void CheckForMatch(GameBoard board)
        {
            //Start with the 1st tile in the list of Base Tiles
            for(int i = 0;i < topOfRecursionBaseTiles.Count;i++)
            {
                //End list that will contain all matches of 3 or more found in match 3 pass
                finalListOfGemsToDestroy.Clear();
                //Make a Copy of 2D gridboard of Type "Gem" for Manipulation purposes
                GameBoard.CopyGridBoard(board, CoreGameManager.gridBoardCopy);
                //Iterate the List of Parent/Master Base Tiles
                parentBaseTile = topOfRecursionBaseTiles[i];
                //Call each matchmaking method seperatly for now, we will combine all dir checking together after testing...
                horzMatchCount = 0;
                collector.Clear ();
                CheckForNeighborsHorz(parentBaseTile,parentBaseTile.Row,parentBaseTile.Column);
                vertMatchCount = 0;
                collector.Clear ();
                CheckForNeighborsVert(parentBaseTile,parentBaseTile.Row,parentBaseTile.Column);
                diagzMatchCount = 0;
                collector.Clear ();
                CheckForNeighborsDiagz(parentBaseTile,parentBaseTile.Row,parentBaseTile.Column);
                //If there were any set of 3 matches or more found, then go destroy gems, resettle board, check for matches again...
                if(finalListOfGemsToDestroy.Count >= minNumGemsForChain)
                {
                    //Destroy all VISUAL game objects in the FINAL LIST of Gems to remove off the VisualGrid
                    DestroyMatchingGems(finalListOfGemsToDestroy);
                    //We removed gems from the grid, now FILL in the gaps left behind, and add NEW PARENT tiles that were found above the empty gaps,as the gapfill may possibly have caused more matches
                    SettleBlocks(CoreGameManager.gridBoard);
                    //The resettle of the board may have caused NEW matches, go check our ParentTile list again until no more base tiles are found
                    CheckForMatch(CoreGameManager.gridBoard);
                }
            
            }

Directional Checks:

//Check for same color tiles in a STRAIGHT line of 3 or more HORIZONTALLY
public static void CheckForNeighborsHorz(Gem currentBaseTile, int x, int y)    
    {
/******************************************************
* If this function finds that the cell is NULL, then we skip tile. (Null = Already Tested this Tile)
* If this function finds that the cell is EMPTY, then we skip tile.(Empty = its..EMPTY... dont need to test)
* parentBaseTile is STATIC and holds the ORIGINAL base tile this check started from and is only changed to a new root gem by CheckForMatch()
******************************************************/
//Horz Checks:
            //Check LEFT, Make sure we are inside the board boundry and the tile we are looking at is NOT NULL, and NOT EMPTY
            if(x - 1 >= 0 && CoreGameManager.gridBoardCopy[x-1,y] != null && CoreGameManager.gridBoardCopy[x-1,y].GemColorType != Gem.GEMTYPE.EMPTY)
            {
                isCheckingNeighbors = true;
                while (isCheckingNeighbors)
                {
                    //Since we will be LOOPING our check to the left we want to make sure we AGAIN are in bounds of the grid...etc.etc.
                    if(x - 1 >= 0 && CoreGameManager.gridBoardCopy[x-1,y] != null && CoreGameManager.gridBoardCopy[x-1,y].GemColorType != Gem.GEMTYPE.EMPTY )
                    {
                        //Test the tile to see if colors match
                        TestTile(x-1,y);
                        //If colors DO MATCH
                        if(isGemMatching == true)
                        {
                        //Add it to Temp list to track all the same color gems that are in the SAME DIRECTION (e.g All gems found to the LEFT of the Root gem)
                            collector.Add(CoreGameManager.gridBoardCopy[x-1,y]);
                            //Make the tile (to the left in this case) that was just checked AND MATCHED, our NEW PARENT tile to check from
                            currentBaseTile = CoreGameManager.gridBoardCopy[x-1,y];
                            //Make tile NULL as we have checked this tile...and our parent tile null as we are using it to check from and we dont want to check any tile twice?
                            CoreGameManager.gridBoardCopy[x-1,y] = null;
                            CoreGameManager.gridBoardCopy[x,y] = null;
                            //Increment the Horz Match Counter (for later use?)
                            horzMatchCount ++;
                            x = x-1;
                            //y stays the same, we are HORZ checking
                        }
                        else
                        //The gems do NOT MATCH
                        {
                        isCheckingNeighbors = false;//Set the LOOP Exit condition.
                        }
                    }
                    else
                    //tile is EMPTY, or we are OFF the edge of the grid so  no need to check further, kill loop.
                    {
                        isCheckingNeighbors = false;
                    }
                }
            //Put ROOT tile back, Start check to RIGHT FROM the ROOT tile that we started checking left from....
            currentBaseTile = parentBaseTile;
            x = currentBaseTile.Row;
            y = currentBaseTile.Column;
            }
        
//CHECKING RIGHT....
            if(x + 1 <= GameBoard.BoardWidth-1 && CoreGameManager.gridBoardCopy[x+1,y] != null && CoreGameManager.gridBoardCopy[x+1,y].GemColorType != Gem.GEMTYPE.EMPTY)
            {
                isCheckingNeighbors = true;
                    while (isCheckingNeighbors)
                    {
                        if(x + 1 <= GameBoard.BoardWidth-1 && CoreGameManager.gridBoardCopy[x+1,y] != null && CoreGameManager.gridBoardCopy[x+1,y].GemColorType != Gem.GEMTYPE.EMPTY )
                        {
                            TestTile(x+1,y);
                            if(isGemMatching == true)
                            {
                                collector.Add(CoreGameManager.gridBoardCopy[x+1,y]);
                                currentBaseTile = CoreGameManager.gridBoardCopy[x+1,y];
                                //Make block NULL as we have checked this block...and our parent block null as we are using it to check from and we dont want to check it twice.
                                CoreGameManager.gridBoardCopy[x+1,y] = null;
                                CoreGameManager.gridBoardCopy[x,y] = null;
                                 x = x+1;
                                //y stays the same, we are HORZ checking
                                horzMatchCount++;
                            }
                            else
                            {
                                isCheckingNeighbors = false;//Set the LOOP Exit condition.
                            }
                        }
                        else
                        {
                            isCheckingNeighbors = false;
                        }
                    }
                    currentBaseTile = parentBaseTile;
                    x = currentBaseTile.Row;
                    y = currentBaseTile.Column;
            }
            horzMatchCount = 0;
        
            //If we Found 3 or more of same color tile in a straight line (horz in this case) then, Process collector
            if(collector.Count >= minNumGemsForChain - 1)
            {
                //If the final list already has the ROOT gem in it, then DONT add the base gem to the list....
                if(!finalListOfGemsToDestroy.Contains(parentBaseTile))
                {
                    finalListOfGemsToDestroy.Add (parentBaseTile);
                }
                //There were 3 or more gems of same color found in a row on the same line, add ALL gems to final list of Gems to Destroy
                    finalListOfGemsToDestroy.AddRange(collector);
 
            }
    }
//Check for same color tiles in a STRAIGHT line of 3 or more VERTICALLY    
public static void CheckForNeighborsVert(Gem currentBaseTile, int x, int y)    
    {
//Vert Checks:
//UP
            if(y + 1 <= GameBoard.BoardHeight-1 && CoreGameManager.gridBoardCopy[x,y+1] != null && CoreGameManager.gridBoardCopy[x,y+1].GemColorType != Gem.GEMTYPE.EMPTY)
            {
                isCheckingNeighbors = true;
                while (isCheckingNeighbors)
                {
                    if(y+1 <= GameBoard.BoardHeight-1 && CoreGameManager.gridBoardCopy[x,y+1] != null && CoreGameManager.gridBoardCopy[x,y+1].GemColorType != Gem.GEMTYPE.EMPTY )
                    {
                        TestTile(x,y+1);
                        if(isGemMatching == true)
                        {
                            collector.Add(CoreGameManager.gridBoardCopy[x,y+1]);
                            currentBaseTile = CoreGameManager.gridBoardCopy[x,y+1];
                            CoreGameManager.gridBoardCopy[x,y+1] = null;
                            CoreGameManager.gridBoardCopy[x,y] = null;
                            vertMatchCount++;
                            //x stays the same, we are VERT checking     
                            y = y+1;
                        }
                        else
                        {
                            isCheckingNeighbors = false;//Set the LOOP Exit condition.
                        }
                    }
                    else
                    {
                        isCheckingNeighbors = false;
                    }
                }
                currentBaseTile = parentBaseTile;
                x = currentBaseTile.Row;
                y = currentBaseTile.Column;
         }
        
//DOWN        
            if(y - 1 >= 0)
            {
                isCheckingNeighbors = true;
                while (isCheckingNeighbors)
                {
                    if(y - 1 >= 0 && CoreGameManager.gridBoardCopy[x,y-1] != null && CoreGameManager.gridBoardCopy[x,y-1].GemColorType != Gem.GEMTYPE.EMPTY )
                    {
                        TestTile(x,y-1);
                        if(isGemMatching == true)
                        {
                            collector.Add(CoreGameManager.gridBoardCopy[x,y-1]);
                            currentBaseTile = CoreGameManager.gridBoardCopy[x,y-1];
                            CoreGameManager.gridBoardCopy[x,y-1] = null;
                            CoreGameManager.gridBoardCopy[x,y] = null;
                            //x stays the same, we are VERT checking     
                            y = y-1;
                            vertMatchCount++;
                        }
                        else
                        {
                            isCheckingNeighbors = false;//Set the LOOP Exit condition.
                        }
                    }
                    else
                    {
                    isCheckingNeighbors = false;
                    }
                }
                 currentBaseTile = parentBaseTile;
                 x = currentBaseTile.Row;
                y = currentBaseTile.Column;
            }
                vertMatchCount = 0;
 
                if(collector.Count >= minNumGemsForChain - 1)
                {
                    if(!finalListOfGemsToDestroy.Contains(parentBaseTile))
                    {
                        finalListOfGemsToDestroy.Add (parentBaseTile);
                    }
                        finalListOfGemsToDestroy.AddRange(collector);
                }
    }
//Check for same color tiles in a STRAIGHT line of 3 or more DIAGONALLY(any of the 4 dir's)
public static void CheckForNeighborsDiagz(Gem currentBaseTile, int x, int y)    
    {
//Diagz Checks:
//CHECKING LEFT and DOWN...
            if(x - 1 >= 0 && y-1 >= 0 && CoreGameManager.gridBoardCopy[x-1,y-1] != null && CoreGameManager.gridBoardCopy[x-1,y-1].GemColorType != Gem.GEMTYPE.EMPTY)
            {
                isCheckingNeighbors = true;
                while (isCheckingNeighbors)
                {
                    if(x - 1  >= 0 && y-1 >= 0 && CoreGameManager.gridBoardCopy[x-1,y-1] != null && CoreGameManager.gridBoardCopy[x-1,y-1].GemColorType != Gem.GEMTYPE.EMPTY )
                    {
                        TestTile(x-1,y-1);
                        if(isGemMatching == true)
                        {
                                    collector.Add(CoreGameManager.gridBoardCopy[x-1,y-1]);
                                    currentBaseTile = CoreGameManager.gridBoardCopy[x-1,y-1];
                                    CoreGameManager.gridBoardCopy[x-1,y-1] = null;
                                    CoreGameManager.gridBoardCopy[x,y] = null;
                                    diagzMatchCount ++;
                                     x = x-1;
                                     y = y-1;
                        }
                        else
                        {
                            isCheckingNeighbors = false;//Set the LOOP Exit condition.
                        }
                    }
                    else
                    {
                        isCheckingNeighbors = false;
                    }
                }
                    currentBaseTile = parentBaseTile;
                x = currentBaseTile.Row;
                y = currentBaseTile.Column;
            }
        
//CHECKING RIGHT and UP....
            if(x + 1 <= GameBoard.BoardWidth-1 && y+1 <= GameBoard.BoardHeight-1 && CoreGameManager.gridBoardCopy[x+1,y+1] != null && CoreGameManager.gridBoardCopy[x+1,y+1].GemColorType != Gem.GEMTYPE.EMPTY )
            {
                isCheckingNeighbors = true;
                while (isCheckingNeighbors)
                {
                    if(x + 1 <= GameBoard.BoardWidth-1 && y+1 <= GameBoard.BoardHeight-1 && CoreGameManager.gridBoardCopy[x+1,y+1] != null && CoreGameManager.gridBoardCopy[x+1,y+1].GemColorType != Gem.GEMTYPE.EMPTY )
                    {
                            TestTile(x+1,y+1);
                            if(isGemMatching == true)
                            {
                                collector.Add(CoreGameManager.gridBoardCopy[x+1,y+1]);
                                currentBaseTile = CoreGameManager.gridBoardCopy[x+1,y+1];
                                CoreGameManager.gridBoardCopy[x+1,y+1] = null;
                                CoreGameManager.gridBoardCopy[x,y] = null;
                                 x = x+1;
                                 y = y+1;
                                diagzMatchCount++;
                            }
                            else
                            {
                                isCheckingNeighbors = false;//Set the LOOP Exit condition.
                            }
                    }
                    else
                    {
                        isCheckingNeighbors = false;
                    }
                }
            currentBaseTile = parentBaseTile;
            x = currentBaseTile.Row;
            y = currentBaseTile.Column;
            }
            diagzMatchCount = 0;
 
            //If we Found 3 or more of same color tile in a straight line then, Process collector
            if(collector.Count >= minNumGemsForChain - 1)
            {
                if(!finalListOfGemsToDestroy.Contains(parentBaseTile))
                {
                    finalListOfGemsToDestroy.Add (parentBaseTile);
                }
                    finalListOfGemsToDestroy.AddRange(collector);
            }
            collector.Clear();
 
//CHECKING LEFT and UP
            if(x - 1 >= 0 && y+1 <= GameBoard.BoardHeight-1 && CoreGameManager.gridBoardCopy[x-1,y+1] != null && CoreGameManager.gridBoardCopy[x-1,y+1].GemColorType != Gem.GEMTYPE.EMPTY)
            {
                isCheckingNeighbors = true;
                while (isCheckingNeighbors)
                {
                    if(x - 1 >= 0 && y+1 <= GameBoard.BoardHeight-1 && CoreGameManager.gridBoardCopy[x-1,y+1] != null && CoreGameManager.gridBoardCopy[x-1,y+1].GemColorType != Gem.GEMTYPE.EMPTY )
                    {
                        TestTile(x-1,y+1);
                        if(isGemMatching == true)
                        {
                            collector.Add(CoreGameManager.gridBoardCopy[x-1,y+1]);
                            currentBaseTile = CoreGameManager.gridBoardCopy[x-1,y+1];
                            CoreGameManager.gridBoardCopy[x-1,y+1] = null;
                            CoreGameManager.gridBoardCopy[x,y] = null;
                            diagzMatchCount ++;
                            x = x-1;
                            y = y+1;
                        }
                        else
                        {
                            isCheckingNeighbors = false;//Set the LOOP Exit condition.
                        }
                    }
                    else
                    {
                        isCheckingNeighbors = false;
                    }
                }
                currentBaseTile = parentBaseTile;
                x = currentBaseTile.Row;
                y = currentBaseTile.Column;
            }
        
        
//CHECKING RIGHT and DOWN....
            if(x + 1 <= GameBoard.BoardWidth-1 && y-1 >= 0 && CoreGameManager.gridBoardCopy[x+1,y-1] != null && CoreGameManager.gridBoardCopy[x+1,y-1].GemColorType != Gem.GEMTYPE.EMPTY)
            {
                isCheckingNeighbors = true;
                while (isCheckingNeighbors)
                {
                    if(x + 1 <= GameBoard.BoardWidth-1 && y-1 >= 0 && CoreGameManager.gridBoardCopy[x+1,y-1] != null && CoreGameManager.gridBoardCopy[x+1,y-1].GemColorType != Gem.GEMTYPE.EMPTY )
                    {
                        TestTile(x+1,y-1);
                        if(isGemMatching == true)
                        {
                            collector.Add(CoreGameManager.gridBoardCopy[x+1,y-1]);
                            currentBaseTile = CoreGameManager.gridBoardCopy[x+1,y-1];
                            CoreGameManager.gridBoardCopy[x+1,y-1] = null;
                            CoreGameManager.gridBoardCopy[x,y] = null;
                            x = x+1;
                            y = y-1;
                            diagzMatchCount++;
                        }
                        else
                        {
                            isCheckingNeighbors = false;//Set the LOOP Exit condition.
                        }
                    }
                    else
                    {
                        isCheckingNeighbors = false;
                    }
                }
                currentBaseTile = parentBaseTile;
                x = currentBaseTile.Row;
                y = currentBaseTile.Column;
            }
                diagzMatchCount = 0;
                //If we Found 3 or more of same color tile in a straight line ,rocess collector
                if(collector.Count >= minNumGemsForChain - 1)
                {
                    if(!finalListOfGemsToDestroy.Contains(parentBaseTile))
                    {
                        finalListOfGemsToDestroy.Add (parentBaseTile);
                    }
                        finalListOfGemsToDestroy.AddRange(collector);
                }
                collector.Clear ();
    }

DESTROY FINAL LIST:

//Destroy FINAL list of contiguous matching gems.  Send the LIST to destroy INTO the helper method
public static void DestroyMatchingGems(List<Gem> matchingListOfContiguousGemsToRemove)
    {
        //Go through each gem in our Final compiled list of gems to be destroyed
        for(int i=0; i < matchingListOfContiguousGemsToRemove.Count;i++)
        {
            int x = matchingListOfContiguousGemsToRemove[i].Row;
            int y = matchingListOfContiguousGemsToRemove[i].Column;
            Destroy (CoreGameManager.visualGrid[x,y]);
            //Populate gridtile with a NEW EMPTY, NORMAL GEM
            CoreGameManager.gridBoard[x,y] = new Gem(Gem.GEMTYPE.EMPTY,Gem.GEMMOD.NORMAL,x,y);
            //Visual Grid array NULL is "empty"
            CoreGameManager.visualGrid[x,y] = null;
            
        }
            //Clean Up
            matchingListOfContiguousGemsToRemove.Clear();
    }

RESETTLE BOARD:

/*
* In each row, we’ll work our way up from the bottom until we find an empty cell.
* Then, we’ll make a note of that cell. The next time we find a tile,
* we’ll simply shift it down to that location and add one to our “empty cell” index:
*/
public static void SettleBlocks(GameBoard board)
        {
            //Clear the List as we are about to use/re-use it
            topOfRecursionBaseTiles.Clear ();
            for (int x = 0; x < GameBoard.BoardWidth; x++)
            {
                firstEmptyTile = null;
            
                for (int y = 0; y <GameBoard.BoardHeight; y++)
                {
                    //check if the tile is EMPTY and firstEmptyTile is NULL
                    if(board[x,y].GemColorType == Gem.GEMTYPE.EMPTY && !firstEmptyTile.HasValue )
                    {
                        firstEmptyTile = y;
                    }
                    else if(board[x,y].GemColorType != Gem.GEMTYPE.EMPTY && firstEmptyTile.HasValue)
                    {
                        CoreGameManager.visualGrid[x,firstEmptyTile.Value] = CoreGameManager.visualGrid[x,y];
                        board[x,firstEmptyTile.Value] = board[x, y];                    
                        board[x, y] = new Gem (Gem.GEMTYPE.EMPTY,Gem.GEMMOD.NORMAL,x,y);
                        //UPDATE INDEX POINTER COORDS IN THE "GEM" at BOARD LOCATION
                        //X will always be the same as we dont move Gems left to right when we resettle the board
                        board[x, firstEmptyTile.Value].Row = x;
                        //Y Needs to be updated as we moved it DOWN "firstEmptyTile.Value" number of squares
                        board[x, firstEmptyTile.Value].Column = firstEmptyTile.Value;//the NEW Y pos
                        //Add the gems ABOVE the empty gaps as ROOT base tiles since we updated their positions internally correctly
                        topOfRecursionBaseTiles.Add(board[x, firstEmptyTile.Value]);
                        //Get the current x,y transform (of the gem GAMEOBJECT) so we can change it
                        Vector3    currentGemToRestack = CoreGameManager.visualGrid[x,firstEmptyTile.Value].transform.position;
                        //Save the Value as the "New" Y position to use
                        currentGemToRestack.y = (firstEmptyTile.Value);
                        //Move the gem down
                        CoreGameManager.visualGrid[x,firstEmptyTile.Value].transform.position = currentGemToRestack;
                        //We moved the gem down, now make sure the empty gap index is updated
                        firstEmptyTile++;
                        //Make the x,y gamebject in memory NULL as we moved it (null is "empty" in the visualGrid Array of GameObjects)
                        CoreGameManager.visualGrid[x,y] = null;
                    }
                }
        
            }
 
//Testing
        for(int i =0;i <topOfRecursionBaseTiles.Count;i++)
            {
print ("topOfRecursionBaseTiles: "+topOfRecursionBaseTiles[i]);
            }
        
        }

Sorry for the LONG post, but I figured I would post the code BEFORE someone says “hey, we dont know what the hell your talking about without seeing it…” Lol


I’m probably not going to get a chance to look through all this code, but now that you’ve written it, I recommend you go back and simplify it. You have an idea about how you want to tackle your problem so the second time through should be much faster and allow you to drastically reduce the amount of code needed. For example, your “checking left” and “checking right” code is virtually identical (same for checking left&up, and right&down) and could probably be the just a single block of code. In fact, you could factor out a lot of your code into ‘checking adjacent’ styles functions that only varies by how the x & y values change. E.g. in any direction you can define a ‘PreviousGem’ and ‘NextGem’, where the value returned is determined by the the axis - horizontal, vertical, or diagonal.

R

Yeah, that’s a lot of code.

Ok, I see the point about alot of code, and I have once before gone through it and broke it down, as I will do again as suggested. I am sorry for the post, I have no one helping me but you guys, so I am giving it a go…Alone… lol
The code is mostly repeative , so it should be to hard to break it down further, however, its NOT working, so I dont know if i should start over or just keep on trying to debug this mess? lol Either way, I’m sorry to tell you guys, I just cant give this up until i get it right. ha Since im not obviously grasping what R.Lindsay and super angry (at me? lol) penguin are trying to tell me to write, maybe a little routine (code) to suggest what direction i should be going other then my previous approach? :slight_smile:
Thanks
King

Great…I can hear it now… King Too (much code) Tall…

There are countless ways to refactor this. Here are some suggestions.

First up let me just say it’s fine to break down the problem into small steps as you have tried to do. However what we want to do after that is factor out common logical steps that are being repeated into a single block of code or function.
For example a lot of your code is concerned with moving along a given axis - horizontal, vertical, negative diagonal and positive diagonal - and collecting a match. All of this code has a common set of steps: given a particular gem, collect the matching gems before and after it into a match sequence. If the sequence length is over a given value, say 3, save them for later processing (in this case deletion).

If you look over your code, this logic is repeated numerous times for each axis. Not only that, its repeated two times for each axis - when checking previous and next gem matches.But the worst thing of all is that it is not done in a way that we can reuse. The next time you have to move around the board, you have to write everything again from scratch.

Before I offer some psuedocode let me highlight what I just said. Whenever you pass around a gem you are also passing around - separately - it’s x & y values. E.g.

public static void CheckForNeighborsVert(Gem currentBaseTile, int x, int y)

This is ugly. Navigating around the board is going to be something you do a lot. We don’t want to have to write it out (and debug it) 500 times. To make our code more readable we just want to pass around gems and refer to those Gems adjacent to it without specifying x&y values. We would prefer code such that given a gem we can always retrieve it’s position on the board. We want to be able to find gems based on their relation to one another. One way is to add the following methods to the Gem class (these are a spatial relation):

public Gem Above();
public Gem Below();
public Gem Left();
public Gem Right();

In order to do this gems will need a method to find their position. You can either store the x&y values on each gem instance, and remember to keep it updated as they move, or index each gem location on the board class with a hashtable. Or just search for it each time.
The methods should return either a Gem or null if there is no adjacent Gem in that direction. You can call these methods whatever you like, I just used Above(), Below() etc as an example.

Building on this, we can specify our axis and add in a function to easily navigate along a given axis (a slightly higher level of spatial abstraction). Implementing the following two methods is one such way to do this:

        public Enum AXIS
        {
            HORIZONTAL,
            VERTICAL,
            DIAGONAL_POS,
            DIAGONAL_NEG
        }

        public Gem Previous(AXIS axis)
        {

        }

        public Gem Next(AXIS axis)
        {

        }

Finally, we can replace almost all of the code you wrote above with the following code that is vastly simpler. Best of all we can reuse the navigational code in other functions.

        public static List<Gem> Match(Gem gem, AXIS axis, int minMatchLength)
        {
            List<Gem> result = new List<Gem>();
      
            // add the given gem
            result.Add(Gem);

            // find longest common match before our given gem
            Gem check = gem;
            while ((check = check.Previous(axis)) != null)
            {
                if (gem.Matches(check))
                {
                    // Prepend the matched gem
                    result.Insert(0, check);
                }
                else
                {
                    break;
                }
            }

            // find longest common match after out given gem
            check = gem;
            while ((check = check.Next(axis)) != null)
            {
                if (gem.Matches(check))
                {
                    // Append the matched gem
                    result.Add(check);
                }
                else
                {
                    break;
                }
            }

            return result.Count >= minMatchLength ? result : null;
        }

Why is this an improvement…
It’s important to reflect and really understand why this is an improvement on the code you have (remember, this is pseudocode and almost certainly wont compile). We have factored out all the code that navigates around the board, and our matching function above has only one simple task: using the navigational methods specified on the Gem class we do only one thing - build up match sequences.
You will have a lot of code in your game that navigates around the board in various ways, based on various relationships between gems (in this case the relationships are spatial) and creating robust methods to do this easily is going to vastly reduce the amount of time spent writing and debugging. Also it is far clearer to read and understand what is going on.

Like I said, this is only one way to approach the problem. At the risk of sounding like a broken record please remember that the important lesson to take away is to factor out common logic - in this case finding gems in a particular relation to another - into general methods that make our code much easier to read and debug, and allow us to build complexity upon them without drowning in unreadable code.

R

P.S. @CaptainScience_1 looks like he was telling you something very similar to this, though with a different implementation (possibly better than mine). Remember the specific implementation I’ve presented is less important than the lesson - break down problems into small reusable methods that can be layered to build up complexity in a natural way. Think about the relations between objects that are important in your game and write out methods to allow you to work with them naturally.

R.Lindsay, thank you for the reply again.The answer that you have given above is to the question I was trying to ask (but didn’t know how to word?) in the first place. I knew there was going to be a good way and a not so good way to setup my data structures/classes. I have approached the resolution to my problem the brute force way, lol which is the not so smart way. Let me go take another look at how my Gem class is setup, and implement the methods you described.
I’ll follow up with my progress asap. Thanks Again. And yes, I did take away more then just the simple code you put together from this. I knew the WHAT, just not the HOW.
King