Волновой алгоритм, помогите
ищу наглядные примеры по созданию волнового алгоритма на Блиц3Д и его использования
|
Re: Волновой алгоритм, помогите
Сделав несколько раз так :wallbash: и так :wild:, после чего переписав все сначала у меня получилось! Пока это еще не алгоритм поиска пути но уже присваивать значения клеткам вроде получилось. Таким образом задача 1 из n выполнена)).
Нижеприведенный код показывает значения клеток от стартовой клетки до клетки назначения в уменьшающемся порядке, таким образом выбирая соседнию клеку с наименьшим значением можно добраться до цели. Теперь пытаюсь разобраться как мне бы это бЫ .... еще неопредилися что, но чтоб вырисовывался маршрут . Прошу уважаемых администраторов переименовать топик (так как незнаю могули сам) в "Чайник ищет путь" :-D. PHP код:
|
Ответ: Волновой алгоритм, помогите
Вложений: 1
Волновой Алгоритм очень похож на Алгоритм Дейкстры для поиска кратчайшего пути в взвешаном графе, с той лишь разницей, что в Алгоритме Дейкстры учитывается расстояние между вершинами !!
Граф представляет собой совокупность точек, которые возможно связаны между собой !! Если они (2 точки) связаны между собой, то между ними существует прямой путь, в противном случае нужно искать путь между этими точками через другие точки !! Для поиска пути нам, естественно, нужна стартовая точка, откуда начинаем поиск, и конечная точка, к которой мы ищем путь !! Так же нам нужно знать сколько всего точек в графе и сколько всего связей между всеми точками есть !! За это будут отвечать глобальные переменные: Код:
Global TotalVertex%; колличество вершин В двух словах, алгоритм работает так: Берем стартовою точку, смотрим точки которые напрямую с ней связаны, «меряем расстояние» от стартовой до каждой из них !! Отмечаем эти расстояния в массиве (массив Label), т.е. ставим метки точкам !! Потом новой стартовой точкой будет, та точка у которой расстояние, т.е. метка оказалась наименьшей !! Так же в другом массиве (массив Active) отмечаем точки которые мы прошли, что бы не проходить одну точку несколько раз, ну и естественно, что бы не забить пройти каждую точку !! Повторяем эти действия пока у не останется не пройденных точек !! Таким образом мы заполним метками, т.е. значениями расстояний все точки !! Но для того что бы построить путь, нам нужно знать номера точек по которым идти !! По этому создадим еще один массив (массив Parent), где для каждой точки будим хранить номер точки с которой мы пришли в данную точку !! Например Parent(2)=4 означает что во вторую точку мы пришли из четвертой !! Ну и для хранения самого пути создадим еще один массив (массив Path) !! Хотя это и необязательно так как вы можете представить сам путь в любом удобном для вас виде, это нужно уже смотреть по программе которая у вас !! Вообщем все массивы: Код:
Dim Graf(TotalVertex,TotalVertex) Код:
mapfile = ReadFile("map4.txt") Код:
StartPoint = Rand(0,TotalVertex-1) Да, и еще немного о массиве Label, там мы храним расстояние. Т.е. если у нас Label(2) = 5, то это значит что расстояние от стартвой к второй вершине 5, а если Label(1) = 0, то эт значит что первая вершина, она в том же месте что и стартовая. Но это не так (по крайней мере должно быть нетак), по этому возмем большую константу: Const VeryBigConst% = ; здесь пишем любое большое число !! Вообще оно должно быть больше чем длина самого длинного пути !! И заполним этим числом все элементи массива Label: Код:
For ij=0 To TotalVertex-1 Сначала мы помечаем стартовую вершину как пройденную (Active(StartPoint) = 1), потом ставим метку стартовой вершине 0, так как расстояние от стартовой вершине к стартовой вершине, т.е. самой себе будет 0 (Label(StartPoint) = 0), ну и запомним стартовую вершину в локальной переменной что бы потом заюзать ее в цикле, т.е переборе связаных вершин (i = StartPoint) !! Далее пошел перебор, берем стартовую вершину (далее будем называть ее активной вершиной), и рассматриваем все остальные, если вершина связана с активной (If Graf(i,j)>0) и ее метка, больше чем метка активной вершины и растояние между рассматриваемой вершиной и активной (Label(j)>Label(i)+Graf(i,j)), тогда омечаем эту вершину как пройденую (Active(j) = 1) и назначаем ей новую метку (Label(j)=Label(i)+Graf(i,j)), так же запоминаем с которой вершины мы пришли в даную вершину (Parent(j) = i) !! Далее «деактивируем» активную вершину (Active(i) = 0), и выберем новую вершину с которой будем продолжать поиск !! Мы выбираем ту вершину, которая была ближе к активной вершине, т.е. у нее самая меньшая метка !! Для этого напишем простенькую функция, которая осуществлит поиск такой вершины: Код:
Function FindMinVertex%() После того как мы «активировали» новую верину, алгоритм действует аналогично !! Так будет продолжатся пока мы не рассмотрим все точки !! Вообщем вот алгоритм в виде кода: Код:
Function FindMinWay() Код:
j = FinishPoint Для демонстрации, работы алгоритма, зделаем вывод точек пути на экран, только уже в правельном направлении, т.е как надо двигатся !! ;) Код:
j = i - 1 Вложение 5344 |
Часовой пояс GMT +4, время: 10:00. |
vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot