Как найти соединения типа T, L или + в массиве 3х3

Делая игру "3 в ряд" столкнулся в таким вопросом. Мне нужно уничтожать подобные группы:

Буква T:          Буква L:          Знак +:
1 1 1             1 0 0             0 1 0
0 1 0             1 0 0             1 1 1
0 1 0             1 1 1             0 1 0

Где единички - это блоки одного цвета, а нули - какие-то другие. Причем эти буквы могут быть повернуты на 90, -90, 180 градусов.

На данный момент я смог сделать так, чтобы программа понимала, что определенная комбинация является такой буквой вот таким образом:

// Определяем, сколько точек есть на одной линии при определенном X и Y
// conn - это массив Vector2Int единичек
        Dictionary<int, int> dictX, dictY;
        dictX = dictY = new Dictionary<int, int>();
        for (int i = 0; i < conn.Length; i++)
        {
            if (!dictX.ContainsKey(conn[i].x))
                dictX.Add(conn[i].x, 1);
            else dictX[conn[i].x]++;

            if (!dictY.ContainsKey(conn[i].y))
                dictY.Add(conn[i].y, 1);
            else dictY[conn[i].y]++;
        }

        if (dictX.ContainsValue(3) && dictY.ContainsValue(3))
            return true;
        else return false;

Эта функция возвращает true, если смогла массив 3х3 содержит столбик из 3 единичек + строчку из 3 единичек.

Однако, помимо простого уничтожения я хочу добавлять специальный бонус, который при активации будет взрываться - это сейчас не так важно. Я хочу, чтобы этот бонус образовывался на пересечении этих строчки и столбца из 3 единичек. То есть:

2: 1 1 1
1: 1 0 0
0: 1 0 0
__0 _1 _2

Бонус должен появляться в координатах (0,2) - на пересечении.

Так вот, я не понимаю, как найти это самое пересечение intersection. Чтобы не быть голословным и "без-собственных-идейным", могу сказать, что есть идея считать пересечением тот (X, Y), при котором
(X,1) == 1 && (X, 2) == 1 && (X, 3) == 1... && (1, Y) == 1 && (2, y) == 1 && (3, Y) == 1...

Но я не знаю, как точно это реализовать. Добавлю, что на вход в указанную мной функцию я подаю List. Я заполнил его с помощью рекурсии. Он хранит позиции всех блоков того цвета, который был у блока, с которого я начал искать, которые соприкасаются с ним прямо или посредственно через те, которые соприкасаются прямо; те, которые соприкасаются с теми, что соприкасаются прямо и т.д. Короче, для такого массива:

1 1 0 0
0 1 0 1
0 1 0 0
1 1 0 0

conn = { (0,0), (0,3), (1,0), (1,1), (1,2), (1,3) }, если начинать искать от левого нижнего угла.



Update: Массив conn не обязан быть 3х3. Он может быть, например, таким:

1 0 0 0
1 0 1 1
1 1 1 0

В таком случае ОПЯТЬ же должна удалиться буква L, чтобы мы получили:

* 0 0 0
* 0 1 1
* * * 0

Знаком * помечены те блоки, которые были удалены, так как составляют букву L.


Ответы (2 шт):

Автор решения: ssa112112

Один из вариантов решения в лоб. Возможно, есть более изящные способы.

  1. Пишем небольшое расширение, что бы проверять содержит ли наш conn искомый Vector2Int
