Она там есть в самом конце. Сейчас ещё раз отдельно вставлю.
Возможно, череда улучшений приведет к тому, что мы получим мощную библиотеку с алгоритмами, а программа станет приятной демкой для неё (Как PathFinding.js, только лучше).
Это в миллисекундах.
Время считают QTimer'ы, один считает общее время, второй считает время на паузы(отрисовка, переходы функций). Если использовать один и постоянно тормозить его, получалось вообще неточно. Эта часть статистики остро нуждается в доработке, желательно поискать какую-нибудь библиотеку для этого или, ещё лучше, попробовать QDebug или QTest для этого.
Про JPS спасибо за совет, обязательно введу какое-нибудь обозначение.
Дейкстра реализовывалась строго по «учебникам», поэтому поиск должен быть верным. Приложу парочку гифок для понятности.
Gif #1
Здесь вы на 100% правы
Gif #2
Здесь расстояние между точками тоже, только появляется стена(вверх короче чем вниз). Пока левая сторона обходит стену, правая продолжает расширятся.
Мы могли бы и прерывать поиск в одну сторону, когда видим, что превышен радиус, в котором находится выход, но одним из ключевых преимуществ Дейкстры является то, что не нужна вообще никакая информация о выходе, и, добавляя проверку радиуса, мы это теряем.
Также этот эффект наблюдается и в проверенной многими библиотеке PathFinding.js (на случай, если вы мне не верите, можете попробовать :) ). Это объясняется тем, что когда мы натыкаемся на стену, например, слева (как на гифке), поиск влево временно прекращается, поэтому и нарушается равенства радиуса поиска во всех направлениях.
Тогда будет необходимо реализовывать длинную арифметику + во всех статьях используются именно такие методы подсчета, а планировалось, что программу нужно использовать в связке со справочным материалом. Следовательно, чтобы пользователю было удобно и привычно, я поставил такие величины
JPS тоже рекурентно просматривает множество клеток, но он не совершает с ними много операций(не заносит в открытий и закрытый список, не проверяет соседей, не вычисляет F, G, H), а лишь вызывает рекурсивную функцию далее, пока точка не будет соответствовать правилам перхода, это и значительно увеличивает скорость поиска. Об этом можно прочитать по ссылке из поста. Цвет в свою очередь показывает принадлежность закрытому(желтый) и открытому(синий) спискам, поэтому все честно)
А Декстра слева ушел далеко, потому что правой стороне надо было еще искать путь обогнуть стену. Если оставить две точки на пустом поле ваше утверждение будет верным, как только появляются препятсвия, Дейкстра пойдет неравномерно.
В этой программе пользователь может запустить правило руки только на самом простом лабиринте без циклов и галерей, поэтому правило руки всегда будет давать верное решение. Да и добавлял я его просто для введения в лабиринты и поиск пути.
Это связано с тем, что для Дейкстры и A* мы используем стоимость единичного перехода горизонталь и вертикаль 10, а диагональ 14, потом делим общий результат на 10. А в JPS мы более точно считаем 1 для горизонтали и вертикали, и sqrt(2) для диагонали. Делалось это для демонстации того, что можно по разному считать: для Дейкстры и AStar'а быстрее, но менее точно, а т.к. JPS сам очень эффективный и быстрый, можем пожертвовать капелькой времени, ради точности. Я хотел об этом сказать, но забыл) Спасибо, что напомнили
Время считают QTimer'ы, один считает общее время, второй считает время на паузы(отрисовка, переходы функций). Если использовать один и постоянно тормозить его, получалось вообще неточно. Эта часть статистики остро нуждается в доработке, желательно поискать какую-нибудь библиотеку для этого или, ещё лучше, попробовать QDebug или QTest для этого.
Это мой первый проект выше уровня тетриса :)Но если так положено приложу в ближайшее время.
Дейкстра реализовывалась строго по «учебникам», поэтому поиск должен быть верным. Приложу парочку гифок для понятности.
Здесь вы на 100% правы
Здесь расстояние между точками тоже, только появляется стена(вверх короче чем вниз). Пока левая сторона обходит стену, правая продолжает расширятся.
Мы могли бы и прерывать поиск в одну сторону, когда видим, что превышен радиус, в котором находится выход, но одним из ключевых преимуществ Дейкстры является то, что не нужна вообще никакая информация о выходе, и, добавляя проверку радиуса, мы это теряем.
Также этот эффект наблюдается и в проверенной многими библиотеке PathFinding.js (на случай, если вы мне не верите, можете попробовать :) ). Это объясняется тем, что когда мы натыкаемся на стену, например, слева (как на гифке), поиск влево временно прекращается, поэтому и нарушается равенства радиуса поиска во всех направлениях.
А Декстра слева ушел далеко, потому что правой стороне надо было еще искать путь обогнуть стену. Если оставить две точки на пустом поле ваше утверждение будет верным, как только появляются препятсвия, Дейкстра пойдет неравномерно.