Как найти соединения типа 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 шт):
Один из вариантов решения в лоб. Возможно, есть более изящные способы.
- Пишем небольшое расширение, что бы проверять содержит ли наш
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;
}
}
- Делаем метод, что бы находить совпадения по горизонтали:
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;
}
- Делаем аналогичный метод для вертикали
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;
}
- Делаем метод для запуска поиска фигуры для конкретной точки //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) , что бы можно было вычеркнуть из поиска
}
}
- Делаем вспомогательный метод, что бы находить соседей конкретной точки:
/// <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();
}
- Делаем метод, что бы находить пересечения в фигуре
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, что бы искать фигуры сразу на всем поле.
Описывать каждый возможный вариант, как отдельный это сложно и бессмысленно.
Находишь все линии 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 . . .