Войти
ПрограммированиеФорумИгровая логика и ИИ

CrystalPathFinding (CPF) - экстремально быстрый и простой A*/WA* для карт на тайлах (5 стр)

Страницы: 14 5 6 730 Следующая »
#60
14:32, 30 мая 2011

DevilDevil
> ну дак если ты "эвристику поправил"
Я её не "поправил", просто взял старую из теста ITALY

  float LeastCostEstimate( void* nodeStart, void* nodeEnd )
  {
    int xStart, yStart, xEnd, yEnd;
    NodeToXY( nodeStart, &xStart, &yStart );
    NodeToXY( nodeEnd, &xEnd, &yEnd );

    float fxStart = (float)xStart;
    float fyStart = (float)yStart;
    float fxEnd = (float)xEnd;
    float fyEnd = (float)yEnd;
    float dx = fxStart - fxEnd;
    float dy = fyStart - fyEnd;

    return (dx * dx) + (dy * dy);
  }

#61
14:34, 30 мая 2011

Igor'
ясно
я думаю я взял самую адекватную и быструю эвристику
одно умножение, одно сложение
(это ещё не домножается на MinTileWeight - дабы чуть сэкономить скорость)

но факт - cpf находит путь почти вдвое короче
значит эвристика лажает

#62
14:41, 30 мая 2011

DevilDevil
> у тебя округления... а мог бы ты выложить без округления, прям в double. Просто
> так точнее - нужно всё-таки тот примерчик помучать. Может у меня баги. Или у
> тебя

Нет у меня дабла. Длины же в битмапе сидят, значит целые числа.
Округление заметно только на 8 направлениях. На 4 округления нету. Так что сравни для 4 направлений результаты.
(да, ещё, я при выводе же делю длину на MinW, но это само собой).

#63
14:44, 30 мая 2011

DevilDevil
> я думаю я взял самую адекватную и быструю эвристику
> одно умножение, одно сложение

Такую?

function FastDist(x1,y1,x2,y2: integer): integer;
  var
    dx, dy: integer;
  begin
    if DirC = 4 then result := (abs(x1-x2) + abs(y1-y2)) * MinW
    else begin
      dx := abs(x1-x2);
      dy := abs(y1-y2);
      if dx>dy then result := dx+dy*27146 div 65536 else result := dy+dx*27146 div 65536;
      result := result * MinW;
    end;
  end;
#64
14:46, 30 мая 2011

TarasB
min * sqrt_2 + (max-min)

попробуй эту для micropather если хочешь

кстати ты в своём алгоритме ищешь из конца в начало или из начала в конец ?

#65
14:49, 30 мая 2011

DevilDevil
> min * sqrt_2 + (max-min)

Короче, то же, что и у меня, только я взял сразу max + min*(sqrt(2)-1)

DevilDevil
> кстати ты в своём алгоритме ищешь из конца в начало или из начала в конец ?

А по волне не видно?

#66
14:52, 30 мая 2011

TarasB
>А по волне не видно?
не хочу теряться в сомнениях )
хочу знать наверняка

#67
14:58, 30 мая 2011

Волна пускается из начала в конец.
Потом идёт проход по волне из конца в начало.

#68
15:31, 30 мая 2011

кстате прошу прощения, действительно налажал с эвристикой, сейчас считает правильно
(длинна путей совпадает)

  virtual float LeastCostEstimate( void* nodeStart, void* nodeEnd )
  {
    int xStart, yStart, xEnd, yEnd;
    NodeToXY( nodeStart, &xStart, &yStart );
    NodeToXY( nodeEnd, &xEnd, &yEnd );

    int dx = abs(xStart-xEnd);
    int dy = abs(yStart-yEnd);

    // fast diagonal heuristics
    if (dx <= dy)
    {
      return ((float)dx)*SQRT_2 + (float)(dy-dx);
    }
    else
    {
      return ((float)dy)*SQRT_2 + (float)(dx-dy);
    }
  }
infinity | CrystalPathFinding (CPF) - экстремально быстрый и простой A*/WA* для карт на тайлах

http://devilhome.narod.ru/cpf_tests.zip

#69
17:19, 30 мая 2011

0 ms меня радуют :) Честно. Он работает в нано секундах, вот это оптимизация.

#70
17:24, 30 мая 2011

Мух
да, приходится извращаться )

p.s. посмотри input_3.bmp - всё станет понятно
это как раз для того чтобы всякие mp и волны не могли затачиваться на лабиринты

#71
23:59, 31 мая 2011

ну вот и зачен нужно было гнать на DevilDevilа что мол он оптимизирует на ассемблере и это подобно нубу и неадеквату ?

результаты говорят сами за себя.
я рад что прогресс не стоит на месте )

п.с.
DevilDevil ты молодчага ! так держать )

#72
9:29, 1 июня 2011

Bashka
пасиб
ну вообще говоря, это особенность mp и сpf - если задать в mp большой буфер (CHEAT_MODE), то разница будет меньше. По внутренней организации cpf быстрее mp в 2-5 раз. Ожидал большей разницы )

а падает на чистом битмапе - потому что не обладает "умной вставкой"

Это кстати показательно. Столько людей глумились, считали своим долгом обсмеять мой труд - но по факту ничего не предприняли чтобы сравнивать cpf и другие наработки. Только ITALY предпринял действия для создания теста. Я и отписывал в лички, и писал на форуме, и код специальным образом организовал - чтобы было проще добавлять свой код, который "уделает" cpf. Нет. Ничего. И люди которые обещались "исправить тест и посадить меня в лужу" - как то куда то пропали и не появляются. Интернет наверно закончился

Просто в очередной раз убеждаюсь - нормальные пацаны бестактности себе не позволяют. А разводят флуд и глумятся - всегда форумное гомно. Которое ничего чаще всего не представляет. Даже не смотря на статусы "Мучастник"

#73
10:17, 1 июня 2011

DevilDevil
> Просто в очередной раз убеждаюсь - нормальные пацаны бестактности себе не
> позволяют. А разводят флуд и глумятся - всегда форумное гомно. Которое ничего
> чаще всего не представляет.
какой ты самокритичный, уважаю!

#74
10:18, 1 июня 2011

Bashka
> ну вот и зачен нужно было гнать на DevilDevilа что мол он оптимизирует на
> ассемблере и это подобно нубу и неадеквату ?

Ну, его поиск пути оказался быстрее, чем микропасер, работающий через его же обёртку.
Ну и что это доказывает?
Когда люди написали свою обёртку микропасера, то результат оказался совсем иным. А я ведьь уже собирался извиняться перед ТС...

DevilDevil
> И люди которые обещались "исправить тест и посадить меня в лужу" - как то куда
> то пропали и не появляются. Интернет наверно закончился

Да достало их, наверное.

Страницы: 14 5 6 730 Следующая »
ПрограммированиеФорумИгровая логика и ИИ

Тема в архиве.