Застосування теорії графів для удосконалення та візуалізації алгоритму пошуку найкоротшого шляху в математичній моделі відео ігри
DOI:
https://doi.org/10.32347/0131-579x.2020.97.23-28Ключові слова:
теорія графів, зважений граф, неорієнтований граф, візуалізація роботи алгоритму, комп’ютерне моделювання.Анотація
Проектування складних систем, вивчення їх властивостей і управління ними потребують розробки математичної моделі. Дослідження характеристик системи за допомогою математичних моделей часто є єдиним способом вивчення складних систем і вирішення найважливіших практичних завдань.
Застосування теорії графів для побудови математичної моделі обумовлено можливістю опису ними широкого класу об’єктів та процесів. Це дає можливість автоматизації пошуку оптимального маршруту, досяжності цілі, мережевого планування. Однією з сфер такого застосування є відеоігри, які потребують розробки інтерфейсу, візуалізації дій користувачів та персонажів, розробки алгоритму та прорахунок дій рухомих персонажів в процесі гри. Широко застосовуються ігри у жанрі Roguelike, особливостями яких є випадкове, створення рівнів, покроковий ігровий процес, плиткова (тайлова) або ASCII-графіка.
В роботі запропоновано узагальнення алгоритму пошуку найкоротшого шляху А* при динамічній кінцевій цілі за допомогою методу проходу всіх вершин зваженого неорієнтованого графу, а також реалізація цього алгоритму для візуалізації.
Посилання
Stuart Russell, Peter Norvig Artificial Intelligence: A Modern Approach, 2004, Prentice Hall, ISBN 3-8273-7089-2
P. E. Hart, N. J. Nilsson, B. Raphael A Formal Basis for the Heuristic Determination of Minimum Cost Paths, IEEE Transactions on Systems Science and Cybernetics SSC4 (2), pp. 100—107, 1968.
P. E. Hart, N. J. Nilsson, B. Raphael Correction to «A Formal Basis for the Heuristic Determination of Minimum Cost Paths», SIGART Newsletter, 37, pp. 28-29, 1972.
Anthony Stentz Optimal and Efficient Path Planning for Partially-Known Environments, Original D* paper, ICRA International Conference on Robotics and Automation, 1994.
Amid P. Red Blob Games. Introduction to the A* Algorithm [Електронний ресурс] / Petel Amid – Режим доступу до ресурсу: https://www.redblobgames.com/pathfinding/a-star/introduction.html.
##submission.downloads##
Номер
Розділ
Ліцензія
Авторське право (c) 2020 Vladimer Vanin, Olha Zalevska, Petro Jablonskiy
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:
Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.
Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.
Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).
