Пошук шляху (англ. Pathfinding) — це побудова найкоротшого шляху між двома точками за допомогою комп'ютерної програми. Це практичніший варіант розв'язування лабіринтів. Ця галузь досліджень ґрунтується на алгоритмі Дейкстри для пошуку найкоротшого шляху на зваженому графі.
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpODBMelJqTDFCaGRHaG1hVzVrYVc1blh6SkVYMGxzYkhWemRISmhkR2x2Ymk1emRtY3ZNalV3Y0hndFVHRjBhR1pwYm1ScGJtZGZNa1JmU1d4c2RYTjBjbUYwYVc5dUxuTjJaeTV3Ym1jPS5wbmc=.png)
Задача пошуку шляху тісно пов'язана з задачею про найкоротший шлях у рамках теорії графів, яка розглядає визначення шляху, що найкраще відповідає деяким критеріям (найкоротший, найдешевший, найшвидший і так далі) між двома точками у великій мережі.
Алгоритми
По суті, алгоритм пошуку шляху досліджує граф, починаючи з однієї вершини та переходить до сусідніх вузлів і так доки не досягне цільового вузла, як правило, з наміром знайти найдешевший (найкоротший) маршрут. Хоча методи пошуку по графу, такі як пошук у ширину, знайдуть маршрут, якщо буде достатньо часу, інші методи, які «досліджують» графи, швидше досягатимуть ціль. Аналогією буде людина, яка йде по кімнаті, замість обговорення всіх можливих маршрутів заздалегідь, вона, як правило, рухається у напрямку призначення і відхиляється від шляху лише задля уникнення перешкод, і відхиляється настільки мало, наскільки це можливо.
Двома основними задачами пошуку шляху є:
- пошук шляху між двома вузлами на графі;
- задача про найкоротший шлях — знайти оптимальний найкоротший шлях.
Основні алгоритми, такі як пошук у ширину і пошук у глибину, спрямовані на першу проблему, вичерпуючи всі можливості за допомогою грубого перебору; починаючи з даного вузла, вони ітераційно досліджують усі потенційні шляхи, доки не досягають цільового вузла. Ці алгоритми використовуються за час або лінійний час, де V — кількість вершин, а E — кількість ребер між вершинами.
Більш складною проблемою є пошук оптимального шляху. Вичерпний підхід у даному випадку відомий як алгоритм Беллмана-Форда має часову складність , або квадратичний час. Однак не потрібно вивчати всі можливі шляхи, щоб знайти оптимальний. Алгоритми, такі як алгоритм A* та алгоритм Дейкстри стратегічно виключають шляхи, як за допомогою евристичного алгоритму, так і за допомогою динамічного програмування. Усунувши неможливі шляхи, ці алгоритми можуть досягати низької складності часу, як
.
Наведені вище алгоритми є одними з найкращих загальних алгоритмів, які працюють на графу без попередньої обробки. Проте, в практичних системах маршрутизації шляхів, навіть найкращі за складністю часу, можна досягти за допомогою алгоритмів, які попередньо обробляють граф для досягнення кращої продуктивності. Одним з таких алгоритмів є [en].
Алгоритм Дейкстри
Загальним прикладом алгоритму пошуку шляху базованого на графі є алгоритм Дейкстри. Цей алгоритм розпочинає роботу з початкового вузла й прямує до «відкритих вузлів» — кандидатів. На кожному наступному кроці обирається відкритий вузол з найменшою відстанню від початкового. Усі вузли, позначені як «закриті» та всі прилеглі до них вузли додаються до відкритого набору, якщо вони ще не були перевірені. Цей процес повторюється доки не буде знайдено шлях до потрібного вузла (пункту призначення). Оскільки найчастіше розглядаються вузли з найменшою відстанню, коли вперше буде знайдено пункт призначення — шлях до нього буде найкоротшим шляхом.
Алгоритм Дейкстри не працює з показниками від'ємної ваги. У гіпотетичній ситуації коли вузли А, В і С утворюють зв'язаний неорієнтований граф з ребрами АВ = 3, АС = 4, та ВС = -2, оптимальний шлях від А до С коштує 1, а оптимальний шлях від A до B витратить 2. Алгоритм Дейкстри починає з А, а потім спочатку розглядає вузол B, оскільки він розташований найближче. Цей шлях буде коштувати 3 і буде позначений як «закритий», а значить, його вартість ніколи не буде переоцінена. Це i є причиною того, чому алгоритм Дейкстри не може оцінити показники від'ємної ваги. Проте, оскільки для багатьох практичних цілей ніколи не буде показників від'ємної ваги, алгоритм Дейкстера в значній мірі підходить для задач на пошук шляхів.
Алгоритм пошуку A*
Алгоритм А* — це варіант алгоритму Дейкстри, який досить часто використовується в іграх. A* придає вагу кожному відкритому вузлу, вага якого дорівнює вазі ребра та додає приблизну відстань від ребра до фінішу. Ця приблизна відстань виявляється евристичною і являє собою мінімальну можливу відстань між цим вузлом і кінцем. Це дозволяє алгоритму усунути довші шляхи після виявлення початкового і працює наступним чином: якщо між початком і кінцем є шлях довжини X, а мінімальна відстань між вузлом і фінішем перевищує X, то цей вузол не потрібно перевіряти далі.
A* використовує цей евристичний метод для поліпшення поведінки алгоритму Дейкстери. Коли евристика дорівнює нулю, A* еквівалентна алгоритму Дейкстра. Оскільки евристична оцінка збільшується і наближається до справжньої відстані, A* продовжує знаходити оптимальні шляхи, але працює швидше (внаслідок вивчення меншої кількості вузлів). Коли значення евристики точно відповідає дійсній відстані, A* розглядає найменші вузли. (Проте, взагалі непрактично писати евристичну функцію, яка завжди обчислює істинну дистанцію). Коли значення евристики збільшується, A * досліджує менше вузлів, але більше не гарантує виявлення оптимального шляху. У багатьох програмах (таких як відеоігри) це прийнятно і навіть бажано, щоб алгоритм швидко працював.
Алгоритм вибірки
Алгоритм вибірки - це досить простий і зрозумілий алгоритм пошуку шляху для мап на основі черепиці. Щоб почати, у вас є карта, початкова координата та координата призначення. Карта буде виглядати так: X — це стінка, S — це початок, O — фініш, _ відкриті простори, цифри вздовж верхніх і правих країв — це номери стовпців та рядків:
1 2 3 4 5 6 7 8 X X X X X X X X X X X _ _ _ X X _ X _ X 1 X _ X _ _ X _ _ _ X 2 X S X X _ _ _ X _ X 3 X _ X _ _ X _ _ _ X 4 X _ _ _ X X _ X _ X 5 X _ X _ _ X _ X _ X 6 X _ X X _ _ _ X _ X 7 X _ _ O _ X _ _ _ X 8 X X X X X X X X X X
Спочатку створимо список координат, який ми будемо використовувати як чергу. Черга буде ініціалізована однією координатою, кінцевою координатою. Кожна координата також матиме змінній лічильник (мета цього скоро стане очевидною). Таким чином, черга починається з ((3,8,0)).
Потім переходимо до кожного елемента в черзі, включаючи елементи, додані до кінця по ходу алгоритму, і до кожного елемента, виконуємо наступне:
- Створюємо список із чотирьох сусідніх комірок зі змінною лічильником змінної поточного елемента +1 (у нашому прикладі чотири комірки — це ((2,8,1), (3,7,1), (4,8,1), (3,9,1)))
- Перевіряємо всі клітинки в кожному списку для наступних двох умов:
- Якщо клітина є стінкою, видаляємо її зі списку
- Якщо в головному списку є елемент з тією ж координатою та лічильник менший або рівний, видаляємо його з списку комірок
- Додаємо всі інші комірки у список до кінця основного списку
- Переходимо до наступного елемента списку
Таким чином, після першого повороту, список елементів буде таким: ((3,8,0),(2,8,1),(4,8,1))
- Після 2 поворотів: ((3,8,0), (2,8,1), (4,8,1), (1,8,2), (4,7,2))
- Після 3 поворотів: (… (1,7,3), (4,6,3), (5,7,3))
- Після 4 поворотів: (… (1,6,4), (3,6,4), (6,7,4))
- Після 5 поворотів: (… (1,5,5), (3,5,5), (6,6,5), (6,8,5))
- Після 6 витків: (… (1,4,6), (2,5,6), (3,4,6), (6,6,6), (7,8,6))
- Після 7 поворотів: ((1,3,7)) — задача розв'язана, закінчимо цей етап алгоритму — зверніть увагу, що якщо у вас є декілька одиниць, що переслідують ту саму ціль (як і в багатьох іграх — закінчення, щоб почати підхід алгоритму щоб зробити це простішим), ви можете продовжувати, доки не буде покрито всю карту, досягнуто всіх одиниць або досягнуто обмеження лічильника.
Тепер мапа лічильників виглядає так:
1 2 3 4 5 6 7 8 X X X X X X X X X X X _ _ _ X X _ X _ X 1 X _ X _ _ X _ _ _ X 2 X S X X _ _ _ X _ X 3 X 6 X 6 _ X _ _ _ X 4 X 5 6 5 X X 6 X _ X 5 X 4 X 4 3 X 5 X _ X 6 X 3 X X 2 3 4 X _ X 7 X 2 1 0 1 X 5 6 _ X 8 X X X X X X X X X X
Тепер почніть з S (7) і перейдіть до найближчої комірки з найменшим числом (неперевірені клітинки не можна перемістити). Простежується шлях (1,3,7) -> (1,4,6) -> (1,5,5) -> (1,6,4) -> (1,7,3) -> (1,8,2) -> (2,8,1) -> (3,8,0). У випадку, якщо два числа однаково низькі (наприклад, якщо S був на рівні (2,5)), виберіть випадковий напрямок — довжини однакові. Алгоритм завершено.
У відеоіграх
[en] в 1982 році описав, як він «витратив багато часу», намагаючись вирішити проблему з пошуком шляхів у Tanktics (комп'ютерна гра), в якій комп'ютерні танки потрапили в пастку на суші в U-образних озерах. «Після довгих витрачених зусиль я виявив краще рішення: видалити U-образні озера з карти», сказав він.
Ієрархічний пошук шляху
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOHhMekUzTDB0bGMxQmhZMUJoYkMxSFJDMHhNQzV6ZG1jdk1qVXdjSGd0UzJWelVHRmpVR0ZzTFVkRUxURXdMbk4yWnk1d2JtYz0ucG5n.png)
Ідея була вперше представлена в відеоігровій індустрії, що має потребує проєктування на великих картах при незначних витратах процесорного часу. Концепція використання абстракції та евристики є давнішою та вперше згадується під назвою ABSTRIPS (Abstraction-Based STRIPS), яка використовувалася для ефективного пошуку стану просторів логічних ігор. Подібною технікою є навігаційні сітки (navmesh), які використовуються для геометричного планування в відеоіграх і мультимодальному [en], яке використовується в задачах комівояжера з більш ніж одним транспортним засобом.
Мапа розділена на кластери. На верхньому рівні планується шлях між кластерами. Після того, як план знайдено, планується другий шлях у кластері на нижньому рівні. Це означає, що планування виконується у два етапи, тобто [en] у вихідному просторі. Перевагою є покращення виконуваного алгоритму за рахунок зменшення кількості вершин. Недоліком є те, що даний меанізм доволі важко реалізувати.
Приклад
Карта має розмір 3000x2000 вершин. Планування шляху на основі вершин займе дуже багато часу. Навіть ефективний алгоритм потребує обчислення багатьох можливих графіків. Причина в тому, що така карта міститиме 6 мільйонів вершин, а можливості для дослідження геометричного простору надзвичайно великі. Першим кроком для планування ієрархічного шляху є розділення карти на менші підкарти. Кожен кластер має розмір 300x200 вершин. Загальна кількість кластерів 10x10=100. У щойно створеному графі кількість вершин невелика і є можливість переміщатися між 100 кластерами, але не в межах детальної карти. Якщо в графі високого рівня знайдено дійсний шлях, наступним кроком є планування шляху в кожному кластері. Підкарта має 300x200 вершин, які можуть бути легко оброблені звичайним алгоритмом пошуку A*.
Алгоритми, які використовуються для пошуку шляхів
- Алгоритм пошуку A*
- Алгоритм Дейкстри, особливий випадок алгоритму A*
- Алгоритм пошуку D* сімейство [en] для проблем/задач, в яких обмеження змінюються з плином часу або невідомі, коли агент спочатку планує свій шлях
- [en] — це сім'я алгоритмів для планування шляхів, які не обмежуються рухатися уздовж країв у графічному пошуковому рядку, розроблені таким чином, щоб мати можливість приймати будь-який кут і таким чином знаходити більш короткі і прямі шляхи
Багатоагентний пошук шляху
Багатоагентний пошук шляху — це пошук шляху для декількох агентів з їх поточних розташувань до цільових місць, не стикаючись один з одним, одночасно оптимізуючи функцію витрат, таку як сума довжин шляху всіх агентів. Це узагальнення пошуку шляху. Багато алгоритмів мультиагентного пошуку шляхів генеровані від A* або базуються на скороченні до інших добре вивчених задач, таких як спрямоване лінійне програмування. Однак, такі алгоритми, як правило є неповні; Іншими словами, не доведено, що вони дають розв'язок протягом поліноміального часу. Інша категорія алгоритмів жертвує оптимальністю заради продуктивності за рахунок використання відомих навігаційних систем (таких як, потік трафіку) або топологією проблемного простору.
Див. також
- Планування руху
- [en]
Список використаної літератури
- http://lcm.csa.iisc.ernet.in/dsa/node162.html
- Delling, D.; ; Schultes, D.; (2009). Engineering route planning algorithms. Algorithmics of Large and Complex Networks: Design, Analysis, and Simulation. Springer. с. 117—139. doi:10.1007/978-3-642-02094-0_7.
- http://students.ceid.upatras.gr/~papagel/project/kef5_7_1.htm
- http://www.raywenderlich.com/4946/introduction-to-a-pathfinding
- Crawford, Chris (December 1982). Design Techniques and Ideas for Computer Games. BYTE. с. 96. Процитовано 19 October 2013.
- Sacerdoti, Earl D (1974). Planning in a hierarchy of abstraction spaces (PDF). Artificial Intelligence. doi:10.1016/0004-3702(74)90026-5.
- Robert C. Holte; M.B. Perez; R.M. Zimmer; A.J. MacDonald (1995). Symposium on Abstraction, Reformulation, and Approximation.
- Pelechano, Nuria; Fuentes, Carlos (2016). Hierarchical path-finding for Navigation Meshes (HNA⁎) (PDF) (вид. Computers & Graphics). с. 68—78. doi:10.1016/j.cag.2016.05.023.
- Botea, Adi; Muller, Martin; Schaeffer, Jonathan (2004). Near optimal hierarchical path-finding (вид. Journal of Game Development). 10.1.1.479.4675.
- Hang Ma, Sven Koenig, Nora Ayanian, Liron Cohen, Wolfgang Hoenig, T. K. Satish Kumar, Tansel Uras, Hong Xu, Craig Tovey, and Guni Sharon. Overview: generalizations of multi-agent path finding to real-world scenarios. [ 2021-07-15 у Wayback Machine.] In the 25th International Joint Conference on Artificial Intelligence (IJCAI) Workshop on Multi-Agent Path Finding. 2016.
- Khorshid, Mokhtar (2011). . SOCS. Архів оригіналу за 2 грудня 2017. Процитовано 2 грудня 2017.
Посилання
- http://sourceforge.net/projects/argorha
- http://qiao.github.com/PathFinding.js/visual/
- StraightEdge Відкриття вихідного Java 2D шляху пошуку (використовуючи A *) та проектування освітлення. Включає демонстрацію аплетів.
- python-pathfinding Відкритий вихідний шлях Python 2D (використовуючи алгоритм Дейкстри) та проект освітлення.
- Daedalus Lib Відкрите джерело. Daedalus Lib керує повністю динамічним триангульованим моделюванням 2D середовища та розробкою шляхів через алгоритм A * алгоритми воронки.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Poshuk shlyahu angl Pathfinding ce pobudova najkorotshogo shlyahu mizh dvoma tochkami za dopomogoyu komp yuternoyi programi Ce praktichnishij variant rozv yazuvannya labirintiv Cya galuz doslidzhen gruntuyetsya na algoritmi Dejkstri dlya poshuku najkorotshogo shlyahu na zvazhenomu grafi Odnakovi shlyahi mizh A ta B v 2D seredovishi Zadacha poshuku shlyahu tisno pov yazana z zadacheyu pro najkorotshij shlyah u ramkah teoriyi grafiv yaka rozglyadaye viznachennya shlyahu sho najkrashe vidpovidaye deyakim kriteriyam najkorotshij najdeshevshij najshvidshij i tak dali mizh dvoma tochkami u velikij merezhi AlgoritmiPo suti algoritm poshuku shlyahu doslidzhuye graf pochinayuchi z odniyeyi vershini ta perehodit do susidnih vuzliv i tak doki ne dosyagne cilovogo vuzla yak pravilo z namirom znajti najdeshevshij najkorotshij marshrut Hocha metodi poshuku po grafu taki yak poshuk u shirinu znajdut marshrut yaksho bude dostatno chasu inshi metodi yaki doslidzhuyut grafi shvidshe dosyagatimut cil Analogiyeyu bude lyudina yaka jde po kimnati zamist obgovorennya vsih mozhlivih marshrutiv zazdalegid vona yak pravilo ruhayetsya u napryamku priznachennya i vidhilyayetsya vid shlyahu lishe zadlya uniknennya pereshkod i vidhilyayetsya nastilki malo naskilki ce mozhlivo Dvoma osnovnimi zadachami poshuku shlyahu ye poshuk shlyahu mizh dvoma vuzlami na grafi zadacha pro najkorotshij shlyah znajti optimalnij najkorotshij shlyah Osnovni algoritmi taki yak poshuk u shirinu i poshuk u glibinu spryamovani na pershu problemu vicherpuyuchi vsi mozhlivosti za dopomogoyu grubogo pereboru pochinayuchi z danogo vuzla voni iteracijno doslidzhuyut usi potencijni shlyahi doki ne dosyagayut cilovogo vuzla Ci algoritmi vikoristovuyutsya za chas O V E displaystyle O left left V right left E right right abo linijnij chas de V kilkist vershin a E kilkist reber mizh vershinami Bilsh skladnoyu problemoyu ye poshuk optimalnogo shlyahu Vicherpnij pidhid u danomu vipadku vidomij yak algoritm Bellmana Forda maye chasovu skladnist O V E displaystyle O V E abo kvadratichnij chas Odnak ne potribno vivchati vsi mozhlivi shlyahi shob znajti optimalnij Algoritmi taki yak algoritm A ta algoritm Dejkstri strategichno viklyuchayut shlyahi yak za dopomogoyu evristichnogo algoritmu tak i za dopomogoyu dinamichnogo programuvannya Usunuvshi nemozhlivi shlyahi ci algoritmi mozhut dosyagati nizkoyi skladnosti chasu yak O E log V displaystyle O E log V Navedeni vishe algoritmi ye odnimi z najkrashih zagalnih algoritmiv yaki pracyuyut na grafu bez poperednoyi obrobki Prote v praktichnih sistemah marshrutizaciyi shlyahiv navit najkrashi za skladnistyu chasu mozhna dosyagti za dopomogoyu algoritmiv yaki poperedno obroblyayut graf dlya dosyagnennya krashoyi produktivnosti Odnim z takih algoritmiv ye en Algoritm Dejkstri Zagalnim prikladom algoritmu poshuku shlyahu bazovanogo na grafi ye algoritm Dejkstri Cej algoritm rozpochinaye robotu z pochatkovogo vuzla j pryamuye do vidkritih vuzliv kandidativ Na kozhnomu nastupnomu kroci obirayetsya vidkritij vuzol z najmenshoyu vidstannyu vid pochatkovogo Usi vuzli poznacheni yak zakriti ta vsi prilegli do nih vuzli dodayutsya do vidkritogo naboru yaksho voni she ne buli perevireni Cej proces povtoryuyetsya doki ne bude znajdeno shlyah do potribnogo vuzla punktu priznachennya Oskilki najchastishe rozglyadayutsya vuzli z najmenshoyu vidstannyu koli vpershe bude znajdeno punkt priznachennya shlyah do nogo bude najkorotshim shlyahom Algoritm Dejkstri ne pracyuye z pokaznikami vid yemnoyi vagi U gipotetichnij situaciyi koli vuzli A V i S utvoryuyut zv yazanij neoriyentovanij graf z rebrami AV 3 AS 4 ta VS 2 optimalnij shlyah vid A do S koshtuye 1 a optimalnij shlyah vid A do B vitratit 2 Algoritm Dejkstri pochinaye z A a potim spochatku rozglyadaye vuzol B oskilki vin roztashovanij najblizhche Cej shlyah bude koshtuvati 3 i bude poznachenij yak zakritij a znachit jogo vartist nikoli ne bude pereocinena Ce i ye prichinoyu togo chomu algoritm Dejkstri ne mozhe ociniti pokazniki vid yemnoyi vagi Prote oskilki dlya bagatoh praktichnih cilej nikoli ne bude pokaznikiv vid yemnoyi vagi algoritm Dejkstera v znachnij miri pidhodit dlya zadach na poshuk shlyahiv Algoritm poshuku A Algoritm A ce variant algoritmu Dejkstri yakij dosit chasto vikoristovuyetsya v igrah A pridaye vagu kozhnomu vidkritomu vuzlu vaga yakogo dorivnyuye vazi rebra ta dodaye pribliznu vidstan vid rebra do finishu Cya priblizna vidstan viyavlyayetsya evristichnoyu i yavlyaye soboyu minimalnu mozhlivu vidstan mizh cim vuzlom i kincem Ce dozvolyaye algoritmu usunuti dovshi shlyahi pislya viyavlennya pochatkovogo i pracyuye nastupnim chinom yaksho mizh pochatkom i kincem ye shlyah dovzhini X a minimalna vidstan mizh vuzlom i finishem perevishuye X to cej vuzol ne potribno pereviryati dali A vikoristovuye cej evristichnij metod dlya polipshennya povedinki algoritmu Dejksteri Koli evristika dorivnyuye nulyu A ekvivalentna algoritmu Dejkstra Oskilki evristichna ocinka zbilshuyetsya i nablizhayetsya do spravzhnoyi vidstani A prodovzhuye znahoditi optimalni shlyahi ale pracyuye shvidshe vnaslidok vivchennya menshoyi kilkosti vuzliv Koli znachennya evristiki tochno vidpovidaye dijsnij vidstani A rozglyadaye najmenshi vuzli Prote vzagali nepraktichno pisati evristichnu funkciyu yaka zavzhdi obchislyuye istinnu distanciyu Koli znachennya evristiki zbilshuyetsya A doslidzhuye menshe vuzliv ale bilshe ne garantuye viyavlennya optimalnogo shlyahu U bagatoh programah takih yak videoigri ce prijnyatno i navit bazhano shob algoritm shvidko pracyuvav Algoritm vibirki Algoritm vibirki ce dosit prostij i zrozumilij algoritm poshuku shlyahu dlya map na osnovi cherepici Shob pochati u vas ye karta pochatkova koordinata ta koordinata priznachennya Karta bude viglyadati tak X ce stinka S ce pochatok O finish vidkriti prostori cifri vzdovzh verhnih i pravih krayiv ce nomeri stovpciv ta ryadkiv 1 2 3 4 5 6 7 8 X X X X X X X X X X X X X X X 1 X X X X 2 X S X X X X 3 X X X X 4 X X X X X 5 X X X X X 6 X X X X X 7 X O X X 8 X X X X X X X X X X Spochatku stvorimo spisok koordinat yakij mi budemo vikoristovuvati yak chergu Cherga bude inicializovana odniyeyu koordinatoyu kincevoyu koordinatoyu Kozhna koordinata takozh matime zminnij lichilnik meta cogo skoro stane ochevidnoyu Takim chinom cherga pochinayetsya z 3 8 0 Potim perehodimo do kozhnogo elementa v cherzi vklyuchayuchi elementi dodani do kincya po hodu algoritmu i do kozhnogo elementa vikonuyemo nastupne Stvoryuyemo spisok iz chotiroh susidnih komirok zi zminnoyu lichilnikom zminnoyi potochnogo elementa 1 u nashomu prikladi chotiri komirki ce 2 8 1 3 7 1 4 8 1 3 9 1 Pereviryayemo vsi klitinki v kozhnomu spisku dlya nastupnih dvoh umov Yaksho klitina ye stinkoyu vidalyayemo yiyi zi spisku Yaksho v golovnomu spisku ye element z tiyeyu zh koordinatoyu ta lichilnik menshij abo rivnij vidalyayemo jogo z spisku komirok Dodayemo vsi inshi komirki u spisok do kincya osnovnogo spisku Perehodimo do nastupnogo elementa spisku Takim chinom pislya pershogo povorotu spisok elementiv bude takim 3 8 0 2 8 1 4 8 1 Pislya 2 povorotiv 3 8 0 2 8 1 4 8 1 1 8 2 4 7 2 Pislya 3 povorotiv 1 7 3 4 6 3 5 7 3 Pislya 4 povorotiv 1 6 4 3 6 4 6 7 4 Pislya 5 povorotiv 1 5 5 3 5 5 6 6 5 6 8 5 Pislya 6 vitkiv 1 4 6 2 5 6 3 4 6 6 6 6 7 8 6 Pislya 7 povorotiv 1 3 7 zadacha rozv yazana zakinchimo cej etap algoritmu zvernit uvagu sho yaksho u vas ye dekilka odinic sho peresliduyut tu samu cil yak i v bagatoh igrah zakinchennya shob pochati pidhid algoritmu shob zrobiti ce prostishim vi mozhete prodovzhuvati doki ne bude pokrito vsyu kartu dosyagnuto vsih odinic abo dosyagnuto obmezhennya lichilnika Teper mapa lichilnikiv viglyadaye tak 1 2 3 4 5 6 7 8 X X X X X X X X X X X X X X X 1 X X X X 2 X S X X X X 3 X 6 X 6 X X 4 X 5 6 5 X X 6 X X 5 X 4 X 4 3 X 5 X X 6 X 3 X X 2 3 4 X X 7 X 2 1 0 1 X 5 6 X 8 X X X X X X X X X X Teper pochnit z S 7 i perejdit do najblizhchoyi komirki z najmenshim chislom neperevireni klitinki ne mozhna peremistiti Prostezhuyetsya shlyah 1 3 7 gt 1 4 6 gt 1 5 5 gt 1 6 4 gt 1 7 3 gt 1 8 2 gt 2 8 1 gt 3 8 0 U vipadku yaksho dva chisla odnakovo nizki napriklad yaksho S buv na rivni 2 5 viberit vipadkovij napryamok dovzhini odnakovi Algoritm zaversheno U videoigrah en v 1982 roci opisav yak vin vitrativ bagato chasu namagayuchis virishiti problemu z poshukom shlyahiv u Tanktics komp yuterna gra v yakij komp yuterni tanki potrapili v pastku na sushi v U obraznih ozerah Pislya dovgih vitrachenih zusil ya viyaviv krashe rishennya vidaliti U obrazni ozera z karti skazav vin Iyerarhichnij poshuk shlyahu Derevo kvadrantiv mozhna vikoristovuvati dlya iyerarhichnogo poshuku shlyahu Ideya bula vpershe predstavlena v videoigrovij industriyi sho maye potrebuye proyektuvannya na velikih kartah pri neznachnih vitratah procesornogo chasu Koncepciya vikoristannya abstrakciyi ta evristiki ye davnishoyu ta vpershe zgaduyetsya pid nazvoyu ABSTRIPS Abstraction Based STRIPS yaka vikoristovuvalasya dlya efektivnogo poshuku stanu prostoriv logichnih igor Podibnoyu tehnikoyu ye navigacijni sitki navmesh yaki vikoristovuyutsya dlya geometrichnogo planuvannya v videoigrah i multimodalnomu en yake vikoristovuyetsya v zadachah komivoyazhera z bilsh nizh odnim transportnim zasobom Mapa rozdilena na klasteri Na verhnomu rivni planuyetsya shlyah mizh klasterami Pislya togo yak plan znajdeno planuyetsya drugij shlyah u klasteri na nizhnomu rivni Ce oznachaye sho planuvannya vikonuyetsya u dva etapi tobto en u vihidnomu prostori Perevagoyu ye pokrashennya vikonuvanogo algoritmu za rahunok zmenshennya kilkosti vershin Nedolikom ye te sho danij meanizm dovoli vazhko realizuvati Priklad Karta maye rozmir 3000x2000 vershin Planuvannya shlyahu na osnovi vershin zajme duzhe bagato chasu Navit efektivnij algoritm potrebuye obchislennya bagatoh mozhlivih grafikiv Prichina v tomu sho taka karta mistitime 6 miljoniv vershin a mozhlivosti dlya doslidzhennya geometrichnogo prostoru nadzvichajno veliki Pershim krokom dlya planuvannya iyerarhichnogo shlyahu ye rozdilennya karti na menshi pidkarti Kozhen klaster maye rozmir 300x200 vershin Zagalna kilkist klasteriv 10x10 100 U shojno stvorenomu grafi kilkist vershin nevelika i ye mozhlivist peremishatisya mizh 100 klasterami ale ne v mezhah detalnoyi karti Yaksho v grafi visokogo rivnya znajdeno dijsnij shlyah nastupnim krokom ye planuvannya shlyahu v kozhnomu klasteri Pidkarta maye 300x200 vershin yaki mozhut buti legko obrobleni zvichajnim algoritmom poshuku A Algoritmi yaki vikoristovuyutsya dlya poshuku shlyahivAlgoritm poshuku A Algoritm Dejkstri osoblivij vipadok algoritmu A Algoritm poshuku D simejstvo en dlya problem zadach v yakih obmezhennya zminyuyutsya z plinom chasu abo nevidomi koli agent spochatku planuye svij shlyah en ce sim ya algoritmiv dlya planuvannya shlyahiv yaki ne obmezhuyutsya ruhatisya uzdovzh krayiv u grafichnomu poshukovomu ryadku rozrobleni takim chinom shob mati mozhlivist prijmati bud yakij kut i takim chinom znahoditi bilsh korotki i pryami shlyahiBagatoagentnij poshuk shlyahuBagatoagentnij poshuk shlyahu ce poshuk shlyahu dlya dekilkoh agentiv z yih potochnih roztashuvan do cilovih misc ne stikayuchis odin z odnim odnochasno optimizuyuchi funkciyu vitrat taku yak suma dovzhin shlyahu vsih agentiv Ce uzagalnennya poshuku shlyahu Bagato algoritmiv multiagentnogo poshuku shlyahiv generovani vid A abo bazuyutsya na skorochenni do inshih dobre vivchenih zadach takih yak spryamovane linijne programuvannya Odnak taki algoritmi yak pravilo ye nepovni Inshimi slovami ne dovedeno sho voni dayut rozv yazok protyagom polinomialnogo chasu Insha kategoriya algoritmiv zhertvuye optimalnistyu zaradi produktivnosti za rahunok vikoristannya vidomih navigacijnih sistem takih yak potik trafiku abo topologiyeyu problemnogo prostoru Div takozh Planuvannya ruhu en Spisok vikoristanoyi literaturihttp lcm csa iisc ernet in dsa node162 html Delling D Schultes D 2009 Engineering route planning algorithms Algorithmics of Large and Complex Networks Design Analysis and Simulation Springer s 117 139 doi 10 1007 978 3 642 02094 0 7 http students ceid upatras gr papagel project kef5 7 1 htm http www raywenderlich com 4946 introduction to a pathfinding Crawford Chris December 1982 Design Techniques and Ideas for Computer Games BYTE s 96 Procitovano 19 October 2013 Sacerdoti Earl D 1974 Planning in a hierarchy of abstraction spaces PDF Artificial Intelligence doi 10 1016 0004 3702 74 90026 5 Robert C Holte M B Perez R M Zimmer A J MacDonald 1995 Symposium on Abstraction Reformulation and Approximation Pelechano Nuria Fuentes Carlos 2016 Hierarchical path finding for Navigation Meshes HNA PDF vid Computers amp Graphics s 68 78 doi 10 1016 j cag 2016 05 023 Botea Adi Muller Martin Schaeffer Jonathan 2004 Near optimal hierarchical path finding vid Journal of Game Development 10 1 1 479 4675 Hang Ma Sven Koenig Nora Ayanian Liron Cohen Wolfgang Hoenig T K Satish Kumar Tansel Uras Hong Xu Craig Tovey and Guni Sharon Overview generalizations of multi agent path finding to real world scenarios 2021 07 15 u Wayback Machine In the 25th International Joint Conference on Artificial Intelligence IJCAI Workshop on Multi Agent Path Finding 2016 Khorshid Mokhtar 2011 SOCS Arhiv originalu za 2 grudnya 2017 Procitovano 2 grudnya 2017 Posilannyahttp sourceforge net projects argorha http qiao github com PathFinding js visual StraightEdge Vidkrittya vihidnogo Java 2D shlyahu poshuku vikoristovuyuchi A ta proektuvannya osvitlennya Vklyuchaye demonstraciyu apletiv python pathfinding Vidkritij vihidnij shlyah Python 2D vikoristovuyuchi algoritm Dejkstri ta proekt osvitlennya Daedalus Lib Vidkrite dzherelo Daedalus Lib keruye povnistyu dinamichnim triangulovanim modelyuvannyam 2D seredovisha ta rozrobkoyu shlyahiv cherez algoritm A algoritmi voronki