Намирането на начин на картата

Темата на намирането на начин да картографира притеснява много игри програмисти (най-вече за начинаещи), а дори и опитни програмисти правят своите алгоритми не са много мобилни. Тук ще опиша някои алгоритми за намиране на пътя. тях като за база, можете да излезе с много доста усъвършенствани алгоритми. За съжаление, не е съвършен алгоритъм, и по тази причина за целите на използване на един или друг се изисква да жертват или изпълнение или интелекта, който е достатъчно малък, за да се нуждаят от нея.

Игрите често използват алгоритъм маршрутизация (или негова модификация) благодарение на своята проста реализация и малко количество от изчисления. Но много често не се strabatyvaet в комплекс игра ситуация и характера започва да се гърчи от страна на страна, по този начин се дразни на играча (например в неговата игра StarCraft). Прилагането на вълна алгоритъм може да постигне по-добри резултати, но алгоритъма вълна за използване в игрите изисква малко подобрение, защото не може да се изгради една линия по диагонал. Съвършенството може да се комбинира вълна и маневреност маршрут чрез третиране на 8-квартал около елементарна вълна отпред в изграждането на пистата. Само тук изчисленията са малко по-малко, тъй като пред стаята на вълната вече има разстояние до първоначалния елемент, след което можете да изберете само най-малкият елемент на квартала и да се насърчи по пътя към него. Но без значение колко е универсален алгоритъм вълна е не само огромен недостатък на лицето - е необходимостта от по-голям обем памет за съхранение на спомагателните карти, за да помаха фронтове и дълъг път, за да се изгради за всеки знак. За да се намалят разходите, аз лично използвате картата вече изчислява фронтовете вълна за всички герои, които идват в една точка, като по този начин намалява времето за маршрут изчисление за всеки от тях.

Wave алгоритъм (алгоритъм Li)

Wave алгоритъм е един от най-уникалните алгоритми за маршрутизация. Тя ви позволява да се изгради маршрут (път) между двата елемента във всеки лабиринт.

От началната клетка разпространява в четири посоки вълна (фигура 1.). Един елемент, който оформя предната дойде вълна volny.Na фигура номер вълна фронтове са номерирани.

Всеки елемент на първата вълна отпред е вторичен източник на вълна (Фигура 2). Елементи на втори фронт на вълната генерират трети фронта на вълната, и т.н. Процесът продължава, докато не се постигне окончателно елемент.

През втория етап е построен на самата верига. Изграждането му се извършва в съответствие със следните правила:

Движение в изграждането на пистата в съответствие с избрания приоритет.
Когато се движи от краен елемент към първоначалната вълна предната стая (туристически координати), следва да се понижат.

Приоритети посоки на движение, са избрани на етапа на проектиране. В зависимост от това, което определя тези приоритети се получават различен път, но дължината на пистата във всеки случай остава същата.

Предимства вълна алгоритъм е, че тя може да се използва за намиране на маршрут по някакъв лабиринт и произволен брой забранени елементи (стени). Единственият недостатък на този алгоритъм е фактът, че в изграждането на пистата изисква голямо количество памет.

Пример за алгоритъм на вълната:

Red маркирани забранени предмети. Грей песен след действието на алгоритъма.
Началната точка, В-финала.
Приоритети LEFT движение, НАДЯСНО, НАГОРЕ, НАДОЛУ.
Изграждане на пистата е от началната точка до края на. Приоритети са показани със зелени стрелки.

алгоритъм на маршрутизиране

Прекарването алгоритъм има два варианта.

Въз основа на изчисляване на разстоянията между точките.
Въз основа на рекурсивни връзката.

Прекарването алгоритъм получава името си, тъй като и двете osuhestvlyaet формирането на предната и полагане trassy.Istochnikom вълна на всяка стъпка е последната част на елемента маршрут положени в предишните стъпки.

Алгоритъмът за маршрутизиране се основава на изчисляване на разстоянието между пункта.

Работа алгоритъм започва от начална елемент. Така разгледана около първичния елемент 8 квартала на клетката. От околностите на всеки елемент на дължина елемент оценява път окончателно. Разстоянието между точките vychisletsya с формулата:

D = | X и Х Б | + | Y и -Y Б |

където (X I, Y и) - Координати съседство. (X B, Y B) - Координатите на краен елемент.

Така, осем стойности, изчислени от които е избран минимум. Елемент от което разстоянието е минимална е избран следа елемент. Около нея се отново счита за 8 клетъчна квартал. Процесът продължава, докато не се постигне окончателно елемент. Ако по пътя срещне препятствие под формата на забранено елемент, избягване на препятствие се извършва въз основа на интуицията за програмисти. Това определя посоката на избягване на препятствие.

Routing алгоритъм, базиран на рекурсивни връзката.

Алгоритъмът на маршрутите могат да се изграждат на базата на следната рекурсивна зависимост:

у (х) = 2y (х + Н) + у (х + 2Н) + г

Когато х, у (х) - ордината и абсциса елемент заети опит в тази стъпка.
(X + з) - ординатата на члена заета писта в предишната стъпка.
(X + 2Н) - ординатата на елемент на разстояние от изчислен в етап 2.
ч - промяна абсциса стойност на всяка стъпка.
г (делта) - Тази функция определя вида на маршрута. Ако г = 0 е конструирана прав коловоз, ако г = конст след построен параболичен път.

Ординатата следващия път елемент се изчислява рекурсивно съгласно формулата и абсциса маршрута изчислява по формулата:

В "+" или "-" във формулата рекурсивно избрани въз основа на реда започва от изграждането на пистата, от първоначален елемент "+", съответно, и от финала "-".

Според тази формула за изчисляване на третия елемент на пистата трябва да знае предишните две. Първият елемент е първоначалната елемент на А (X A, Y А), а ординатата на втория елемент се изчислява по формулата:

Y (Х) = Y (Х А) + ((Y (Х А) -Y (X B)) / (X A-Х В)) * з

Ако по пътя за да посрещне своята забранено байпас елемент се извършва въз основа на интуицията за програмисти.
Основното предимство е простотата на маршрутния алгоритъм, както и възможността за движение по диагонал.