Unlimited Plugins, WordPress themes, videos & courses! Unlimited asset downloads! From $16.50/m
Advertisement
  1. Code
  2. Games
Code

Серыя пра штучны інтэлект - Частка 1: Пошук шляхоў

by
Difficulty:IntermediateLength:LongLanguages:

Belarusian (беларуская мова) translation by Alex Grigorovich (you can also view the original English article)

Гэты ўрок з'яўляецца першым з трох, у якім абмяркоўваецца, як падключыць штучны інтэлект (AI) у гульні і праграмы, якія вы ствараеце. У першым уроку мы даведаемся аб пошуку шляху.


Агляд вынiку работы

Давайце паглядзім фінальны вынік, над якім мы будзем працаваць:

Націсніце на кропку, затым на іншую кропку, і ІІ вызначыць самы кароткі шлях, каб прайсці паміж імі. Вы можаце выкарыстоўваць расчыняецца спіс, каб выбраць алгарытм які будзе выкарыстоўваць AI.


Крок 1: Агляд серый AI

Гэты ўрок стане першым з трох, у якім будзе абмяркоўвацца ўбудаванне штучнага інтэлекту (AI) у гульні і праграмы, якія вы ствараеце. Вы можаце падумаць, што гэта занадта складана, але на самой справе ўсё даволі проста! Я растлумачу два ключавых аспекты ІІ ў гульнях, а затым ствару класную гульню, выкарыстоўваючы тое, што мы даведаемся. Спадзяюся, вам спадабаецца наша кароткая серыя!


Крок 2: Увядзенне

У гульнях адзін з самых важных аспектаў - зрабіць яе эфектыўнай, то ёсць выканаць тое, што яна павінна рабіць, выкарыстоўваючы мінімальныя рэсурсы. Для гэтага існуе цэлая навука.

У гэтым уроку мы разгледзім ключавой аспект развіцця гульні: пошук шляху. Мы абмяркуем два лепшых метаду, то як яны працуюць, і тое як працаваць з імі ў AS3, і нарэшце, але не ў апошнюю чаргу, калі іх выкарыстоўваць. Давайце пачнем..


Крок 3: Такім чынам, пра што ідзе гаворка?

Выкажам здагадку, вы знаходзіцеся пасярэдзіне лесу з 50 рознымі патэнцыяльнымі маршрутамі, у вас амаль няма энергіі і вам трэба знайсці лепшае выйсце, як бы вы гэта зрабілі?

Адзін з варыянтаў - прайсці па кожным з 50 маршрутаў; метад спроб і памылак. Вы абавязкова аберацеся, але гэта зойме занадта шмат часу. Гэта не новая праблема, і многія людзі прапанавалі мноства ідэй як яе вырашыць. Адным з іх быў Эдсгер В.Дейкстра, які распрацаваў алгарытм для атрымання найкарацейшага шляху маючы граф, крыніца і мэта.

Перш чым мы зможам пачаць вырашэнне праблемы, мы павінны стварыць тыя элементы, граф які змяшчае ўсю інфармацыю, вузлы, якія з'яўляюцца кропкамі графіка, і лініі, якія злучаюць кропкі. Ўяўляйце, як быццам граф - гэта карта: кропкі - гэта гарады, а лініі - гэта дарогі, якія іх злучаюць.


Крок 4: Налада праекта

Перш чым мы пачнем пісаць код, давайце спачатку наладзім наша працоўная прастора. Стварыце новую тэчку і назавіце яе "PathFinding". Ўнутры стварыце іншую тэчку і назавіце яе "Graph". Затым у тэчцы PathFinding стварыце новы FLA-файл Flash (AS3) і назавіце яго "PathFinding".


Крок 5: Стварэнне сімвала вузла

У файле "PathFinding.fla" перайдзіце ў Insert > New Symbol і стварыце новы MovieClip пад назвай "Node". Выберыце "export for actionscript" і ў якасці класа напішыце "Graph.Node"


Крок 6: Маляванне вузла

Ўнутры вузла Movieclip стварыце новы круг з радыусам 25 і змесціце яго ў цэнтр. Затым дадайце новае тэкставае поле, усталюйце параметр Dynamic і дайце яму імя асобніка "idx_txt" і змесціце яго ў цэнтр сцэны.


Крок 7: Стварэнне пункту

