7
\$\begingroup\$

I have a grid of tiles in a game and each tile can have a certain simple shape on it.

I want to be able to determine whether the combined shape from any given arrangement of these tiles results in an 'unbroken' or 'broken' larger shape.

For example; this is an example of an 'unbroken' shape...

This is an example of an unbroken shape

And this is an example of an 'broken' shape...

This is an example of an broken shape

I'll be able to write the necessary code once I figure out the logic of this problem, but so far I've been struggling.

I've tried data tables associated to each tile that describe it's edges, for example :

var edges = {
    top : false,
    right : true,
    bottom : true,
    left : false
}

And from this I can determine whether each tile is 'connected' to it's neighbours. But this doesn't help for all situations.

EDIT 1: Multiple clusters of isolated 'unbroken' shapes would be considered a 'broken' shape...

Multiple clusters of isolated 'unbroken' shapes

EDIT 2:

Also, an 'unbroken' shape can be achieved if a shape tile's edge is not connected to every neighbouring tile, it can be just one connection. For example I would consider this to be 'unbroken' ...

an 'unbroken' shape can be achieved if a tile's edge is not connected to every neighbouring tile

Anyone got any ideas on this?

\$\endgroup\$
1
  • \$\begingroup\$ "But this doesn't help for all situations." Do you have an example of a situation where determining connectivity to neighbours isn't enough? It looks like a connected components problem which could be solved with depth-first/breadth-first search. \$\endgroup\$
    – DMGregory
    May 13 '15 at 15:21
8
\$\begingroup\$

This is a basic connected components problem, and can be solved with a single invocation of breadth-first or depth-first search, or any flood-fill algorithm.

bool IsOneSolidShape(TileCollection tiles)
{
    // Clear visited flags on all tiles.
    // (This can also be implemented as a temporary set/map or parallel array,
    // if you prefer not to clutter your Tile type with book-keeping data)
    foreach(var tile in tiles)
        tile.IsVisited = false;

    // Prepare a container to hold tiles whose neighbours we haven't searched yet.
    // With a stack, this is depth-first search. A queue gives breadth-first.
    var pending = new stack<Tile>();

    // Seed the search with some start tile - this choice is arbitrary.
    var startTile = tiles.GetSomeNonEmptyTile();
    startTile.IsVisited = true;
    pending.Push(startTile);
    int numVisited = 1;

    // Search for as long as we have unexplored tiles in our stack:
    while(pending.Count > 0)
    {
         var tile = pending.Pop();
         foreach(var neighbour in tile.GetNeighbours())
         {
             // Skip over tiles we've already reached.
             if(neighbour.IsVisited)
                continue;

             // Check for a valid connection between this tile and this neighbour.
             if(tile.IsConnectedTo(neighbour))
             {
                // This tile is connected.
                // Mark it visited so we don't double-count it later.
                neighbour.IsVisited = true;

                // Add it to our reached set.
                numVisited++;

                // Keep note of it so we can search its neighbours.
                pending.Push(neighbour);
             }
         }
    }

    // If we have reached every non-empty tile,
    // then they are all in one connected shape.
    return numVisited == tiles.GetNonEmptyTileCount();
}

The code above only tells you if you have exactly one group.

If you want to count how many groups there are, you can do it by wrapping the outer while loop in a while(numVisited < tiles.GetNonEmptyTileCount()), each time seeding the inner while loop with a new unvisited tile and incrementing your group count.

