Извините, ничего не найдено.

Putin · 30.01.2009, 16:27

ищу наглядные примеры по созданию волнового алгоритма на Блиц3Д и его использования

Putin · 30.01.2009, 23:45

Сделав несколько раз так

и так

, после чего переписав все сначала у меня получилось! Пока это еще не алгоритм поиска пути но уже присваивать значения клеткам вроде получилось. Таким образом задача 1 из n выполнена)).
Нижеприведенный код показывает значения клеток от стартовой клетки до клетки назначения в уменьшающемся порядке, таким образом выбирая соседнию клеку с наименьшим значением можно добраться до цели. Теперь пытаюсь разобраться как мне бы это бЫ .... еще неопредилися что, но чтоб вырисовывался маршрут .

Прошу уважаемых администраторов переименовать топик (так как незнаю могули сам) в "Чайник ищет путь"

.



SeedRnd MilliSecs()
Graphics 640, 480,16,2
SetBuffer BackBuffer()

Global Ni

Const Nk=20

Dim P(9,9)
Dim R(8,8)

Ni=0

fon1=LoadFont ("arrial", 19)
SetFont fon1



;-----------------------;-------------parametrs of MAP's cells-------------
For i=0 To 9 ;boarder 1 ; M
    For j=0 To 0        ; A
        P(i,j)=888      ; P
    Next                ;
Next                    ; B
For i=0 To 0;boarder  2 ; O
    For j=0 To 9        ; A
        P(i,j)=888      ; R
    Next                ; D
Next                    ; E
For i=0 To 9;boarder  3    ; R
    For j=9 To 9        ; S
        P(i,j)=888        ;
    Next                ; (marks as 888)
Next                    ;
For i=9 To 9;boarder  4    ;
    For j=0 To 9        ;
        P(i,j)=888        ;
    Next                ;
Next                    ;
;-----------------------;


;-----------------------;
For i=1 To 8            ; 
    For j=1 To 8        ; MAP's FREE CELLS (marks as 333) 
        P(i,j)=333        ;
    Next                ;  
Next                    ;                                      
;-----------------------;

;-----------------------; CHANGEBLE PARAMETRS
P(3,4)=888                ;
P(3,2)=888                ;
P(3,3)=888                ; 
P(3,5)=888                ; BLOKS on MAP (marks as 888)
P(4,4)=888                ; 
P(5,4)=888                ; 
P(6,4)=888                ;                                              
P(1,2)=555                ; START
P(7,8)=0                ; FINISH
;-----------------------;---------------------------------------------------




Repeat

    Cls

;-------------------------------------------;
    For i=0 To 9                            ; D
        For j=0 To 9                        ; R
            If P(i,j)=888 Then                ; A
                Color 255,255,255            ; W
                Rect i*40,j*40,40,40,0        ;
                Color 180,100,108            ; M
                Rect 4+i*40,4+j*40,32,32,1    ; A
            EndIf                            ; P
            If P(i,j)=333 Then                ; 
                Color 255,255,255            ; C
                Rect i*40,j*40,40,40,0        ; O
            EndIf                            ; D
            If P(i,j)=0 Then                ; E
                Color 255,255,255            ;
                Rect i*40,j*40,40,40,0        ;
                Oval 5+i*40,5+j*40,30,30,1    ;                
            EndIf                            ;
            If P(i,j)=555 Then                ;
                Color 255,255,255            ;  
                Rect i*40,j*40,40,40,0        ;    
                Color 145,255,225            ;                
                Oval 5+i*40,5+j*40,30,30,1    ;                
            EndIf                            ;                        
        Next                                 ;
    Next                                    ;
;-------------------------------------------;


