Forum in READ ONLY mode! All questions and discussions on Discord official server, invite link: https://discord.gg/VxsGzJ7

Несколько слов о поиске пути.(moveXY и GetPathArray)

Часто задаваемые вопросы
Post Reply
grundick
Developer
Developer
Posts: 272
Joined: 31.01.2008 21:16

Несколько слов о поиске пути.(moveXY и GetPathArray)

Post by grundick »

Итак, в RC4 появились функции moveXY и getPathArray.

Code: Select all

function MoveXY(Xdst,Ydst: Word; Optimized: Boolean; Accuracy: Integer; Running: Boolean): Boolean; // Поиск пути. 
Accuracy - точность приближения: 0 - прямо на точку, 1 - рядом в радиусе одного тайла и т.д. длина ограничена 200 точек(тайлов). 
Optimized - включать настоятельно рекомендуется только на поиске пути длиной до 200 точек. 
// Когда выключено - идет поиск просто пути, когда включен - оптимального. 

function GetPathArray(DestX,DestY: Word; Optimized: Boolean; Accuracy : integer; var PathArray: TPathArray): Integer; // возвращает кол-во точек в маршруте, 
// в PathArray пишет массив шагов пути. первый - это координаты точки первой от старта и т.д. до последней. Ограничено 200 точек.
Реализованы два алгоритма поиска пути - "А-звёздочка" (Optimized=true) и "Лучший-первый" (Otpimized=false) . На каждом шаге эти алгоритмы заранее прокладывают путь, учитывая карту ,статику и динамику . Фактически A* объединяет алгориты Дийкстры и "Лучший-первый". Отличие алгоритмов - А* ищет кратчайший путь, "Лучший-первый" идёт напролом, не учитывая стоимость пройденного пути.
Пока поиск работает на карте размером 200х200 тайлов. Это ограничение введено в связи с существенными аппаратными требованиями алгоритмов.

На текущий момент рекомендую использовать алгоритм "Лучший-первый" (То есть параметр Optimized=false). Этот алгоритм проверяет гораздо меньшее кол-во тайлов, соответственно работает быстрее, хотя найденный путь не является оптимальным.
Для сравнения Скачать файл sravni.jpg (зеленые кружки показывают проверенные точки).

Тем не менее, даже на такой небольшой карте могут возникнуть ситуации, когда поиск пути будет осуществляться достаточно долго. (Скажем, чтобы пройти из шахты Mt.Kendalt к миноковскому хилеру, у меня до прохода моста тратилось до 2ух секунд на шаг! Поэтому маршрут я разбивал на две части , перевалочная точка была за минок мостом) В этих случаях рекомендую разбивать путь на несколько частей. Опытным путём несложно выяснить на каких маршрутах поиск работает более-менее оптимально.

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

В настрйоках шарда появилась галочка Diagonal Move Check. Для корректной работы поиска пути, а также функции IsWorldCellPassable, эту галочку НЕОБХОДИМО устанавливать на шардах, где запрещены диагональные шаги через угол непроходимого тайла. X - непроходимый тайл, О - точка , куда надо шагнуть, С -сам чар.
X O
C X
Если на Вашем шарде чар на стелс клиенте может сделать шаг в точку О,
значит у Вас со стороны сервера разрешены диагональные шаги и нет нужды устанавливать эту галочку. Отсутствие галочки означает, что при поиске пути будет проверяться в ТРИ(!) раза меньше тайлов.
(На антаресе,оскоме и дрв вроде запрещены запрещены). Если же шаги запрещены, а галочка у Вас не стоит, при хождении будут постоянные цепляния за углы айтемов, и ,как следствие, moveReject ы.

Фукция GetPathArray выдаёт Вам массив точек пути, используя те же самые алгоритмы. Это может потребоваться, если Вам нужна какая то особенная ходилка. Например, хождение в хайде. Вот пример ходилки, которую я использовал на Оскоме для хождения в скрипте на ламбер и мининг:

Code: Select all

Program MoveInHide;

