Detect if all objects between two points are of same tag in Unity

Question

I am making a game where the floor consists of individual live and dead pixels. If a line of live pixels are drawn between the two points, you pass. If the line is broken, you cannot pass.

I would like to detect wether all objects between two points are of the same Tag. Here is a drawing to try and illustrate this:

At the moment, I have the following code that checks if the next "pixel" is live or dead using RayCasts:

function Update () {

    var pixfwd = transform.TransformDirection (Vector3.up  * Reach);
    var pixbwd = transform.TransformDirection (Vector3.down  * Reach);
    var pixleft = transform.TransformDirection (Vector3.left * Reach);
    var pixright = transform.TransformDirection (Vector3.right * Reach);

    Debug.DrawRay(transform.position, pixfwd * Reach, Color.red, 0.1f);
    Debug.DrawRay(transform.position, pixbwd * Reach, Color.green, 0.1f);
    Debug.DrawRay(transform.position, pixleft * Reach, Color.yellow, 0.1f);
    Debug.DrawRay(transform.position, pixright * Reach, Color.blue, 0.1f);

    Physics.Raycast (transform.position, pixfwd, pixhit);
    Physics.Raycast (transform.position, pixbwd, pixhit2);
    Physics.Raycast (transform.position, pixleft, pixhit3);
    Physics.Raycast (transform.position, pixright, pixhit4);


    if ( checkVision(pixhit)  || checkVision(pixhit2)  || checkVision(pixhit3)  || checkVision(pixhit4) ) { 
        nextisLive = true;
    }
    else
    {   
        nextisLive=false;
    }

}

function checkVision(pixhit:RaycastHit):boolean
{
    if ( pixhit != null && pixhit.collider != null && pixhit.collider.tag == "Live" )
    {
        return true;
    }
    return false;

    if ( pixhit2 != null && pixhit2.collider != null && pixhit2.collider.tag == "Live" )
    {
        return true;
    }
    return false;

    if ( pixhit3 != null && pixhit3.collider != null && pixhit3.collider.tag == "Live" )
    {
        return true;
    }
    return false;

    if ( pixhit4 != null && pixhit4.collider != null && pixhit4.collider.tag == "Live" )
    {
        return true;
    }
    return false;
}

Answer 1

An approach to this problem which doesn't rely on Unity's physics system is to store your "pixel" objects in a 2D array, and iterate through the array to evaluate whether or not the live pixels form a continuous path from one side to the other.

Note: This assumes that when you create/initialize your game, you store your pixel objects in the array correctly, reflective of their in-game arrangement. (ie. Representative of the rows and columns of the grid they form.)

Here's an idea of how your path validation algorithm might look:

var pixels : GameObject[,];

function Start()
{
    // Populate pixels array in here, or when you create the grid if the pixels are
    // created dynamically.
    //
    // Array should be initialized to new GameObject[GRID_WIDTH, GRID_HEIGHT];
    //
    // For this approach, it can be helpful if you group your pixel GameObjects under
    // empty GameObjects that match the structure of the array, as this will make it
    // easier to populate.
    // (Only really applies if you the pixels are not created dynamically.)
}

// Accepts two parameters, which provide the top and bottom of the generator at each
// point.
// 
// (For example, a generator spanning between pixels 0 and 2 in width would be
// represented by new int[]{0, 2})
function CheckForClearPath(startPoint : int[], endPoint : int[])
{
    // For tracking live pixels in last and current column
    var prevColumn : boolean[] = new boolean[pixels[0].length];
    var currColumn : boolean[] = new boolean[pixels[0].length];
    InitializeArray(prevColumn);

    // Iterating through each column of grid
    var x : int = 0;
    for (x = 0; x < pixels.length; x++)
    {
        // Special cases for first and last column
        var isFirstColumn : boolean = (x == 0);
        var isLastColumn : boolean = (x == pixels.length - 1);

        // Iterating through each row of grid column, first to identify live pixels
        // adjacent to previous column's live pixels
        var y : int = 0;
        for (y = 0; y < pixels[x].length; y++)
        {
            if (prevColumn[x]) {
                currColumn[y] = (pixels[x][y].tag == "Live");
            }
            else {
                currColumn[y] = false;
            }
        }

        // Next, iterating through each row of grid column, to identify live pixels
        // adjacent to current column's live pixels
        // 
        // This is done by checking whether current pixel is live, then checking whether
        // next pixel has live tag
        for (y = 0; y < pixels[x].length - 1; y++)
        {
            if (currColumn[y]){
                currColumn[y + 1] = (pixels[x][y].tag == "Live");
            }
        }

        // Check if any pixels are recorded as alive in column - if not, it means that no
        // live pixels were adjacent to last columns live pixels, and path is broken.
        if (AreAllPixelsDead(currColumn)) {
            return false;
        }

        // If first column, check if pixels next to start point are live.
        if (isFirstColumn) {
            if (!DoesPathMeetPoint(startPoint, currColumn)) {
                return false;
            }
        }

        // If last column, check if pixels next to end point are live.
        if (isLastColumn) {
            if (!DoesPathMeetPoint(endPoint, currColumn)) {
                return false;
            }
        }

        // Saving current column results in last column results
        for (x = 0; x < pixels.length; x++)
        {
            prevColumn[x] = currColumn[x];
        }
    }

    // If all goes well, path is valid
    return true;
}

function InitializeArray(arrayRef : boolean[]) {
    for (var i : int = 0; i < arrayRef.length; i++)
    {
        arrayRef[i] = true;
    }
}

function AreAllPixelsDead(arrayRef : boolean[]) {
    for (var i : int = 0; i < arrayRef.length; i++)
    {
        if (arrayRef[i]) {
            return false;
        }
    }
    return true;
}

function DoesPathMeetPoint(point : int[], columnPixels : boolean[]) {
    for (var i : int = 0; i < columnPixels.length; i++)
    {
        if (columnPixels[i] && i >= point[0] && i <= point[1]) {
            return true;
        }
    }
    return false;
}

Basically, the algorithm goes through each column of the grid, and determines whether there are live pixels adjacent to the previous column's live pixels, and live pixels adjacent to those. Successfully passing this test means that the live pixels in the grid form at least one continuous path from one end to the other. (Then there are the couple special checks to make sure the path connects to the start and end points.)

Hope this helps! Let me know if you have any questions.

Disclaimer: Code not tested, but the logic of the algorithm is there.