Find connected tiles in puzzle game

Question

I am developing my first game using libGDX and it is a puzzle game wherein you have to click on a tile to rotate it and establish a correct path from source to destination.

The highlightRoute() method can be skipped completely. Instead simply run a loop from starting tile to last tile and call method isConected() in it.:

private boolean isConnected(int position)
{
    connected = false;
    Tile currentTile = getTile(position);
    Tile topTile = null,nextTile= null ,prevTile = null ,downTile = null;
    if(currentTile.isFlag_top()){
         topTile = currentTile.topLink;
         if(currentTile.contains(currentTile.top,topTile.getState()))
         {
             //Checks if top tile's state matches with the allowed top tile states
             currentTile.top_connected = true;
             topTile.down_connected = true;
             topTile.connected = true;
             connected = true;
             topTile.checked = true;
             if(currentTile.isSource == true || currentTile.connectedToSource == true){
                 System.out.println("\n\n***Position : "+ position );
                 System.out.println("###Current tile connected to source hence Top Tile also connected to source###");
                topTile.connectedToSource = true;
             }
             else if(topTile.isSource == true || topTile.connectedToSource == true){
                 System.out.println("\n\n***Position : "+ position );
                 System.out.println("###Current tile connected to source as Top Tile is connected to source###");
                 currentTile.connectedToSource = true;
             }
             else currentTile.connectedToSource = false;
         }
         else {
             currentTile.top_connected = false;
             topTile.down_connected = false;
         }

        }
    else{
        //As flag_top of current tile is false , set its top_connected flag to false.
        currentTile.top_connected = false;
    }

    if(currentTile.isFlag_down()){
         downTile = currentTile.downLink;
         if(currentTile.contains(currentTile.down,downTile.getState()))
         {
             currentTile.down_connected = true;
             downTile.top_connected = true;
             downTile.connected = true;
             connected = true;
             downTile.checked =true;
             if(currentTile.isSource == true || currentTile.connectedToSource == true){
                 System.out.println("\n\n***Position : "+ position );
                 System.out.println("###Current tile connected to source hence Down Tile also connected to source###");
                downTile.connectedToSource = true;
             }
             else if(downTile.isSource == true || downTile.connectedToSource == true){
                 System.out.println("\n\n***Position : "+ position );
                 System.out.println("###Current tile connected to source as Down Tile is connected to source###");
                 currentTile.connectedToSource = true;
             }
             else currentTile.connectedToSource = false;
         }
         else {
             currentTile.down_connected = false;
             downTile.top_connected = false;
         }

        }
    else{
        currentTile.down_connected = false;
    }

    if(currentTile.isFlag_left()){
         prevTile = currentTile.prevLink;
         if(currentTile.contains(currentTile.left,prevTile.getState()))
         {
             currentTile.prev_connected = true;
             prevTile.next_connected = true;
             prevTile.connected = true;
             connected = true;
             prevTile.checked=true;
             if(currentTile.isSource == true || currentTile.connectedToSource == true){
                 System.out.println("\n\n***Position : "+ position );
                 System.out.println("###Current tile connected to source hence Prev Tile also connected to source###");
                prevTile.connectedToSource = true;
             }
             else if(prevTile.isSource == true || prevTile.connectedToSource == true){
                 System.out.println("\n\n***Position : "+ position );
                 System.out.println("###Current tile connected to source as Prev Tile is connected to source###");
                 currentTile.connectedToSource = true;
             }
             else currentTile.connectedToSource = false;
         }
         else{
             currentTile.prev_connected = false;
             prevTile.next_connected = false;
         }

        }
    else{
        currentTile.prev_connected = false;
    }

    if(currentTile.isFlag_right()){
         nextTile = currentTile.nextLink;
         if(currentTile.contains(currentTile.right,nextTile.getState()))
         {
             currentTile.next_connected = true;
             nextTile.prev_connected =true;
             nextTile.connected = true;
             connected = true;
             nextTile.checked =true;
             if(currentTile.isSource == true || currentTile.connectedToSource == true){
                 System.out.println("\n\n***Position : "+ position );
                 System.out.println("###Current tile connected to source hence Next Tile also connected to source###");
                nextTile.connectedToSource = true;
             }
             else if(nextTile.isSource == true || nextTile.connectedToSource == true){
                 System.out.println("\n\n***Position : "+ position );
                 System.out.println("###Current tile connected to source as Next Tile is connected to source###");
                 currentTile.connectedToSource = true;
             }
             else currentTile.connectedToSource = false;


         }
         else{
             currentTile.next_connected = false;
             nextTile.prev_connected =false;
         }

        }
    else{
        currentTile.next_connected = false;
    }
  currentTile.connected = connected;
   currentTile.checked = true;
    return connected;
}

