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

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

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

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

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

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

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

Заценил.

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

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

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

для udaaff
 

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

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

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

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

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

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

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

Уберите selectable с текстфилдов.

для MonkDead
 

благодарю за ценный совет, буду искать инфу Quad, Octree.
При сложном лаберинте действительно долговато думает. Буду пробовать расширить, интересно что получится.

2 forcer

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

2 VovkaMorkovka1
 

запросто, отправляй на почту ... там же где и народ

Вот сцылочго http://gamesdevandmath.blogspot.com/

Оффтоп: в какой момент албанский перестал быть наказуемым?

Не перестал.

4 VovkaMorkovka1
 

такая ознакомительная статейка, без погружения в технические моменты, похожа на лекцию в универе. Есть мнение что если добавить больше зрительных образов (особенно это касается первых пунктов статьи, А*), то будет немного проще сориентироваться по ходу изучения или ознакомления, смотря какую цель преследует автор, но для изучения представленных алгоритмов, этой статьи маловато, как минимум нужны примеры с описанием действий.

p.s.
обновил пример работы, есть возможность загрузить лабиринт, жмите "load".

вот и ответ на вопрос: как шашке побыстрее попасть в дамки)
+

а почему только одна преграда?