0
\$\begingroup\$

This is a follow-up to a similar question Determine if a set of tiles on a grid forms an enclosed shape. My needs are similar, but I do not need to check diagonal connections. I am also using Unity.

I’ve been in the process of trying to workout if a shape is closed. I decided to use VB.net as my language of choice.

enter image description here

  • Red = walls
  • Light Blue = water
  • Black = Towers
  • Dark Blue = Fill

enter image description here I’ve workout the code for filling the shape using the following website

lodev.org/cgtutor/floodfill.html

As far as I’m aware the graph formula is taken from here:

Tarjan strongly connected components algorithm

I’ve seen versions that have a list of connecting nodes in a node. The problem with that is not all sides could be connected (e.g. a node has four sides top, right, bottom, left edges these can have a connection to another node).

Although the list will only have a maximum of four connections the order could be all over, with a list depending on what order they where inserted (yes you could order them) it’s an overload that I wanted to mitigate if all possible then I though to make this easy on checking for connections each node could have four connection variables e.g. TopConnection, RightConnection, BottomConnection and LeftConnection, this would greatly simplify checking.

Please can you let me know if I’m on the correct track, if you still think the other ways is best please can you make it in layman’s terms or I’ll get lost before you start.

\$\endgroup\$
1
\$\begingroup\$

Let's break this down for you. First you are going to want a Tile class, that will keep track of each individual tiles. This class will store a reference to each of its neighbors (top, bottom, left, right).

public class Tile
{
    public float HeightValue { get; set; }
    public int X, Y;

    public Tile Left;
    public Tile Right;
    public Tile Top;
    public Tile Bottom;

    public Tile()
    {
    }
}

You are going to store these tiles in an array, when you first load up your game. Your initialization would look something like this:

//Init your tiles
Tile[,] Tiles = new Tile[Width, Height];
for (int x = 0; x < Width; x++) {
    for (int y = 0; x < Height; y++) {
        Tiles[x,y] = LoadTile(x,y);
    }
}

You would also benefit from having some helper methods that will help you retrieve information on tiles in order to later populate your tile's neighbor references.

private Tile GetTop(Tile t)
{
    return Tiles [t.X, MathHelper.Mod (t.Y - 1, Height)];
}
private Tile GetBottom(Tile t)
{
    return Tiles [t.X, MathHelper.Mod (t.Y + 1, Height)];
}
private Tile GetLeft(Tile t)
{
    return Tiles [MathHelper.Mod(t.X - 1, Width), t.Y];
}
private Tile GetRight(Tile t)
{
    return Tiles [MathHelper.Mod (t.X + 1, Width), t.Y];
}

So, with the help of the above code, you would then be able to update every Tile's neighbors, with a reference to the actual Tile that is neighboring it.

private void UpdateNeighbors()
{
    for (var x = 0; x < Width; x++)
    {
        for (var y = 0; y < Height; y++)
        {
            Tile t = Tiles[x,y];

            t.Top = GetTop(t);
            t.Bottom = GetBottom (t);
            t.Left = GetLeft (t);
            t.Right = GetRight (t);
        }
    }
}

Now your data is ready to be checked against a simple flood fill algorithm. You are going to want to add a couple of variables to your Tile class to help with this process.

public Color Color;       //You are using colors, so we can check against this
public bool FloodFilled;  //indicates that the tile was already checked

With this you can now implement any floodfill algorithm, check a tile to see what tiles are contained with it based on its color. Check if all of the tiles returned by your flood fill algorithm includes all of the tiles that you want to verify. If a tile is missing, then you know it is not a closed shape.

public class TileGroup  {
    public List<Tile> Tiles;
    public Color Color;

    public TileGroup()
    {
        Tiles = new List<Tile> ();
    }
}

private void FloodFill(Tile tile)
{
    // Use a stack instead of recursion
    Stack<Tile> stack = new Stack<Tile>();
    TileGroup tileGroup = new TileGroup();
    tileGroup.Color = tile.Color;
    stack.Push(tile);
    FloodFill(stack.Pop(), ref group, ref stack);
}

 private void FloodFill(Tile tile, ref TileGroup tiles, ref Stack<Tile> stack)
{
    // Validate
    if (tile.FloodFilled) 
        return;
    if (tiles.Color == TileGroupType.Color)
        return;

    // Add to TileGroup
    tiles.Tiles.Add (tile);
    tile.FloodFilled = true;

    // floodfill into neighbors
    Tile t = GetTop (tile);
    if (!t.FloodFilled)
        stack.Push (t);
    t = GetBottom (tile);
    if (!t.FloodFilled)
        stack.Push (t);
    t = GetLeft (tile);
    if (!t.FloodFilled)
        stack.Push (t);
    t = GetRight (tile);
    if (!t.FloodFilled)
        stack.Push (t);
}
\$\endgroup\$
  • \$\begingroup\$ Please don't take this as been rude, I developed the simple map editor above (loading saving, adding tiles with the mouse etc), That's not the issue here \$\endgroup\$ – Jason Howells Oct 23 '16 at 20:47
  • 2
    \$\begingroup\$ Use a simple flood fill algorithm is the answer. \$\endgroup\$ – jgallant Oct 23 '16 at 20:51
  • 1
    \$\begingroup\$ A flood fill will do the job. \$\endgroup\$ – jgallant Oct 24 '16 at 10:30
  • 1
    \$\begingroup\$ The amount of years you've programmed doesn't matter. A flood fill will do the job here. \$\endgroup\$ – Tyyppi_77 Oct 24 '16 at 10:34
  • 1
    \$\begingroup\$ Your arrogant behavior also doesn't add much charm. You have a person here, willing to help you solve your issue, and you are telling him to read the post properly, and schooling him on your credentials. \$\endgroup\$ – jgallant Oct 24 '16 at 10:41

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.