Русский   English
ДонНТУ   Портал магістрів

Реферат за темою випускної роботи

Зміст

Введення

Від первісних ритуалів до сучасних високобюджетних комп'ютерних проектів, ігри були однією з найважливіших частин нашого буття. Вони розважають, надають терапевтичний вплив і навчають людей. У даній роботі ми будемо розглядати специфічний вид ігор, які зародився в 40-х роках двадцятого століття. Але широке поширення отримав в 70-х - 80-х роках минулого століття. Йдеться про комп'ютерні ігри.

За вікіпедії « Комп'ютерна ігрa – комп'ютерна програма, що служить для організації ігрового процесу (геймплея), зв'язку з партнерами по грі, або сама виступає в якості партнера » [1]. Завдяки технічному прогресу розробка програмного забезпечення в сфері розваг став загальнодоступним і простим

Одним з важливих елементів гри є ігрова механіка, тобто набір правил і способів які і реалізують ігровий процес. Взаємодія з неігровими персонажами є однією з таких механік. Розробка механік і правил за якими ці персонажі існують в грі є дуже трудомістким процесом. Але не менш важливим, так як взаємодія з персонажами в рольових або аркадних іграх є основним кістяком самої гри.

1. Мета і завдання дослідження, плановані результати

Метою моєї дипломної роботи є розробка і програмна реалізація моделі поведінки неігрових персонажів.

Завданням мого дослідження це розробити програмну реалізацію поведінки неігрового персонажа. Також розробити ігровий рушій для подальшого використання.

Одним із способів емоційно прив'язати людину до вигаданого ігровому світу, це створити ілюзію життя і наповненості. За це відповідальні персонажі комп'ютерної гри, а зокрема їх поведінку і реакція на дії гравця. Вони можуть бути, як і, доброзичливими їх називають неігровими персонажами (NPC від англ. Non – player character), так і ворожими до гравця боти (від англ. Bot) і моби (від англ. Mob).

За вікіпедії « неігровий персонаж – персонаж в іграх, що не перебуває під контролем гравця. » [2]

Плановані результати моєї роботи & ndash; це розробка алгоритму прийняття рішень неігрових персонажем і реалізація основної частини механіки гри на pygame. Надалі планую розвивати гру і при переході на більш кращий ПК перенесення на більш кращий ПК.

2. Огляд досліджень і розробок

2.1 Огляд міжнародних джерел

Дослідження по моделі поведінки були розпочаті ще в 40 – х роках минулого століття з книги Норберта Вайнера « Кібернетика, або управління і комунікації між людиною та машиною ». [3 ] У книзі « Транспортні засоби: експерименти в синтетичної психології » [4] Валентино Брайтенберг описує серію уявних експериментів, в яких « транспортні засоби » з простою внутрішньою структурою поводяться несподівано складним чином.

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

В книзі « Шампандар А.Дж. Штучний інтелект в комп'ютерних іграх: як навчити віртуальні персонажі реагувати на зовнішні впливи » [5] показано, як ввести в комп'ютерну гру синтетичні ігрові персонажі з реалістичними формами поведінки, зосереджуючись на окремих анімат (автономних створіння зі штучним тілом), що знаходяться в віртуальному світі. В « Artificial Intelligence for Games » [6] Ян Міллінгтон привносить великий професійний досвід у розв'язанні проблеми підвищення якості ІІ в іграх.Он описує безліч прикладів з реальних ігор і досліджує лежать в їх основі ідеї за допомогою докладних тематичних досліджень. Він йде далі, щоб представити безліч технік, які сьогодні мало використовуються розробниками.

2.2 Огляд національних джерел

В роботі « Розробка моделі поведінки персонажів » [7] розглядається стратегії поведінки, що застосовуються для вирішення завдання, використовуються для опису вибору шляху пересування об'єктів. У статті « Звичайно – автоматна модель управління інтелектуальних агентів в навчальних іграх » [8] розглядається застосування звичайно – автоматної моделі для моделювання поведінки інтелектуальних агентів. Проводиться обгрунтування вибору звичайно – автоматної моделі поведінки. Описується реалізація програмної платформи для моделювання поведінки.

У статті « Інтелектуальні системи в комп'ютерних іграх. Перспективи розвитку штучного інтелекту в ігровій індустрії » [9] розглядаються особливості технічної реалізації штучного інтелекту в іграх, основні методи створення інтелектуальних систем, пропонуються варіанти їх поліпшення, а також описуються перспективи розвитку даної області інформаційних технологій.

