Программирование игр, создание игрового движка, OpenGL, DirectX, физика, форум
GameDev.ru / Программирование / Форум / CrystalPathFinding (CPF) - экстремально быстрый и простой A*/WA* для карт на тайлах (3 стр)

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

Поделиться

Страницы: 1 2 3 4 ... 15 ... 28 29 30 Следующая

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

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

1 frag / 2 deathsУчастникwww28 мая 201120:56#31
Профайлер говорит, что дело не в аллокаторе.
DevilDevilПостоялецwww28 мая 201121:15#32
TarasB
поверь мне на слово )
можешь перекомпилировать, там есть пометка CHEAT_MODE )
BoringirlУдалёнwww28 мая 201121:21#33
Изображение удалено
Изображение удалено
Не знаю как на счет самого БЫСТРОГО поиска пути, но на счет самого короткого и самого "человечного" - сомневаюсь. Никогда бы не использовал такой алгоритм для перемещения юнитов, т.к. он создает очень плохое впечатление. Юнит должен имитировать поведение человека.Так же поиск пути по диагонали отсутствует, я вообще не знаю для какого жанра игры это можно использовать, разве что для бомбермена какого-то 80х годов.
ИМХО скоростью можно принебречь, если она работает в ущерб адекватности.

Правка: 28 мая 2011 21:43

1 frag / 2 deathsУчастникwww28 мая 201121:29#34
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

Правка: 28 мая 2011 21:32

DevilDevilПостоялецwww28 мая 201121:38#35
cky4Ha9I
справа поставь "режим карты" - mmDiagonal

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

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

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

Правка: 28 мая 2011 21:44

Igor'Постоялецwww28 мая 201121:44#36
DevilDevil
> какой-то неадекват )
Нифигасе неадекват, человек даже не поленился чутли не схемы чертил...
BoringirlУдалёнwww28 мая 201121:52#37
DevilDevil извиняюсь не увидел, но это мне кажется тоже сомнительный случай. Такой проход скорее интерпретируется как непроходимый, чем проходимый
Изображение удалено
1 frag / 2 deathsУчастникwww28 мая 201121:53#38
DevilDevil
> у тебя вес серых которые посветлее какой получается ?

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

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

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

1 frag / 2 deathsУчастникwww28 мая 201121:53#39
cky4Ha9I
> Такой проход скорее интерпретируется как непроходимый, чем проходимый

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

DevilDevilПостоялецwww28 мая 201121:54#40
cky4Ha9I
TarasB
режим карты mmDiagonalEx
BoringirlУдалёнwww28 мая 201122:00#41
DevilDevil
> режим карты mmDiagonalEx
Увидел! Спасибо. Ну в принципе норм, есть еще одна - последняя деталь: поиск не расчитывается вообще, если проходимости нет. Это как бэ не страшно, но это что получается, если между персонажем и целевой позицией горы, реки и леса, проходимости "где-то там" нет, а мы его просим туда передвинуться, то он ничего не будет делать? он как бэ видит всю карту получается, ну таких возможностей у него быть не может и эта деталь разрушает легенду персонажа, о том что он персонаж вообще. Я имею в виду, что человек сначала бы попытался найти путь, уткнулся бы в стену, но не говорил "там все равно проходимости нет, я конечно не вижу этого, но точно знаю (откуда?), поэтому че париться, лучше стоять на месте". Но думаю добавить это будет не сложно

Правка: 28 мая 2011 22:02

TryПостоялецwww28 мая 201122:06#42
cky4Ha9I
А в Starcraft2 зилоты по такому маршруту пройдут)
DevilDevilПостоялецwww28 мая 201122:07#43
cky4Ha9I
ну это я уж не знаю
решай как-нибудь
библиотека отвечает на вопрос есть ли путь до цели и если есть, то какой кратчайший

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

Правка: 28 мая 2011 22:12

1 frag / 2 deathsУчастникwww28 мая 201122:46#44
DevilDevil
> мне кажется cpf считает правильнее

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

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

А, ну да.

Правка: 28 мая 2011 22:48

Страницы: 1 2 3 4 ... 15 ... 28 29 30 Следующая

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

2001—2017 © GameDev.ru — Разработка игр