Поиск пути по алгоритму A*

[forcer]

Предлагаю заценить результат работы базового алгоритма A*

http://bola2008.narod.ru/A-star/Scene1.html

Поля редактируется:
для чего необходимо выбрать <edit>

фиолетовая плитка - стена,
бледно-желтая - начальная точка,
голубая - очистка поля,
// бледно-розовая - не используется
для начала теста выти из редактора <edit>

цель указывается нажатием курсора на соотв. плитке

[MonkDead]

Сетка слишком мелкая 6х8, сделаете сетку 100х100 тогда и можно будет понять актуальность работы и степень полезности. Если на сетки 100х100 (в независимости от сложности сетки) путь у вас будет искаться меньше чем за 20ms алгоритм написан удачно. А также вывидети поле со временем поиска.

[etc]

Заценил.

[VovkaMorkovka1]

На A* похоже, и чего? Добавь количество клеток хотяб 1000/1000, несколько юнитов(штук десять), тогда можно будет посмотреть. Пока ничего особенного

[WRC_S]

ну не знаю так себе, сколько по времени делал?

[udaaff]

Вы свой алгоритм не достаточно хорошо тестировали? Посложнее преграду сделайте и "зацените".

[forcer]

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

обновил размер поля, теперь 60x40,

[MonkDead]

forcer, вам стоит серьезно оптимизировать алгоритм. 5 секунд на расчет от верхнего левого до нижнего правого угла через препятствия (на сильном компе) это очень много (+ в реальном применении надо путь искать, для как минимум 10 персонажей, а это уже минута тормоза)! Учитывая, что таких алгоритмов написано невероятно много и даже на AS, вам стоит его расширить (например поиск оптимального пути при возвышенностях, если конечно вы алгоритм позиционируете для игр или учитывать тип тайлота: вода, песок, болото и т.д.)

Судя по медленной работе вы ищете путь сразу по всей сетке, а надо хотя бы сетку бить на сегменты и отбрасывать заведомо не участвующие сегменты. Думаю вам стоит ознакомится поподробнее с иерархическими деревьями Quad, Octree для начала.

[Psycho Tiger]

Странно, что кликая на одну и ту же клетку время скачет от 10 до 40 мс. Хотя я вижу "подвисание" на 200-300.

[udaaff]

Сообщение от forcer

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

Да, запаролся. Повторить преграду не смогу, уж большо изощренная была. Неправильно находился путь или совсем не находился.