Кожная кропка складаецца з двух асноўных элементаў; індэкс для яго ідэнтыфікацыі і яго становішча на графе. Памятаючы пра гэта, стварыце новы клас ўнутры тэчкі/пакета Graph і назавіце яго "Node". Пашырце ім клас спрайтов, а затым проста дадайце дзве зменныя: адну int для індэкса і Vector3D для пазіцыі. Акрамя таго, дадайце іх адпаведны набор і атрымаеце метады:


Крок 8: Стварэнне Лініі

Лінія складаецца з трох розных элемента: індэксы двух пунктаў, якія ён злучае, і яго "кошт" (або адлегласць паміж кропкамі ў дадзеным выпадку). Зноў жа ў пакеце/тэчцы Graph стварыце новы клас і назавіце яго "Edge"; пашырце ім клас Sprite.

Зараз дадайце дзве зменныя ints для кропак і адну зменную Number для кошту, затым дадайце адпаведны якія адпраўляюць і прымаюць метады:


Крок 9: Стварэнне графа

Граф з'яўляецца больш складаным элементам, паколькі ён павінен захоўваць усю інфармацыю. У тэчцы Graph стварыце новы клас і назавіце яго Graph. Паколькі ён проста змяшчае дадзеныя, няма неабходнасці пашыраць клас Sprite.

Граф будзе ўтрымліваць Вектар з усімі кропкамі на графе, іншы Вектар з лініямі, якія маюцца ў кожным пункце, і статычную зменную int, каб атрымаць наступны, даступны індэкс для кропкі. Такім чынам, будзе лягчэй атрымаць доступ да ўсіх элементаў на графе, паколькі індэкс пункту будзе з'яўляцца ключом вектара ліній, што азначае, што калі вы хочаце атрымаць лінію кропкі з індэксам 3, вы атрымліваеце доступ да вектар ліній у 3 пазіцыі, і вы зможаце звярнуцца да ліній для гэтай кропкі.

Зараз давайце створым гэтыя зменныя:

Графу таксама патрэбныя метады для дадання і атрымання вузлоў і ліній:


Крок 10: Пабудова Графа

Такім чынам, цяпер, калі ў нас ёсць усе неабходныя элементы, давайце працягнем і пабудуем граф.

У тэчцы PathFinding стварыце новы клас і назавіце яго "Main", гэта будзе наш асноўны клас:

Зараз нам трэба імпартаваць класы, якія мы толькі што стварылі, так як яны знаходзяцца ў тэчцы Graph. Затым стварыце дзве зменныя: адну для графа і іншую, якая ўяўляе сабой масіў пазіцыі кропак, якія мы хочам дадаць. Пасля гэтага дадайце гэтыя кропкі і іх лініі:


Крок 11: Як выбраць правільны шлях?

Як я ўжо вам казаў, існуе шмат спосабаў атрымаць самы кароткі шлях паміж двума кропкамі, напрыклад, DFS (Deep First Search) або BFS (Broad First Search), але часам вы не проста хочаце атрымаць шлях, які злучае кропкі, вы таксама хочаце атрымаць "самы лепшы" шлях, які часцей за ўсё азначае той шлях, які займае менш часу або знаходзіцца бліжэй, у залежнасці ад таго, што вам трэба.

Падчас гэтага ўроку я буду проста спасылацца на яго як на той, які каштуе менш. (У нашым выпадку памятайце, што "кошт" азначае адлегласць. У гульні вы можаце шукаць найменш небяспечны шлях, або той, які выкарыстоўвае найменшую колькасць паліва або найбольш ўтойлівы ...)

Існуюць алгарытмы, якія працуюць грунтуючыся на кошт, найбольш важнымі з якіх з'яўляюцца Алгарытм Dijkstra і Алгарытм A* (A-Star). Давайце спачатку пагаворым пра алгарытм Dijkstra. Давайце гаварыць першы пра алгарытм Dijkstra


Крок 12: Уводзіны ў алгарытм Dijkstra

Гэты алгарытм быў створаны Эдсгерам Дейкстрам ў 1959 годзе. Ён разлічваецца ў залежнасці ад кошту, якую ўяўляе кожная лінія, лініі з больш нізкай коштам заўсёды будуць выбірацца першымі, таму, калі вы дасягне мэты, вы будзеце ўпэўнены, што шлях - гэта самы выгадны шлях з магчымых.


