НЕДОСТАТКИ И ПРЕИМУЩЕСТВА ИСПОЛЬЗОВАНИЯ ТЕОРИИ ГРАФОВ В ВИДЕОИГРАХ

Аннотация

В работе рассматриваются недостатки и преимущества использования теории графов в видеоиграх.  Проведен анализ существующих методов применения теории графов, как алгоримив поиска кратчайшего пути и его модификации в выгладит алгоритма Дейкстри, Беллмана, алгорим А *, жадный алгоритм и другие.  Рассмотрено использование теории графов для описания состояния в котором находится персонаж и преобразования таких состояний, граф редукции.  К общим недостаткам использования теории графов можно отнести работу только со структурами, содержащих графы с неотъемлемой длиной дуг, поиск кратчайшего пути только от одной вершины, для реализации метода необходимы повторы алгоритма для каждой вершины, не ищут рефлексивные замыкания и имеют достаточно сложную в  сравнению с матричными методами программную реализацию.

К достоинствам метода можно отнести простоту реализации, невысокую полиномиальное вычислительную сложность, возможность машинной реализации, нахождение решении задачи, если таковой существует.

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

Для небольшого количества вершин оптимальным для применения в видеоиграх алгоритм а *, но когда количество вершин графа достигает ста, то применение данного алгоритма является не эффективным.  Это связано с количеством сравнений, проводит алгоритм.  Для большого количества вершин, с учетом недостатков и преимуществ, как оптимальным предлагаются методы последовательного уточнения сверху и метод порождения и проверки.  Данные методы обладают такими недостатками как отсутствие достоверных способов оценки метода, риск потери некоторых возможных роз вязки и поиск всех возможных рас вязки.  К преимуществам данных методов можно отнести наличие в них алгоритма уточнения раз вязки и внешнее воздействие на них в процессе нахождения решения.

Ключевые слова: теория графов, алгоритми поиска, алгоритм  А*, видеоигра.