;-------------------------------------------;
    For i=0 To 9                            ; P
        For j=0 To 9                        ; R
            If P(i,j)=888 Then                ; I
                Color 4,5,255                ; N
                Text 6+i*40,9+j*40,P(i,j)    ; T
            ElseIf    P(i,j)=333 Then            ;
                Color 0,200,0                ; T
                Text 6+i*40,9+j*40,P(i,j)    ; E
            ElseIf P(i,j)=555 Then            ; X
                Color 255,55,97                ; T
                Text 6+i*40,9+j*40,P(i,j)    ; 
            ElseIf    P(i,j)=0 Then            ; 
                Color 255,55,97                ; 
                Text 16+i*40,9+j*40,P(i,j)    ;
            Else                             ;
                Color 255,0,0                ;
                Text 16+i*40,9+j*40,P(i,j)    ;
            EndIf                            ;
            Color 255,255,255                ;
            Rect i*40,j*40,40,40,0            ;
        Next                                ;
    Next                                    ;
;-------------------------------------------;

;----------------------------------------------------;
    For Ni=0 To Nk
        For i=1 To 8
            For j=1 To 8
                If P(i,j)=Ni Then
                    If P(i+1,j)=333 P(i+1,j)=Ni+1
                    If P(i-1,j)=333 P(i-1,j)=Ni+1
                    If P(i,j+1)=333 P(i,j+1)=Ni+1
                    If P(i,j-1)=333 P(i,j-1)=Ni+1
                End If
            Next
        Next
    Next
;----------------------------------------------------;


    Flip
    
    Until KeyHit(28)

End

IGR · 04.02.2009, 13:21

Волновой Алгоритм очень похож на Алгоритм Дейкстры для поиска кратчайшего пути в взвешаном графе, с той лишь разницей, что в Алгоритме Дейкстры учитывается расстояние между вершинами !!

Граф представляет собой совокупность точек, которые возможно связаны между собой !! Если они (2 точки) связаны между собой, то между ними существует прямой путь, в противном случае нужно искать путь между этими точками через другие точки !!

Для поиска пути нам, естественно, нужна стартовая точка, откуда начинаем поиск, и конечная точка, к которой мы ищем путь !! Так же нам нужно знать сколько всего точек в графе и сколько всего связей между всеми точками есть !! За это будут отвечать глобальные переменные:

Global TotalVertex%; колличество вершин
Global TotalEdges%; колличество связей
Global StartPoint%; начальная точка
Global FinishPoint%; конечная точка

Данные о точках, содержатся в двумерном массиве Graf, где значение Graf(i,j) это расстояние между точками i и j !! Например, Graf(2,5) = 50 означает что расстояние между второй и пятой точками равно 50 единиц !!
В двух словах, алгоритм работает так:
Берем стартовою точку, смотрим точки которые напрямую с ней связаны, «меряем расстояние» от стартовой до каждой из них !! Отмечаем эти расстояния в массиве (массив Label), т.е. ставим метки точкам !! Потом новой стартовой точкой будет, та точка у которой расстояние, т.е. метка оказалась наименьшей !! Так же в другом массиве (массив Active) отмечаем точки которые мы прошли, что бы не проходить одну точку несколько раз, ну и естественно, что бы не забить пройти каждую точку !! Повторяем эти действия пока у не останется не пройденных точек !! Таким образом мы заполним метками, т.е. значениями расстояний все точки !! Но для того что бы построить путь, нам нужно знать номера точек по которым идти !! По этому создадим еще один массив (массив Parent), где для каждой точки будим хранить номер точки с которой мы пришли в данную точку !! Например Parent(2)=4 означает что во вторую точку мы пришли из четвертой !! Ну и для хранения самого пути создадим еще один массив (массив Path) !! Хотя это и необязательно так как вы можете представить сам путь в любом удобном для вас виде, это нужно уже смотреть по программе которая у вас !! Вообщем все массивы:

Dim Graf(TotalVertex,TotalVertex)
Dim Label(TotalVertex)
Dim Active(TotalVertex)
Dim Parent(TotalVertex)
Dim Path(TotalVertex)