Крок 13: Як працуе алгарытм Dijkstra

Паколькі гэты алгарытм працуе з выдаткамі, у нас павінна быць месца, дзе мы будзем захоўваць кошт пераходу на кожную кропку з зыходнай пазіцыі (стартавай кропкі); назавем гэта вектарам кошту.

Напрыклад, калі зыходнай пазіцыяй з'яўляецца кропка 0, калі мы звяртаемся да вектару кошту ў пазіцыі 3, ён верне самую нізкую кошт, пераходу ад 0 да 3 кропкі. Нам таксама спатрэбіцца спосаб захавання найкарацейшага шляху: я растлумачу паняцце самыя кароткія Дрэва шляхоў на наступным этапе.

Асноўныя этапы алгарытму наступныя:

  1. Бярэм бліжэйшую кропку, пакуль яшчэ не прааналізавалі.
  2. Дадаваны сваю лепшую лінію ў Дрэва самыя кароткія шляхi.
  3. Калі гэта мэтавая кропка, завяршаем пошук.
  4. Вымаемы усе лініі гэтай кропкі.
  5. Для кожнай лініі вылічаем кошт пераходу ад зыходнай кропкі да кропкі прыбыцця.
  6. Калі агульны кошт гэтага пункту менш кошту пункту прыбыцця, абнаўляем кошт пункту новым значэннем.
  7. Берём наступную бліжэйшую кропку, яшчэ не прааналізавалі.
  8. Паўтараем гэта дзеянне да дасягнення мэты, або да перабору ўсіх кропак.

Анімацыя надасць гэтаму больш сэнсу. Тут мы спрабуем перайсці ад 1 да 6 кропкі:


Крок 14: Асноўныя элементы алгарытму

Гэты алгарытм складаецца з розных вектараў, якія будуць захоўваць усю неабходную інфармацыю, напрыклад выдаткі на пераход да кропак, або лепшы шлях да бягучага месцы. Я растлумачу гэта больш проста:

  • Вектар выдаткаў: тут мы захаваем найлепшую кошт да таго часу, пакуль не дасягнем пэўнага пункту з адпраўной кропкі. Напрыклад, калі зыходнай кропкай будзе 3 і мы звяртаемся да элемента 6 вектара кошту, мы атрымаем найлепшую кошт, знойдзеную да гэтага часу, пачынаючы з 3, зыходнай кропкі, да кропкі 6.
  • Дрэва найкароткіх шляхоў (SPT): гэты вектар змяшчае лінію найменшых затрат для пераходу да пэўнай кропцы. Гэта азначае, што, калі мы атрымаем доступ да элемента 7 на SPT, ён верне лепшую лінію для доступу да гэтай кропкі.
  • Search Frontier (SF): гэты вектар будзе захоўваць найлепшую лінію для доступу да вызначанай кропкі, амаль гэтак жа, як і SPT, але тут будуць усе кропкі, якія яшчэ не знаходзяцца ў SPT. Гэта азначае, што SF будзе працаваць у якасці тэставай вобласці, дзе мы праверым усе лініі для адной кропкі, калі ўсе лініі будуць прааналізаваныя, мы будзем упэўненыя, што SF ўтрымлівае лепшы вынік, таму мы можам дадаць яго ў SPT.
  • Чарга з індэксаваным прыярытэтам (pq): прыярытэтная чаргу ўяўляе сабой структуру дадзеных, якая заўсёды захоўвае свае элементы спарадкаваны спосабам. Паколькі алгарытм павінен спачатку атрымаць кропку з найменшымі  выдаткамі, гэтая структура будзе размяшчаць кропкі ў парадку змяншэння у залежнасці ад іх затратнасці, але паколькі мы хочам атрымаць індэкс пункту, а не самі выдаткі, мы выкарыстоўваем індэксаваць чаргу прыярытэтаў. Напрыклад, калі першым элементам pq з'яўляецца кропка 4, гэта будзе азначаць, што гэта той пункт, якая мае самы нізкі кошт.

Заўвага: AS3 не ўтрымлівае шмат структур дадзеных, уключаючы індэксавацца чаргу прыярытэтаў, таму я напісаў код для выкарыстання яго ў гэтым уроку. Каб атрымаць яго, проста загрузіце зыходныя файлы і імпартуе тэчку utils ў тэчку PathFinding. Клас utils.IndexPriorityQ.


