Алгоритм поиска пути, чтобы найти, если каждый кусок связан с конкретным объектом

Question

Я делаю игру, в которой игрок должен вращать трубы, чтобы соединить их с источником воды, но в определенный момент я получаю переполнение стека , и я не знаю, где и почему,Есть ли подходящие алгоритмы поиска пути для этой ситуации?

Первый уровень пока выглядит следующим образом:

"Сетка" - 9x9.Синий крестик является источником воды, и другие трубы должны проверить, имеют ли они правильный путь к источнику.

Каждый объект трубы выглядит следующим образом:

Он состоит из родительского элемента game object для хранения всего, обводненного объекта трубы, collider для обнаружения щелчков мыши и 3 circle colliders для обнаружения столкновения с другими каналами.Эта установка со всеми этими коллайдерами - это то, что мне удалось заставить работать.У пустой трубы и заполненной трубы есть polygon collider, чтобы предотвратить столкновение с circe colliders в странных углах.Объекты 3 circle collider необходимы из-за разных входов канала.

Теперь о коде:

Я попытался создать алгоритм поиска пути самостоятельно, чтобы проверить, есть ли у каждого тайладействительный путь к источнику воды.Я понятия не имею, почему это вызывает переполнение стека.

Вот метод поиска пути:

    public bool FindSourceOfWater() {
        foreach (var item in collidedList) {
            if (!checkedObjectsList.Contains(item)) {
                Pipe targetObjectScript = item.GetComponent<Pipe>();
                checkedObjectsList.Add(item);
                if (item.CompareTag("Pipes_WaterSource")) {
                    checkedObjectsList.Clear();
                    return true;
                } else {
                    targetObjectScript.checkedObjectsList.Add(gameObject);
                    if (targetObjectScript.FindSourceOfWater()) {
                        checkedObjectsList.Clear();
                        return true;
                    }
                }
            }
        }
        checkedObjectsList.Clear();
        return false;
    }

Что делает код:

• Каждый в настоящее время столкнулсяТовар добавлен в список.Foreach пробегает этот список.
• Если целевого объекта нет в списке уже проверенных объектов, продолжайте.
• Получите тот же сценарий в целевом объекте и добавьте этот объект в список уже проверенных объектов.
• Если тег из целевого объекта математический, очистите список проверенных объектов и верните true.Это означает, что объект, вызвавший метод, подключен к источнику воды.
• Если тег не совпадает, добавьте этот объект в список уже проверенных объектов цели (чтобы предотвратить бесконечный цикл).
• Теперь он вызывает целевой метод FindSourceOfWater.
• Если вызванный метод возвращает true, то этот экземпляр также возвращает true.
• Если нет, переходите к следующему объекту, с которым столкнулись.

Методы вызываютсяво время обновления:

    private void Update() {
        if (collidedList.Count != 0) {
            isConnectedToWaterSource = FindSourceOfWater();
        } else {
            isConnectedToWaterSource = false;
        }
        if (isConnectedToWaterSource && !filledPipe.activeSelf) {
            filledPipe.SetActive(true);
        } else if (!isConnectedToWaterSource && filledPipe.activeSelf) {
            filledPipe.SetActive(false);
        }
    }

Ошибка StackOverflow ссылается на эту строку:

if (item.CompareTag("Pipes_WaterSource")) {

Это s intended to return true if it has a valid connection to the water source tile. But i guess it s, вызывающий метод слишком много раз.Может быть, потому что это было вызвано в обновлении?Так что все проверяют источник воды одновременно.

Answer 1

Я бы сделал объект менеджера, который будет обрабатывать это для вас, в отличие от запуска этого в обновлении каждого имеющегося у вас объекта канала, вы бы запускали его только один раз в объекте менеджера и либо менеджер должен обновить все каналы, или опросите класс менеджера из метода обновления вашей трубы.

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

public class WaterConnectionManager
{
    static IList<Pipe> WaterConnectedPipes = new List<Pipe>();
    static IList<Pipe> AllPipes = new List<Pipe>();

    static void UpdatePipes()
    {
        //get the starting point for this algorithm
        Pipe waterSource = GetWaterSource();

        //recurse for all connected pipes
        UpdateWaterConnectedPipesList(waterSource);

        //Update each pipe with its current status
        foreach(Pipe pipe in AllPipes)
        {
            pipe.IsWaterConnected = WaterConnectedPipes.Contains(pipe);
        }
    }

    static void UpdateWaterConnectedPipesList(Pipe sourcePipe)
    {
        //create a method that returns connected pipes on your Pipe script.
        IEnumerable<Pipe> connectedPipes = sourcePipe.GetConnectedPipes();

        foreach(Pipe connectedPipe in connectedPipes)
        {
            //prevent infinite recursion
            if (WaterConnectedPipes.Contains(connectedPipe))
            {
                continue;
            }

            //store these connected pipes for later recursions/iterations
            WaterConnectedPipes.Add(connectedPipe);

            //recurse into the connected pipe, to find its connected pipes.
            UpdateWaterConnectedPipesList(connectedPipe);
        }
    }

    static Pipe GetWaterSource()
    {
        return AllPipes.First(p => p.IsWaterSource);
    }

}

Answer 2

Для контекста это проблемное пространство известно как Обход графика (на случай, если вы захотите продолжить изучение такого рода вещей), и здесь нет необходимости в рекурсии.Кроме того, ваши имена переменных со списком означают, что вы используете List<T>, но HashSet<T> выполняет Contains() за O (1) раз (в отличие от List<T> за O(n) время) в дополнение к , обеспечивающему уникальность его содержимого ;он лучше подходит для вашей проблемы.

Чтобы решить эту проблему, вы можете просто использовать HashSet<T> вместе с Stack<T>;один из пунктов, которые вы уже проверили, и один из оставшихся элементов, подлежащих проверке.Пока еще есть пункты, которые нужно проверить, снимите один и оцените его.Если он подключен к чему-либо, что еще не было проверено, добавьте его в проверенный набор и поместите в стек.

Вот ваш алгоритм, слегка измененный:

public bool FindSourceOfWater() {
    //Prep collections with this object's connections
    var checkedSet = new HashSet<ItemType>(collidedList);
    var remainingStack = new Stack<ItemType>(collidedList);

    //Are there items left to check?
    while (remainingStack.Count > 0) {
        //Reference the next item and remove it from remaining
        var item = remainingStack.Pop();
        Pipe targetObjectScript = item.GetComponent<Pipe>();

        //If it's the source, we're done
        if (item.CompareTag("Pipes_WaterSource")) {
            return true;
        } else {
            //Otherwise, check for new items to evaluate
            //(You'll have to publicly expose collidedList for this)
            foreach (var newItem in targetObjectScript.collidedList) {
                //HashSet.Add returns true if it's added and false if it's already in there
                if (checkedSet.Add(newItem)) {
                    //If it's new, make sure it's going to be evaluated
                    remainingStack.Push(newItem);
                }
            }
        }
    }

    return false;
}

---

Примечание: Вы также можете использовать Queue<T> для поиска в ширину вместо Stack<T> (что делает это обходом в глубину).