Данные о точках можна хранить в любом удобном\привычном для вас виде !! Напимер, в текстовом файле !! Там же будим хранить и общее количество точек (TotalVertex) и общее количество связей между всеми точками (TotalEdges) !! Получается, первая строчка – TotalVertex, вторая – TotalEdges, далее пошло перечисление всех связей таким образом: точка1 связи, точка2 связи и расстояние между точкой1 и точкой2. Еще раз повтрю, что данные можна хранить в любом удобном виде, гланое что бы правельно их записать и считать !! Чтение из файла и заполнения массива Graf осуществляется так:

mapfile = ReadFile("map4.txt")
	mf_str = ReadLine(mapfile)
	TotalVertex = Int(mf_str)
	mf_str = ReadLine(mapfile)
	TotalEdges = Int(mf_str)

For ij=0 To TotalEdges-1
	gi = Int(ReadLine(mapfile))
	gj = Int(ReadLine(mapfile))
	gv = Int(ReadLine(mapfile))
	Graf(gi,gj) = gv
	Graf(gj,gi) = gv
Next

CloseFile(mapfile)

Стартовую и конечную точки поиска пути сгенерируем случайно:

	StartPoint = Rand(0,TotalVertex-1)
	FinishPoint = Rand(0,TotalVertex-1)

Незабываем поставить SeedRnd MilliSecs() !!

Да, и еще немного о массиве Label, там мы храним расстояние. Т.е. если у нас Label(2) = 5, то это значит что расстояние от стартвой к второй вершине 5, а если Label(1) = 0, то эт значит что первая вершина, она в том же месте что и стартовая. Но это не так (по крайней мере должно быть нетак), по этому возмем большую константу:
Const VeryBigConst% = ; здесь пишем любое большое число !! Вообще оно должно быть больше чем длина самого длинного пути !!
И заполним этим числом все элементи массива Label:

For ij=0 To TotalVertex-1
	Label(ij) = VeryBigConst
Next

Так, вот мы подошли к самому главному – написание самого алгоритма поиска пути !! Алгоритм реализуется, грубо говоря 1 функцией FindMinWay() !!
Сначала мы помечаем стартовую вершину как пройденную (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%()
Local min% = VeryBigConst
Local k%
Local min_pos% = -1

For k=0 To TotalVertex-1
	If Label(k)<min And Active(k)=1 Then
		min = Label(k)
		min_pos = k
	EndIf
Next

	Return min_pos
End Function

Как мы видим здесь просто осуществляется перебор по пройденым вершинам !! Функция возратит номер вершины с самой меньшой меткой, если такой неокажется, то функция возратит -1 и поиск закончится !!
После того как мы «активировали» новую верину, алгоритм действует аналогично !! Так будет продолжатся пока мы не рассмотрим все точки !!
Вообщем вот алгоритм в виде кода:

Function FindMinWay()
Active(StartPoint) = 1
Label(StartPoint) = 0
i = StartPoint
While Not i=-1
	For j=0 To TotalVertex-1
		If Graf(i,j)>0 And Label(j)>Label(i)+Graf(i,j) Then
			Active(j) = 1
			Label(j)=Label(i)+Graf(i,j)
			Parent(j) = i
		EndIf

	Next		
		Active(i) = 0
		i = FindMinVertex()
Wend
End Function

Далее, строим путь !! Здесь маленькое неубоство, так как путь у нас получится с заду на перед !! На экран то мы его вывидим правельно, но об этом стоит помнить, чо бы не допустить ненужных ошибок !! Так, пути и нас хранится в массиве Path. Для построения пути берем конечную точку (j = FinishPoint) и пока недостигнем стартовой точки, перебераем масив Parent. Код выглядит так:

j = FinishPoint
i = 1
Path(0) = FinishPoint
While Not j=StartPoint
	Path(i) = Parent(j)
	j = Parent(j)
	i = i + 1
Wend

Ну вот и все !!
Для демонстрации, работы алгоритма, зделаем вывод точек пути на экран, только уже в правельном направлении, т.е как надо двигатся !!

j = i - 1
i = 0
While j>=0
	Write Path(j) + " "
	j = j - 1
Wend

В аттаче пример !!
4.zip