Крок 15. Стварэнне тэчкі з алгарытмам

Перш чым мы пачнем пісаць код, у тэчцы PathFinding стварыце новую тэчку і назавіце яе "Algorithms".

У гэтай новай тэчцы стварыце новы клас AS3 з імем "Dijkstra":


Крок 16: Алгарытм Дейкстры ў AS3

Зараз давайце напішам алгарытм. Гэта запатрабуе трох асноўных рэчаў: уласна графа, адпраўной кропкі і мэтавай кропкі; мы таксама павінны ствараць вектары, пра якія мы толькі што казалі (кошт, SPT, SF). Не забудзьцеся імпартаваць класы Graph:


Крок 17: Функцыя пошуку

Як толькі мы ўсталявалі клас, мы можам пачаць кадаваньне алгарытму, які будзе знаходзіцца ў функцыі "Search". Я растлумачу код каментарамі, таму, калі ў вас усё яшчэ засталіся пытанні, вяртайцеся да крокаў 12 і 13, каб нагадаць сабе, пра тое, як працуе гэты алгарытм:


Крок 18: Атрыманне шляху

Калі функцыя завершыць пошук, у нас будзе ўвесь шлях, які будзе запушчаны на SPT, таму мы можам атрымаць яго. Паколькі SPT абраў лепшую лінію для доступу да кропкі, мы зможам прапрацаваць яго, каб атрымаць лепшы шлях. Возьмем у якасці спасылкі наступнае выява, атрыманае з папярэдняй анімацыі:

Калі мы звернемся да SPT на мэтавай кропкі, якая ў гэтым выпадку роўная 6, яна верне лепшую лінію, каб патрапіць туды. Гэта будзе 6 - 5 лінія. Цяпер, калі мы паўторым гэты працэс з новым пунктам, які ідзе з лініяй, у 5 мы атрымаем лепшае перавага, каб дабрацца да гэтай кропкі, які з'яўляецца лініяй 5 - 2. Паўтарэнне гэтага працэсу яшчэ раз з кропкай 2 дасць нам лінію 2 - 1 , таму мы, нарэшце, дойдзем да пачатку, цяпер злучаючыся з гэтымі лініямі, атрымаем найлепшы шлях: 6 > 5 > 2 > 1.

Як вы бачыце, мы павінны рухацца назад, пачынаючы з мэты і пераходзячы да адпраўной кропкі, каб атрымаць лепшы шлях.


Крок 19: Функцыя getPath

Стварыце новую функцыю, якая будзе вяртаць масіў з кропкамі шляху, назавіце яго "getPath":


Крок 20: Завяршаем клас Дийкстра

Мы скончылі амаль усе, нам проста трэба запоўніць канструктар і выклікаць функцыю пошуку, таму клас будзе выглядаць так:


Крок 21: Стварэнне новага графа

Каб пабачыць найлепшы вынік працы алгарытму, я напісаў клас, які дапамагае з стварэннем графаў. Ён завецца Grapher і знаходзіцца ўнутры тэчкі utils, якая ідзе разам з зыходнымі файламі. Гэты клас стварае сетку кропак, з якой мы можам назіраць, як алгарытм рухаецца па графу.

З дапамогай гэтага класа зноў адкрыйце файл "Main.as" і зменіце яго. Цяпер у нас будзе наступны код:

Захавайце і запусціце файл, і вы атрымаеце гэты вынік:


Крок 22: Выкарыстанне алгарытму Дейкстры

Зараз давайце працягнем і правядзем пошук з новым алгарытмам, які мы толькі што зрабілі. Імпартуе клас Dijkstra, стварыце асобнік і выклічце функцыю getPath:

Захавайце і запусціце файл. Вы ўбачыце лініі, якія алгарытм прааналізаваў пазначаныя чырвоным, гэта лепшы шлях (ад пункту 24 да кропкі 35), які з'яўляецца як чорная лінія:


Крок 23: Ці няма чаго лепей?

Як бачым, алгарытм Дейкстры знаходзіць самы кароткі шлях паміж двума кропкамі, але, як паказвае апошняе малюнак, там шмат чырвоных ліній. Гэта азначае, што ўсе гэтыя лініі былі прааналізаваны, што немалаважна, таму што цяпер у нас невялікі граф, але ўявіце сабе большы; там было б занадта шмат ліній для аналізу. Калі б мы маглі знайсці спосаб спрасціць гэта і зрабіць алгарытм яшчэ больш эфектыўным ... такім чынам, я ўяўляю вам алгарытм A* (A-Star).


