Волновой алгоритм является одним из самых уникальных алгоритмов трассировки. Он позволяет построить трассу(путь) между двумя элементами в любом лабиринте .
Из начального элемента распространяется в 4-х направлениях волна. Элемент в который пришла волна образует фронт волны.На рисунках цифрами обозначены номера фронтов волны.
Каждый элемент первого фронта волны является источником вторичной волны. Элементы второго фронта волны генерируют волну третьего фронта и т.д. Процесс продолжается до тех пор пока не будет достигнут конечный элемент.
На втором этапе строится сама трасса. Её построение осуществляется в соответствии со следующими правилами :
1) Движение при построении трассы осуществляется в соответствии с выбранными приоритетами.
При движении от конечного элемента к начальному номер фронта волны (путевые координаты) должны уменьшатся.
2) Приоритеты направления движения выбираются на стадии разработки. В зависимости от того какими задаются эти приоритеты получаются разные трассы, НО длина трассы в любом случае остается одной и той же.
Преимущества волнового алгоритма в том, что с его помощью можно найти трассу в любом лабиринте и с любым количеством запретных элементов (стен). Единственным недостатком этого алгоритма является, то что при построении трассы требуется большой объем памяти.
пс
кстати я почти догадался, когда решил из своего дерева убрать лишние ветки, сначала я заносил все ходы в массив и проверял при новом ходе его равность с занесенными, но такое дерево засохло в начале 3-го уровня, т.к уже все новые шаги были в массиве, тогда я убрал проверку массива и просто исключил шаг обратно(проверил прародителя), мысль что массив должен содержать только шаги предыдущих уровней у меня была, но после тестирования деревьев "без одинаковых шагов" и "без обратных шагов" мне показалось что лучше не будет и стало лень, а ведь тогда бы и получился этот волновой алгоритм
если б не нашел сегодня завтра бы точно сделал