This code is not yet perfectly running , even after you get disconnected from source, the flag does not change if you have connected to source before.

Answer 1

Here is a Pseudocode which should do it:

public void markNodes(Node startnode)
{
    colour(startnode);//<-- this highlightes the Tile
    if(left != null && startnode.isconnected(neighbourleft))
        markNodes(startnode);

    if(right != null && startnode.isconnected(neighbourright))
        markNodes(startnode);

    if(up != null && startnode.isconnected(neighbourup))
        markNodes(startnode);

    if(down != startnode.isconnected(neighbourdown))
        markNodes(startnode);
}

give the as startposition the root tile and it does highlight all tiles that are connected to it. If there is nothing connected anymore it stops automatically. This starts finding all connected to the left edge if its not null and then the right and so on.

If you dont have a Tiledmap that is up to thousands of tiles there shouldnt be any stackoverflow with it. Else do that iterative without the recursion.

Answer 2

This is how I was able to accomplish finding connected tiles and highlight specific tiles :

        //reset all flags
        reset_connectedToSource_flags();

        //find connected tiles
        for(int pos=11;pos<89;pos++)
        {
            Tile tile = getTile(pos);
            //check only route Tiles as background tiles need not be checked
            if(!tile.isBackground)
            { 
                isConnected(pos);
            }
        }

        //Find connected to source Tiles
        for(int i=0;i<no_of_Sources;i++)
            isConnectedToSource(BaseLevel.Sources[i]);

        //highlight connectedToSource Tiles
        highlightRoutes();


//  Function resets all flags indicating connected or connectedtoSource to false        
public void reset_connectedToSource_flags(){
    Tile tile=null;
    for(int pos=11;pos<89;pos++)
    {
        tile = getTile(pos);
        //check only route Tiles as background tiles need not be checked
        if(!tile.isBackground)
        {
            tile.connectedToSource = false;
            tile.checked = false;
        }
    }
}   


//Function to detect which tiles are connected to each other
boolean isConnected(int position)
{
    connected = false;
    Tile currentTile = getTile(position);
    Tile topTile,nextTile,prevTile,downTile;

    if(currentTile.isFlag_top()){
        topTile = currentTile.topLink;
        if(topTile!= null){
            if(currentTile.contains(Tile.top,topTile.getState()))
            {
                //Checks if top tile's state matches with the allowed top tile states
                currentTile.top_connected = true;
                connected = true;
            }
            else currentTile.top_connected = false;
        }
    }
    else{
        //As flag_top of current tile is false , set its top_connected flag to false.
        currentTile.top_connected = false;
    }

    if(currentTile.isFlag_down()){
        downTile = currentTile.downLink;
        if(downTile!= null){
            if(currentTile.contains(Tile.down,downTile.getState()))
            {
                currentTile.down_connected = true;
                connected = true;
            }
            else currentTile.down_connected = false;
        }
    }
    else{
        currentTile.down_connected = false;
    }

    if(currentTile.isFlag_prev()){
        prevTile = currentTile.prevLink;
        if(prevTile!= null){
            if(currentTile.contains(Tile.prev,prevTile.getState()))
            {
                currentTile.prev_connected = true;
                connected = true;
            }
            else currentTile.prev_connected = false;
        }
    }
    else{
        currentTile.prev_connected = false;
    }

    if(currentTile.isFlag_next()){
        nextTile = currentTile.nextLink;
        if(nextTile!= null){
            if(currentTile.contains(Tile.next,nextTile.getState()))
            {
                currentTile.next_connected = true;
                connected = true;
            }
            else currentTile.next_connected = false;
        }
    }
    else{
        currentTile.next_connected = false;
    }

    currentTile.connected = connected;
    return connected;
}



