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

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

Страницы: 15 6 7 830 Следующая »
#75
10:28, 1 июня 2011

TarasB
>Да достало их, наверное.
достало что они унылое г***о и не отвечают за свои слова ?
понимаю

>Ну, его поиск пути оказался быстрее, чем микропасер, работающий через его же обёртку.
э, как бэ я взял сорсы ITALY и изменил их так чтобы удобно было сравнивать разные реализации
плюс убрал читерство.. и хочешь - компилируй в CHEAT_MODE

>Ну и что это доказывает?
это доказывает что cpf - самый простой и быстрый A*/WA* в мире
а люди с этим несогласные ничего не могут сделать. я бы относился к ним с уважением, если бы они действительно что-то попытались делать, а не голословили. ITALY например я уважаю за то, что он не просто кричал в пустоту "а ты докажи, а ты покажи", а взял и написал тест. Косячный.. но написал. И это важно

kas
ну я в отличие от тебя написал действительно быструю и удобную библиотеку


#76
11:01, 1 июня 2011

Ты только одно забываешь. О том как твой cpf слил в первых тестах тому же уродскому mp. При условии, что в твоем cpf были аццкие асм оптимизации, а в уродском mp их отродяся не было. Но это конечно уже не докажешь. Это да.
100% Перепиши сейчас mp на asm, скорость будет такая же, если не быстрее.
Только что это доказывает? Ограниченность использования, и больше ничего.

#77
11:07, 1 июня 2011

Мух
ты делаешь голословные утверждения
cpf содержит больше оптимизаций, чем "тупо заассемблировать"
причём я ожидал значительно больше буста

>Ты только одно забываешь. О том как твой cpf слил в первых тестах тому же уродскому mp.
cpf слил из-за того чтобы было медленное изменение (косяк на количестве узлов больше 2000). а mp сейчас сливает на большом количестве клеток из-за медленного релокатора
я делаю скидки на разные идеи и разные оптимизации, и разные точности
я ж ясно говорю, что cpf не быстрее mp в 20-30 раз как видно на тестах, а в 2-5. потому что делаю скидку на..

почему тебя так огорчает превосходство библиотеки ?
я не заставляю её использовать для других платформ и т.д.
и не надо навязывать свои приоритеты мне и другим участникам
мой приоритет - максимальная скорость и простота для карт основанных на тайлах в простых играх. Платформа Windows (может быть в каком-нибудь будущем Linux, MacOS, и т.д.)

#78
11:10, 1 июня 2011

DevilDevil
> почему тебя так огорчает превосходство библиотеки ?
Меня не огорчает :) Я рад тому что тебя зацепило и ты написал нормальный тест, попотрошил свою библиотеку и она стала работать быстрее чем аналоги.
Имхо это только плюсы.

#79
11:13, 1 июня 2011

Мух
что меня зацепило ?
что разные уроды начали выливать г*мно ?
меня это не зацепило - меня это огорчило
а исправление косяков и увеличение производительности было бы в любом случае - постепенно при любом раскладе
micropather оттачивался годами коммерческого использования
cpf месяц от роду

#80
11:20, 1 июня 2011

DevilDevil
Ну изначально ты слил со своим патчером, так что заявление в названии темы ложь.
Я рад, что тебя зацепило то "что разные уроды начали выливать г*мно", и ты взялся за еще большие оптимизации. Ибо поначалу ты ведь даже слушать не хотел что твоя библа сливает :)

Кстати, где можно качнуть исходники последних тестов?

#81
11:28, 1 июня 2011

Мух
что есть патчер ?
моя либа никогда не сливала, никогда не была медленне mp. Она работала медленее на конкретных тестах. К примеру сейчас mp показывает никакую скорость на простом битмапе где нужно найти путь из левого верхнего угла в правый нижний. Это не значит что cpf быстрее mp в тысячу раз, это значит что для конкретного теста реализация имеет какой-то минус

исходники тестов находятся всегда вместе с самими тестами
и всегда по ссылке http://devilhome.narod.ru/cpf_tests.zip

#82
12:25, 1 июня 2011

Пару коментариев хотелось бы о последнем тесте:

1)

