контекст
Old Lucas Arts (эпоха ScummVM) указывает и щелкает графические приключенческие игры, использующие предварительно вычисленные пути. Вот примерный план техники.
Шаг 1
Пол в каждой комнате был разделен на то, что они называли «прогулочными коробками», которые были в значительной степени эквивалентны узлам в навигационной сетке, но ограничены трапециевидными формами. Например:
______ _____ _________ _____
\ A | B | C | D \
\_____| | |_______\
|_____| |
|_________|
Шаг 2
Автономный алгоритм (например, Dijkstra или A *) будет вычислять кратчайший путь между каждой парой узлов и сохранять первый шаг пути в двумерной матрице, индексируемой в каждом измерении по используемому начальному и конечному узлу. Например, используя прогулочные коробки выше:
___ ___ ___ ___
| A | B | C | D | <- Start Node
___|___|___|___|___|
| A | A | A | B | C | ---
|___|___|___|___|___| |
| B | B | B | B | C | |
|___|___|___|___|___| |-- Next node in shortest path
| C | B | C | C | C | | from Start to End
|___|___|___|___|___| |
| D | B | C | D | D | ---
|___|___|___|___|___|
^
|
End Node
Как вы можете догадаться, требования к памяти быстро увеличиваются с увеличением количества узлов (N ^ 2). Поскольку short обычно бывает достаточно большим, чтобы хранить каждую запись в матрице, со сложной картой из 300 узлов, что приведет к сохранению дополнительного:
300^2 * sizeof(short) = 176 kilobytesШаг 3
С другой стороны, вычисление кратчайшего пути между двумя узлами было чрезвычайно быстрым и тривиальным, всего лишь серия поисков в матрице. Что-то вроде:
// Find shortest path from Start to End
Path = {Start}
Current = Start
WHILE Current != End
Current = LookUp[Current, End]
Path.Add(Current)
ENDWHILE
Применение этого простого алгоритма для нахождения кратчайшего пути от C до A возвращает:
1) Path = { C }, Current = C
2) Path = { C, B }, Current = B
3) Path = { C, B, A }, Current = A, Exit
Вопрос
Я подозреваю, что с сегодняшним мощным аппаратным обеспечением в сочетании с требованиями к памяти для выполнения этого для каждого уровня любые преимущества, которые когда-то имели этот метод, теперь перевешиваются простым выполнением A * во время выполнения.
Я также слышал, что в настоящее время поиск в памяти может быть даже медленнее, чем общие вычисления, поэтому создание таблиц поиска синусов и косинусов уже не так популярно.
Но я должен признать, что я еще не слишком разбираюсь в этих вопросах низкой эффективности аппаратного обеспечения, поэтому я пользуюсь этой возможностью, чтобы спросить мнение тех, кто более знаком с предметом.
На моем движке мне также требовалась возможность динамически добавлять и удалять узлы на графике во время выполнения ( см. Это ), поэтому предварительно вычисленный маршрут только усложнил ситуацию, поэтому я удалил его (не говоря уже о том, что мое решение A * во время выполнения уже отлично работало) ). Тем не менее, мне было интересно ...
Итог, эта техника все еще актуальна в настоящее время в любом сценарии?
источник
Ответы:
Я не вижу никакой выгоды от использования такой техники.
Мне не хватает гибкости графика (у вас могут быть разные LODы, они не должны быть какой-то конкретной формы, т. Д.). Также любой пользователь вашего движка узнает, что такое график и как его использовать. Поэтому, если они хотят добавить дополнительные функциональные возможности, им нужно будет научиться реализовывать свое расширение, используя совершенно новую для них ситуацию.
Как вы упомянули, похоже, что это будет ужасно масштабироваться. Также стоит отметить, что если график умещается на кассе и вы выполняете все свои пути назад, то это действительно сокращает время ввода-вывода. Похоже, ваша реализация скоро станет слишком большой, чтобы поместиться в любой кеш.
Если вы не можете разместить всю свою программу и ее нужную память в кеше, вы будете вынуждены пытаться извлекать и извлекать память из памяти до того, как загрузите процессор.
Также следует понимать, что во многих играх есть отдельные циклы для обновления ИИ. Я полагаю, что способ, которым мой проект настроен, состоит в том, что есть цикл обновления для пользовательского ввода на 60 Гц, AI - только 20 Гц, и игры рисуются как можно быстрее.
Кроме того, в качестве примечания, я занимался программированием GBA просто для удовольствия, и ничто не переходит на использование современного устройства. Для GBA все сводилось к минимизации нагрузки на процессор (потому что это было жалко). Вы также должны понимать, что большинство языков высокого уровня C # и Java (не так много C ++ или C) делают для вас тонны оптимизаций. Что касается оптимизации вашего кода, их не так много, кроме как доступ к памяти как можно меньше, и когда вы выполняете на нем столько вычислений, сколько возможно, прежде чем вводить новую память, которая вытеснит ее из кэша, и убедитесь, что вы работаете с ней. делаю только один раз.
Изменить: Также, чтобы ответить на ваш заголовок, да, это так. Предварительное вычисление часто используемых путей - отличная идея, и ее можно выполнить с помощью A * в любом месте за пределами игрового цикла. Например, от базы к ресурсу в RTS, так что собрания не должны пересчитываться каждый раз, когда они хотят уйти или вернуться.
источник