Намирането на пътя от точка А до точка Б - един от най-често срещаните задачи при разработването на игри. За да се реши този проблем, има много алгоритми, но най-често се използва е A * (звезда). Той е посветен на днешната публикация.
- Създадена на Преди 2 оглавява списъка - в очакване и вече обсъжда. Чакането се добавя към началната точка, списъкът е празен досега взети под внимание.
- Изчислено за всяка точка F = G + Н. G - разстоянието от началото до точката, Н - приблизително разстояние от точката на вратата. На изчисляване на тази стойност, за което ще говоря по-късно. Както е добре, всяка точка съхранява препратка към точката, от която идва.
- От списъка с точка до избраната точка с най-малката F. го Нека X.
- Ако X - стремим, ние открихме по маршрута.
- Прехвърляне на X от списъка на висящите дела в списъка вече взети под внимание.
- За всяка от точките в близост до Х (означен със съседната точка за Y), направете следното:
- Ако Y е вече в процес на разглеждане - я прескоча.
- Ако Y не е посочен на чакащите - го добавите отново, не забравяйте, Позоваванията на Х и изчисляване Y.G (X.G + е разстоянието от X до Y) и Y.H.
- Ако Y в списъка за разглеждане - проверете дали X.G + разстояние от Х до Y
- Ако в списъка на точки върху празната и целта никога не сме достигнали - тогава по маршрута не съществува.
оценка Функция на приблизителното разстояние до целта.
Тази функция трябва да отговарят на няколко условия:
- Функцията никога не надценява разстоянието до целта.
- За тази функция разстояние, неравенството триъгълник. Ще се обясни по-: Да предположим, че има три условия - А, В и С. За пътеки А-В В-С и A-C трябва да важи следното неравенство: A-B + B-C> = A-C.
Реализация.
I прилага алгоритъм за правоъгълна карта, състояща се от клетки.
За да започнете, да създадете точка клас:
Остава да се добавят няколко полезни функции.
Първият от тях - в зависимост от разстоянието от X до Y:
Разстоянието между съседни клетки имам винаги едно.
Функция приблизителни оценки на разстоянието до целта:
За да изчислите разстоянието използвам дължината на пътя, без препятствия.
Получаване на списък съсед до точката:
маршрут разписка. Път е представен и списък с координати на точка.
Ето защо ние продължавахме отправна точка, от която идва.
За да се промени алгоритъма на друг начин на представяне на точките (напр разстояния между градове графика), е необходимо да се променят стават съседи и изчисляване на разстояния.
Това е, което в крайна сметка се е случило:
Между другото площади вече знаят как да ходи и да се борят :-)
Функция приблизителни оценки на разстоянието до целта:
1
2
3
4private статично вътр GetHeuristicPathLength (Point от, посочете)
върне Math.Abs (from.X - to.X) + Math.Abs (from.Y - to.Y);
>
грешката ми е приятел. очевидно с геометрия много лошо. най-малкия път е път, по права линия
частен статично вътр GetHeuristicPathLength (Point от, посочете)
Var DeltaX = Math.Abs (from.X - to.X);
Var DeltaY = Math.Abs (from.Y - to.Y);
Var Dist = Math.sqrt (DeltaX * DeltaX + DeltaY * DeltaY);
и където изходния код?
Свързани статии