Первый пост. Я тоже разместил это в стеке, но кто-то посоветовал мне опубликовать его и здесь / вместо этого.
Я написал сценарий кратчайшего пути для игрового проекта 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);
}
}
Таким образом, в основном это далеко не достаточно эффективно, и я не могу понять, как в рамках этой базовой структуры это улучшить. Сейчас я склоняюсь к тому, чтобы начать заново или попытаться провести действительно эксперимент, но подумал, что сначала проверю здесь.
Одна из главных вещей здесь заключается в том, что мне нужно сохранить фактический путь, который персонаж должен использовать и следовать в игре. Так что мне не только нужно знать, насколько коротким может быть путь, мне также нужен реальный путь.
Любые идеи будут очень признательны.