68516

Metody globalne to:

•    Propagacja fali

•    Diagramów Woronoia

•    Grafu widoczności

•    M etody biologiczne

Metoda propagacji fali- działadnie tej metody na podzieleniu przestrzeni 2D na komórki elementarne, zazwyczaj jest to jednorodna siatka. W danym obszarze przestrzeni konfiguracyjnej

Pierwsza faza generuje falę rozchodzącą się w przestrzeni konfiguracyjnej a jej algorytm wygląda następująco

Krok 1 zadanej komórce początkowej nadać wagę 0 i ustalić wartość poszukiwanej wagi i=0 Krok 2 przeglądając jednokrotnie wszystkie komórki przestrzeni konfiguracyjnej wykryć te o wadze rów nej i

Krok 3 jeśli nie znaleziono komórek o takiej wadze wykonuje się kolejny krok

Krok 4 każdemu z sąsiadów znalezionej komórki którego waga nie została uprzednio zdeterminow ana przez nadanie statusu zajętej lub przypisanie wagi nieujemnej, nadaje się wagę i + 1 Krok 5 gdy przeglądnięto wszystkie komórki o wadze i o 1, kontynuować od kroku 2