koobas.hobune.stream
Finding all connected tiles in a 8x8 grid / array
Hi all.
I'm looking for a method to search an 8x8 array of tiles for a game I'm working on.
Please read the outline of the problem below as its not a simple pattern match problem.
I have a grid of tiles. Each tile can be either blank or hold a token ( aka atom in the code ) each atom/token has a value that represents the number of connections the atom can make to any other atom placed N,E,S or west of it. These values range from Zero ( where no connections can be made ) to 4 ( where a maximum of four connections can be made.
Each tile holds a map of the connections that it has made as other atoms are places around it. This tile grid is stored in a TIle[8,8] array.
I am looking to search this array and find all the groups of tiles where every possible connection has been made. Below is an image giving an example of a few of these possible patterns. However in a 8x8 grid of these tiles I recon there are at least approximately 4x(8x8)to the power 64 +1 possible combinations of tiles to make valid patterns. if a valid pattern is where all tiles in the pattern are connected to at least one other tile ( of any value) and all tiles have all connections made.
Originally i planed of making a library of patterns and searching the grid for them. but this will months to compile and take a long to execute. As this need to be ran whenever a new atom is placed on a tile and at least two atoms exits in the array its not a good solution.
To recap, I'm looking for a method/algorithm that will find all instances of patterns that meet the following criteria:
At least two atoms are connected.
Each atom in the pattern is connected to at least one other in the pattern to it's N, S, E or W depending on how many connections the atom has.
All connections on all atoms in the pattern are used to connect to other atoms in the pattern.
All valid patterns that exist in the grid/array must be identified.
Any help on this or pointers towards a solution would be greatly appreciated. Thanks.
Below is a screen of the actual game where a valid pattern exits (bottom right corner).Tile colors denote number of connections Gray = 0 Red = 1 Yellow = 2 Green = 3 Blue = 4 
I worked it out!!
I'm sure it's not the most eloquent of solutions for this, but it worked for what I need. I have posted the main method below taken straight from my code. It outlines the main steps of algorithm. I got the jist of this solution from reading up on maze solving routines. I hope this helps someone else avoid the headache it gave me.
public Dictionary<int, List<Tile>> LookForPatterns()
{
Dictionary<int, List<Tile>> patternList = new Dictionary<int, List<Tile>>(); // the output goes here
int patternID = 0;
Tile[,] tiles = WorldController.Instance.World.tiles; // the grid we are going to search for patterns in
List<Tile> nodes = new List<Tile>(); // temp list used to hold the tiles the first part of this code finds
// get all the tiles/nodes that
// 1: have an atom
// 2: all the atoms connections made (fully connected)
// 3: all the atoms conected neighbours are themselves fully connected
for (int x = 0; x < tiles.GetLength(0); x++)
{
for (int y = 0; y < tiles.GetLength(1); y++)
{
Tile tile = tiles[x, y]; // the tile we are goinf to check
// check it has an atom, its not a null atom, and it is fully conected
if (tile.Atom != null && tile.MaxConnections > 0 && tile.IsFullyConnected())
{
// check that all the tiles conected to this tile are fully conected
if (tile.GetFullyConnectedNeighbours().Count == tile.MaxConnections)
{
// if the are then add this tile to nodes list for use late
if (nodes.Contains(tile) == false)
{
nodes.Add(tile);
}
}
}
}
}
// if no valied nodes where found
// return null now. no point in going further
if (nodes.Count == 0)
{
return null;
}
// find all the nodes that are linked togeather and place them in to the pattern list as a distinct pattern(ID)
// loop through the list of nodes found at the start of this method
for (int i = 0; i < nodes.Count; i++)
{
Tile currentNodeTile = nodes[i];
// create a new pattern that contains the current node only
List<Tile> pattern = new List<Tile>
{
currentNodeTile
};
// find and add all the the current nodes fully conected neighbours to the pattern
List<Tile> FcN = currentNodeTile.GetFullyConnectedNeighbours();
pattern.AddRange(FcN);
// remove the connected neighbours from the node list
foreach (Tile ct in FcN)
{
nodes.Remove(ct);
}
// remove the currentNodeTile from the nodes list
nodes.Remove(currentNodeTile);
bool invalid = false; // flag used to bail out the following loop if an invalid pattern is encountered
// loop through the tiles in the current pattern so far
// checking for fully conected neighbours that are not al ready in the pattern list
// if any are found add them to the end of the pattern and continue lopping to all
// are found or a tile that is not fully conected is found.
for (int x = 0; x < pattern.Count; x++)
{
//
if (pattern[x].GetFullyConnectedNeighbours().Count == pattern[x].MaxConnections)
{
foreach (Tile nT in pattern[x].GetFullyConnectedNeighbours())
{
if (pattern.Contains(nT) == false)
{
pattern.Add(nT);
nodes.Remove(nT);
}
}
}
else
{
invalid = true;
break;
}
}
if (!invalid)
{
Debug.Log("Valid pattern Found");
PrintCollection(pattern);
patternList.Add(patternID, pattern);
patternID++;
}
else
{
// pattern is not valid. Dump it and contine
// reset loop counter as we dropped nodes and the current count is off;
i = 0;
}
}
if (patternList.Count > 0)
{
return patternList;
}
else
{
return null;
}
}