//Function which identifies from all connected tiles, which all are connected to source

public boolean isConnectedToSource(int currentPos){
    boolean connected = false;
    boolean fork_result = false;
    Tile curTile = getTile(currentPos);
    Tile nextTile=null,prevTile=null,downTile=null,topTile=null;
    if(curTile.checked == false) curTile.checked =  true;

    if(curTile.isHacker){
        System.out.println("####### Your network is being Hacked!! Disconnect Now!! ###########");
        return false;
    }

    //cur.top_CONNECTED
    if(curTile.top_connected){
        connected = true;
        topTile = curTile.topLink;
        if(!topTile.checked){
            //check if top isConnectedToSource
            topTile.to_source_go_down = true;
            topTile.connectedToSource = true;
            int topPos = topTile.getPos();
            boolean result = isConnectedToSource(topPos);
            if(result){ 
                if(curTile.isFork == true || curTile.isDevice== true){
                    fork_result = result;
                }
                else {
                    return true;
                }
            }

        }
    }//end cur.top_CONNECTED


    //cur.down_CONNECTED
    if(curTile.down_connected){
        connected = true;
        downTile = curTile.downLink;
        if(!downTile.checked){
            //check if down isConnectedToSource
            downTile.to_source_go_down = true;
            downTile.connectedToSource = true;
            int downPos = downTile.getPos();
            boolean result = isConnectedToSource(downPos);
            if(result){
                if(curTile.isFork == true || curTile.isDevice== true){
                    fork_result = result;
                }
                else {
                    return true;
                }
            }

        }
    }//end cur.down_CONNECTED


    //cur.next_CONNECTED
    if(curTile.next_connected){
        connected = true;
        nextTile = curTile.nextLink;
        if(!nextTile.checked){
            //check if next isConnectedToSource
            nextTile.to_source_go_down = true;
            nextTile.connectedToSource = true;
            int nextPos = nextTile.getPos();
            boolean result = isConnectedToSource(nextPos);
            if(result){
                if(curTile.isFork == true || curTile.isDevice== true){
                    fork_result = result;
                }
                else {
                    return true;
                }
            }
        }
    }//end cur.next_CONNECTED


    //cur.prev_CONNECTED
    if(curTile.prev_connected){
        connected = true;
        prevTile = curTile.prevLink;
        if(!prevTile.checked){
            //check if prev isConnectedToSource
            prevTile.to_source_go_down = true;
            prevTile.connectedToSource = true;
            int prevPos = prevTile.getPos();
            boolean result = isConnectedToSource(prevPos); 
            if(result){ 
                if(curTile.isFork == true || curTile.isDevice== true){
                    fork_result = result;
                }
                else {
                    return true;
                }
            }

        }
    }//end cur.prev_CONNECTED

    if(!curTile.isFork || !curTile.isDevice) return connected;
    else return fork_result;
}


//      Function to highlight all tiles which are connectedToSource 
void highlightRoutes(){
    Tile currentTile = null;
    int highlightedState = 0;
    int unHighlightedState = 0;
    for(int pos=11;pos<89;pos++)
    {
        Tile tile = getTile(pos);
        //check only route Tiles as background tiles need not be checked
        if(!tile.isBackground)
        {
            currentTile  = tile;
            int state =currentTile.getState();
            if(currentTile.connectedToSource){
                highlightedState = getHighlightedState(state);
                currentTile.setState(highlightedState);
            }
            else{
                unHighlightedState = getUnHighlightedState(state);
                currentTile.setState(unHighlightedState);
            }

        }
    }
}