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

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

Страницы: 1 2 3 4 530 Следующая »
#30
20:33, 28 мая 2011

TarasB
в тесте я указал стандартный размер "реллокатора", поэтому такая большая разница
если слега считерить и задать огромный размер "релокатора" - то считать будет раза в 4-5 медленнее cpf

у себя кстати тоже посмотри как релоцируется память - может быть сможешь увеличить произовдительность
а cpf я вставил умный реллокатор. первый раз выделяется например 100 элементов, потом ещё 200, потом ещё 400 и т.д. предел - 1/5 количества клеток
+ реаллокатор ещё может постепенно "сдуваться", если задействован не весь


#31
20:56, 28 мая 2011

Профайлер говорит, что дело не в аллокаторе.

#32
21:15, 28 мая 2011

TarasB
поверь мне на слово )
можешь перекомпилировать, там есть пометка CHEAT_MODE )

#33
21:21, 28 мая 2011
Изображение удалено
Изображение удалено

Не знаю как на счет самого БЫСТРОГО поиска пути, но на счет самого короткого и самого "человечного" - сомневаюсь. Никогда бы не использовал такой алгоритм для перемещения юнитов, т.к. он создает очень плохое впечатление. Юнит должен имитировать поведение человека.Так же поиск пути по диагонали отсутствует, я вообще не знаю для какого жанра игры это можно использовать, разве что для бомбермена какого-то 80х годов.
ИМХО скоростью можно принебречь, если она работает в ущерб адекватности.
#34
21:29, 28 мая 2011

DevilDevil
> поверь мне на слово )

Чё верить, я по rdtsc проверил, внутри SetLength очень мало времени проводится.

Короче, у меня неверно считалась эвристика для 8 направлений, из-за этого тормоза (корректность не страдала).

Новый результат:

C:\...Files\Delphi\Projects\PathFinder>pathfinder input_1.bmp
finding path, 4 directions...
complete. Total (finding+drawing) time = 1382 ms
finding path, 8 directions...
complete. Total (finding+drawing) time = 1492 ms

C:\...Files\Delphi\Projects\PathFinder>pathfinder input_2.bmp
finding path, 4 directions...
complete. Total (finding+drawing) time = 2614 ms
finding path, 8 directions...
complete. Total (finding+drawing) time = 3415 ms

C:\...Files\Delphi\Projects\PathFinder>pathfinder input_3.bmp
finding path, 4 directions...
complete. Total (finding+drawing) time = 230 ms
finding path, 8 directions...
complete. Total (finding+drawing) time = 1151 ms

cky4Ha9I
Ты долбанулась рисунки на ультрашару выкладывать? Я что, их ещё и вручную скачивать должен, чтобы посмотреть?

Вот исправленный вариант моей программы PathFinder

#35
21:38, 28 мая 2011

cky4Ha9I
справа поставь "режим карты" - mmDiagonal

TarasB
замётано. я про mp говорил

я правильно понял, cpf работает в 5 раз быстрее чем твоя разработка ?

p.s.
>Вот исправленный вариант моей программы PathFinder
cpf рисует другой
у тебя вес серых которые посветлее какой получается ?

#36
21:44, 28 мая 2011

DevilDevil
> какой-то неадекват )
Нифигасе неадекват, человек даже не поленился чутли не схемы чертил...

#37
21:52, 28 мая 2011

DevilDevil извиняюсь не увидел, но это мне кажется тоже сомнительный случай. Такой проход скорее интерпретируется как непроходимый, чем проходимый
Изображение удалено

#38
21:53, 28 мая 2011

DevilDevil
> у тебя вес серых которые посветлее какой получается ?

255*3 - 192*3 + MinW = 392 (а у белого - 200, то есть относительно белого это будет 1.96).

DevilDevil
> cpf рисует другой

Ну может их много разных.

#39
21:53, 28 мая 2011

cky4Ha9I
> Такой проход скорее интерпретируется как непроходимый, чем проходимый

Да не, ну не будет же никто для диагонали всех соседей смотреть. Просто надо карты делать так, чтобы таких угловых вещей не было.

#40
21:54, 28 мая 2011

cky4Ha9I
TarasB
режим карты mmDiagonalEx

#41
22:00, 28 мая 2011

DevilDevil
> режим карты mmDiagonalEx
Увидел! Спасибо. Ну в принципе норм, есть еще одна - последняя деталь: поиск не расчитывается вообще, если проходимости нет. Это как бэ не страшно, но это что получается, если между персонажем и целевой позицией горы, реки и леса, проходимости "где-то там" нет, а мы его просим туда передвинуться, то он ничего не будет делать? он как бэ видит всю карту получается, ну таких возможностей у него быть не может и эта деталь разрушает легенду персонажа, о том что он персонаж вообще. Я имею в виду, что человек сначала бы попытался найти путь, уткнулся бы в стену, но не говорил "там все равно проходимости нет, я конечно не вижу этого, но точно знаю (откуда?), поэтому че париться, лучше стоять на месте". Но думаю добавить это будет не сложно

#42
22:06, 28 мая 2011

cky4Ha9I
А в Starcraft2 зилоты по такому маршруту пройдут)

#43
22:07, 28 мая 2011

cky4Ha9I
ну это я уж не знаю
решай как-нибудь
библиотека отвечает на вопрос есть ли путь до цели и если есть, то какой кратчайший

TarasB
мне кажется cpf считает правильнее
pictures
а 255*3 - 192*3 + MinW у меня равен 389

#44
22:46, 28 мая 2011

DevilDevil
> мне кажется cpf считает правильнее

Проверь на примере размером 5х5.
Через болото удвоенной вязкости путь короче, через в 2 раза по сравнению с обходом, значит через болото (как у меня) - правильнее.

DevilDevil
> а 255*3 - 192*3 + MinW у меня равен 389

А, ну да.

Страницы: 1 2 3 4 530 Следующая »
ПрограммированиеФорумИгровая логика и ИИ

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