1
\$\begingroup\$

I'm currently having a problem that has stopped my productivity for quite a while. I need to check if all tiles of a color is touching each other for each color like this:
enter image description here I have all my code for moving the tiles around and switching levels, but i can't seem to work out a proper algorithm that checks if the level is complete(see image above).

The base of my code is the Tile[] that holds information about all these tiles.

The Tile class looks like this:

public class Tile {
int x = 0;
int y = 0;
int type = 0;
boolean checked = false;

//SETTERS AND GETTERS FOR ALL VALUES
public void setX(int v){
    x = v;
}
public int getX(){
    return x;
}
public void setY(int v){
    y = v;
}
public int getY(){
    return y;
}
public void setType(int v){
    type = v;
}
public int getType(){
    return type;
}
public void setChecked(boolean v){
    checked = v;
}
public boolean getChecked(){
    return checked;
}
}

The "type" is the color of the tile.
Should mention that the Tile[]'s length is 25 and that each tile has got a X & Y from 0-4.
I need something that can return me a boolean[] finishedColors so i can check if it's done.

All kinds of help is surely welcome!

\$\endgroup\$
  • 1
    \$\begingroup\$ Urgh. That Tile class reeks of C++. Use properties, please. \$\endgroup\$ – MrCranky Jun 30 '14 at 9:16
  • \$\begingroup\$ @MrCranky Explain please? Why c++? \$\endgroup\$ – VelocityHD Jun 30 '14 at 9:17
  • 1
    \$\begingroup\$ You could use a flood like algorithm to get store groups of adjacent same colours. Then check if there's more than one group per colour. \$\endgroup\$ – Ben Jun 30 '14 at 9:24
  • \$\begingroup\$ @VelocityHD If you need get and set functions for your variables, use properties instead, which would be something like this: pastebin.com/1TD2BLrV Then, to access these values, you transparently use tile.x and tile.x = something instead of tile.getX() and tile.setX(something). It looks cleaner, but works the same. \$\endgroup\$ – Kroltan Jun 30 '14 at 9:27
  • \$\begingroup\$ @Ben Do you have an example of usage or how a "flood algorithm" works? Sorry i'm kind of a scrub when it comes to algorith thinking. \$\endgroup\$ – VelocityHD Jun 30 '14 at 9:38
3
\$\begingroup\$

Essentially a series of flood fills - one for each cell in the grid, but skipping over any you've already visited, and dropping out early if you find a cell not connected to a group you've already flood-filled/gathered but of the same type as that group.

Written blind, so please excuse any code typos or holes; highlight them in a comment and I will amend. Also assuming a 2D array storing tiles, width and height variables detailing dimensions. With this algorithm, you don't need a Tile class at all - just a 2D array of ints would do just fine.

int IndexFromXY(int x, int y)
{
    return (y * width) + x;
}

void GatherConnectedTilesOfType(int type, int x, int y, List<int> visitedTiles)
{
    if ((x < 0) || (x >= width)) { return; } //Trivial succeed when out of bounds
    if ((y < 0) || (y >= height)) { return; }

    int index = IndexFromXY(x,y);
    if (visitedTiles.Contains(index))
    {
        //We've already checked this tile, assume that if we're still iterating, it succeeded last time
        return;
    }

    if (tiles[x][y].Type == type)
    {
        visitedTiles.Add(index);

        //Check adjacent tiles
        GatherConnectedTilesOfType(type, x+1, y, visitedTiles);
        GatherConnectedTilesOfType(type, x, y+1, visitedTiles);
        GatherConnectedTilesOfType(type, x-1, y, visitedTiles);
        GatherConnectedTilesOfType(type, x, y-1, visitedTiles);
    }
    else
    {
        //Don't proceed to adjacent tiles, this one doesn't match
    }
}

boolean IsComplete()
{
    Map<int, List<int>> connectedTiles = new HashMap<int, List<int>>();
    for (int x = 0; x < width; ++x)
    {
        for (int y = 0; y < height; ++y)
        {
            int type = tiles[x][y].Type;
            if (connectedTiles.containsKey(type))
            {
                //We've already found at least one contiguous segment of this type,
                // so if this tile isn't in that segment, the type has more than
                // one segment of that type
                int index = IndexFromXY(x,y);

                List<int> connectedTilesOfThisType = connectedTiles.get(type);
                if (!connectedTilesOfThisType.contains(index))
                {
                    return false; //More than one contiguous segment with this type
                }
                else
                {
                    //Continue on - we've already covered this cell in a Gather
                }
            }
            else
            {
                List<int> connectedTilesOfThisType = new ArrayList<int>();
                GatherConnectedTilesOfType(type, x, y, connectedTilesOfThisType);

                connectedTiles.put(type, connectedTilesOfThisType);
            }
        }
    }
    //If we get this far, we only found cells which were contiguous with cells of the same colour (and connectedTiles details the various sets)
    return true; 
}
\$\endgroup\$
  • \$\begingroup\$ This seems like it would work perfectly for my game. Although I'm unsure about one thing; This would return true for the one type it's getting? So i'll have to for loop this function for every color giving it another type? Also, it's the "IsComplete()" i'm calling? \$\endgroup\$ – VelocityHD Jun 30 '14 at 9:42
  • \$\begingroup\$ No, the IsComplete property is what you'd call, GatherConnectedTilesOfType is just a helper. I'll attempt a quick rewrite in Java, but you'll have to excuse me my knowledge of the equivalent C# collections is a little rusty. \$\endgroup\$ – MrCranky Jun 30 '14 at 9:50
  • \$\begingroup\$ This is the sole error getting thrown at all dictionaries and lists:- Syntax error on token "int", Dimensions expected after this token \$\endgroup\$ – VelocityHD Jun 30 '14 at 9:52
  • \$\begingroup\$ That was probably my use of [x,y] (C# style) instead of [x][y] (Java style) which I've corrected now. Other than that, I'm not going to go through and debug exactly where it's broken, I don't have that much time, nor is this site a good place to do so. So sorry, you'll have to tackle getting it compiling yourself. Algorithmically it should be sound, so tweak the syntax to match what you've actually got already and you should be fine. If there are any flaws with the logic though, come back and point them out. \$\endgroup\$ – MrCranky Jun 30 '14 at 9:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.