Крок 24: Алгарытм A*

Алгарытм A* ўяўляе сабой мадыфікаваную версію Dijkstra. Ён ўлічвае зменены спосаб атрымання кошту кожнай кропкі з эўрыстычнага падыхода. Гэта азначае, што мы трохі «дапамагаем» алгарытму і расказваем яму, куды ісці, працуючы як компас і перамяшчаючы алгарытм непасрэдна да мэты.

Замест вылічэнні кошту пункту шляхам падсумоўвання кошту лініі да кошту захаванай пункту цяпер вылічаецца сумаваннем кошту захаванай кропкі і эўрыстычнай коштам, якая ўяўляе сабой ацэнку таго, наколькі блізка да мэты, кропка, якую мы аналізуем. Гэты кошт называецца коштам F


Крок 25: Кошт F

Кошт F вылічаецца па наступнай формуле: F = G + H, дзе G - кошт кропкі, а H - эўрыстычная кошт ад гэтай кропкі да мэты. У гэтым уроку кошт H будзе разлічвацца з выкарыстаннем эўклідавай адлегласці паміж кропкай і мэтай, што з'яўляецца прамой лініяй паміж двума кропкамі.

Сэнс, таго што мы робім, заключаецца ў тым, што ў канцы будуць правераны першыя кропкі з больш нізкай коштам F і таму, што кошт F будзе залежаць у асноўным ад кошту H, у канцы алгарытм заўсёды будзе вызначаць прыярытэты кропак, бліжэйшых да мэты.


Крок 26: Алгарытм A* ў AS3

У тэчцы Algorithms стварыце новы клас "Astar". Зменныя ўнутры класа будуць амаль такімі ж, як клас Dijkstra, але тут у нас будзе іншы вектар для захоўвання F-кошту кожнай кропкі:

Крок 27: Новы клас пошуку

Адзіная розніца паміж функцыяй пошуку алгарытму Dijkstra і гэтым будзе заключацца ў тым, што кропкі будуць сартуюцца (у чарзе з індэксаваным прыярытэтам) у залежнасці ад вектару кошту F і што F вектар кошту будзе задавацца разлічанай коштам H і захаванай коштам G:


Крок 28: Поўны клас A*

Гэта адзіныя змены, якія неабходныя, паколькі функцыя getPath для абодвух класаў аднолькавая. У канцы клас будзе выглядаць наступным чынам:


Крок 29: Выкарыстанне алгарытму A*

Яшчэ раз адкрыйце файл "Main.as" і імпартуе клас Astar, затым выдаліце ​​створаны намі Dijkstra, замяніўшы яго на пошук A*:

Захавайце і запусціце файл. Як вы можаце бачыць, вынік вельмі ўражвае, няма чырвоных ліній, што азначае, што пошук ішоў наўпрост ад крыніцы да мэты без аналізу дадатковых ліній:


Крок 30: Які з іх лепш?

Ну, хоць алгарытм A* хутчэй і больш эфектыўна атрымлівае прамы шлях ад крыніцы да мэты, будуць выпадкі, калі Dijkstra будзе лепшым варыянтам.

Напрыклад, уявіце сабе гульню RTS, дзе вы паказалі свайму жыхару пайсці і знайсці некаторыя рэсурсы; з алгарытмам A * вам трэба будзе выканаць пошук для кожнага рэсурсу на карце, а затым прааналізаваць, які з іх бліжэй. З пошукам Dijkstra, так як ён выкарыстоўвае тую ж суму па ўсіх напрамках, першы знойдзены ім рэсурс будзе лепшым для збору, і вы выканалі б толькі адзін пошук у параўнанні з многімі пошукамі A*.

У асноўным, вы захочаце выкарыстоўваць алгарытм Dijkstra, калі вы выконваеце агульны пошук, а алгарытм A *, калі шукаеце пэўны элемент.


заключэнне

На гэтым урок завяршаецца. Я спадзяюся, што вам спадабалася і вы будзеце выкарыстоўваць яго ў вашых праектах. Сачыце за наступным урокам гэтай серыі пра AI і дайце мне ведаць, што вы думаеце пра гэта.

Дзякуй за чытанне! -Eduardo

Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.