var
    sTimerHide: cardinal; 
    BadObj: array [0 .. 4] of word;
const
   TimeNeededToHide=5000;             // время, которого гарантированно хватает чтобы войти в hide
   
   Lysyi=$0040297B;

Function Abs(A: integer): integer;
Begin
If A>=0 then result:=A 
Else result:=0-A;
End;

function Min(x,y: integer): integer;
begin
 if x>y then Result:=y else Result:=x;
end;

function Dest(x,y: integer): integer;
var dx,dy,Ddx : integer;
begin
  dx:= Abs(GetX(self)-x);
  dy:= Abs(GetY(self)-y);
  Ddx:=Abs(dx-dy);
 
  Result:= min(dx,dy)+Ddx;
end;

function SetDirection(x, y : integer) : byte; 
var
   MyX,MyY,DiffX,DiffY,GoDir: integer;
Begin
MyX:=GetX(self);
MyY:=GetY(self);
DiffX:=Abs(MyX-x);
DiffY:=Abs(MyY-y);

if (DiffX/(DiffY+0.1))>=2 then 
   begin
   if (MyX>X) then 
      GoDir:=6 
   else 
      GoDir:=2; 
   end  
else 
   if (DiffY/(DiffX+0.1))>=2 then 
      begin
      if (MyY>Y) then 
         GoDir:=0 
      else 
         GoDir:=4;
      end  
   else 
        
      if (MyX>X) and (MyY>Y) then  GoDir:=7
      else 

        if (MyX>X) and (MyY<Y) then  GoDir:=5 
        else 

           if (MyX<X) and (MyY>Y) then  GoDir:=1 
           else 

             if (MyX<X) and (MyY<Y) then  GoDir:=3; 
result:=GoDir;
end;

Procedure HideMove(X,Y: integer; accurance: word);
var 
  i: integer;
  Dir: byte;
  PathArr: TPathArray;
Begin
While Dest(X,Y)>accurance do
   begin
   If (Not Dead) then
      If (Stam<Dex) then 
         begin
         // если стамины меньше чем дексы, устанавливаем хумов и элемов в bad objects
         For i:=0 to 4 do
            SetBadObject(BadObj[i],$FFFF,0);
         end
      Else
         ClearBadObjectList;

   //  вычисляем следующую точку   
   repeat
     i:= GetPathArray(X,Y,false,accurance,PathArr);
     wait(100);
     //WaitConnection(1000);
   until i>-1;
   
   //  определяем направление шага.
   Dir:=SetDirection(PathArr[0].x,PathArr[0].y);
   If GetDirection(self)<> Dir then Step(Dir, false);
   if ((Timer-sTimerHide)>TimeNeededToHide) AND (Not Dead) AND (Not Hidden) then
         begin
               If WarMode then SetWarMode(false);
	       UseSkill('Hiding');
	       wait(300);
	       sTimerHide:=Timer;
	       
	 end;
   Step(Dir, false);
   end;
End;

BEGIN
BadObj[0]:=$0190;            // man
BadObj[1]:=$0191;            // woman
BadObj[2]:=$000E;             // элемы
BadObj[3]:=$000E;
BadObj[4]:=AMSpirit;             // энгрик

sTimerHide:= timer;
wait(5000);


hideMove(getX(Lysyi),getY(Lysyi),0); 

END.
К сожалению, на данный момент мы не располагаем достоверной информацией о том , как УОшный клиент определяет возможно ли сделать шаг. Поэтому та проверялка, что встроена в стелс и используется при поиске пути и функцией IsWorldCellPassable , работает не всегда корректно. Поэтому к возникающим проблемам прошу отнестись с понимаем.

Дополнение. Одна из скриптововозможных оптимизаций поиска пути ). Суть в том ,что теперь маршрут просчитывается не на каждом шагу, а только на старте и при незапланированных (с точки зрения построенного маршрута) столкновениях с препятствиями. Чем меньше непроходимой динамики на Вашем пути - тем реже скрипт обращается к GetPathArray, и , соответственно, меньше нагрузка на процессор. ВАЖНО: Если скрипт оправдает себя в действии, мы встроим эту ходилку непосредственно в стелс.