Note that tile.IsConnecedTo(neighbour) should return true if and only if both tile and neighbour connect along their shared edge. (ie. if tile connects to the shared edge, but neighbour doesn't, it should return false)

Edit: here's a recursive version:

bool IsOneSolidShape(TileCollection tiles)
{
    // Clear visited flags on all tiles.
    // (This can also be implemented as a temporary set/map or parallel array,
    // if you prefer not to clutter your Tile type with book-keeping data)
    foreach(var tile in tiles)
        tile.IsVisited = false;

    // Seed the search with some start tile - this choice is arbitrary.
    var startTile = tiles.GetSomeNonEmptyTile();

    // Recursively search all tiles reachable from startTile.
    int numVisited = CountConnected(startTile);

    // If we have reached every non-empty tile,
    // then they are all in one connected shape.
    return numVisited == tiles.GetNonEmptyTileCount();
}

int CountConnected(Tile tile)
{
   // Initialize connected set to include "myself."
   tile.IsVisited = true;
   int connected = 1;

   // Check for connections to neighbours.
   foreach(Tile neighbour in tile.GetNeighbours())
   {
      // Skip tiles we've already visited, to avoid double-counting.
      if(neighbour.isVisited)
         continue;

      // Recursively search any neighbour we're connected to)
      if(tile.IsConnectedTo(neighbour))
         connected += CountConnected(neighbour);
   }

   return connected;
}
\$\endgroup\$
6
  • \$\begingroup\$ This looks promising. I'm just trying to pick this apart and translate it into my LUA code to test it... \$\endgroup\$ May 13 '15 at 16:43
  • \$\begingroup\$ You can implement this recursively too, rather than using a stack. I've been TAing an algorithms course where we're dealing with data sets in the thousands & millions, so I'm in the habit of using iterative forms to avoid recursion limits, but that's unlikely to be a problem for the cases you're handling. ;) \$\endgroup\$
    – DMGregory
    May 13 '15 at 16:51
  • \$\begingroup\$ Do you have an example of a recursive implementation of this? It would help me in my LUA / Corona porting. Part of me thinks it won't work with something like the last example I put on EDIT 2 of my question. But I'm eager to test it though. \$\endgroup\$ May 13 '15 at 17:11
  • 1
    \$\begingroup\$ @juliusbangert, I've added a recursive example. I can also confirm that a connected components search algorithm will correctly classify the example you shared in EDIT 2. Just ensure IsConnectedTo() checks both tiles along the shared edge, otherwise you'll get some bugs. \$\endgroup\$
    – DMGregory
    May 13 '15 at 17:31
  • 1
    \$\begingroup\$ +1 for mentioning the type of algorithm to use (graph traversal) instead of only giving a solution for the OP's specific situation. \$\endgroup\$
    – Kevin
    May 13 '15 at 22:42
3
\$\begingroup\$

Record the vertexes as lines on the edges where a shapes points lie. These will be used to match up to points/lines on the other tiles each time a tile changes.

For example: enter image description here

Above the blue lines on the top two tiles, A and B, have been calculated/saved for each edge of the tile according the shape it contains (note even though they are on different sides respectively you can extract the line for comparison using simple integer values ranging from 0 -> X.)

In the broken example the lines do not match so you could say the image is broken. Store the data as extra information in the tile to then use for comparison. If you have a set number of edge types (full edge, half edge, etc) then you could even create an enumerator for sides A,B,C and D on each tile and compare appropriately.

In our example our edges can be compared from values 0 -> 10.

var exampleTileA = {
    top : undefined,
    right : {0,10},
    bottom : {0,10},
    left : undefined
}

var exampleTileB = {
    top : undefined,
    right : undefined,
    bottom : {0,10},
    left : {0,10}
}

var exampleTileC = {
    top : {5,10},
    right : {5,10},
    bottom : {0,5},
    left : {0,5}
}

function compareLeftRight(leftTile, rightTile){
    return leftTile.right === rightTile.left;
}

console.log(compareLeftRight(exampleTileA, exampleTileB));
console.log(compareLeftRight(exampleTileA, exampleTileC));

//// Output
//  true
//  false

To approach the clusters of unbroken shapes you can simply iterate through each tile and check if it is connected to any of the previously iterated tiles:

var tiles = [tileA, tileB, ...];
var tempTiles = tiles;

// Loop through each tile and remove it from the temp
// tile array if it is connected to any of the previous tiles
for (var tile in tiles) {
     var currentIndex = tiles.indexOf(tile);

     for(var i = 0; currentIndex > i; i++) {
         if ( tileA.connectedTo(tile)) {             
             // remove from temp tiles
             var index = tempTiles.indexOf(tile);
             if (index > -1) {
                 tempTiles.splice(index, 1);
             }
         }
     }
}

if (tempTiles.length > 0) {
    // Some tile was not connected to the group
    console.log("There are " + tempTiles.length + " tiles not connected to the group");
}
\$\endgroup\$
4
  • \$\begingroup\$ Thanks Blue, I have been doing this but this only determines if one tile is connected to it's neighbour. When there are multiple 'clusters' of isolated 'unbroken' shapes I would consider it to be a 'broken' shape. But I'm not sure how to pick this up... \$\endgroup\$ May 13 '15 at 15:22
  • \$\begingroup\$ Instead of storing edge vertex information, you could also just store an integer describing the type of edge that it is - basically an edge type enum. Going this route you can check for compatible edge types with less storage, and you could have more complex matching rules including colors, textures, animations, slope of line at junction point etc. You could even make it so edges had n matches instead of just a single match per edge. \$\endgroup\$
    – Alan Wolfe
    May 13 '15 at 15:24
  • \$\begingroup\$ @AlanWolfe I did exactly that but with values from 0 to 1 : local edges = { top = nil, right = nil, bottom = { 0, 1 }, left = { 0, 0.5 } } ( in lua ) But the problem I'm having is determining if on the whole, I've got one or more 'unbroken' shapes \$\endgroup\$ May 13 '15 at 15:30
  • \$\begingroup\$ Updated with some more pseudo logic to add functionality for grouping tiles. \$\endgroup\$ May 13 '15 at 15:39
0
\$\begingroup\$

It sounds like all you are looking for is to see if there are ANY broken edges in your tiles and get a true or false back.

If that is the case, all you need to do is look at every place tiles join together (on the x axis and the y axis) and see if the edges are compatible.

You'd loop until you either found a broken edge (and you'd return true), or until you ran out of edges to check (and you'd return false).

It would basically be a for loop within a for loop (one would be X axis, the other would be Y axis) so would be an N^2 algorithm.

Is that what you are after? Does this help?

\$\endgroup\$
1
  • \$\begingroup\$ Since not all edges of a tile need to be connected (one is enough) your answer wont work. \$\endgroup\$
    – zoran404
    May 13 '15 at 19:49

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.