Как найти все завершённые пути на карте?

Question

[Мимокрокодил]

Есть игровая карта MxN из квадратных плиток. Каждый ход на одну из плиток спавнится фигура, имеющая соединения с одной или нескольких сторон. Если на карте обнаруживается замкнутый контур, или контур из 2+ фигур замыкается краем, то контур считается завершённым и плитки пропадают.

Вопрос в том, как эти контуры обнаружить?

Скрипты:

Плитка

using UnityEngine;

public class Tile : MonoBehaviour {

    [SerializeField] private Direction2D[] directions;
    [SerializeField] private TileType tileType;

    public Direction2D[] Directions { get => directions; }
    public TileType Type { get => tileType; }

    public bool HasDirection(Direction2D direction) {
        for (int i = 0; i < directions.Length; i++)
            if (directions[i] == direction)
                return true;
        return false;
    }
}

Направления

public enum Direction2D { Up, Down, Left, Right }

На данный момент я придумал только то, как собирать подсоединённые ближайшие фигуры:

фрагмент

// int[,] grid - массив ссылок на GameObject-ы фигур

private List<GameObject> GetNearestTilesInPath(int x, int y) {
	List<GameObject> tiles = new List<GameObject>();
	Tile thisTile = grid[x,y].GetComponent<Tile>();

	foreach (Direction2D direction in thisTile.Directions) {
		switch (direction) {
			case Direction2D.Up:
				if (y + 1 < 5) {
					Tile otherTile = grid[x,y+1].GetComponent<Tile>();
					if (thisTile.Type == otherTile.Type && otherTile.HasDirection(Direction2D.Down))
						tiles.Add(otherTile.gameObject);
				}
				break;

			case Direction2D.Down:
				if (y - 1 >= 0) {
					Tile otherTile = grid[x,y-1].GetComponent<Tile>();
					if (thisTile.Type == otherTile.Type && otherTile.HasDirection(Direction2D.Up))
						tiles.Add(otherTile.gameObject);
				}
				break;

			case Direction2D.Right:
				if (x + 1 < 5) {
					Tile otherTile = grid[x+1,y].GetComponent<Tile>();
					if (thisTile.Type == otherTile.Type && otherTile.HasDirection(Direction2D.Left))
						tiles.Add(otherTile.gameObject);
				}
				break;

			default:
				if (x - 1 >= 0) {
					Tile otherTile = grid[x-1,y].GetComponent<Tile>();
					if (thisTile.Type == otherTile.Type && otherTile.HasDirection(Direction2D.Right))
						tiles.Add(otherTile.gameObject);
				}
				break;
		}
	}
	return tiles;
}

Answer 1

[Wataru]

Самое простое - это воспользоватся обходом в глубину по графу для поиска циклов. Фигуры являются вершинами, а соединения между соседними - ребрами.

С обработкой контура с краем чуть-чуть сложнее. Тут можно добавить в граф фиктивную вершину, представляющую собой все края и соединить ее с фигурами, соединенными с краем. Дальше тем же самым алгоритмом надо проверить на наличие циклов. Есть только одно исключение - фигура в углу может сама иметь 2 ребра в край. Но тут можно добавить проверку в сам алгоритм - надо не останавливаться, если глубина стека равна 2, т.е. цикл получается только из края и одной фигуры.

Answer 2

[Rsa97]

Задача сводится к поиску циклов в графе.
https://neerc.ifmo.ru/wiki/index.php?title=%D0%98%...