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

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

Поделиться

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

RPGmanУдалёнwww28 мая 201115:40#15
DevilDevil
> в этом моя принципиальная позиция
Твоя позиция - удовлетворение чсв путем оглашения завялений, не подтвержденных фактами.
> с чего ему быть медленнее ?
А с чего ему быть быстрее? На основании одних лишь голословных заявлений? Или потому что "я убил на нее полгода, значит она стопудово быстрее"?

/ я офф зи ченнел...

DevilDevilПостоялецwww28 мая 201115:54#16
RPGman
моя позиция основана на том, что я выжимаю самый максимум из алгоритма
соответственно все реализации которые не выжимают самый максимум - работают медленнее
они могут работать на уровне, могут работать быстрее на каких-то тестах. но в целом тенденция такая - что они работают медленнее. И разница в скорости пропорциональна в геометрической прогрессии объёму внимания и знаний, направленных на оптимизацию данного алгоритма

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

DevilDevilПостоялецwww28 мая 201117:13#17
TarasB
> У меня багов пока нету, кстати?
а ты можешь выводить расстояние и количество точек ?
у меня пока другой результат получается
1 frag / 2 deathsУчастникwww28 мая 201117:33#18
DevilDevil
> у меня пока другой результат получается

А у тебя вязкость точки - это время захода на неё, или время схода с неё?
И при движении по диагонали считается, что можно пройти, если клетка [x+1,y+1] свободна, независимо от состояния клеток [x,y+1] и [x+1,y].

DevilDevilПостоялецwww28 мая 201117:36#19
TarasB
стоимость перехода = стоимость тайла с которого сходишь. Если smart_weight, то (откуда+куда)/2. Если диагональный - то ещё помножить на корень из двух
1 frag / 2 deathsУчастникwww28 мая 201117:39#20
DevilDevil
> стоимость перехода = стоимость тайла с которого сходишь

Да

DevilDevil
> Если smart_weight, то (откуда+куда)/2.

Этого я не делал

DevilDevil
> Если диагональный - то ещё помножить на корень из двух

Да.

DevilDevil
> у меня пока другой результат получается

Проверь на простом лабиринте размеров примерно 5х5 пикселей, на котором можно вручную перепроверить.

DevilDevilПостоялецwww28 мая 201117:43#21
TarasB
ты лучше выводи результат - так проще
можешь подсчитывать путь и количество точек после замера времени
BashkaПостоялецwww28 мая 201118:29#22
TarasB
лучше не суммировать время поиска и время отрисовки - отрисовка пути не относится к поиску.

to all
а как искать путь если юнит толстый и занимает больше одной клетки например 4 или имеет какойто радиус

1 frag / 2 deathsУчастникwww28 мая 201118:31#23
Bashka
> лучше не суммировать время поиска и время отрисовки - отрисовка пути не
> относится к поиску.

У меня относится. Я отрисовкой называю проход по волне от выхода назад. Просто именно во время неё путь закрашивается красным.

DevilDevilПостоялецwww28 мая 201118:43#24
Bashka
> а как искать путь если юнит толстый и занимает больше одной клетки например 4
> или имеет какойто радиус

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

а если тебя беспокоит чтобы перс не залезал на преграды согласно радиусу - я бы решил через Excluded points. Или в карте устанавливал преграды (tile = 255). Или через веса тайлов = 0. Это большой плюс - для одной карты тайлов можно иметь множество массивов весов (Weights). Определённые типы тайлов можешь устанавливать как непроходимые, указав им value = 0.0


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

1 frag / 2 deathsУчастникwww28 мая 201118:57#25
DevilDevil
> я так понял у него данные битмапа задействуются

Я исходник потом выложу, там ровно 300 строк.
А чужие екзешники у меня ни один не пошёл из тех что выкладывались.

Правка: 28 мая 2011 18:58

DevilDevilПостоялецwww28 мая 201119:00#26
TarasB
> Я исходник потом выложу, там ровно 300 строк.
поэтому выражаю респект

TarasB
> А чужие екзешники у меня ни один не пошёл из тех что выкладывались.
карту для тестов просто меньше бери
887х552 например )
и сорец перекомпилируй. чтобы не было команд которых нет в твоём процессоре

Правка: 28 мая 2011 19:01

1 frag / 2 deathsУчастникwww28 мая 201119:52#27
Так что мне с этим делать?
screen | CrystalPathFinding (CPF) - экстремально быстрый и простой A*/WA* для карт на тайлах

Можно мне дать екзешник, что запустится на моих 600МГЦ, чтобы сравнить скорость, я то я даже примерно не знаю свой результат.

DevilDevilПостоялецwww28 мая 201120:10#28
TarasB
попробуй test
у меня на Athlon 1700 работает
input_list.txt - это список файлов на обработку
1 frag / 2 deathsУчастникwww28 мая 201120:21#29
Результат такой:
Press any key
C:\...Files\Delphi\Projects\PathFinder>pathfinder input_1.bmp
Loading...
weights...
finding path, 4 directions...
drawing path...
saving file...
complete. Total (finding+drawing) time = 1523 ms
finding path, 8 directions...
drawing path...
saving file...
complete. Total (finding+drawing) time = 1672 ms
Press ENTER to exit.


C:\...Files\Delphi\Projects\PathFinder>pathfinder input_2.bmp
Loading...
weights...
finding path, 4 directions...
drawing path...
saving file...
complete. Total (finding+drawing) time = 3044 ms
finding path, 8 directions...
drawing path...
saving file...
complete. Total (finding+drawing) time = 3465 ms
Press ENTER to exit.


C:\...Files\Delphi\Projects\PathFinder>pathfinder input_3.bmp
Loading...
weights...
finding path, 4 directions...
drawing path...
saving file...
complete. Total (finding+drawing) time = 240 ms
finding path, 8 directions...
drawing path...
saving file...
complete. Total (finding+drawing) time = 8772 ms
Press ENTER to exit.


C:\...Files\Delphi\Projects\PathFinder>TEST


input_1.bmp (2500x800)...
cpf. simple: 251ms(p:14038 d:14037.00), diagonal: 420ms(p:9559 d:11414.09)
MP. simple: 3716ms(p:14038 d:14037.00), diagonal: 4506ms(p:9559 d:11412.88)

input_2.bmp (2500x800)...
cpf. simple: 611ms(p:11292 d:11291.00), diagonal: 1462ms(p:7635 d:9117.30)
MP. simple: 12448ms(p:11296 d:11295.00), diagonal: 16774ms(p:7659 d:9142.58)

input_3.bmp (2500x800)...
cpf. simple: 10ms(p:3299 d:3298.00), diagonal: 20ms(p:2500 d:2829.96)
MP. simple: 60ms(p:3299 d:3298.00), diagonal: 20ms(p:2500 d:2829.94)


Total time:
cpf: 2774
MP: 37524

Что-то у тебя MP делает не то.

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

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

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