Code: Select all

// Функция easyMoveXY(X,Y: integer; Otpimized: boolean;  Accuracy : integer; Running : boolean): Boolean;
// Возвращает true если чар достиг цели. Если же не удалось найти пути- вернёт false.
// X,Y - пункт назначения.
// Optimized - тип просчёта пути. Пока рекомендую устанавливать false.
// Accuracy - точность подхода.
// Running - если true, чар бегает. Если false - ходит пешком.
// Этот файл называете easyMoveXY.sc и кладёте в папку Include.
// Для использования в скрипте не забывайте его подключать! 
// Собственно смысл функции: При старте запускается функция GetPathArray.
// Чар бежит, используя созданный маршрут. При столкновении с препятствием,
// маршрут пересчитывается снова. 
//  example / пример
//  easyMoveXY(1279,540,false,1,true);

// function easyMoveXY(X,Y: integer; Optimized: boolean; Accuracy : integer; Running : boolean): Boolean;
// Return true if your character reached the destination, else - return false.
// X,Y - destination.
// Optimized- algorithm of pathfinding(If false then FIRST-BEST is using, else A* ) .Highly recommended use FALSE.
// Running: if true then char is running, else - walking.
// Rename this file to easyMoveXY.sc and put it in Include directory.
// Don't forget include that file in your scripts!
//  example :  easyMoveXY(1279,540,false,1,true);

var
 mPathArr : TPathArray;

procedure LocalWaitConnection(WaitTime : Integer);
begin
if Connected then Exit;
while not Connected do Wait(1000);
{WaitTime - Waiting After Connected}
wait(WaitTime);
end;

function FindMin(x,y: Integer): integer;
Begin
 if x>y then Result:=y else Result:=x;
End;

function sign(x : Integer) : Integer;
Begin
If x<0 then result:=-1;
If x=0 then result:=0;
If x>0 then  result:=1;
End;

function Dist(x,y: Integer): integer;
var dx,dy,Ddx : integer;
Begin
  dx:= GetX(self)-x;
  dy:= GetY(self)-y;
  Ddx:= dx-dy;
  If dx<0 then dx:=0-dx;
  If dy<0 then dy:=0-dy;
  If Ddx<0 then Ddx:=0-Ddx;
  Result:= FindMin(dx,dy)+Ddx;
End;

function MoveToPoint(X,Y: Integer; Running: Boolean) : boolean;
var 
  remap : array [0..8] of byte;
  dx,dy,dir,StepResult : Integer;

Begin
remap[0] := 7;
remap[1] := 6;
remap[2] := 5;
remap[3] := 0 ;
remap[4] := -1;
remap[5] := 4;
remap[6] := 1;
remap[7] := 2;
remap[8] := 3;

Result:=false;
While  true do
   begin
   dx:=X-getX(self); dy:=Y-getY(self);
   If (dx=0) AND (dy=0) then 
       begin
       Result:=true; 
       Exit; 
       end;
   dx:=sign(dx);
  dy:=sign(dy);
   dir := remap[(dx + 1)*3 + dy + 1];
   
   LocalWaitConnection(1000);
   While (Not Dead)  AND (Stam<=0) do Wait(1000);

   If GetDirection(self) <> dir then Step(dir, Running);
   StepResult:=Step(dir,Running);
   If (StepResult=1) OR (StepResult=5) then Wait(5000);
   If StepResult<7 then
      begin
      result:=false;
      Exit;
      end; 
   end;
End;

function easyMoveXY(X,Y: integer; Optimized: boolean; Accuracy : Integer; Running: boolean): boolean;
var
   StepCnt,i : Integer;