static class ExtendOfVector2IntArray
{
    public static bool Contains(this Vector2Int[] array, Vector2Int value)
    {
        foreach (var currentVector in array)
        {
            if (currentVector == value)
            {
                return true;
            }
        }
        // optimize: преобразование данных в настоящую матрицу ускорит эту операцию
        return false;
    }
}
  1. Делаем метод, что бы находить совпадения по горизонтали:
   private List<Vector2Int> GetRow(Vector2Int[] conn, Vector2Int startFrom)
    {
        List<Vector2Int> result = new List<Vector2Int>();

        const int maxPointer = 3; //количевство рядов
        int currentPointer = startFrom.x;
        for (int i = currentPointer+1; i < maxPointer; i++) //+1 что бы не добавлять себя же
        {
            if (conn.Contains(new Vector2Int(i, startFrom.y)))
            {
                result.Add(new Vector2Int(i, startFrom.y)); // todo: два одинаковых new не нужны
            }
            else
            {
                return result;
            }
        }

        return result;
    }

  1. Делаем аналогичный метод для вертикали
    private List<Vector2Int> GetСolumn(Vector2Int[] conn, Vector2Int startFrom)
    {
        List<Vector2Int> result = new List<Vector2Int>();

        const int maxPointer = 3; //количевство столбцов
        int currentPointer = startFrom.y;
        for (int i = currentPointer+1; i < maxPointer; i++)
        {
            if (conn.Contains(new Vector2Int(startFrom.x, i)))
            {
                result.Add(new Vector2Int(startFrom.x, i)); // todo: два одинаковых new не нужны
            }
            else
            {
                // или ещё проверить клетки сверху?
                return result;
            }
        }

        return result;
    }
  1. Делаем метод для запуска поиска фигуры для конкретной точки //conn - координаты клеток закрашенные одним цветом
   private Vector2Int[] findFigure(Vector2Int[] conn, Vector2Int checkIt)
    {
        bool isFigure = false;
        List<Vector2Int> result = new List<Vector2Int>();
        result.Add(checkIt);

        List<Vector2Int> row = GetRow(conn,checkIt);

        if (row.Count > 1) //3 в строке
        {
            isFigure = true;
        }

        result.AddRange(row);

        List<List<Vector2Int>> columns = new List<List<Vector2Int>>();

        foreach (var currentPointer in result)
        {
            columns.Add(GetСolumn(conn,currentPointer));
        }

        foreach (var currentColumn in columns)
        {
            if (currentColumn.Count > 1) // 3 в ряду
            {
                isFigure = true;
            }

            result.AddRange(currentColumn);
        }
        // todo: возможно нужна рекурсия для ловли совсем сложных фигур типа буквы Ш

        if (isFigure)
        {
            return result.ToArray();
        }
        else
        {
            return null; //или не null, а (bool isFigure, Vector2Int[] coords) , что бы можно было вычеркнуть из поиска 
        }
    }
  1. Делаем вспомогательный метод, что бы находить соседей конкретной точки:
   /// <summary>
    /// Возвращает соседей точки point в массиве figure
    /// </summary>
    /// <param name="figure"></param>
    /// <param name="point"></param>
    private Vector2Int[] GetNeighbors(Vector2Int[] figure, Vector2Int point)
    {
        //todo: если мы точно знаем, что figure как-то отсортирован, то этим можно пользоваться
        List<Vector2Int> result = new List<Vector2Int>(4); //4 - максимальное кол-во соседей
        foreach (var currentPoint in figure)
        {
            if (currentPoint.x == point.x+1 && currentPoint.y == point.y) //сосед справа
            {
                result.Add(currentPoint);
            }
            if (currentPoint.x == point.x-1 && currentPoint.y == point.y) //сосед слева
            {
                result.Add(currentPoint);
            }
            if (currentPoint.x == point.x && currentPoint.y == point.y+1) //сосед сверху
            {
                result.Add(currentPoint);
            }
            if (currentPoint.x == point.x && currentPoint.y == point.y-1) //сосед снизу
            {
                result.Add(currentPoint);
            }
        }

        return result.ToArray();
    }
  1. Делаем метод, что бы находить пересечения в фигуре
    private Vector2Int[] GetСrossings(Vector2Int[] figure)
    {
        //todo: если фигура меньше 5 элементов сразу возвращаем пустышку        
        List<Vector2Int> result = new List<Vector2Int>();
        foreach (var currentPoint in figure)
        {
            var neighbors = GetNeighbors(figure, currentPoint);

            if (neighbors.Length > 2) // 3 или 4 соседа, по любому пересечение
            {
                result.Add(currentPoint);
                continue;
            }

            // если не интересны пересечения типа буквы Г, то continue при одном соседе
            bool oneRow = true; //все соседи на одной строке
            bool oneСolumn = true; //все соседи на одном столбце

            for (var i = 0; i < neighbors.Length-1; i++)
            {
                if (neighbors[i].x != neighbors[i + 1].x)
                {
                    oneRow = false;
                }

                if (neighbors[i].y != neighbors[i + 1].y)
                {
                    oneСolumn = false;
                }
            }

            if (!oneRow && !oneСolumn)
            {
                result.Add(currentPoint);
            }
        }

        return result.ToArray();
    }

Немножко расширив метод сравнения можно научить эту штуку работать не только с бинарными массивами, но и с массивами int, что бы искать фигуры сразу на всем поле.

→ Ссылка
Автор решения: Yaroslav

Описывать каждый возможный вариант, как отдельный это сложно и бессмысленно.

Находишь все линии 3+! Это довольно просто прочесав весь массив по горизонтали и вертикали. Найденные группы записываешь в объекты Figure.

У нас получится List<Figure> Figures, которые могут пересекаться. Сравниваем каждый с каждым и если они пересекаются, записываем новую фигуру из двух в массив List<Figure> CombineFigures и оставляем на эту новую фигуру ссылку (Contains) в тех из кого она была сделана.

public enum TileType { Red, Green, Blue };

public class Figure {
    public TileType Type;
    public List<Vector2Int> Tiles;
    public Figure Contains;

    public Figure (TileType type) {
        Type = type;
    }

    public Figure (Figure figureA, Figure figureB) {
        Type = figureA.Type;
        Tiles.AddRange(figureA.Tiles);
        Tiles.AddRange(figureB.Tiles);
        Tiles = Tiles.Distinct();
        figureA.Contains = this;
        figureB.Contains = this;
    }

    public void Add (Figure figure) {
        Tiles.AddRange(figure.Tiles);
        Tiles = Tiles.Distinct();
        figure.Contains = this;
    }

    public bool Cross (Figure figure) {
        for (int i = 0; i < Tiles.Count; i++)
            for (int j = 0; j < figure.Tiles.Count; j++)
                if (Tiles[i] == figure.Tiles[j])
                    return true;
        return false;
    }
}

for (int i = 0; i < Figures.Count-1; i++)
    for (int j = i+1; j < Figures.Count; j++)
        if (Figures[i].Type == Figures[j].Type && Figures[i].Cross(Figures[j]))
            if (Figures[i].Contains == null && Figures[j].Contains == null)
                CombineFigures.Add(new Figure(Figures[i], Figures[j]));
            else if (Figures[i].Contains != Figures[j].Contains) {
                if (Figures[i].Contains != null)
                    Figures[i].Contains.Add(Figures[j]);
                else
                    Figures[j].Contains.Add(Figures[i]);
            }

В итоге результатом будут все CombineFigures и все Figures не имеющие комбинаций (Contains == null).

И все сработает на любой комбинации, хоть такой

X X X . .
. X . . .
X X X X X
. X . . .
→ Ссылка