2.3 Огляд локальних джерел

В роботі магістра Бугу К.В. « Вивчення методів побудови ігрового штучного інтелекту і розробка інформаційної технології для її реалізації в покрокових стратегіях » [10] розглянуті методи побудови універсального штучного інтелекту і способи пересування. Дослідження і розробка ігрового ШІ на основі генетичного алгоритму проводив Жудіна А.Ю. в своїй роботі « Дослідження і розробка ігрового штучного інтелекту за допомогою генетичного алгоритму для колекційної карткової гри Dual choice & raquo; [11]. Також розробкою ігрового движка займався Шкімба А.А. в роботі « Засоби розробки ігрового движка для гри в жанрі стратегія » [12].

3. Короткий опис роботи

Пошук шляху – термін в інформатиці та штучному інтелекті, який означає визначення комп'ютерною програмою найкращого, оптимального маршруту між двома точками.

Пошук шляху в контексті комп'ютерних ігор стосується шляху, на якому об'єкт, що рухається шукає шлях навколо перешкод. Найбільш часто завдання пошуку шляху виникає в стратегіях реального часу, в яких гравець дає завдання ігровим юнитам (одиницям) рухатися через ігровий рівень, який містить перешкоди. Крім стратегій, завдання пошуку шляху, так чи інакше, в тій чи іншій мірі зустрічається в більшості сучасних ігрових жанрів. Так як ігри стають все складніше, то пошук шляху також еволюціонує і розвивається разом з ними.

3.1 Алгоритм A зірка

A * покроково переглядає всі шляхи, що ведуть від початкової вершини в кінцеву, поки не знайде мінімальний. Як і всі поінформовані алгоритми пошуку, він переглядає спочатку ті маршрути, які « здаються » провідними до мети. Від жодного алгоритму, який теж є алгоритмом пошуку по першому найкращому збігу, його відрізняє те, що при виборі вершини він враховує, крім іншого, весь пройдений до неї шлях. Складова g (x) – це вартість шляху від початкової вершини, а не від попередньої, як в жадібному алгоритмі.

На початку роботи проглядаються вузли, суміжні з початковим; вибирається той з них, який має мінімальне значення f (x), після чого цей вузол розкривається. На кожному етапі алгоритм оперує з безліччю шляхів з початкової точки до всіх ще не розкритих (листових) вершин графа – безліччю приватних рішень, – яке розміщується в черзі з пріоритетом. Пріоритет шляху визначається за значенням f (x) = g (x) + h (x).

Алгоритм продовжує свою роботу до тих пір, поки значення f (x) цільової вершини не виявиться меншим, ніж будь-яке значення в черзі, або поки все дерево не буде переглянуто. З безлічі рішень вибирається рішення з найменшою вартістю. Чим менше евристика h (x), тим більше пріоритет, тому для реалізації черги можна використовувати сортувальні дерева. Як і алгоритм пошуку в ширину, A * є повним в тому сенсі, що він завжди знаходить рішення, якщо такий існує.

Якщо евристична функція h допустима, тобто ніколи не переоцінює дійсну мінімальну вартість досягнення мети, то A * сам є допустимим (або оптимальним), також за умови, що ми не відкидаємо пройдені вершини. Якщо ж ми це робимо, то для оптимальності алгоритму потрібно, щоб h (x) була ще й монотонної, або спадкового евристикою. A * і припустимо, і обходить при цьому мінімальна кількість вершин, завдяки тому, що він працює з « оптимістичною » оцінкою шляху через вершину. Оптимістичною в тому сенсі, що, якщо він піде через цю вершину, у алгоритму « є шанс », що реальна вартість результату буде дорівнює цій оцінці, але ніяк не менше. Але, оскільки A * є поінформованим алгоритмом, така рівність може бути цілком можливим.

Коли A * завершує пошук, він, згідно з визначенням, знайшов шлях, справжня вартість якого менше, ніж оцінка вартості будь-якого шляху через будь-який відкритий вузол. Але оскільки ці оцінки є оптимістичними, відповідні вузли можна без сумнівів відкинути. Інакше кажучи, A * ніколи не упустить можливості мінімізувати довжину шляху, і тому є допустимим.

Припустимо тепер, що якийсь алгоритм B повернув в якості результату шлях, довжина якого більше оцінки вартості шляху через деяку вершину. На підставі евристичної інформації, для алгоритму B можна виключити можливість, що цей шлях мав і меншу реальну довжину, ніж результат. Відповідно, поки алгоритм B переглянув менше вершин, ніж A *, він не буде допустимим. Отже, A * проходить найменшу кількість вершин графа серед допустимих алгоритмів, що використовують таку ж точну (або менш точну) евристику. На малюнку 1 показаний приклад роботи алгоритму.