Begin
Result:=false;
While true do
   begin
   AddToSystemJournal('pathfinding...')
   StepCnt:=GetPathArray(X,Y,Optimized,Accuracy,mPathArr);
   If StepCnt<0 then Exit;
   If StepCnt=0 then
      begin
      Result:= true;
      Exit;
      end;
   For i:=0 to StepCnt do
      begin
      
      If Not IsWorldCellPassable(getX(self),getY(self),mPathArr[i].X,mPathArr[i].Y,WorldNum,getZ(self)) then  Break; 
      If Not MoveToPoint(mPathArr[i].X,mPathArr[i].Y,Running) then  Break;
      If Dist(X,Y)<=Accuracy then 
         begin
	 AddToSystemJournal('Location reached!');
	 Result:=true;
	 Exit;
	 end;
      end;
    end;
End;


Last edited by grundick on 08.09.2009 13:06, edited 7 times in total.
rasta
Neophyte
Neophyte
Posts: 22
Joined: 06.07.2009 0:31

Post by rasta »

На чем написана темка, в которой происходит сравнение поиска пути?
CFA
Developer
Developer
Posts: 492
Joined: 20.04.2006 6:03
Contact:

Post by CFA »

по иконке видно что делфи, причем не первой свежести.
grundick
Developer
Developer
Posts: 272
Joined: 31.01.2008 21:16

Post by grundick »

Программа написана не мной, её автор -Alex M.A (Алексей Моисеенко). Он же автор программы UOScript. Собственно , он написал программу для последующей реализации алгоритма в скрипте. Вот отсюда всё содрано
Конечно же, огромное ему спасибо за его наследие )
http://www.delphikingdom.com/asp/viewit ... alogID=166
Mirage
Novice
Novice
Posts: 90
Joined: 18.07.2009 19:41

Post by Mirage »

2 grundick
C утра пораньше глупый вопрос. На скрине путь со стоящий из скольких координат? Начало и конец или все точки пробиты? :roll:
grundick
Developer
Developer
Posts: 272
Joined: 31.01.2008 21:16

Post by grundick »

Не совсем вопрос понял )
Тёмно-зеленая точка - это старт, красная - пункт назначения. Синие - найденный путь. Зеленые и жёлтые - точки, проверяемые при построении пути. Тёмно коричневые квадратики - стены )
User avatar
Vizit0r
Developer
Developer
Posts: 3958
Joined: 24.03.2005 17:05
Contact:

Post by Vizit0r »

rasta wrote:На чем написана темка, в которой происходит сравнение поиска пути?
CFA wrote:по иконке видно что делфи, причем не первой свежести.
не-а.

иконка просто зашита в проекте в res-файле и никоим образом не является показателем версии.
"Пишите код так, как будто сопровождать его будет склонный к насилию психопат, который знает, где вы живете". (с) Макконнелл, "Совершенный код".
Mirage
Novice
Novice
Posts: 90
Joined: 18.07.2009 19:41

Post by Mirage »

grundick wrote:Не совсем вопрос понял )
Тёмно-зеленая точка - это старт, красная - пункт назначения. Синие - найденный путь. Зеленые и жёлтые - точки, проверяемые при построении пути. Тёмно коричневые квадратики - стены )
я имел ввиду
чар находится в координатах (Xтемнозеленая, Yтемнозеленая)

скриптом скажем

Code: Select all

GoTo(Xкрасная, Yкрасная)
проходит от начала до конца или надо

Code: Select all

GoTo(X1синяя, Y1синяя)
GoTo(X2синяя, Y2синяя)
GoTo(X3синяя, Y3синяя)
GoTo(X4синяя, Y4синяя)
// -- // -- //
GoTo(Xкрасная, Yкрасная)
доходим до конца?

Просто если задав 1 конечную координату конца чар сам нашел оптимальный путь и прошел его - это акуительно, но если тысяча координат и чар найдя "оптимальный" путь прошел его то в чем соль?
grundick
Developer
Developer
Posts: 272
Joined: 31.01.2008 21:16

Post by grundick »

