НЕДОСТАТКИ И ПРЕИМУЩЕСТВА ИСПОЛЬЗОВАНИЯ ТЕОРИИ ГРАФОВ В ВИДЕОИГРАХ
Аннотация
В работе рассматриваются недостатки и преимущества использования теории графов в видеоиграх. Проведен анализ существующих методов применения теории графов, как алгоримив поиска кратчайшего пути и его модификации в выгладит алгоритма Дейкстри, Беллмана, алгорим А *, жадный алгоритм и другие. Рассмотрено использование теории графов для описания состояния в котором находится персонаж и преобразования таких состояний, граф редукции. К общим недостаткам использования теории графов можно отнести работу только со структурами, содержащих графы с неотъемлемой длиной дуг, поиск кратчайшего пути только от одной вершины, для реализации метода необходимы повторы алгоритма для каждой вершины, не ищут рефлексивные замыкания и имеют достаточно сложную в сравнению с матричными методами программную реализацию.
К достоинствам метода можно отнести простоту реализации, невысокую полиномиальное вычислительную сложность, возможность машинной реализации, нахождение решении задачи, если таковой существует.
Приведенные недостатки и преимущества алгоритмов, основанных на применении теории графов в видеоиграх позволяют сделать следующий вывод: выбор алгоритма для реализации зависит от количества вершин графа, его ориентированности и количества связей между вершинами графов. Не существует единого оптимального алгоритма задач в соответствии которым невозможно установить граф с определенным количеством количеством вершин и связей между ними.
Для небольшого количества вершин оптимальным для применения в видеоиграх алгоритм а *, но когда количество вершин графа достигает ста, то применение данного алгоритма является не эффективным. Это связано с количеством сравнений, проводит алгоритм. Для большого количества вершин, с учетом недостатков и преимуществ, как оптимальным предлагаются методы последовательного уточнения сверху и метод порождения и проверки. Данные методы обладают такими недостатками как отсутствие достоверных способов оценки метода, риск потери некоторых возможных роз вязки и поиск всех возможных рас вязки. К преимуществам данных методов можно отнести наличие в них алгоритма уточнения раз вязки и внешнее воздействие на них в процессе нахождения решения.
Ключевые слова: теория графов, алгоритми поиска, алгоритм А*, видеоигра.