НЕДОЛІКИ ТА ПЕРЕВАГИ ВИКОРИСТАННЯ ТЕОРІЇ ГРАФІВ В ВІДЕОІГРАХ

Анотація

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

До переваг методу можна віднести простоту реалізації, невисоку поліноміальну обчислювальну складність, можливість машинної реалізації, знаходження розв’язку задачі, якщо такий існує.

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

Для невеликої кількості вершин оптимальним  для застосування у відеоіграх є алгоритм а*, але коли кількість вершин графа досягає ста, то застосування даного алгоритму є не ефективним. Це пов’язано з кількістю порівнянь, що проводить алгоритм. Для великої кількості вершин, з урахуванням недоліків та переваг, як оптимальними пропонуються методи послідовного уточнення згори та метод породження та перевірки. Дані методи володіють такими недоліками як відсутність достовірних способів оцінки методу, ризик втрати деяких можливих роз в’язків та пошук всіх можливих роз в’язків.  До переваг даних методів можна віднести наявність в них алгоритму уточнення роз в’язків  та зовнішній вплив на них в процесі знаходження розв’язку.

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