Во-первых , скриптом скажем не GoTo, а moveXY.
Во-вторых, чар ничего не ищет. Путь ищет стелс, а не чар )
На каждом шаге с учётом карты, статики и динамики согласно заданному алгоритму ищется путь. Если путь найден, чар делает шаг на следующую точку. Далее происходит снова поиск пути. На каждом шаге приходится искать потому что динамику чар видит только в зоне обзора (16-18 тайлов), соотвественно при каждом шаге приходится обновлять информацию.
Для конечного пользователя moveXY(Xfinish,Yfinish) приведёт чара к финишу (Если, конечно ,путь будет найден).
Функция getPathArray просто выдает Вам найденный путь (либо -1, если путь не найден) в виде массива точек. И Вы можете использовать его как Вас заблагорассудится.
Edred
Moderator
Moderator
Posts: 559
Joined: 28.03.2006 21:29

Post by Edred »

grundick wrote:На каждом шаге с учётом карты, статики и динамики согласно заданному алгоритму ищется путь. Если путь найден, чар делает шаг на следующую точку. Далее происходит снова поиск пути. На каждом шаге приходится искать потому что динамику чар видит только в зоне обзора (16-18 тайлов), соотвественно при каждом шаге приходится обновлять информацию.
Что-то я не понял логики в тех фразах, что я выделил жирным. Если прошел просчет маршрута с учетом динамики на 16-18 тайлов - зачем после первого шага все пересчитывать? Предлагаю сделать дополнительный вариант оптимизации: добавить флаг типа "сложная местность". Если он включен - то считать так, как считается сейчас (подобное нужно при передвижении по сильно пересеченной местности либо по сильно застроенному участку). Если он выключен (то есть обычная местность, лес, изредка мелкие дома) - то пересчитывать маршрут после 5-6 шагов. А лучше - сразу параметр - через сколько шагов пересчитывать маршрут. И пусть люди подбирают себе индивидуально. Пока движение на 90% используется при мининге/ламбере, а обход мелких препятствий не нужно пересчитывать на каждом шагу.
User avatar
Vizit0r
Developer
Developer
Posts: 3958
Joined: 24.03.2005 17:05
Contact:

Post by Vizit0r »

на ламбере\майнинге при шагании на 25-40 шагов этот пересчет вообще не чуствуется.
"Пишите код так, как будто сопровождать его будет склонный к насилию психопат, который знает, где вы живете". (с) Макконнелл, "Совершенный код".
grundick
Developer
Developer
Posts: 272
Joined: 31.01.2008 21:16

Post by grundick »

Edred wrote:
Что-то я не понял логики в тех фразах, что я выделил жирным. Если прошел просчет маршрута с учетом динамики на 16-18 тайлов - зачем после первого шага все пересчитывать? Предлагаю сделать дополнительный вариант оптимизации: добавить флаг типа "сложная местность". Если он включен - то считать так, как считается сейчас (подобное нужно при передвижении по сильно пересеченной местности либо по сильно застроенному участку). Если он выключен (то есть обычная местность, лес, изредка мелкие дома) - то пересчитывать маршрут после 5-6 шагов. А лучше - сразу параметр - через сколько шагов пересчитывать маршрут. И пусть люди подбирают себе индивидуально. Пока движение на 90% используется при мининге/ламбере, а обход мелких препятствий не нужно пересчитывать на каждом шагу.
Есть функция GetPathArray.
Она позволяет делать юзеру всё ,чего ему захочется. Просчитывать путь через 5-6 шагов, либо после пройдённого экрана (о чём, вообще говоря, нам стоит призадуматься), либо включая свои специфические условия. (Хождение в хайде, невозможность пройти через нпц\чара и т.д.)
Edred
Moderator
Moderator
Posts: 559
Joined: 28.03.2006 21:29

Post by Edred »

Окей. Только прошу сделать одну вещь. Мы находимся в разделе FAQ. И такое большое и красивое описание этих двух функций тут очень уместно, но еще уместнее все-таки дать и синтаксис этих двух функций. Не отсылку куда-то в другую тему, где этот синтаксис приведен, а прямо тут его и дать.
Post Reply