Алгоритм кратчайшего маршрута ужасно медленный

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

Я написал сценарий кратчайшего пути для игрового проекта Unity, и, хотя он работает, он становится настолько медленным при масштабировании, что при выполнении приводит к сбою Unity. То есть для одного тестового персонажа он работает медленно, но для проекта требуется масштаб.

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

Вот код. Я исключил метод, который изначально вызывает этот рекурсивный метод:

void ExploreBranch(List<Point> stem, List<List<Point>> masterList, Point target)
{
    if (masterList.Count > 0)
    {
        for (int m = 0; m < masterList.Count; m++)
        {
            List<Point> thisList = masterList[m];
            if (stem.Count + 1 >= thisList.Count) 
            {
                return;
            }
        }
    }
    Point lastPoint = stem[stem.Count - 1];
    for (int c = 0; c < lastPoint.Connections.Count; c++)
    {
        List<Point> updatedRoute = new List<Point>(stem);
        Point newConnection = new Point();
        newConnection = lastPoint.Connections[c];
        if (newConnection == target)
        {
            updatedRoute.Add(newConnection);
            masterList.Add(updatedRoute);
            return;
        }
        if (updatedRoute.Contains(newConnection))
        {    
            continue;
        }
        updatedRoute.Add(newConnection);
        ExploreBranch(updatedRoute, inspected, masterList, target);
    }
}

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

Одна из главных вещей здесь заключается в том, что мне нужно сохранить фактический путь, который персонаж должен использовать и следовать в игре. Так что мне не только нужно знать, насколько коротким может быть путь, мне также нужен реальный путь.

Любые идеи будут очень признательны.

0

Добавить комментарий

Ваш адрес email не будет опубликован.