virtual void PrepareData()
 {
  m_vPath.reserve(Width * Height);

    /*STANDARD_MODE*/ m_pAStar = new micropather::MicroPather(this, 250, Diagonal?8:4);
   /*CHEAT_MODE*/ //m_pAStar = new micropather::MicroPather(this, Width * Height / 2, Diagonal?8:4);
 }

Standart mode - заведомо (умышленно ? ;) ) медленная константа. 250 - Некорректное значение, вот что говорит документация micropather на этот счет:

If you have a small map (a few thousand states?) it may make sense to pass in the maximum value. This will cache everything, and MicroPather will only need one main memory allocation. For a chess board, allocate would be set to 8x8 (64)
If your map is large, something like 1/4 the number of possible states is good. For example, Lilith3D normally has about 16,000 states, so 'allocate' should be about 4000.
If your state space is huge, use a multiple (5-10x) of the normal path. "Occasionally" call Reset() to free unused memory.
Таким образом, исходя из офф документации - считаю более корректным значением в диапазоне [Width * Height / 4, Width * Height / 2].

2) Предлагаю заменить

  
void NodeToXY( void* node, int* x, int* y )
{
    int index = (int)node;
    *y = index / Width;
    *x = index - (*y) * Width;
}

void* XYToNode( int x, int y )
{
    return (void*) ( y * Width + x );
}

На

void NodeToXY( void* node, int* x, int* y )
{
    int index = (int)node;
    *y = index & 0xFFFF;
    *x = index >> 16;
}

void* XYToNode( int x, int y )
{
    return (void*) ((x << 16) | y);
}

#83
12:28, 1 июня 2011

Кстати да :)
Что за двойные стандарты?
Своей либы ты передаешь размеры карты, а микропатчеру об них знать не обязательно?
Там вроде в описании параметра написано, для чего он нужен.

Во вторых, своему патчеру ты передаешь карту из 0 и 255, а микропатчер ищет напрямую в картинке.
Что то тест какой то странный.

#84
12:40, 1 июня 2011

DevilDevil
> плюс убрал читерство..

Какое?

#85
12:45, 1 июня 2011

началось

лично я считаю любое "подстраивание" под конкретный тест - читерством. Соответственно если ты минимум для карты выделяешь половину клеток... эта ситуация - 100% заточка под лабиринты. Ну если в документации сказано, что нормально аллоцировать 4ю часть карты (минимум 500 000 ё-моё) -ok. Только давайте заметим, сколько минимум памяти зажрёт micropather. Минимальный размер блока в cpf к примеру - Max(CellsCount / 1000, 32). + память может не только возрастать, но и сдуваться.
я не против огромного зажирания памяти.. я за, но с оговоркой - чтобы всем это было известно. "данный тест слегка подточен на большой битмап, чтобы уж не казаться полным уг. Но он зажирает много памяти просто по умолчанию. Увы"

ITALY
>2) Предлагаю заменить
заменяй, отправляй сорсы - буду вставлять в официальный тест
я за честность на самом деле
лучше если тесты перед выкладыванием будут согласовываться со мной

Мух
> Во вторых, своему патчеру ты передаешь карту из 0 и 255, а микропатчер ищет
> напрямую в картинке.
micropather ищет в ImageParser, где данные - сплошной поток данных (если не ошибаюсь char[])
можешь исправить тест - я не против

#86
13:43, 1 июня 2011

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

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


Насчет памяти спорный вопрос, вряд ли cpf что нибудь знает о VirtaulAlloc/Free и выделенную память OC не отдает.

#87
13:55, 1 июня 2011

susageP
> Нету правила ограничения на память, то об это даже не заикайся. Нет ограничения
> на сложность пути, тоже не заикайся - типа заточен под лабиринты и т.д.

Мальчику просто надо самореализоваться, вот и всё. Плюньте вы на него, как это сделали умные люди, и не обращайте внимания, всё равно его CPF с заточенными под него тестами никому не нужен, пускай сидит с ним в треде один.

#88
14:15, 1 июня 2011

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

#89
14:30, 1 июня 2011

susageP
такое впечатление что я тебя чем-то задел
отобрал последнее
это же надо моя реализация считает в разы быстрее чем ты предполагал

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

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