Порівняння ефективності алгоритмів пошуку шляху при розробці ігрового штучного інтелекту

Анотація

З точки зору ігор справжній ШІ далеко виходить за рамки вимог розважального програмного проекту. В іграх така міць не потрібна. Ігровий ШІ не повинен бути наділений почуттями та самосвідомістю, йому немає необхідності вчитися чогось за межами рамок ігрового процесу. Справжня мета ШІ в іграх полягає в імітації розумної поведінки та у наданні гравцеві переконливого, правдоподібного завдання. Щоб штучний інтелект міг приймати осмислені рішення, йому необхідно будь-яким чином сприймати середовище, в якому він знаходиться. У найпростіших системах таке сприйняття може обмежуватися простою перевіркою положення об’єкта гравця. У складних системах потрібно визначати основні показники і якості ігрового світу, наприклад можливі маршрути для пересування, наявність природних укриттів на території, області конфліктів. При цьому розробникам необхідно вигадувати спосіб виявлення та визначення основних властивостей ігрового світу, важливих для ШІ системи. Наприклад, укриття на місцевості можуть бути визначені дизайнерами рівнів або заздалегідь обчислені при завантаженні або компіляції карти рівня. Деякі елементи необхідно обчислювати на льоту, наприклад, карти конфліктів і найближчі загрози. Пошук шляху або pathfinder — визначення комп’ютером найоптимальнішого маршруту між двома точками. З ним часто можна зіткнутися при розробці ігор, наприклад, якщо в них є вороги, що вільно пересуваються. Потрібно не просто прагнемо знайти найкоротшу відстань, а також необхідно враховувати і тривалість руху. Для пошуку цього шляху можна використовувати алгоритм пошуку за графом, який застосовується, якщо карта є графом. A* часто використовується як алгоритм пошуку за графом. Пошук в ширину — це найпростіший алгоритм пошуку за графом, тому в цій статті почнемо розбиратися з нього і поступово перейдемо до A*. Карти, на яких шляхи прокладаються за допомогою алгоритму «Зіткнутися і повернути», дозволяють пристосуватися до карт, що змінюються. Але у стратегічних іграх гравці не можуть чекати, поки їхні війська розберуться з прокладанням маршрутів. Крім того, карти шляхів можуть бути дуже великими, і на вибір правильного шляху на таких картах витрачатиметься дуже багато ресурсів. У таких ситуаціях на допомогу приходить алгоритм пошуку шляхів.