Алгоритм А *

Малюнок 1 – Приклад роботи алгоритму А *(25 кадрів, цикл повторень: нескінченно, розмір: 45 кб)

3.2 Хвильовий алгоритм

Алгоритм працює на дискретній робочому полі (ДРП), що представляє собою обмежену замкнутою лінією фігуру, не обов'язково прямокутну, розбиту на прямокутні осередки, в окремому випадку – квадратні. Безліч всіх осередків ДРП розбивається на підмножини: « прохідні » (Вільні), т. Е при пошуку шляху їх можна проходити, « непрохідні » (Перешкоди), шлях через цей осередок заборонений, стартова осередок (джерело) і фінішна (приймач). Призначення стартовою і фінішної осередків умовно, досить – вказівка пари осередків, між якими потрібно знайти найкоротший шлях.

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

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

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

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

На малюнках 2 – 3 показані кроки роботи хвильового алгоритму на графі.

волновой алгоритм

Малюнок 2 – Приклад роботи алгоритму

волновой алгоритм

Малюнок 3 – Приклад роботи алгоритму

3.3 Графічний рушій

За графіком в ігровому движку відповідає графічний рушій. Найкраще визначення поняття графічний рушій знайдено на вікіпедії: Графічний рушій & ndash; це проміжне програмне забезпечення, програмний рушій, основним завданням якого є візуалізація (рендеринг) двомірної або тривимірної комп'ютерної графіки [13].

Часто графічний рушій є найбільш складним компонентом ігрового движка, тому він цілком претендує на звання головного компонента ігрового движка. З цієї причини графічні движки рідко поширюються окремо самі по собі і часто включаються в якій – або інший продукт (ігровий рушій, зокрема). Однак подібне правило не відноситься до вільного програмного забезпечення, створеного ентузіастами, які створюють вільні графічні движки, які потім можна підключити як модуль до свого проекту як і інші компоненти, що входять до ігровий рушій.

Перелік посилань

  1. Википедия. Компьютерная игра [Электронный ресурс]. – Режим доступа: https://ru.wikipedia.org/wiki/Компьютерная_игра
  2. Неигровой персонаж [Электронный ресурс]. – Режим доступа: https://ru.wikipedia.org/wiki/Неигровой_персонажа
  3. Wiener, Norbert // Cybernetics, or control and communication in the animal and the machine. Cambridge, Massachusetts: The Technology Press; New York: John Wiley & Sons, Inc.
  4. Braitenberg, Valentino // Vehicles: Experiments in Synthetic Psychology, The MIT Press, Cambridge, MA. 1984г.
  5. Шампандар А.Д. Искусственный интеллект в компьютерных играх: как обучить виртуальные персонажи реагировать на внешние воздействия. : Пер. с англ. – М. : ООО «И.Д. Вильямс», 2007. – 768 с
  6. Millington, Ian Artificial intelligence for games / Ian Millington, John Funge. – 2nd ed. – 895 с.
  7. Анохин А.О. Конечно–автоматная модель управления интеллектуальных агентов в обучающих играх / А.О. Анохин, А.В. Катаев // ИТНОУ: Информационные технологии в науке, образовании и управлении, № 4 (14), 2019. – с. 75–80.
  8. Буковшин В.А. Интеллектуальные системы в компьютерных играх. Перспективы развития искусственного интеллекта в игровой индустрии / В.А. Буковшин, С.Г. Воскобойников // Современные материалы, техника и технологии, №3 (11), 2017. – ст 21–36
  9. Буга К.В. «Изучение методов построения игрового искусственного интеллекта и разработка информационной технологии для ее реализации в пошаговых стратегиях»[Электронный ресурс]. – Режим доступа: http://masters.donntu.ru/2013/fknt/buga/bio/index.htm
  10. Жудин А.Ю. «Исследование и разработка игрового искусственного интеллекта с помощью генетического алгоритма для коллекционной карточной игры Dual choice» http://masters.donntu.ru/2017/fknt/zhudin/
  11. Шкимба А.А. «Средства разработки игрового движка для игры в жанре стратегия» http://masters.donntu.ru/2014/fknt/shkimba/index.htm
  12. Википедия. Графический движок [Электронный ресурс]. – Режим доступа: http://ru.wikipedia.org/...